左再帰に対応するPackrat Parserの実装

情報処理学会

書誌事項

タイトル別名
  • Implementation of Packrat Parser to Parse Left Recursive Grammars

説明

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

Packrat Parsing is a kind of parsing method. Packrat Parsing is a combination of Recursive Descent Parsing and memoization that can parse backtracking and unlimited look-ahead in linear parse time. However, Packrat Parsing cannot parse left recursive grammars. Thus, traditional method transforms left recursive grammars into right recursive grammars. Unfortunately, syntax tree is changed by the transforming. Moreover, particular left recursive grammars cannot be transformed. Traditional method cannot parse particular grammars. Alessandro Warth et al made possible to support left recursive grammars without transforming in Packrat Parsing. However, the method cannot parse some grammars that have multiple left recursions at an input position. This paper presents imprementation and evaluation of Packrat Parser that possible to support left recursive grammars without transforming, and grammars that have multiple left recursions at an input position.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ