著者

今泉 良紀 篠埜 功

雑誌

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

巻号頁・発行日

vol.11, no.3, pp.24, 2018-09-20

---

PEG(Parsing Expression Grammar,解析表現文法)は文法規則に曖昧さのない形式文法であり,プログラミング言語の構文記述に有用である.PEGによる文法は再帰下降構文解析器と対応しているため,パーサコンビネータによる簡易な実装によってPEGの文法から実際に動作するパーサが得られる.特にEDSL(Embedded Domain Specific Language)によるパーサコンビネータ実装は,パーサの記述のし易さを確保しつつ,意味規則の記述などの点でホスト言語との接続が簡潔であるという利点がある.また,バックトラックのある再帰下降構文解析器は素朴な実装では入力長に対して最悪指数関数時間を要するが,再帰下降構文解析にメモ化を組み合わせたパックラット構文解析という手法によって入力長に対して線形時間で解析が可能となる.本発表では,C++で記述されたPEGに基づくパーサコンビネータ実装として,Boost.Spirit.X3,cpp-peglib,PEGTL,matcha2の4つの実装の実行性能について比較した結果と,これらの中で最も実行速度の速いmatcha2の実装の詳細について報告する.