著者

山口 大輔 山口 真弥 千田 忠賢 倉光 君郎

雑誌

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

巻号頁・発行日

vol.10, no.2, pp.2, 2017-02-27

---

再帰下降構文解析は人気の実装方法であるが,バックトラッキングにより,最悪ケースにおいて指数時間を要することが知られている.現実のパーサでは,最悪ケースはほとんど発生しないが線形時間性を保証することは難しい.本研究では,再帰下降構文解析の形式モデルとしてPEGを用い,PEGの文法定義から線形時間性を判定する方法に取り組んだ.