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
