情報処理学会論文誌．プログラミング (PRO 51) 1 最適化 Packrat Parser の 空間計算量の計算手法の提案 ○ 水 島 宏 太†1 前 田 敦 司†1 山 口 喜 教†1 従来主流の構文解析手法である LL や LR 法��

情報処理学会論文誌．プログラミング (PRO 51) 1 最適化 Packrat Parser の 空間計算量の計算手法の提案 ○ 水 島 宏 太†1 前 田 敦 司†1 山 口 喜 教†1 従来主流の構文解析手法である LL や LR 法の欠点を解決する構文手法の一つとし て packrat parsing という構文解析手法が注目を集めている．packrat parsing は， parsing expression grammar (PEG) という形式文法で表現できる任意の言語を扱 うことができ，これは LL 法や LR 法よりも強力である．また，packrat parsing で は解析を線形時間で行うことができる．しかし，packrat parsing では，構文解析の 中間結果を全てメモ化するため，メモリ使用量が線形になってしまうという欠点があ る．我々の研究では，カット演

[isgk]

最適化Packrat Parserの空間計算量の計算手法の提案