トップ «前の日記(2006-01-08) 最新 次の日記(2006-01-10)» 月表示 編集

日々の流転


2006-01-09 [長年日記]

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

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

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

*1 このメモ化の方法は histomorphism に少し似ているな。