決定性オートマトンのネットワークを用いるCC-PEG構文解析手法

• Item type: Trans(1)
• 公開日: 2022-07-04
• タイトル: 決定性オートマトンのネットワークを用いるCC-PEG構文解析手法
• タイトル / 言語: en
• タイトル: CC-PEGs Based Parsing Method Using Deterministic Automata Networks
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要, Unrefereed Presentatin Abstract]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 筑波大学
• 著者所属: 筑波大学
• 著者所属(英): en
• 著者所属(英): University of Tsukuba
• 著者所属(英): en
• 著者所属(英): University of Tsukuba
• 著者名: 森田, 大樹; 前田, 敦司
• 著者名(英): Hiroki, Morita; Atusi, Maeda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Parsing expression grammar（PEG）に基づく構文解析はpackrat parsingにより入力長の線形時間で行えるが，多くのPEG文法ではpackrat parsingが単にオーバヘッドとなることが指摘されている．またPEGに基づく解析ではバックトラックにより入力が先頭まで巻き戻りうるため，入力文字列の全体を保持し続ける必要がある．これらに対処するPEGの方言としてcommitted-choice PEG（CC-PEG）が提案されている．CC-PEGの選択はガード式を持ち，これは正規表現と等価なLinear PEGで記述されるため，CC-PEGに基づく解析ではバックトラックの発生はガード式の解析後に限定される．本発表では，CC-PEG文法をオートマトンのネットワークに変換することで高速かつ省メモリな構文解析を実現する手法を提案する．選択のガード式を解析すべき選択肢を決定する先読みDFAに変換することでオートマトンは決定性となり，単純なアルゴリズムで解析を行うことが可能となる．またガード式の解析後にはバックトラックが発生しないため，入力をストリームとして扱うことで入力全体を保持せずに解析を進めることが可能である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Parsing expression grammars (PEGs) based packrat parsers can parse any input in linear-time of the input length. However, some papers have pointed out that packrat parsing is simply an overhead for most grammars except pathological cases. Moreover, since backtrackings may rewind input to the beginning, PEG-based parsers need to hold the whole input string. Committed-choice PEGs (CC-PEGs), a dialect of PEGs, were proposed to deal with these problems. CC-PEGs' choice operators have guard expressions written in Linear PEGs, which is equivalent to regular expressions. In CC-PEGs based parsing, backtrackings only occur after parsing guard expressions. In this presentation, we propose a fast and heap-saving parsing method by translating CC-PEGs into automata networks. Translating guard expressions into lookahead DFAs which select an alternative to parse, we can make whole automata deterministic. In addition, since backtrackings never occur after parsing guard expressions, we can handle input as a stream. Thus, the proposing parsing algorithm becomes simple and need not hold the whole input.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 15, 号 3, p. 1-1, 発行日 2022-07-04
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会