更新検知を用いて左再帰に対応するPackrat Parserの実装

概要

論文の詳細を見る
構文解析法で Packrat Parsing という手法がある.Packrat Parsing は,再帰下降構文解析にメモ化を組み合わせた手法であり,バックトラックや無限先読みを用いた解析において,線形時間で解析可能である.しかし,左再帰を含む文法は解析不可能である.そこで,従来は左再帰を含む文法を解析する際,左再帰部分を等価な右再帰に変換し,解析を行っていた.だが文法の変換を行うと構文木の構造が変化してしまう.また,特定の左再帰は変換できない.たとえば,閉路が存在する文法である.よって,この手法では解析できない文法がある.Warth らは,左再帰を含む文法を,右再帰への変換なしに解析を可能にした.しかし,Warth らの手法では,同一の入力位置で左再帰が複数発生する文法において,特定の入力の解析に失敗する.また,構文木の構造が意図したものとは異なるという問題がある.そこで本研究では,更新検知を用いて,左再帰を含む文法を右再帰への変換なしに解析でき,かつ従来手法の 2 つの問題点に対応する Packrat Parser を提案・実装し,評価を行った.
2011-06-29