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といった式も受理してしまいますのでご注意をお願いします。