Packrat Parserを使ってみた

新しくブログ作ってみました。
Advent Calendar遅くなってすいません…。

Akasaka Scalaで、Parserのバックトラッキングについて話していたときに、教えて頂いたPackratParsersを使ってみました。

PackratParsersを使うことによるメリットは、
解析結果をメモ化し、バックトラック時に無駄な再解析を防ぐことで、解析処理を線形時間で終了させられること
ですが、
メモ化のために、余計なメモリを使ってしまう
というデメリットもあります。

それでは普通のParsersとPackratParsersを使ってメモ化がされているかを確かめてみます。

import util.parsing.combinator.{PackratParsers, Parsers}
import util.parsing.input.CharSequenceReader


object Example {

 // 普通のParsersバージョン
 object NormalExample extends Parsers {

  type Elem = Char

  lazy val X = Y ~ 'b' | Y ~ 'c'

  lazy val Y = 
   elem("a", char => {
    println("Parsing a in packrat parser.")
    char == 'a'
   })

  def parseInput(in: String) = 
   X(new PackratReader(new CharSequenceReader(in)))
 }


 // PackratParsersバージョン
 object PackratExample extends PackratParsers {

  type Elem = Char

  lazy val X: PackratParser[Any] = Y ~ 'b' | Y ~'c'

  lazy val Y: PackratParser[Any] = 
   elem("a", char => {
    println("Parsing a in packrat parser.")
    char == 'a'
   })

  def parseInput(in: String) = 
   X(new PackratReader(new CharSequenceReader(in)))
 }

 // 実行
 def main(args: Array[String]): Unit = {

  println(NormalExample.parseInput("ac"))
  println("------------------------------------")
  println(PackratExample.parseInput("ac"))

 }

}

上記のNormalExampleとPackratExampleとは全く同じ文法を解析します。
パーサYは、文字'a'をパースし、その時に文字出力を行います。
パーサXは、文字'a'の解析にパーサYを使用し、"ab" または "ac" をパースします。

パーサXに"ac"という文字列を入力すると、

NormalExampleは

パーサYで解析 → 成功 →
文字'b'が来るか解析→ 失敗 →
最初に戻る →
パーサYで解析 → 成功 →
文字'c'が来るか解析 → 成功

となりパーサYの解析は2回行われますが、

PackratExampleは

パーサYで解析 → 成功 →
文字'b'が来るか解析→ 失敗 →
最初に戻る →
★パーサYで解析済み →
文字'c'が来るか解析 → 成功

となるので、パーサYの解析は1回しか行われません。

以下が実行結果になります。

Parsing a in normal parser.
Parsing a in normal parser.
[1.3] parsed: (a~c)
------------------------------------
Parsing a in packrat parser.
[1.3] parsed: (a~c)

PackratParsersを使用する場合に注意しなければいけないのは、
PackratParsersを継承したクラスで作成したパーサがすべてPackratParserになるのではない所です。
パーサに型を指定して暗黙変換してもらうか、memoメソッドによって明示的に変換する必要があります。

と、この辺で。