[Scala] How to Use Combinator Parser (2)

Scala の Parser Combinator の使い方の勉強 (続き)

以下は Scala 2.7.1 の元での話です。

●数式のパーサを書いてみる (続き)

　前回の記事[Scala] How to Use Combinator Parser (1)で、使い方練習として定番の数式パーサを書きました。
　その際に、パーサコンビネータでは左再帰が苦手なので

expr ::= expr "+" term | expr "-" term | term

を、繰り返し

expr ::= term { ("+" | "-") term}

と変形して、それをそのままにコードに直しました。

　実は、用意されている関数 chainl1 を使ってもうちょっと奇麗に処理する事が出来ます。右結合性の演算子に対しては chainr1 を同じ様に使えばいいはず。

　まず、構文木のノード型を定義します。

 abstract class Expr {
   def eval:Int
 }
 case class Add(e:Expr,t:Term) extends Expr {
   def eval = e.eval + t.eval
 }
 case class Sub(e:Expr,t:Term) extends Expr {
   def eval = e.eval - t.eval
 }
 abstract class Term extends Expr {
   def eval:Int
 }
 ...

と書きます。
　Term は単独で Expr になる事が出来るから、Term が Expr のサブクラスになります。
　Expr のサブクラスの case class として Add, Sub を定義します。
　ここまではいいですよね。

　さて、chainl1 は、

def chainl1 [T, U](first : => Parser[T], p : => Parser[U], q : => Parser[(T, U) => T]) : Parser[T]

というメソッドです。これは、first { q p } にマッチするパーサみたいなもの。
　我々の場合だと、Expr をパースするパーサ def expr:Parser[Expr] が作りたいのだから、T = Expr です。
　expr (+|-) term => expr を表現したいのだから、U = term で、p = term:Parser[Term] です。
　q は "+", "-" とかの演算子の部分ですが、(Expr,Term) => Expr という関数を返すパーサです。つまり、(Expr,Term) => Add の様な関数を返せば OK。
　first をどうするかですが、ここに T = expr だから expr と書くと無限ループになって NG。正解は term を指定します。これで term { q term } になりますね。
　これをコードに直すと、

 def add = "+" ^^ {case a => ((e:Expr,t:Term)=>Add(e,t))}
 def sub = "-" ^^ {case a => ((e:Expr,t:Term)=>Sub(e,t))}
 def expr:Parser[Expr] = chainl1(term, term, (add | sub))

となります。

　term についても同様に考えれば OK で、完成したコードは下記の様。

package test;

import scala.util.parsing.combinator._

abstract class Expr {
  def eval:Int
}
case class Add(e:Expr,t:Term) extends Expr {
  def eval = e.eval + t.eval
}
case class Sub(e:Expr,t:Term) extends Expr {
  def eval = e.eval - t.eval
}
abstract class Term extends Expr {
  def eval:Int
}
case class Mul(t:Term,f:Factor) extends Term {
  def eval = t.eval * f.eval
}
case class Div(t:Term,f:Factor) extends Term {
  def eval = t.eval / f.eval
}
abstract class Factor extends Term {
  def eval:Int
}
case class Parens(e:Expr) extends Factor {
  def eval = e.eval
}
case class Num(n:Int) extends Factor {
  def eval = n
}
class ExprParser2 extends JavaTokenParsers {
  def add = "+" ^^ {case a => ((e:Expr,t:Term)=>Add(e,t))}
  def sub = "-" ^^ {case a => ((e:Expr,t:Term)=>Sub(e,t))}
  def expr:Parser[Expr] = chainl1(term, term, (add | sub))
  def mul = "*" ^^ {case a => ((t:Term,f:Factor)=>Mul(t,f))}
  def div = "/" ^^ {case a => ((t:Term,f:Factor)=>Div(t,f))}
  def term:Parser[Term] = chainl1(factor, factor, (mul | div))
  def factor:Parser[Factor] =
    ( wholeNumber ^^ {case s => Num(s.toInt)}
    | "("~expr~")" ^^ {case a~b~c => Parens(b)}
    )
}
object Test2 extends ExprParser2 {
  def main(args:Array[String]) {
    val s = "1 * (2 * 3) - 4*5+(6*7 + 8*9)"
    println(s)
    println(parse(expr, s))
    println(parse(expr, s).get.eval) // -> 100
  }
}

実行すると、

1 * (2 * 3) - 4*5+(6*7 + 8*9)
[1.30] parsed: Add(Sub(Mul(Num(1),Parens(Mul(Num(2),Num(3)))),Mul(Num(4),Num(5))),Parens(Add(Mul(Num(6),Num(7)),Mul(Num(8),Num(9)))))
100