同一入力位置で複数発生する左再帰へ対応したPackrat Parsingの設計と実装

• Item type: Trans(1)
• 公開日: 2011-03-25
• タイトル: 同一入力位置で複数発生する左再帰へ対応したPackrat Parsingの設計と実装
• タイトル / 言語: en
• タイトル: Design and Implementation of Packrat Parsing to Parse Grammars That Have Multiple Left Recursions at an Input Position
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 熊本大学大学院自然科学研究科
• 著者所属: 熊本大学大学院自然科学研究科
• 著者所属: 熊本大学大学院自然科学研究科
• 著者所属(英): en
• 著者所属(英): Kumamoto Graduate School of Science and Technology, Kumamoto University
• 著者所属(英): en
• 著者所属(英): Kumamoto Graduate School of Science and Technology, Kumamoto University
• 著者所属(英): en
• 著者所属(英): Kumamoto Graduate School of Science and Technology, Kumamoto University
• 著者名: 白田, 佳章; 木山, 真人; 芦原, 評
• 著者名(英): Yoshiaki, Shirata; Masato, Kiyama; Hyo, Ashihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 構文解析法で Packrat Parsing という手法がある．Packrat Parsing は，バックトラックや無限先読みを用いた解析において，線型時間で解析可能である．また，Packrat Parsing は再帰下降構文解析法の一種であるため，左再帰を含む文法を解析できない．そこで従来は，左再帰を含む文法の解析を要求される際，左再帰部分を同一の入力を解析可能な右再帰へと変換し，左再帰を除去して解析を行う．だが，特定の左再帰は除去できないため，この手法で解析できない文法がある．Alessandro らは，Packrat Parsing において，左再帰を含む文法を，右再帰への文法の変換なしに解析可能にした．しかし，Alessandro らの実装では，同一の入力位置で左再帰が複数発生する文法において，特定の入力の解析に失敗するという問題点がある．そこで本論文では，左再帰が複数発生する文法において，解析できる手法を提案・実装し，評価を行った．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: There is Packrat Parsing among parsing methods. Packrat Parsing can parse backtracking and unlimited look-ahead in linear parse time. And Packrat Parsing is Recursive Descent Parsing. So, Packrat Parsing can't parse left recursive rules. Traditionally, we must remove left recursions by converting to right recursions to parse same inputs as original recursion when parse left recursive rules. There are grammars that can't be parsed with this method because some left recursions can't be converted to right recursions. Alessandro et al made possible to support left recursive rules without converting in Packrat Parsing. But the method can't parse some grammars that have multiple left recursions at an input position. This paper presents method to parse grammars that have multiple left recursions and implementation and evaluation of this method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 4, 号 2, p. 104-115, 発行日 2011-03-25
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会