読者です 読者をやめる 読者になる 読者になる

Scalaで数式をパースして整形表示

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で表した構造をそのままコードに落とし込むイメージがつきやすい気がしたのでパーサの構築の敷居が大分下がっているように思いました。