[Scala] How to Use Combinator Parser (3)

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

　今回は小ネタ。

　例えばXMLとかでタグが対応していたりとか、(La)TeXのenvironmentなどの¥bigin{xxx}...¥end{xxx}のように、ある範囲の最初と最後に同じ文字列が出てくることを要請したい場合。こんな感じで実現出来る。

　例えばXML風のタグの対応を実装する場合、

 def tagged:Parser[Tagged] =
     "<"~>ident~">"~tkn~"</"~ident<~">" ^? {
     case i~_~t~_~j if i==j => Tagged(i,t)
     }

　a~>b, c<~d というのは、a~b, c~d と同じ様なものだが、a, d の結果を使用しない場合に使えるscala.util.parsing.combinator.Parsers.Parserのメソッド。今回の場合は最初の"<"と最後の">"はマッチさせても後で使わないので。但し、~と違って、a~b~c~... と繋いで結果のcaseを作れないので、"</"とかは~で前後を繋いで、caseでは_を使って結果を使わない事を示してみた。
　^? というのは ^^ と同じ様なものだが、^^ は case にマッチする事が必要。^? の場合、caseのマッチで失敗した場合にはパース失敗と出来る。今回は i!=j になる場合は失敗させるため、^? を使う。

　全体のコードはこんな感じ。(...しかし不等号をblogに書くのはいちいちエスケープするのが面倒だった...)

package test;

import scala.util.parsing.combinator._

abstract class Tkn
case class Lit(s:String) extends Tkn
case class Tagged(tag:String, t:Tkn) extends Tkn
object Test3 extends JavaTokenParsers {
 def tagged:Parser[Tagged] =
     "<"~>ident~">"~tkn~"</"~ident<~">" ^? {
     case i~_~t~_~j if i==j => Tagged(i,t)
     }
 def tkn:Parser[Tkn] =
   ( tagged
   | ident ^^ {case s => Lit(s)}
   )
 def main(args:Array[String]) {
   val s = "<aaa><bbb>ccc</bbb></aaa>"
   println(s)
   println(parse(tagged, s))
 }
}

結果は下記の様な感じ

結果１
<aaa><bbb>ccc</bbb></aaa>
[1.26] parsed: Tagged(aaa,Tagged(bbb,Lit(ccc)))

---
結果２
<aaa><bbb>ccc</bbbb></aaa>
[1.21] failure: Constructor function not defined at ((((bbb~>)~Lit(ccc))~</)~bbbb)

<aaa><bbb>ccc</bbbb></aaa>
---
結果３
<aaa><bbb>ccc</bbb></aaaa>
[1.27] failure: Constructor function not defined at ((((aaa~>)~Tagged(bbb,Lit(ccc)))~</)~aaaa)

<aaa><bbb>ccc</bbb></aaaa>

[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

[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