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

情報処理学会 Web Site

書誌事項

タイトル別名
  • コウシン ケンチ オ モチイテ ヒダリ サイキ ニ タイオウ スル Packrat Parser ノ ジッソウ
  • Implementation of Packrat Parser with Update Detection to Parse Left Recursive Grammars

この論文をさがす

抄録

構文解析法で 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.

収録刊行物

キーワード

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

問題の指摘

ページトップへ