Parser Combinator 続き

scala

http://www.scala-lang.org/docu/files/ScalaByExample.pdf

のCombinator Parsing のサンプルなんだけど、最新版のScalaだと動かない。
ドキュメントがついていけてないっぽい。

これを、今インストールしているバージョン(2.7.0)で動くものを作ろうと、

http://d.hatena.ne.jp/ryugate/20080221#p1

を参考にしつつ、あれこれやってて、結局こうなった。

import scala.util.parsing.combinator._
import scala.util.parsing.input.CharArrayReader
import scala.util.parsing.input.Reader

abstract class Tree
case class Id(s: String) extends Tree
case class Num(n: Int) extends Tree
case class Lst(elems: List[Tree]) extends Tree

trait ListParsers extends Parsers  {
  type Elem = Char
  
  def letter: Parser[Elem] = elem("LETTER", Character.isLetter _)
  def digit:  Parser[Elem] = elem("DIGIT",  Character.isDigit _)
  
  def ident:  Parser[Id]            = letter ~ (letter | digit).* ^^ createIdNode
  def number: Parser[Num]           = digit ~ digit.*             ^^ createNumNode

  def list:   Parser[Lst]           = '(' ~> listElems.? <~ ')'   ^^ createLstNode
  def expr:   Parser[Tree]          = ident | number | list       ^^ createExprNode
  def listElems: Parser[List[Tree]] = expr ~ (',' ~> listElems).? ^^ createListElemsNode

  def createIdNode(value:  ~[Elem, List[Elem]]): Id
  def createNumNode(value: ~[Elem, List[Elem]]): Num
  def createLstNode(value: Option[List[Tree]]): Lst
  def createExprNode(value: Tree): Tree
  def createListElemsNode(value: ~[Tree, Option[List[Tree]]]): List[Tree]
}

class TreeListParsers extends ListParsers {

  def createIdNode(value:  ~[Elem, List[Elem]]): Id = value match {
    case ~(a, b) => Id("" + a + b.mkString)
  }

  def createNumNode(value: ~[Elem, List[Elem]]): Num = value match {
    case ~(a, b) => Num(("" + a + b.mkString).toInt)
  }

  def createLstNode(value: Option[List[Tree]]): Lst = value match {
    case Some(t) => Lst(t)
    case None    => Lst(List())
  }

  def createExprNode(value: Tree): Tree = value

  def createListElemsNode(value: ~[Tree, Option[List[Tree]]]): List[Tree] = value match {
    case ~(head, Some(list)) => head :: list
    case ~(head, None)       => List(head)
  }
}


def toInput(s: String): Reader[Char] = new CharArrayReader(s.toArray)

val p = new TreeListParsers

println(p.expr(toInput("12")))
println(p.expr(toInput("ab")))
println(p.expr(toInput("()")))
println(p.expr(toInput("(ab,12)")))
println(p.expr(toInput("((ab),12,(cd,34))")))

0

グラマーの定義は、ListParsers に、Treeの組み立ては、TreeListParsers に別個にしてみた。

これを、ListParsers.scala というファイルに保存して実行すると、以下のような結果が出力される。

&lt; scala ListParsers.scala
[1.3] parsed: Num(12)
[1.3] parsed: Id(ab)
[1.3] parsed: Lst(List())
[1.8] parsed: Lst(List(Id(ab), Num(12)))
[1.18] parsed: Lst(List(Lst(List(Id(ab))), Num(12), Lst(List(Id(cd), Num(34)))))

できたはできたけど、こんな感じでいいのかよくわからんなー。

ポイントは、

  • "^^"の左辺の関数の戻り値の型と、グラマー(identとか、exprとか）の型Parser[?] の ? の部分を一致させる。
  • "^^"の左辺の関数の引数の型は、グラマー定義の内容で決まる。上で使ったやつを説明すると。
    • A ~ B の場合は、~[A, B] という型*1（A, Bは任意の型）
    • A | B の場合は、AとBの型が同じクラスなら、A。A と B が共通の親クラスCを持つなら、C。共通の親クラスを持たないとコンパイルできない。
    • A.* の場合は、List[A]
    • A.? の場合は、Option[A]
    • A ~> B は、A,Bの順番を指定するけど、Aの値は処理に不要な時。
    • A <~ B は、上のやつの逆
  • type Elemで指定した型には、Parsers.scala内の以下の Implicit Conversion が適用される。
    • implicit def accept(e: Elem): Parser[Elem]
    • 上記のグラマーだと、「'(' ~> 」の部分に、Implicit Conversion が適用されている。

*1:Parsers.scalaの中で、"~"というcase class が定義されている。