自顶向下的语法分析器中最典型的就是LL(k)语法分析器，采用的是从左到右扫描输入（因此需要避免左递归）产生最左推导，其中k表示向前看多少个符号位。
文法表示规则，语法分析器将这种规则具象化了，但是这两者并非等价，文法可以描述的语言在语法分析器中不一定可以被识别出来，如下就是一个有趣的案例可供分析。（这有助于我们理解编译器的工作原理）
———————————————————————————————————————————
龙书练习4.4.5：
文法S->aSa|aa生成了所有由a组成的长度为偶数的串。我们可以为这个文法设计一个带回溯的递归下降分析器。如果我们首先选择先用产生式S->aa展开，那么我们只能识别到串aa。因此，任何合理的递归下降分析器将首先尝试S->aSa。
1）说明这个递归分析器识别输入aa、aaaa、aaaaaaaa，但识别不了aaaaaa。
———————————————————————————————————————————
这一个很有趣的题目，但在处理题目之前，我们首先需要知道编译器在面对输入时应该是如何处理的。语法分析器理应生成栈（这在计算机中是普遍使用的数据结构），将输入串和开始符号压入栈中，并用标识指针指明当前的栈顶。从这里可以看出，编译器只清楚指针指向的输入符号，对输入流后面的符号完全不清楚，甚至有多少输入的符号也是不清楚的，它能做的事情仅仅只是根据下一个输入符号，根据预测分析表然后进行规则推导。现在我们设计一个简单的递归下降分析器的代码：
def match_a(input): return input.read(1) == 'a' def match_end(input): return input.read(1) == ' ' def match_S(input): backtracking = inp.tell() if match_a(input) and match_S(input) and match_a(input): return true input.seek(backtracking) if match_a(input) and match_a(input): return true return false def match(input): return match_s(input) and match_end(input)
具体实现内容可以参考网站：https://cs.stackexchange.com/questions/143480/dragon-book-exercise-4-4-5-why-is-aaaaaa-not-recognized-by-the-recursive-descen
上面是具体内容实现者，这里为了更简单的说明问题所以就不再讲那些技术上的实现。直接上分析过程。
stack input_stream process S$ aaaaaa$ 0 aSa$ aaaaaa$ Sa$ aaaaa$ 1 aSaa$ aaaaaa$ Saa$ aaaa$ 2 aSaaa$ aaaa$ Saaa$ aaa$ 3 aSaaaa$ aaa$ Saaaa$ aa$ 4 aSaaaaa$ aa$ Saaaaa$ a$ 5 aSaaaaaa$ a$ Saaaaaa$ $ 6 aSaaaaaaa$ $ aaaaaaaaaa$ $ frist time go to fail,then try another method,strat backtracking 5 Saaaaa$ a$ aaaaaaa$ a$ aaaaaa$ $ 4 Saaaa$ aa$ aaaaaa$ aa$ aaaaa$ a$ aaaa$ $ match's->aa' at 4 aaaa$ $ 3 Saaa$ aaa$ aaaaa$ aaa$ ... aaa$ a$ match's->aa' at 3 aa$ $ match's->aSa' at 2 aa$ $ match'a' at 6 but fail,so pass's->asa' at 2,turn to 1 this time is the important,now try 's->asa' at 1 but input_stream is empty,so 's->asa' at 1 is fail,then pass's->asa' at 2. /* The expected results 2 Saa$ aaaa$ aaaa$ aaaa$ .... aa$ aa$ match'a' at 4,match 's->asa' at 1 a$ a$ match'a' at 5,match 's->asa' at 0 $ $ try'$' at 6,match 's->s$' at 0 */ 1 Sa$ aaaaa$ aaa$ aaaaa$ ... a$ aaa$ match's->aa' at 1 $ aa$ match's->asa' at 0 $ aa$ try'$' at 4,but the input_stream is not empty,so fail fail S->S$ at 0,so 'a'*6 is fail
通过程序可知，一定是先调用S->aSa，并且不是推导到aaSaa，而是（aaaaaa）Saaaaaa，具体原因前面已经说过。当第七次规则推导时，输入已经空了，于是编译器开始回溯到上一步，这里有一个关键一定要理解，第七次调用S->aSa时失败，这就表明第六次调用S->aSa失败，并且开始尝试使用S->aa匹配输入，如若这个也失败那么就继续回溯。于是我们会来到一个关键的结点部位。即标号为3的时间段，并且将S展开为aa进行匹配，前面两个a都匹配成功说明S->aa匹配成功，第三个a匹配成功说明这个阶段的前一个阶段S->aSa（即第三次）匹配成功。而问题就在这里出现了，由于编译器无法传达匹配失败的信息给上一个匹配阶段（根据程序信息只能从上往下传递），告诉他尝试别的方法，因此在继续匹配输入时，输入为空，因此第二次S->aSa失败了，识别器拒绝解析，直接导致S->aSa第一次失败,这就跳过了我们梦寐以求的标号为2的阶段，并尝试S->aa，于是接下来无论如何调整组合都无法完成匹配了，只能失败。上面可以看出只有解析器在正确的栈深位置时进行回溯第二次S->aSa生成时才会成功，因此这种成功定然时一种连续的，有规则的，可以归纳整合为一个论点，这里也可以看出这个并非上下文无关文法。
