@article{oai:ipsj.ixsq.nii.ac.jp:00238216,
 author = {菅井, 雅文 and 前田, 敦司 and Masafumi, Sugai and Atusi, Maeda},
 issue = {4},
 journal = {情報処理学会論文誌プログラミング（PRO）},
 month = {Aug},
 note = {形式言語の記述方法の1種であるParsing Expression Grammar（PEG）に基づく構文解析アルゴリズムは，無制限の先読みが可能であり，文脈自由言語の範囲を超える言語も解析できる能力を持っている．一方，解析の巻き戻し（バックトラック）が行われた場合，最悪計算時間が指数オーダーになるという問題がある．これに対して優先度付き選択の代替表現としてガート付き選択を用いたCommitted-Choice PEG（CC-PEG）が提案されている．この手法では選択の際にガード式の解析結果を用いて選択肢を決定することでバックトラックを抑制しスタックに積む情報を削減することで，解析時間を線形に抑える．本発表ではこのCC-PEGと構文解析器の実装方法である仮想マシン方式を組み合わせたパーザジェネレータを実装し，CC-PEGの意味論に特化した命令セットを導入することで新たな仮想マシンアーキテクチャを構築し効率の良いパーザの生成手法を提案する．また，パーザの出力時には仮想マシンレベルでの覗き穴最適化を適用する．, Parsing algorithms based on Parsing Expression Grammar (PEG), a method of writing formal languages, allow unlimited lookahead and have the ability to parse languages beyond the scope of context-free languages. On the other hand, the worst-case computation time is of exponential order when the parsing is rewound (backtracked). In response to this problem, Committed-Choice PEG (CC-PEG) using a guarded choice has been proposed as an alternative to ordered choice. This method suppresses backtracking and reduces information on the stack by using the parsing results of guard expressions to determine the choice, thereby keeping the parsing time linear. In this presentation, we implement a parser generator that combines CC-PEG and the virtual machine method, a parser implementation method, and propose an efficient parser generation method by constructing a new virtual machine architecture by introducing a set of instructions specialized for CC-PEG's semantics. We also apply peephole optimization at the virtual machine level to the output of the parser.},
 pages = {21--21},
 title = {仮想マシン方式のCC-PEGパーサの実装と最適化},
 volume = {17},
 year = {2024}
}