| Item type |
Trans(1) |
| 公開日 |
2018-09-20 |
| タイトル |
|
|
タイトル |
解析表現文法に基づくC++のパーサコンビネータ実装の実行速度の比較 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Comparison among the Runtime Performance of PEG-based Parser Combinator Implementations Written in C++ |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[発表概要] |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
芝浦工業大学大学院理工学研究科 |
| 著者所属 |
|
|
|
芝浦工業大学大学院理工学研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Engineering and Science, Shibaura Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Engineering and Science, Shibaura Institute of Technology |
| 著者名 |
今泉, 良紀
篠埜, 功
|
| 著者名(英) |
Yoshiki, Imaizumi
Isao, Sasano
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
PEG（Parsing Expression Grammar，解析表現文法）は文法規則に曖昧さのない形式文法であり，プログラミング言語の構文記述に有用である．PEGによる文法は再帰下降構文解析器と対応しているため，パーサコンビネータによる簡易な実装によってPEGの文法から実際に動作するパーサが得られる．特にEDSL（Embedded Domain Specific Language）によるパーサコンビネータ実装は，パーサの記述のし易さを確保しつつ，意味規則の記述などの点でホスト言語との接続が簡潔であるという利点がある．また，バックトラックのある再帰下降構文解析器は素朴な実装では入力長に対して最悪指数関数時間を要するが，再帰下降構文解析にメモ化を組み合わせたパックラット構文解析という手法によって入力長に対して線形時間で解析が可能となる．本発表では，C++で記述されたPEGに基づくパーサコンビネータ実装として，Boost.Spirit.X3，cpp-peglib，PEGTL，matcha2の4つの実装の実行性能について比較した結果と，これらの中で最も実行速度の速いmatcha2の実装の詳細について報告する． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11464814 |
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO）
巻 11,
号 3,
p. 24-24,
発行日 2018-09-20
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7802 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-TPRO1103005.pdf (98.4 kB)
