パックラット構文解析

パックラット構文解析(英：Packrat Parsing)とは、PEGにより構文解析を行うアルゴリズムである。"packrat"はネズミの一種であり、そのネズミの習性に由来して「役に立たなそうなものでも習慣的に集めて持っておく人」[1]という意味でも使われる。

アルゴリズム

バックトラックのある再帰下降構文解析の途中結果をメモ化し、各構文解析関数が同じ入力位置について高々1回までしか呼ばれないようにする。このことにより、解析時間は文字列の長さに対して常に線型時間で動作するようになる。

実装一覧

パーサジェネレータやパーサコンビネータでの実装がある。

• Waxeye [1]
• PackCC [2] - C 用 (左再帰サポート)

脚注

1. http://www.thefreedictionary.com/packrat

参考文献

• The Packrat Parsing and Parsing Expression Grammars Page [3]
• Bryan Ford, Packrat Parsing: Simple, Powerful, Lazy, Linear Time[4]