著者

後藤 勇太 木山 真人 芦原 評

雑誌

夏のプログラミング・シンポジウム2011報告集

巻号頁・発行日

pp.49-55, 2012-01-06

---

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

著者

後藤 勇太 白田 佳章 木山 真人 芦原 評

出版者

情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.4, no.3, pp.84-93, 2011-06-29

---

構文解析法で Packrat Parsing という手法がある.Packrat Parsing は,再帰下降構文解析にメモ化を組み合わせた手法であり,バックトラックや無限先読みを用いた解析において,線形時間で解析可能である.しかし,左再帰を含む文法は解析不可能である.そこで,従来は左再帰を含む文法を解析する際,左再帰部分を等価な右再帰に変換し,解析を行っていた.だが文法の変換を行うと構文木の構造が変化してしまう.また,特定の左再帰は変換できない.たとえば,閉路が存在する文法である.よって,この手法では解析できない文法がある.Warth らは,左再帰を含む文法を,右再帰への変換なしに解析を可能にした.しかし,Warth らの手法では,同一の入力位置で左再帰が複数発生する文法において,特定の入力の解析に失敗する.また,構文木の構造が意図したものとは異なるという問題がある.そこで本研究では,更新検知を用いて,左再帰を含む文法を右再帰への変換なしに解析でき,かつ従来手法の 2 つの問題点に対応する 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. 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. Furthermore, syntax tree is be unintended consequence when the method parses particular grammars. This paper presents imprementation and evaluation of Packrat Parser with Update Detection that possible to support left recursive grammars without transforming, and grammars that have multiple left recursions at an input position.