文法 S -> a S a | aa は、a の偶数長の文字列をすべて生成します。この文法のバックトラックを備えた再帰降下パーサーを考案できます。最初に生成 S -> aa によって展開することを選択した場合、文字列 aa のみを認識します。したがって、合理的な再帰降下パーサーは、最初に S -> aSa を試行します。
この再帰降下パーサーが入力 aa、aaaa、および aaaaaaaa を認識するが、aaaaaa は認識しないことを示します。
文法 S -> a S a | aa は、a の偶数長の文字列をすべて生成します。この文法のバックトラックを備えた再帰降下パーサーを考案できます。最初に生成 S -> aa によって展開することを選択した場合、文字列 aa のみを認識します。したがって、合理的な再帰降下パーサーは、最初に S -> aSa を試行します。
この再帰降下パーサーが入力 aa、aaaa、および aaaaaaaa を認識するが、aaaaaa は認識しないことを示します。