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メソッドによって明示的に変換する必要があります。
と、この辺で。
0 件のコメント:
コメントを投稿