Scala で Packrat Parsing

最近あちこちでこの名前を見かけてよく分からなくて気になっていたので [1] の文献を読みつつ（最後まで読んでないけど） Scala で書いてみた。lazy も導入されたのでこれは Scala 向きの問題のはず。ちゃんと検索すれば既にやっている人とかライブラリとか見つかるのかもしれないけど。

文献に出てくるのと同様の単純な電卓パーサーで、記法上のポイントは Scala の Option 型は for comprehension と組み合わせると Haskell の Maybe モナド + do 記法みたいに使えるという点です。また orElse は Option 型のメソッドで None だった場合のデフォルト値みたいなものです。

私の誤解がなければこれでよいはず…

case class Derivs(s: List[Char]) {
  type Result[T] = Option[(T, Derivs)]

  lazy val additive: Result[Int] = {
    for ((vLeft,  d1) <- multitive;
         ('+',    d2) <- d1.character;
         (vRight, d3) <- d2.additive)
      yield (vLeft + vRight, d3)
    } orElse multitive

  lazy val multitive: Result[Int] = {
    for ((vLeft,  d1) <- primary;
         ('*',    d2) <- d1.character;
         (vRight, d3) <- d2.additive)
      yield (vLeft * vRight, d3)
    } orElse primary

  lazy val primary: Result[Int] = {
    for (('(', d1) <- character;
         (v,   d2) <- d1.additive;
         (')', d3) <- d2.character)
      yield (v, d3)
    } orElse decimal

  lazy val decimal: Result[Int] = {
    character match {
      case Some(c, d1) if c.isDigit => Some(c.asDigit, d1)
      case _ => None
    }
  }

  lazy val character: Result[Char] = {
    s match {
      case c::s2 => Some(c, new Derivs(s2))
      case Nil => None
    }
  }
}

実行例は以下のような感じ。

scala> Derivs("2*(3+4)".toList).additive
res0: Derivs#Result[Int] = Some((14,Derivs(List())))

[1] http://pdos.csail.mit.edu/~baford/packrat/icfp02/