日々の流転

λ. Packrat Parsing: Simple, Powerful, Lazy, Linear Time. Bryan Ford

ナイーブなパーサコンビネータライブラリーでパーサを書くと、入力文字列に対して最悪指数オーダだが、メモ化(memoization)*1によってリニアなオーダになる。非正格関数型言語の性質を利用してそのメモ化を行うのがPackratパーサ。

ちょっと面白いと思ったのは、一般的なアルゴリズムでパーサを書く場合にレキサとパーサを分ける理由。一般的なアルゴリズムでは、トークン単位でしか先読みできず、より大きな単位での先読みが出来ないために、先読みで必要なだけの情報をレキサがトークンにまとめておかなくてはならないから、というもの。ちなみに、Packratパーサは入力文字列のSuffixに対するパース結果を自由に先読み出来るので、レキサをパーサから分離する必要はない。