scala のパーサーコンビネーターで数式を評価

Scalaのパーサーコンビネーターの練習のため、数式をパースして計算してみる。

参考にしたのはコップ本と、以下のサイト。

• Functional Programming Memo / How to Use Combinator Parser (1)
• Ayutaya.com / Scala: 中置記法→逆ポーランド記法のパーサ練習
• じゅんいち☆かとうの技術日誌 / パーサーコンビネータで遊んでみた

	import scala.util.parsing.combinator._
	abstract class Value {
	def eval():Double
	}
	case class Number(n:Double) extends Value {
	def eval():Double = n
	}
	case class Binomial(op: String, v1:Value, v2:Value) extends Value {
	def eval():Double = op match {
	case "*" => v1.eval() * v2.eval()
	case "/" => v1.eval() / v2.eval()
	case "+" => v1.eval() + v2.eval()
	case "-" => v1.eval() - v2.eval()
	}
	}
	case class Rest(op:String, v:Value)
	case class Formula(v:Value, rest:List[Rest]) extends Value {
	def eval():Double = rest.foldLeft(v.eval()) {
	(r:Double, rest:Rest) => Binomial(rest.op, Number(r), rest.v).eval()
	}
	}
	case class Paren(e:Value) extends Value {
	def eval():Double = e.eval()
	}
	class ArithmeticParser extends JavaTokenParsers {
	def multiDiv: Parser[Rest] = ("*"|"/")~factor ^^ { case op~v => Rest(op, v) }
	def addSub: Parser[Rest] = ("+"|"-")~term ^^ { case op~v => Rest(op, v) }
	def expr: Parser[Value] = term~rep(addSub) ^^ { case f1~rest => Formula(f1, rest) }
	def term: Parser[Value] = factor~rep(multiDiv) ^^ { case f1~rest => Formula(f1, rest) }
	def factor: Parser[Value] = (
	floatingPointNumber ^^ { case n => Number(n.toDouble) }
	| "-"~>floatingPointNumber ^^ { case n => Number(n.toDouble * -1.0) }
	| "("~>expr<~")" ^^ { case e => Paren(e) }
	)
	def parse(e:String): Double = {
	parseAll(expr, e).get.eval
	}
	}
	val parser = new ArithmeticParser
	val e = args(0)
	val result = parser.parse(e)
	println(result)

view raw ArithmeticParser.scala hosted with ❤ by GitHub

実行

実行引数に数式を文字列で与えると計算結果を標準出力にプリントする。

$ scala ArithmeticParser.scala "(2 + 3) * -2.5"
-12.5

数式の文法定義

ValueからParenまでのクラスは、数式をモデリングするためのもの。ここはパーサーからは独立している。

ArithmeticParserで、これらのクラスに入力の数式をマッピングしていく。

def factor: Parser[Value] = (
  floatingPointNumber ^^ { case n => Number(n.toDouble) }
  | "-"~>floatingPointNumber ^^ { case n => Number(n.toDouble * -1.0) }
  | "("~>expr<~")" ^^ { case e => Paren(e) }
)

factorがもっとも細かい単位にマッチする。つまり、数値か括弧()。数値を表すfloatingPointNumberは継承元のJavaTokenParsersで定義されていて、浮動小数表現にマッチする。マッチしたあとの処理（返り値の計算）は^^で定義する。この箇所のように複数種類の要素にマッチする場合は、それぞれを | で列挙する。"-"~>floatingPointNumber で負の数（-2.5など）にマッチさせる。最後の"("~>expr<~")"で括弧表記にマッチさせる。"x"~>という表記は、読み取った"x"を捨てる。逆に"x"~という表記であれば"x"を解析結果として利用できる。

def expr: Parser[Value] = term~rep(addSub)     ^^ { case f1~rest => Formula(f1, rest) }
def term: Parser[Value] = factor~rep(multiDiv) ^^ { case f1~rest => Formula(f1, rest) }

termはfactorの掛け算／割り算の連続(2 * 3など)。連続ということをrepで表現している。exprは同様にterm同士の足し算／引き算の連続(2 + 3など)。またfactorのうち括弧表現のときは、内容としてexprを含む。

def multiDiv: Parser[Rest] = ("*"|"/")~factor ^^ { case op~v => Rest(op, v) }
def addSub: Parser[Rest]   = ("+"|"-")~term   ^^ { case op~v => Rest(op, v) }

multiDivは掛け算のうち、記号と後ろ側の数値にマッチする(/ 2など)。したがって1 * 2 / 3というtermは、イメージとしては[1, [[*, 2], [/, 3]]]という形にパースされる。addSubも同様。

パースと計算の実行

parseAll(expr, e).get.eval

パースの実行はparseAllで。第一引数に、入力全体にマッチさせる関数を指定。第二引数にパースする文字列を渡す。結果としてパース結果のオブジェクトが帰って来るので、getで最終的な^^で指定したパース結果を取得する。今回はValue型で帰って来るので、evalで計算している。

最初は全然よくわからなかったが、ちょっと書いてみると確かに強力そうな気がしてきた。