3A.3.2 自顶向下 - 递归下降

递归下降解析（Recursive-Descent Parsing）为文法中每个非终结符号定义一个解析程序，整个解析过程就是递归调用各个非终结符号解析程序的过程，其程序结构与文法结构是同构的。

我们来看一个递归下降的详细例子。考虑文法：

S -> cAd A -> ab A -> a

假设有输入 w=cad ，递归下降的解析过程为：

下列步骤中符号 | 代表当前位置

1. 解析树符号串当前位置：｜S

输入流当前位置：｜cad

当前处在解析树的根节点，对应的开始符号 S 只有一个产生式，所以我们选择将其展开后得到解析树为：

Fig. Step 1

对应的符号串为 cAd, 下一个字符为 c, 与输入流中下一个字符相匹配，所以我们将两边都前进一个符号。

2. 解析树符号串当前位置：c|Ad

输入流当前位置：c|ad

文法中符号 A 对应的产生式有两个，我们先选择 A -> ab 来尝试，得到解析树为：

Fig. Step 2

对应的符号串为 cabd, 下一个符号为 a, 与输入流中下一个字符匹配，于是我们将两边都前进一个符号

3. 解析树符号串当前位置：ca|bd

输入流当前位置：ca|d

解析树中下一个符号是终结符号 b，直接将其与输入符号相对比，而输入流中下一个符号是 d, 不相匹配。这说明我们之前所选择的产生式是不正确的，需要回溯到对应的位置重新选择。于是我们将两边都回到第 2 步中的起始位置

4. 解析树符号串当前位置：c|Ad

输入流当前位置：c|ad

这次选择产生式 A -> a, 得到解析树：

Fig. Step 4

对应的符号串为 cad, 下一个符号为 a, 与输入流中下一个字符匹配，于是我们将两边都前进一个符号

5. 解析树符号串当前位置：ca|d

输入流当前位置：ca|d

解析树下一个符号是终结符号 d, 与输入流中下一个符号一致。将两边都前进一个符号后都到达了符号串的末尾，所以解析结束，第 4 步中的解析树即为最终结果

通过整个例子我们发现递归下降的解析方式可能需要回溯，因为当遇到有多个产生式的非终结符号时，我们的算法并没有提供合适的策略来明确应该选择哪一个，所以只有挨个尝试进行穷举。

递归下降算法还有个缺点是文法中不能包含左递归，通过上面例子我们很容易发现如果某个符号的产生式包含左递归的话，则会导致算法进入死循环。