著者

水島 宏太 前田 敦司 山口 喜教

出版者

一般社団法人情報処理学会

雑誌

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

巻号頁・発行日

vol.49, no.1, pp.117-126, 2008-01-15

---

Packrat parsingは,バックトラック付き再帰下降構文解析にメモ化を組み合わせた構文解析法であり,parsing expression grammar(以下PEG)で記述できる広範囲の文法を入力サイズの線形時間で解析することができるという特徴を持っている.しかし,packrat parsingには,メモ化を行うために入力サイズに比例する記憶領域を要するという欠点がある.本論文では,カット演算子をPEGに加えることにより,不要な記憶領域を削除する機能を持つpackratパーザ生成系を提案する.カットはPrologから借用した概念であり,構文規則中でカットより後ろでバックトラックが不要な場合にそのことを処理系に指示し,不必要なバックトラックが起こらないようにするための機能である.カットの評価によって,ある入力位置より前にバックトラックしないということが判明した場合,その入力位置より前にバックトラックしたときのために使用されているメモ化領域を動的に削除し,再利用することができる.我々は,構文規則中にカットを適切に挿入することで,多くの実用的文法について有界なメモリ量で解析できるパーザを生成可能と考えている.一方,カットによるメモリ効率の改善は,パーザ生成系のユーザが手動でカットを挿入しなければならないという問題点があるが,本論文ではこの問題点を解決するために,解析する言語の構文の意味を変えない範囲でカットを自動的に挿入する手法と,不要なメモ化が行われている箇所を検出して必要な記憶領域を静的に削減するための手法についても提案する.Packrat parsing is a parsing technique that combines memoization with backtracking recursive descent parser. It can handle any grammars that can be expressed in powerful grammar notation called parsing expression grammar (PEG). Generated parsers can analyze its input in linear time. However, to memoize intermediate result, packrat parsing requires storage area proportional to the input size. In this paper, we propose the packrat parser generator system that disposes unnecessary storage area by adding the notion of a cut operator to PEG. Cut operators is the notion we borrowed from Prolog that can be used by programmers to 'cut off' an alternative execution branch of a choice point in a syntax rule when the alternative should not be tried for suppressing unnecessary backtracking. When an alternative is removed by execution of a cut operator (and thus the parser can make sure that no backtracking can occur before a particular input positon), the memoization storage kept against backtracking can be deallocated and reclaimed dynamically. We believe that, for most pratical grammars,parsers which only use bounded memory size can be generated by appropriate insertion of cut operators in syntax rules. Although memory efficiency that can be achieved by hand-insertion of cut operators would be valuable, it is awesome and error-prone. In this paper, we also propose a technique to reduce required storage area by statically detecting syntax rules which memoization is unnecessary and another technique for automatically inserting cut operators without changing meanings of syntax rules.