プログラミングHaskell 8.8 数式
自然数と加算演算子、乗算演算子、および括弧からなる数式を考える。 加算演算子と乗算子は右結合とし、乗算演算子は加算演算子よりも高い結合順序を持つとする。 「2 + 3 + 4」 は「2 + (3 + 4)」 「2 * 3 + 4」は 「(2 * 3) + 4」 を意味する。
BNFで表していきたい。
expr ::= expr '+' expr | expr '*' expr | '(' expr ')' | nat nat ::= '0' | '1' | '2' | ...
これでは、 +
と *
の結合順位についての条件が含まれないので、
以下のように結合順位ごとに規則を用意して書く。
expr ::= expr '+' expr | term term ::= term '*' term | factor factor ::= '(' expr ')' | nat nat ::= '0' | '1' | '2' | ...
さらに、右結合であることを表現するために、以下のように規則を変更する。 これで曖昧さはなくなる。
expr ::= term '+' expr | term term ::= factor '*' term | factor
簡略化すると、
expr ::= term('+' expr | ε) term ::= factor('*' term | ε) factor ::= '(' expr ')' | nat nat ::= '0' | '1' | '2' | ...
これを書いていく。 Haskellでは、
expr :: Parser Int expr = do t <- term do symbol "+" e <- expr return (t + e) +++ return t
と書けるようだけど、 Scalaだと以下のようになるのかな・・?
def expr: Parser[Int] = for { t <- term e <- (for { _ <- symbol("+") ee <- expr } yield t + ee) +++ succeed(t) } yield e
同様に、termとfactorについても式を書く。
def term: Parser[Int] = for { f <- factor e <- (for { _ <- symbol("*") ee <- term } yield f * ee) +++ succeed(f) } yield e def factor: Parser[Int] = +++(for { _ <- symbol("(") e <- expr _ <- symbol(")") } yield e)(nat)
なんとこれだけでできる!!
eval関数も加えて実行。ソースコードはあとで全部まとめて。
println("sample23: " + eval("2 * 3 + 4")) println("sample24: " + eval("2 * (3 + 4)")) println("sample25: " + eval("2 * (3+4)")) println("sample26: " + eval("4")) println("sample27: " + eval("2*3-4"))
sample23: 10 sample24: 14 sample25: 14 sample26: 4 Exception in thread "main" java.lang.Exception: unused expression: -4 ....
完成した!シンプル!! なんとなく、ちょっとだけパーサーについて理解が深まった気がした。。。
別話だけど、ParserOpsのimplicit conversionをExpressionオブジェクトの中かから使いたかったけど、最初うまく使えなかった。 ExpressionオブジェクトでParsersオブジェクトの中にあるimplicit conversion使いたかったら、ParsersオブジェクトをExpressionオブジェクトよりも上に書かなきゃいけないと。ふむ