[Scala] How to Use Combinator Parser (1)

Scala の Parser Combinator の使い方の勉強 (1)

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

●数式のパーサを書いてみる

使い方練習という事で、整数の括弧有り四則演算の出来るパーサを書くことにします。
scala.util.parsing.combinator.JavaTokenParsers を元に作成するのが簡単です。なぜならば、

• 識別子(大文字+小文字+数字+'_'からなる文字列)、数（整数、実数、指数形式の実数）、文字列リテラル（"..."な文字列でUnicode対応）のパーサが予め用意されている。


• 空白文字を自動的に読み飛ばす機能付き。
  

だから。

パーサクラスを、

import scala.util.parsing.combinator._

class ExprParser1 extends JavaTokenParsers {
  ...
}

と宣言して、...の部分を考えることにします。

まず数式の(E)BNF文法ですが、

<expr> ::= <expr> "+" <term> | <expr> "-" <term> | <term>
<term> ::= <term> "*" <factor> | <term> "/" <factor> | <factor>
<factor> ::= "(" <expr> ")" | <number>

と書くと、左再帰でパーサコンビネータでは都合が悪い（expr の解析で expr を呼んで...を繰り返しすぐにstack overflowする）ので、(以下、HTMLでは面倒なので < > は省略)

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

と書き直す事にします。

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

の部分をどうするかですが、

  case class OpTerm(op:String, t:Term) { // op = "+" or "-"
    def eval(n:Int):Int = op match {
     case "+" => n + t.eval()
   case "-" => n - t.eval()
   case _   => error(this.toString)
 }
  }
  case class Expr(t:Term, ots:List[OpTerm]) {
    def eval():Int = ots.foldLeft(t.eval()){(n:Int, ot:OpTerm) => ot.eval(n)}
  }
  def opTerm:Parser[OpTerm] = ("+" | "-")~term ^^ {case a~b => OpTerm(a,b)}
  def expr:Parser[Expr] = term~rep(opTerm) ^^ {case a~b => Expr(a,b)}

と、構文木のノード型を定義し、パーサ関数を定義します。
　関数 opTerm は ("+" | "-" ) term の部分を表現しています。JavaTokenParsersでは、文字列 "+" は「文字列 "+" にマッチするパーサ」に暗黙の型変換がされます。"~" は、あるパーサにマッチした後に別のパーサにマッチすることを表します。"^^" は、 パーサがマッチした後の値を与える関数を書きます。"a~b" は実は case classで、a には("+" | "-")のマッチした結果 (文字列 "+" か "-") が入り、b には term のマッチした結果 (型 Term の値) が入ってます。
　関数 expr は term { opTerm } を表現します。rep(opTerm) で、opTerm の０回以上の繰り返しに対応するパーサになり、opTerm の繰り返しなので List[OpTerm] を与えるパーサとなります。
　case class の OpTerm, Expr の eval メソッドについては説明は省略。

　term ::= factor { ("*" | "/") factor } についても同様に書けるので説明は省略。

　factor ::= "(" expr ")" | number については下記の様に書けます。

 def factor:Parser[Factor] = 
   ( wholeNumber ^^ {case s => Num(s.toInt)}
   | "("~expr~")" ^^ {case a~b~c => Parens(b)}
   )
 abstract class Factor {
   def eval():Int
 }
 case class Num(n:Int) extends Factor {
   def eval():Int = n
 }
 case class Parens(e:Expr) extends Factor {
   def eval():Int = e.eval()
 }

　wholeNumber は、JavaTokenParsersで定義されている、整数を表す文字列にマッチするパーサ。
"("~expr~")" ^^ ... の部分は見当がつくと思います。その２つを "|" で繋いでいます。

パーサを使う部分はこんな感じで書けます。

object Test1 extends ExprParser1 {
  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
  }
}

作成したクラス ExprParser1 のメソッド parse に、パースしたい関数 (我々の場合は expr )と、入力 (String以外にjava.io.ReaderなどもOK) を渡します。得られたParseResult[Expr] のメソッド get で Expr 型の結果を得て、eval すれば OK です。

実はもっと要領よく書けるはずですが、判りやすさを優先して書いてみました。

全体のソースは下記の通り。

package test;

import scala.util.parsing.combinator._
// BNF with Left Recursion
// expr ::= expr + term | expr - term | term
// term ::= term * factor | term / factor | factor
// factor ::= ( expr ) | number
//
// BNF without Left Recursion
// expr ::= term { (+|-) term }
// term ::= factor { (*|/) factor }
// factor ::= ( expr ) | number

class ExprParser1 extends JavaTokenParsers {
  def opTerm:Parser[OpTerm] = ("+" | "-")~term ^^ {case a~b => OpTerm(a,b)}
  def expr:Parser[Expr] = term~rep(opTerm) ^^ {case a~b => Expr(a,b)}
  def opFactor:Parser[OpFactor] = ("*" | "/")~factor ^^ {case a~b => OpFactor(a,b)}
  def term:Parser[Term] = factor~rep(opFactor) ^^ {case a~b => Term(a,b)}
  def factor:Parser[Factor] = 
    ( wholeNumber ^^ {case s => Num(s.toInt)}
 | "("~expr~")" ^^ {case a~b~c => Parens(b)}
 )
  case class OpTerm(op:String, t:Term) { // op = "+" or "-"
    def eval(n:Int):Int = op match {
   case "+" => n + t.eval()
   case "-" => n - t.eval()
   case _   => error(this.toString)
 }
  }
  case class Expr(t:Term, ots:List[OpTerm]) {
    def eval():Int = ots.foldLeft(t.eval()){(n:Int, ot:OpTerm) => ot.eval(n)}
  }
  case class OpFactor(op:String, f:Factor) { // op = "*" or "/"
    def eval(n:Int):Int = op match {
      case "*" => n * f.eval()
      case "/" => n / f.eval()
      case _   => error(this.toString)
    }
  }
  case class Term(f:Factor, ofs:List[OpFactor]) {
    def eval():Int = ofs.foldLeft(f.eval()){(n:Int, of:OpFactor) => of.eval(n)}
  }
  abstract class Factor {
    def eval():Int
  }
  case class Num(n:Int) extends Factor {
    def eval():Int = n
  }
  case class Parens(e:Expr) extends Factor {
    def eval():Int = e.eval()
  }
}
object Test1 extends ExprParser1 {
  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.28] parsed: Expr(Term(Num(1),List(OpFactor(*,Parens(Expr(Term(Num(2),List(OpFactor(*,Num(3)))),List()))))),List(OpTerm(-,Term(Num(4),List(OpFactor(*,Num(5))))), OpTerm(+,Term(Num(6),List(OpFactor(*,Num(7))))), OpTerm(+,Term(Num(8),List(OpFactor(*,Num(9)))))))
100