@article{oai:ipsj.ixsq.nii.ac.jp:00191428,
 author = {今泉, 良紀 and 篠埜, 功 and Yoshiki, Imaizumi and Isao, Sasano},
 issue = {3},
 journal = {情報処理学会論文誌プログラミング（PRO）},
 month = {Sep},
 note = {PEG（Parsing Expression Grammar，解析表現文法）は文法規則に曖昧さのない形式文法であり，プログラミング言語の構文記述に有用である．PEGによる文法は再帰下降構文解析器と対応しているため，パーサコンビネータによる簡易な実装によってPEGの文法から実際に動作するパーサが得られる．特にEDSL（Embedded Domain Specific Language）によるパーサコンビネータ実装は，パーサの記述のし易さを確保しつつ，意味規則の記述などの点でホスト言語との接続が簡潔であるという利点がある．また，バックトラックのある再帰下降構文解析器は素朴な実装では入力長に対して最悪指数関数時間を要するが，再帰下降構文解析にメモ化を組み合わせたパックラット構文解析という手法によって入力長に対して線形時間で解析が可能となる．本発表では，C++で記述されたPEGに基づくパーサコンビネータ実装として，Boost.Spirit.X3，cpp-peglib，PEGTL，matcha2の4つの実装の実行性能について比較した結果と，これらの中で最も実行速度の速いmatcha2の実装の詳細について報告する．, PEGs (parsing expression grammars) are used for formally describing unambiguous grammars and thus are useful to describe the syntax of programming languages. Grammars described by PEGs are recognized by recursive descent parsers, which are obtained by combining parser combinators. By embedding combinators based on PEGs in some language, it becomes easy to construct parsers with semantic actions by having interoperability with the host language. Although it takes exponential time in the worst case to execute the parsers with backtracking in naive implementation, packrat parsers operate in linear time with respect to the input length by using memoization. In this presentation, we compare the runtime performance of four PEG-based parser combinators implemented in C++: Boost.Spirit.X3, cpp-peglib, PEGTL, and matcha2. Furthermore, we also report the implementation detail of matcha2, which runs fastest among them.},
 pages = {24--24},
 title = {解析表現文法に基づくC++のパーサコンビネータ実装の実行速度の比較},
 volume = {11},
 year = {2018}
}