WEKO3
アイテム
仮想マシン方式のCC-PEGパーサの実装と最適化
https://ipsj.ixsq.nii.ac.jp/records/238216
https://ipsj.ixsq.nii.ac.jp/records/238216b422fac9-428e-406a-93da-990211267307
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TPRO1704004.pdf (122.2 kB)
2026年8月19日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥0, IPSJ:学会員：¥0, PRO:会員：¥0, DLIB:会員：¥0 | ||
| Item type | Trans(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-08-19 | |||||||||
| タイトル | ||||||||||
| タイトル | 仮想マシン方式のCC-PEGパーサの実装と最適化 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Implementation and Optimization of CC-PEG Parser with Virtual Machine Method | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | [発表概要, Unrefereed Presentatin Abstract] | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| 著者所属 | ||||||||||
| 筑波大学理工情報生命学術院システム情報工学研究群情報理工学位プログラム | ||||||||||
| 著者所属 | ||||||||||
| 筑波大学理工情報生命学術院システム情報工学研究群情報理工学位プログラム | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Master's Program in Computer Science, Degree Programs in Systems and Information Engineering, Graduate School of Science and Technology, Tsukuba University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Master's Program in Computer Science, Degree Programs in Systems and Information Engineering, Graduate School of Science and Technology, Tsukuba University | ||||||||||
| 著者名 |
菅井, 雅文
× 菅井, 雅文
× 前田, 敦司
|
|||||||||
| 著者名(英) |
Masafumi, Sugai
× Masafumi, Sugai
× Atusi, Maeda
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 形式言語の記述方法の1種であるParsing Expression Grammar（PEG）に基づく構文解析アルゴリズムは，無制限の先読みが可能であり，文脈自由言語の範囲を超える言語も解析できる能力を持っている．一方，解析の巻き戻し（バックトラック）が行われた場合，最悪計算時間が指数オーダーになるという問題がある．これに対して優先度付き選択の代替表現としてガート付き選択を用いたCommitted-Choice PEG（CC-PEG）が提案されている．この手法では選択の際にガード式の解析結果を用いて選択肢を決定することでバックトラックを抑制しスタックに積む情報を削減することで，解析時間を線形に抑える．本発表ではこのCC-PEGと構文解析器の実装方法である仮想マシン方式を組み合わせたパーザジェネレータを実装し，CC-PEGの意味論に特化した命令セットを導入することで新たな仮想マシンアーキテクチャを構築し効率の良いパーザの生成手法を提案する．また，パーザの出力時には仮想マシンレベルでの覗き穴最適化を適用する． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 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. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA11464814 | |||||||||
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO） 巻 17, 号 4, p. 21-21, 発行日 2024-08-19 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 1882-7802 | |||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
