著者

矢口 拓実 池袋 教誉 前田 敦司

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.9, no.1, pp.14-14, 2016-02-26

---

Packrat Parsingは,広範囲な構文規則を解析できる構文解析手法である.この手法では,解析が成功するまで構文を探索するバックトラックを用い,一度解析した解析対象文字列の位置と結果を保存するメモ化と呼ばれる手法によって解析時間を線形時間に保っている.既存の多くのPackrat Parsing実装は,PEG(Parsing Expression Grammer)で記述された文法規則を,再帰呼び出しによるバックトラックとメモ化表を用いるプログラムに変換するが,このような処理系の実行速度は,正規表現に基づいて表引きを用いた字句解析器と,同じく表引きとスタックを用いて処理を進めるLALR(1)などのパーサアルゴリズムの組み合わせと比較すると,一般的に劣っている.本発表では,Packrat Parsingの高速化のため,解析の意味が変化しない範囲で表引きによって構文解析を進める手法を検討する.本発表では,Packrat Parsingの処理の中に可能な限り表引きをとり入れることで,実行速度を向上させる手法を提案する.また,基本的な実行方式としてはMedeirosらの提案した仮想マシン方式を改良したものを採用している.既存の手法と比較した性能評価の結果を示す.