メモ化
従って S を始点として X まで下降して再帰的に生成規則の適用を繰り返すが、バックトラックして B に移行した後は RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd) のリターン値が 16 であることが分かっている(メモ化済みである)ので、実際に X を適用する必要がない。
統語的述語(syntactic predicate)を使った構文解析器でも、述語の構文解析結果をメモ化できる。例えば次のような構文規則があるとする。
これは、入力の先頭で A で受理できるなら A で受理することを表している。述語部分 (A)? の結果をメモ化しておけば、実際の生成規則適用時は省略できる。
構文解析時に構文木を構築する場合、メモ化ではマッチした入力の長さだけでなく、その位置と生成規則によって生成された部分木も記憶しておく必要がある。同様に、生成規則がマッチしたときに外部のコードを呼び出す方式の構文解析器の場合、その呼び出し順序が本来期待されている順序になるよう注意してメモ化する必要がある。
全ての文法でバックトラッキングや統語的述語が必要となるわけではないので、個々の生成規則について結果を記憶しておくことで構文解析の性能が低下する可能性がある。これは、メモ化する生成規則を明示的に選択することで問題を限定することができる。