プログラミング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オブジェクトよりも上に書かなきゃいけないと。ふむ