2 0 0 0 OA 解析表現文法に基づくC++のパーサコンビネータ実装の実行速度の比較
- 著者
- 今泉 良紀 篠埜 功
- 雑誌
- 情報処理学会論文誌プログラミング(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の実装の詳細について報告する.
1 0 0 0 OA マクロ処理の実装に適したパックラットパーサーコンビネータの設計と実装
- 著者
- 今泉 良紀 篠埜 功
- 雑誌
- 情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)
- 巻号頁・発行日
- vol.10, no.6, pp.1, 2017-12-12
パックラット構文解析ではLALR(1)よりも強力な形式文法であるParsing Expression Grammar(以下PEG)によって構文解析を行う.PEGによる文法規則には曖昧さがなく,プログラミング言語の構文の記述やその処理系の作成に際し非常に有用である.既存のPEGベースの構文解析器では直接文字列を入力として受け付けるが,字句解析と構文解析を分けたい場合にそのままでは使用に適さない.たとえば,字句ベースのマクロ処理系であるCプリプロセッサを実装する際,マクロ展開後のコードに再度マクロ展開の処理が行われうる.その結果,マクロ展開の過程で同じレクシムに対して字句解析を複数回実行する場合がある.これを避けるためにPEGベースの構文解析器を使用しないとすると,字句解析や構文解析用にPEG以外の形式文法を学んだりその処理系を導入したりする必要がある.そこで文字列だけでなく字句列などを入力できるパックラットパーサーコンビネータをC++で実装し,本発表では実装の詳細について報告する.この実装を用いて生成した構文解析器はchar型だけでなく任意の型を返す前方反復子(Forward Iterator)を入力として受け付ける.結果はtuple・variant・optional・expectedなどを組み合わせたデータ構造として得られ,意味規則によって自由に変換することが可能である.