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

AccessViolation Exception

仕事でもはんだづけ、家でもはんだづけ

パーサコンビネータで数式パーサ

Scala parsercombinator 技術ネタ

導入

  • 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"とかやると非常に残念なので注意。

簡易数式パーサ