最適化Packrat Parserの空間計算量の計算手法の提案

概要

論文の詳細を見る
従来主流の構文解析手法である LL や LR 法の欠点を解決する構文手法の 1 つとして packrat parsing という構文解析手法が注目を集めている.packrat parsing は,parsing expression grammar(PEG) という形式文法で表現できる任意の言語を扱うことができ,これは LL 法や LR 法よりも強力である.また,packrat parsing では解析を線形時間で行うことができる.しかし,packrat parsing では,構文解析の中間結果をすべてメモ化するため,メモリ使用量が線形になってしまうという欠点がある.我々の研究では,カット演算子を PEG に導入し,プログラマがカットを適切に挿入することで,実用上,メモ化ために必要なメモリ使用量がほぼ一定である packrat parser を生成できるpackrat parser 生成系を提案した.しかし,文法定義に対してカットが必要十分なだけ挿入できているかを確認するのは簡単ではなく,文法定義を入念にチェックしたうえで,実際に構文解析を行ってメモリ使用量を測定する必要があった.本論文では,カットによって拡張された PEG による文法定義を静的に解析することで,その文法定義から生成される packrat parser が必要とするメモリ使用量を推計する手法を提案する.本論文の提案手法を適用することで,実際に構文解析を行うことなしに,カットが必要十分なだけ挿入されているかどうかのチェックを機械的に行うことができる.提案手法は,先行研究で提案した packrat parser 生成系を実用で使ううえで重要な問題点を解決するものである.また,提案手法は,PEG から生成された packrat parser の空間計算量に対するカットのインパクトを測る 1 つの尺度を与えているといえる.
2011-03-25

最適化Packrat Parserの空間計算量の計算手法の提案

スポンサーリンク

概要

著者

関連論文

スポンサーリンク