Packrat Parsing という構文解析手法の入力になる parsing expression grammer (PEG) に新しい演算子を追加して解析時のメモリ効率を良くしてみました、という論文。Packrat Parsing は、バックトラックにメモ化を組み合わせることで時間効率を良くしているが、メモ化のためにメモリ効率は良くない。そこで、バックトラックしなくてもよくなるポイントを PEG 上に示すためにカット演算子というの導入して、メモ化のための記憶領域を節約する。どうやって意味を変えないように効果的にカット演算子を挿入できるかが課題。

author="水島 宏太 and 前田 敦司 and 山口 喜教",
title="{Packrat Parsing のメモリ効率の改善手法}",
journal="情報処理学会論文誌 プログラミング",
volumn="49",
number="SIG 1",
pages="117--126",
year="2008"

コメント追加

投稿者 kw : 2009/03/27 21:52:00 JST #