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

スポンサーリンク

概要

論文の詳細を見る
構文解析法で Packrat Parsing という手法がある.Packrat Parsing は,バックトラックや無限先読みを用いた解析において,線型時間で解析可能である.また,Packrat Parsing は再帰下降構文解析法の一種であるため,左再帰を含む文法を解析できない.そこで従来は,左再帰を含む文法の解析を要求される際,左再帰部分を同一の入力を解析可能な右再帰へと変換し,左再帰を除去して解析を行う.だが,特定の左再帰は除去できないため,この手法で解析できない文法がある.Alessandro らは,Packrat Parsing において,左再帰を含む文法を,右再帰への文法の変換なしに解析可能にした.しかし,Alessandro らの実装では,同一の入力位置で左再帰が複数発生する文法において,特定の入力の解析に失敗するという問題点がある.そこで本論文では,左再帰が複数発生する文法において,解析できる手法を提案・実装し,評価を行った.
2011-03-25

著者

関連論文

スポンサーリンク