メモ化
そして、構文解析におけるバックトラッキングにメモ化を応用する余地があることがわかる。ここで、関数 RuleAcceptsSomeInput(Rule, Position, Input) を考える。引数の意味は次の通りである。
Rule は、検討中の生成規則の名前
Position は、現在検討中の入力上のオフセット位置
Input は、検討中の入力
関数 RuleAcceptsSomeInput のリターン値は Rule が受理した入力の長さとする。その生成規則が指定されたオフセット位置の入力文字を受理しなかった場合は 0 を返す。バックトラッキングとメモ化を使う場合、構文解析は次のようになる。
オフセット 0 で、生成規則 A から生成規則 X へと下降していき、そこでその位置と生成規則 X について長さ 5 をメモ化(記録)する。d の位置で生成規則の適用に失敗すると、生成規則 B が選ばれ、再び X を適用するのではなく、メモ化エンジンに対して位置 0 と生成規則 X についての記録があるかを訊ねる。メモ化エンジンは長さ 5 が記録されているのでそれを返す。これにより実際に X を適用することなく処理を省略でき、前回と同じぶんだけ X を適用したのと同じ効果を得る。
この例では、X は再帰的に何度でも適用可能であるため、xxxxxxxxxxxxxxxxbd のような文字列もありうる。