Packrat Parsingのメモリ効率の改善手法

概要

論文の詳細を見る
Packrat parsingは,バックトラック付き再帰下降構文解析にメモ化を組み合わせた構文解析法であり,parsing expression grammar(以下PEG)で記述できる広範囲の文法を入力サイズの線形時間で解析することができるという特徴を持っている.しかし,packrat parsihgには,メモ化を行うために入力サイズに比例する記憶領域を要するという欠点がある.本論文では,カット演算子をPEGに加えることにより,不要な記憶領域を削除する機能を持つpackratパーザ生成系を提案する.カットはPrologから借用した概念であり,構文規則中でカットより後ろでバックトラックが不要な場合にそのことを処理系に指示し,不必要なバックトラックが起こらないようにするための機能である.カットの評価によって,ある入力位置より前にバックトラックしないということが判明した場合,その入力位置より前にバックトラックしたときのために使用されているメモ化領域を動的に削除し,再利用することができる.我々は,構文規則中にカットを適切に挿入することで,多くの実用的文法について有界なメモリ量で解析できるパーザを生成可能と考えている.一方,カットによるメモリ効率の改善は,パーザ生成系のユーザが手動でカットを挿入しなければならないという問題点があるが,本論文ではこの問題点を解決するために,解析する言語の構文の意味を変えない範囲でカットを自動的に挿入する手法と,不要なメモ化が行われている箇所を検出して必要な記憶領域を静的に削減するための手法についても提案する.
2008-01-15

Packrat Parsingのメモリ効率の改善手法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク