kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Scalaで作るPEGパーザコンビネータ

といっても、昨日Javaで作ったPEGパーザコンビネータライブラリをScalaで書き直しただけのものだけど。Java版に比べて、1/3くらいの行数になっている。

object PEGParserCombinator {
  abstract class Parser[+A] extends (String => Option[(A, String)]) {
    def /[B >: A](that: => Parser[B]): Parser[B] = parserOf((in) => {
      this(in) orElse that(in)
    })
    def ~[B](that: => Parser[B]): Parser[(A, B)] = parserOf((in) => {
      for((r1, rest1) <- this(in);
          (r2, rest2) <- that(rest1)) yield ((r1, r2), rest2)
    })
    def ^^[B](f: A => B): Parser[B] = parserOf((in) => {
      for((r, rest) <- this(in)) yield (f(r), rest)
    })
    def ? : Parser[Option[A]] = parserOf((in) => {
      this(in).map{p => (Some(p._1), p._2)}.orElse(Some(None, in))
    })
    def * : Parser[List[A]] = parserOf((in) => {
      def parse(in: String) : (List[A], String) = {
        this(in) match {
          case Some((r, rest)) => val (r2, rest2) = parse(rest); (r::r2, rest2)
          case None => (Nil, in)
        }
      }
      Some(parse(in))
    })
    def + : Parser[List[A]] = (this ~ this.*) ^^ {p => p._1::p._2}
    def unary_! : Parser[Unit] = parserOf((in) => {
      this(in) match {
        case Some(_) => None
        case None => Some((), in)
      }
    })
  }
  def parserOf[A](f: String => Option[(A, String)]): Parser[A] = 
    new Parser[A] {
      def apply(param: String): Option[(A, String)] = f(param)
    }
  def string(param: String): Parser[String] = parserOf((in) => {
    if(in startsWith param) Some(param, (in substring(param length)))
    else None
  })
  def and[A](p: => Parser[A]): Parser[Unit] = !(!p)
  lazy val any: Parser[String] = parserOf((in) => {
    if(in.length > 0) Some(in substring(0, 1), in substring 1) else None
  })
  implicit def stringToParser(param: String) = string(param)
}

使い方は以下のような感じ。昨日と同じく、文脈自由文法では表現できない、a^n b^n c^nをPEGで表現したものを記述している。演算子のオーバーロードが使える分(それだけじゃないけど)、Javaに比べて記述がだいぶ簡潔になっているのがわかると思う。

import PEGParserCombinator._
object User {
  lazy val A: Parser[Any] = "a" ~ A.? ~ "b"
  lazy val S: Parser[Any] = and(A ~ !"b") ~ string("a").+ ~ B ~ !"c"
  lazy val B: Parser[Any] = "b" ~ B.? ~ "c"
}
println(User.S(args(0)))