パーサコンビネータで数式パーサ
導入
scala 2.11.x以降は標準から切り離されてしまったのでsbtに依存関係を追記。面倒なのでscala 2.10.4で
scala.util.parsing.combinator.RegexParserを継承して独自クラスを作る。
とりあえず粒度の細かいものから作っていく
数字パーサを作る
作った数字パーサと掛け算の演算子を組み合わせて二項演算を作る
掛け算の演算結果を組み合わせて足し算の二項演算を作る
といったように作ったパーサを組み合わせていけるのが強みです。変換先のクラスはパターンマッチが使えるようにcase classに。この例は手を抜いてExpr乱用してますがもう少し厳密にも出来るはず。
だいたい同じような構成で作ってますが
def expr : Parser[Expr] = term ~ rep(exprTerm ~ term) ^^ { case n ~ body => (n /: body){ (s,x) => { x._1 match { case "+" => Add(s, x._2) case "-" => Sub(s, x._2) }}} } def term: Parser[Expr] = unary ~ rep(opTerm ~ unary) ^^ { case n ~ body => ((n.asInstanceOf[Expr]) /: body){ (s,x) => { x._1 match { case "*" => Mul(s, x._2) case "/" => Div(s, x._2) case "%" => Rest(s,x._2) }}} } def unary = single | literal def single: Parser[Expr] = singleTerm ~ unary ^^ { case ("!" ~ literal) => BitNot(literal) case ("~" ~ literal) => BitInv(literal) }
とあったら、termは数字か変数に単項演算した(かそのままの)unaryが来て、演算子とunaryの繰り返しを2項演算としてまとめることをしています。
(n.asInstanceOf[Expr]) /: body){ (s,x) =>
はfoldLeftの糖衣構文で、最初の項と次の項の演算子と式を組み合わせて、Mul,Div,Restの2項演算にした後、した2項演算と次の項で再び2項演算をします。非常に便利。
単純な結合に def exprTerm : Parser[String] = "+" | "-"
みたいなことをしていますが、左から評価されるので"A" | "AA" | "AAA"
とかやると非常に残念なので注意。