Packrat Parserのメモ化領域の自動調整手法
スポンサーリンク
概要
- 論文の詳細を見る
現在一般的に使われている構文解析手法では,解析時間を線形時間に保つため,バックトラックを行わない.しかし,バックトラックを行わない解析手法では,先読みできる記号数が限られ,解析できる文法に制限ができてしまう.バックトラックを行い,parsing expression grammarで表現できる広範囲な構文規則を解析する手法としてpackrat parsingという手法がある.この手法では,解析対象文字列のすべての位置において1度解析した結果を保存するメモ化という手法を用いて,同じ解析を繰り返し行わないことで,単純なバックトラックでは最悪の場合に指数時間が必要だった解析時間を線形時間に抑えている.本発表では,この手法の問題点である,解析対象文字列のサイズに比例してメモ化領域が肥大化する点を改善することを目標としている.本発表での提案手法として,効果的にメモからエントリを削除するための手法と,メモ領域のサイズと解析効率のトレードオフを軽減するための手法の2点がある.まず,前者として直近にメモを行った付近で頻繁にバックトラックが発生することを前提とし,時間的局所性を用いて最近最も用いていないエントリをメモから削除する手法や,バックトラックを行う際に入力対象の細かい部分から広い部分に解析が進むことを考慮し,最も古いエントリをメモから削除する手法を提案する.また,後者の手法として,メモのヒット率が悪くなってきた場合に,動的にメモ領域の大きさを変化させ解析効率を維持する手法を提案する.以上の3つの手法を組み合わせ,解析効率をなるべく維持した状態でメモ領域を削減を行う.
- 2013-08-29