Packrat

PEG内PEGを使ってPackrat Parserを生成できるようにした。
Packrat Parserとは要するにメモ化付きのPEG実装だ。PEGでは非終端記号と入力列の位置だけから結果が求まる。つまりメモ化すれば(非終端記号の種類)×（入力列の長さ)程度の時間で解析が終わる。
ただし、私のPEGは実行中に文法が変わる可能性がある。当然、文法が一部でも変わればメモが使えなくなる。今のところは文法が変わった瞬間に全部のメモを捨てるという実装になっている。もちろん、他の可能性として

• 影響のある部分だけメモを捨てる。
• 辞書を複数用意しておき必要に応じて切り替える。
• 影響のある部分ごとに辞書を用意して組み合わせて使う。

などが考えられるが、その辺りの細かい部分は後回しにしようと思う。