【急募】PEGパーサのメモ化の実装
http://twitter.com/anatoo/status/1253132392
とかあったんで、せっかくなのでサクっと実装してみた。
ポイントは、PEGパーサコンビネータでは、ParserがString => Option[(A, String)]
を継承していたのを、Int => Option[(A, Int)]
を継承するようにしたことと、Parserの外側のクラスに入力文字列を表すメンバinput
を追加したこと。Stringを引数に取る形でも良いのだけど、そうすると、テーブルのルックアップコストが高くなってしまうので、メモ化する意味がほとんど無くなってしまう。
trait PackratParser[+A] { val input: String abstract class Parser[+A] extends (Int => Option[(A, Int)]) { def /[B >: A](that: => Parser[B]): Parser[B] = parserOf{pos => this(pos) orElse that(pos) } def ~[B](that: => Parser[B]): Parser[(A, B)] = parserOf{pos => for((r1, rpos1) <- this(pos); (r2, rpos2) <- that(rpos1)) yield ((r1, r2), rpos2) } def ^^[B](f: A => B): Parser[B] = parserOf{pos => for((r, rpos) <- this(pos)) yield (f(r), rpos) } def ? : Parser[Option[A]] = parserOf{pos => this(pos).map{p => (Some(p._1), p._2)}.orElse(Some(None, pos)) } def * : Parser[List[A]] = parserOf{pos => def parse(pos: Int) : (List[A], Int) = { this(pos) match { case Some((r, rpos)) => val (r2, rpos2) = parse(rpos); (r::r2, rpos2) case None => (Nil, pos) } } Some(parse(pos)) } def + : Parser[List[A]] = (this ~ this.*) ^^ {p => p._1::p._2} def unary_! : Parser[Unit] = parserOf{pos => this(pos) match { case Some(_) => None case None => Some((), pos) } } } class Memoized[+A](val parser: Parser[A]) extends Parser[A] { import scala.collection.mutable._ private[this] val cache = new HashMap[Int, Option[(A, Int)]] def apply(pos: Int): Option[(A, Int)] = { cache.get(pos).getOrElse { val result = parser(pos) cache(pos) = result result } } } def parserOf[A](f: Int => Option[(A, Int)]): Parser[A] = new Parser[A] { def apply(param: Int): Option[(A, Int)] = f(param) } def string(param: String): Parser[String] = parserOf{pos => val in = input.substring(pos) if(in startsWith param) Some(param, pos + param.length) else None } def and[A](p: => Parser[A]): Parser[Unit] = !(!p) lazy val any: Parser[String] = parserOf{pos => val in = input.substring(pos) if(in.length > 0) Some(in substring(0, 1), pos + 1) else None } implicit def stringToParser(param: String) = string(param) implicit def parserToMemoized[A](p: Parser[A]) = new Memoized(p) def parse: Option[(A, String)] = { for((r, pos) <- S(0)) yield (r, input.substring(pos)) } val S: Parser[A] }
使い方は以下のような感じ。
class ParenParser(override val input: String) extends PackratParser[Any] { lazy val S: Parser[Any] = A ~ !any lazy val A: Parser[Any] = P ~ "+" ~ A / P ~ "-" ~ A / P lazy val P: Parser[Any] = "(" ~ A ~ ")" / "1" } //memoized class MemoizedParenParser(override val input: String) extends PackratParser[Any] { lazy val S: Memoized[Any] = A ~ !any lazy val A: Memoized[Any] = P ~ "+" ~ A / P ~ "-" ~ A / P lazy val P: Memoized[Any] = "(" ~ A ~ ")" / "1" } def time(any: => Any): Long = { val start = System.currentTimeMillis any System.currentTimeMillis - start } val input = "(((((((((((((1)))))))))))))" printf("not memoized: %dms%n", time{new ParenParser(input).parse}) printf("memoized: %dms%n", time{new MemoizedParenParser(input).parse})
ここでは、メモ化した場合としない場合で著しい差が出る文法に対してマッチングを行い、実行時間を出力しようとしている。このプログラムを実行すると(Intel Core2 Duo 2.40GHz, RAM 2.0GB, JDK1.6.0 Client VM)、
not memoized: 5063ms memoized: 0ms
となり、メモ化が確かに効いていることが確認できる(ほんとはこんなテキトーな測定方法じゃ良くないけど、明らかに差があるのはわかる)。