PEGパーサーのバックトラッキング

Haskell Parser PEG

前回、どちゃっと乗せたPEG電卓のコードなんですが、これはPappyやFrisbyのようにメモ化をまったくやっていないPEGパーサーです。ちょっと思いついて、いったいどれくらいの勢いでバックトラッキングが起きているのかを調べてみました。
バックトラッキングがたくさん起きているということはメモ化がそれだけ動作効率に影響しやすいという事になりますよね…

あれだけでかいコードでも、実際に文字をマッチしている関数は二つだけです。そこで、その２つの関数にDebug.Trace.traceをくっつけてみることにしました

_char :: (a -> Bool) -> [a] -> Maybe ([a], [a])
_char _  = Nothing
_char f (c:cs) =
	if (f c) then Just ([c], cs)
		else trace "_char failed" Nothing

eofP :: Parse [a] [a]
eofP = Parse $ \i -> f i
	where
		f  = Just(, )
		f _ = trace "eofP failed" Nothing

そして、コンパイルしなおした電卓に簡単な計算をさせます。

calc "1 + 1"

=>
_char failed
_char failed
　　:
     中略
　　:
_char failed
_char failed
_char failed
_char failed
_char failed
_char failed
_char failed
_char failed
2

ということで、トレースメッセージの出現回数をカウントするとなんと４６回です！
何でこんなことになったのでしょう？入力したのはたったの５文字です…

今回のコードの元になったPEGを引っ張ってきましょう

OPTBLANK=(' '/'\t')*

DIGIT = (1/2/3/4/5/6/7/8/9)
DIGIT0 = (0/DIGIT)

NUMBER=(ZERO/-?NONZERO)

ZERO = 0!(DIGIT0)
NONZERO = (DIGIT, DIGIT0*)

BLOCK=(\(,OPTBLANK,FORMULA,OPTBLANK,\),OPTBLANK,)
BLOCKORNUM=(NUMBER/BLOCK)

ADDDEC=(MULDIVORNUM,OPTBLANK,(+/-),OPTBLANK,ADDDEC)
MULDIV=(BLOCKORNUM,OPTBLANK,(*/\//),OPTBLANK,MULDIV)
MULDIVORNUM=(MULDIV/BLOCKORNUM)

FORMULA=(OPTBLANK,(ADDDEC/MULDIVORNUM))

バックトラックという観点から見ると、'9'をDIGITがパースするのには実はバックトラックを８回することになります。同じ'9'をNUMBERがパースするためには、まずZEROが失敗して、その次にオプショナルな'-'、そしてやっとNONZEROにいきますが、そこで'9'を発見した後にまたDIGIT0*なんていうのがあって、残念ながら次の文字はないので、ここではすべての選択肢を試した挙句にフェイルして帰ってくることになります。

ということで、NUMBERだけでもかなり大変なことになっているのがわかりますね…

もう少し上のレベルのパーサーを見てみると、ADDDECもMULDIVもさらにそれらを統合しているFULDIVORNUMやFORMULAも選択オペレータをとても贅沢に使っていることがわかりますね…自分の頭でこのPEG文法に沿って数式をパースしようと思うと気が遠くなりそうです。1 + 1をパースするのに４６回バックトラックしてもおかしくない気がしてきますね…

ちょっと考えてみると、バックトラックしたときの振る舞いはおそらく２つに大別できて、一度フェイルしたらもうその文字に対して同じパーサーが走ることはない場合（たとえばDIGITが'9'をパースするときの１−８まで）と、同じパーサーが同じ文字列に対して走る場合があるようです。

２つ目のほうの例を今回の電卓で見てみると、足し算は乗除よりもプライオリティが低いうえ、両方ともパラメタを２項とも含んだ形で定義されているので、1 + 1の最初の１はまずはMULDIVORNUM経由のMULDIVの１項目めとしてマッチして、そのあと＊も／もないのでMULDIVが失敗して、次にMULDIVORNUMの第２選択肢であるBLOCKORNUMにもう一度マッチします…

この場合はメモ化が効果を発揮しそうですね…メモ化をしなくてもパーサーの定義のほうである程度のバックトラック量の削減はできそうな気もします。パーサーの可読性や再利用性は犠牲になるかもしれませんが…

今日はこの辺で。
ではでは。