Scalaのパーサコンビネータで右結合
四則演算が出来るパーサに変数を追加して=演算子を使いたい場合に、右結合する演算子を作る必要性が出てきます。右再帰はしたいとかですね。LL文法では左再帰すると無限ループしてしまうので困るのですが、右再帰は特に問題ないはずです。しかし、現時点でググってみて、なかなかよい例が出て来なかったのでメモしておきます。
以下のように書く事で右結合する代入演算子のあるパーサを書く事が出来ます。
package calc import util.parsing.combinator._ object parse extends RegexParsers { def exp:Parser[Any] = repsep(assign,",") ^^ { case a => a.reduceRight[Any] { case (a, b) => (a, ",", b) } } def assign:Parser[Any] = id ~ "=" ~ assign ^^ { case a ~ op ~ b => (a, op, b) } | add def add = term ~ rep(("+" | "-") ~ term) ^^ { case a ~ b => b.foldLeft[Any](a){ case (a, op ~ r)=> (a, op, r) } } def term = fact ~ rep(("*" | "/") ~ fact) ^^ { case a ~ b => b.foldLeft[Any](a) { case(a, op ~ r) => (a, op, r) } } def fact = int | id | "("~>exp<~")" def id = "[a-zA-Z_][a-zA-Z_0-9]*".r def int = """-?[1-9][0-9]*|0""".r ^^ { a => a.toInt } def apply(str:String) = parseAll(exp, str) match { case Success(tree,_) => tree case e => throw new Exception(""+e) } } object Main { def main(argv:Array[String]) { println(parse("a=b=1")) } }
上の例ではfoldLeftを使ったりreduceRightを使ったり書き方がまちまちで、統一感がありません。
reduceLeft,reduceRightだけで書くとより分かりやすく書く事ができます。
以下のように書くと右結合と左結合の書き分けをreduceLeftとreduceRightを書き換えるだけで済みます:
package calc import util.parsing.combinator._ object parse extends RegexParsers { def exp:Parser[Any] = repsep(assign,",") ^^ { case a => a.reduceRight[Any] { case (a, b) => (a, ",", b) } } def assign = add ~ rep("=" ~> add) ^^ { case a ~ b => (a::b).reduceRight[Any] { case (a, b) => (a, "=", b) } } def add = term ~ rep(("+" | "-") ~ term) ^^ { case a ~ b => (a::b).reduceLeft[Any] { case (a, op ~ r)=> (a, op, r) } } def term = fact ~ rep(("*" | "/") ~ fact) ^^ { case a ~ b => (a::b).reduceLeft[Any] { case(a, op ~ r) => (a, op, r) } } def fact = int | id | "("~>exp<~")" def id = "[a-zA-Z_][a-zA-Z_0-9]*".r def int = """-?[1-9][0-9]*|0""".r ^^ { a => a.toInt } def apply(str:String) = parseAll(exp, str) match { case Success(tree,_) => tree case e => throw new Exception(""+e) } } object Main { def main(argv:Array[String]) { println(parse("a=1,b=2,a=b*2=1*2*3+3*4+1+2+3")) } }
リストの生成とリストの変換の分性能は悪くなると思いますが、実験していないので詳しいことは分かりません。
b*2=3といった式も受理してしまいますのでご注意をお願いします。