メモ化
この文法が生成する文字列は、xac、xbc、xbd(なお、x は1つ以上の x の連続となりうる)のいずれかである。次にこの文法から構文解析の仕様をトップダウンでかつ左から右に解析するものとしたとき、文字列 xxxxxbd の解析がどうなるかを考える。
トップダウンであるから、まず全体が S に置換可能であるとの前提で、S の規則から、まず全体が (A c) であると仮定する。最後の文字がここで既に違っていることは明らかだが、左から右に構文解析するので、構文解析器にはまだ最後の文字が見えていない。次に A の生成規則を見て、さらに X の生成規則を見ていく。ここで初めて先頭の文字が一致する。そして、x が続いている間は X の規則を再帰的に適用し、次の文字 b も A の規則に一致するが、その次の d と c が一致しない。ここでバックトラックが発生し、S のもう一方の選択肢である B の規則を適用し、同様に X を必要な回数適用して、最終的に最後の文字まで一致する。以上によりこの文字列は、この文法で認識される。
ここで重要となるのは、以上の説明の中で X の繰り返し適用が2回出現することである。このように処理を進めていって失敗し、元に戻って別の選択肢に移って処理を再開することをバックトラッキングと呼ぶ。
ピーター・ノーヴィグは1991年、構文解析戦略にメモ化を応用し、単純なバックトラッキング式の再帰下降構文解析に自動メモ化を適用することでアーリー法のようなアルゴリズムになることを示した。1995年には Johnson と Dörre も構文解析でのメモ化の応用を提案した。2002年、Ford はこれのパックラット構文解析への応用をかなり詳細に論じた。
ノーヴィグは構文解析器をメモ化によって強化したが、時間計算量はアーリー法と同じであった。つまりこれは、速度的性能の最適化以外にメモ化を応用した例である。Johnson と Dörre も同様に時間短縮以外の応用を示した。それは、言語的制約の解決を必要な情報が構文解析によって十分集まった時点にまで遅延されることにメモ化を利用するものだった。一方、Ford は時間的性能の最適化にメモ化を応用し、パックラット構文解析が最悪ケースのバックトラッキングが必要な形式言語でも線形時間で構文解析できることを示した。
次のような形式文法を考えてみよう。
ここで、生成規則 S → (A c) | (B d) の意味は、「S は、A の後に1つの c が続くか、あるいは B の後に1つの d が続くかのどちらかである」となる。また、生成規則 X → x [X] の意味は、「X は、1つの x の後にオプションの X が続く」となる。