関数型言語マニアのための論文紹介２：Packrat Parsing

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

http://pdos.csail.mit.edu/~baford/packrat/icfp02/

「設定ファイルや専用言語のparserをYACCで書こうと思ったけど、conflictだらけになってわけがわからない」という経験はないでしょうか。それはLALR(1)という構文解析アルゴリズムがややこしいからいけないのです。packrat parsingは、すごく単純で効率のよい構文解析アルゴリズムです。大ざっぱに言うと「再帰＋バックトラッキング＋dynamic programming」だけ。YACCみたいな自動生成器もあるようですが、関数型言語なら手書きしてもno problemなぐらい楽みたいです。（Y研の卒論でC++パーザを手書きした人もいます。しかもHaskellではなくOCamlで。）

追記：コピペミスでエントリのタイムスタンプ(?)が狂ってたかも。すみません。