Ordered ChoiceのかわりにCommitted Choiceを用いるGuarded PEGの提案

• Item type: Trans(1)
• 公開日: 2020-01-29
• タイトル: Ordered ChoiceのかわりにCommitted Choiceを用いるGuarded PEGの提案
• タイトル / 言語: en
• タイトル: Guarded PEG: Parsing Expreesion Grammar with Committed Choice in Place of Ordered Choice
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要，Unrefereed Presentation Abstract]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻
• 著者所属: 筑波大学システム情報系情報工学域
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Department of Information Engineering, Faculty of Engineering, Information and Systems, University of Tsukuba
• 著者名: 小坂, 俊介; 前田, 敦司
• 著者名(英): Shunsuke, Osaka; Atusi, Maeda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Fordが提唱した分析的形式文法であるParsing Expression Grammar（PEG）では，選択肢のある規則において解釈に優先順位を設けることで解釈の曖昧さを取り除いている．このPEGを用いた構文解析アルゴリズムの1つにpackrat parsingがある．Packrat parsingではバックトラックに備えて入力文字列やメモ化表をすべて保持しておく必要がため，LL(1)などの他のアルゴリズムよりメモリ空間が必要になるうえ，解析に時間がかかる．しかし，もし解析の途中でバックトラックの可能性がなくなった場合，そのときの解析位置から巻き戻す必要がなくなり，すでに解析した位置に関連付けられたメモ化表は削除することができる．本発表では，PEGの順序付き選択をより制限のある形に置き換えた記法であるGuarded PEG（G-PEG）を提案する．この制限の考え方はcommitted choice言語とcut演算子に基づく．G-PEGでは順序付き選択の代わりに選択のネストを制限する「ガード付き選択」を用いる．ガード付き選択は選択のネストを許さないガード式を持ち，それがマッチした選択肢を解析して他の選択肢を捨てる．これによりメモ化表を引くことなく，バックトラックの情報がたかだか1つで構文解析が可能となる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Parsing expression grammar (PEG) is an analytic grammar introduced by Ford. PEG eliminates ambiguity from grammars by ordered choices. Packrat parsing is a class of recursive-descent parsing algorithm with PEG. The feature of this algorithm is that it memoizes all intermediate results, and will backtrack when parsing fails. Therefore, this algorithm requires holding all input strings and memoization table for backtracking, so it uses more memory space and takes more time in comparison with other algorithms like LL(1). However, when there is no further alternative to backtrack, the parser can delete memoization table entries associated with previous input positions. In this presentation, we propose Guarded PEG (G-PEG), a notation that replaces PEG's ordered choice to more limited form. The idea of the limitation comes from committed choice language and cut operator. G-PEG has `guarded choice' instead of ordered choice. Guarded choice has guard expressions. If a guard expression matches, the parser will choose the corresponding alternative and discard the other alternatives. We further put a condition for guarded choices that their guard expression must be simple (that is, which does not contain guarded choice). This condition guarantees that backtracking never occurs while evaluating a guard expression. So maximum backtrack depth is at most 1, and after evaluating a guard expression, we can discard all backtrack information.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 13, 号 1, p. 22-22, 発行日 2020-01-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会