著者

多田 拓 倉光 君郎

雑誌

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

巻号頁・発行日

vol.12, no.2, pp.1-9, 2019-05-21

---

曖昧さのある形式文法から生成されたパーサは異なる解釈をした複数の結果が導出されうる.このような複数の可能性を試すパーサは非線形の計算時間を必要とし,プログラミング言語などの人工言語の構文解析において望ましくない.Parsing Expression Grammar(PEG)の強みは優先度付き選択と貪欲な繰り返しによって曖昧さがないように形式化されている点である.しかしながら,近年の文法推論や自然言語を含んだ解析への応用では曖昧さが重要となっている.本研究では,PEGに文法的な拡張を加えることで,曖昧さを追加した新しい形式化基盤Generalized PEG(GPEG)を提案する.GPEGは決定的なPEGの文法に対して,優先度なし選択を加えた拡張となっている.一般化構文解析手法であるGLRやGLLで構築される曖昧な木とは異なり,曖昧さを文法から制御可能であるため部分的に曖昧な木を構築する.さらに,本研究で提案しているgeneralized packrat parsingによって実用的な時間で構文解析が可能である.