Scalaで数式をパースして整形表示
数式パーサ
Scalaのコップ本を一通り読んだので振り返りも兼ねて数式をパースして計算、整形するDSLを実装したいと思います。全部自力で作れたら良いのですが、ソースコードはほとんど(http://blog.j5ik2o.me/entry/20101126/1290763057) とコップ本から拝借しています。
パースした数式は探索して評価を行うので、式を表すExpressionトレイトと訪問するExpressionVisitorトレイトを用意します。
// 式を訪問するビジター
trait ExpressionVisitor {
def visit(e:Expression):BigDecimal
}
// 式を表すトレイト
trait Expression {
def accept(visitor:ExpressionVisitor):BigDecimal = {
visitor.visit(this)
}
}
それから各数式を表すのに使うケースクラスを定義しておきます。
// 各式を表すケースクラス。これを使ってAST(抽象構文木)を作ります。 case class Value(digit:BigDecimal) extends Expression case class Add(expr1:Expression, expr2:Expression) extends Expression case class Sub(expr1:Expression, expr2:Expression) extends Expression case class Plus(expr:Expression) extends Expression case class Minus(expr:Expression) extends Expression // カッコで囲んでいる部分 case class Parenthesized(expr:Expression) extends Expression case class Multiply(expr1:Expression, expr2:Expression) extends Expression case class Divide(expr1:Expression, expr2:Expression) extends Expression // 数式と評価結果を表す case class ExecResult(exp:Expression, result: Value) extends Expression
RegexParsersを使って数式をパースします。構文解析にはASTというものを使います。数式のクラスは入れ子構造になるのですが、ASTで解析する時はまず+,-次に*,/それからカッコというように優先度の低いものを先に評価することで正しくパースが行えるようです。この辺りは既にあるものを見るならなんとなくわかるけど、自分で一から考えるのは難しそう
// 式のパーサ
class ExprParser extends RegexParsers {
def parse(data:String) = parseAll(expression, data)
// expression ::= term { "+" term | "-" term }
def expression : Parser[Expression] = term~rep("+"~term | "-"~term) ^^ {
case opr1~lists => {
var operand1 = opr1
lists.foreach {
l => l match {
case "+"~f => { operand1 = Add(operand1, f) }
case "-"~f => { operand1 = Sub(operand1, f) }
}
}
operand1
}
}
// term ::= factor { "*" factor | "/" factor }
def term : Parser[Expression] = factor~rep("*"~factor | "/"~factor) ^^ {
case opr1~lists => {
var operand1 = opr1
lists.foreach {
l => l match {
case "*"~f => { operand1 = Multiply(operand1, f) }
case "/"~f => { operand1 = Divide(operand1, f) }
}
}
operand1
}
}
// factor ::= unary
def factor : Parser[Expression] = unary
// unary :: = "+" unary | "-" unary | primary
def unary : Parser[Expression] =
("+"|"-")~unary ^^ {
case "+"~u => Plus(u)
case "-"~u => Minus(u)
}| primary
// primary ::= "(" expression ")" | value
def primary : Parser[Expression] =
"("~expression~")" ^^ {
case lbrace~expr~rbrace => Parenthesized(expr)
}|value
// value ::= "[0-9]+"
// floatingPointNumberは浮動小数点を表す正規表現のParser
def value : Parser[Expression] =
fpn ^^ {
n => Value(BigDecimal(n, MathContext.DECIMAL32))
}
def fpn: Parser[String] =
"""-?(\d+(\.\d*)?|\d*\.\d+)([eE][+-]?\d+)?[fFdD]?""".r
}
それから、パース後に数式の答えを出すのは以下のvisitorパターンを使います。
class Evaluator extends ExpressionVisitor {
// ケースクラスの抽出(unapply)を使って内包されている式を取り出してさらに訪問する
override def visit(e:Expression) : BigDecimal = e match {
case Value(digit) => digit
case Add(l,r) => l.accept(this) + r.accept(this)
case Sub(l,r) => l.accept(this) - r.accept(this)
case Multiply(l,r) => l.accept(this) * r.accept(this)
case Divide(l,r) => l.accept(this) / r.accept(this)
case Minus(e) => e.accept(this) * -1
case Plus(e) => e.accept(this)
case Parenthesized(e) => e.accept(this)
}
}
整形表示なしで式を計算するだけなら、以下のようになります。
val parser = new ExprParser
val parseResult = parser.parse("3/2 + 5 * (24 + 7) /2")
if ( parseResult.successful ){
parseResult.get.accept(new Evaluator)
}else{
""
}
次に、数式の整形表示についてですが、表示用の情報はElementオブジェクトを拡張したクラスを使用して使います。
object Element{
private class ArrayElement(val contents: Array[String]) extends Element
private class LineElement(s: String) extends Element{
val contents = Array(s)
override def width = s.length
override def height = 1
}
private class UniformElement(
ch:Char,
override val width: Int,
override val height:Int
)extends Element{
private val line = ch.toString * width
def contents = Array.fill(height)(line)
}
def elem(contents:Array[String]):Element =
new ArrayElement(contents)
def elem(chr: Char, width: Int, height: Int ): Element =
new UniformElement(chr, width, height)
def elem(line: String): Element =
new LineElement(line)
}
表示用のクラスには数式の一部が格納されていて、その一部の数式同士の位置を調整するためのメソッド群をElementのabstractクラスに持たせておきます。分子を分母の上に表示するのにはここのクラスのメソッドを使用します。
abstract class Element {
import util.Element.elem
def contents: Array[String]
def width: Int = contents(0).length
def height: Int = contents.length
def above(that: Element): Element = {
val this1 = this widen that.width
val that1 = that widen this.width
assert(this1.width == that1.width)
elem(this1.contents ++ that1.contents)
}
def beside(that: Element): Element = {
val this1 = this heighten that.height
val that1 = that heighten this.height
elem(
for((line1, line2) <- this1.contents zip that1.contents)
yield line1 + line2)
}
def widen(w:Int):Element =
if(w<=width) this
else{
val left = elem(' ', (w-width)/2, height)
val right = elem(' ', w - width - left.width, height)
left beside this beside right
}
def heighten(h: Int): Element =
if(h <= height)this
else{
val top = elem(' ', width, (h - height)/2)
val bot = elem(' ', width, h - height - top.height)
top above this above bot
}
override def toString = contents mkString "\n"
}
それからパースされた数式のクラスを表示用クラスに変換するExprFormatterクラスを作成します。Scalaのパターンマッチを使って入れ子構造のクラスを再帰的に評価しています。
class ExprFormatter {
private val fractionPrecedence = -1
private def format(e: Expression, enclPrec: Int): Element =
e match {
case Value(num) =>
elem(" " + num.toString + " ")
case Add(x, y) =>
val l = format(x, fractionPrecedence)
val op = elem("+")
val r = format(y, fractionPrecedence)
l beside op beside r
case Sub(exp1, exp2) =>
val l = format(exp1, fractionPrecedence)
val op = elem("-")
val r = format(exp2, fractionPrecedence)
l beside op beside r
case Plus(exp) =>
val op = elem("+")
val ex = format(exp, fractionPrecedence)
op beside ex
case Minus(exp) =>
val op = elem("-")
val ex = format(exp, fractionPrecedence)
op beside ex
case Parenthesized(exp) =>
val l = elem("(")
val ex = format(exp)
val r = elem(")")
l beside ex beside r
case Multiply(exp1, exp2) =>
val l = format(exp1, fractionPrecedence)
val op = elem("x")
val r = format(exp2, fractionPrecedence)
l beside op beside r
case Divide(exp1, exp2) =>
val top = format(exp1, fractionPrecedence)
val bot = format(exp2, fractionPrecedence)
val line = elem('-', top.width max bot.width, 1)
val frac = top above line above bot
if (enclPrec != fractionPrecedence) frac
else frac
case ExecResult(exp, result) =>
val e = format(exp, fractionPrecedence)
val eq = elem("=")
val r = format(result, fractionPrecedence)
e beside eq beside r
}
def format(e: Expression): Element = format(e, 0)
}
最後に数式のパース,整形表示は以下のように利用します。
trait MathParser {
def mathParse(input: String) = {
val f: ExprFormatter = new ExprFormatter
val parser = new ExprParser
val parseResult = parser.parse(input)
if ( parseResult.successful ){
val evalResult = parseResult.get.accept(new Evaluator)
f.format(ExecResult(parseResult.get, Value(evalResult)))
}else{
""
}
}
}
これで以下のように入力を行うと
3/2 + 5 * (24 + 7) /2
こんな風に整形して出力されることが確認できます。
3 5 x( 24 + 7 ) ---+--------------= 79.0 2 2
他の言語でDSLを実装したことがないので比較はできませんが、Scalaを使うことでASTで表した構造をそのままコードに落とし込むイメージがつきやすい気がしたのでパーサの構築の敷居が大分下がっているように思いました。
