简述
我们在上一章中学习了自顶向下解析技术解析输入，并从根节点开始构建解析树，逐渐向下移动到叶节点。自顶向下解析的类型如下所示：
递归下降解析
递归下降是一种自顶向下的解析技术，从顶部构造解析树，从左到右读取输入。它为每个终端和非终端实体使用程序。这种解析技术递归地解析输入以生成解析树，这可能需要也可能不需要回溯。但是与之相关的语法（如果不考虑左因素）无法避免回溯。一种不需要任何回溯的递归下降解析形式称为predictive parsing.
这种解析技术被认为是递归的，因为它使用本质上是递归的上下文无关语法。
回溯
自上而下的解析器从根节点（开始符号）开始，并将输入字符串与生产规则匹配以替换它们（如果匹配）。要理解这一点，请看下面的 CFG 示例：
S → rXd | rZd
X → oa | ea
Z → ai
对于输入字符串： read 是一个自上而下的解析器，其行为如下：
它将从生产规则中的 S 开始，并将其产量与输入的最左边的字母相匹配，即“r”。S (S → rXd) 的产生与它相匹配。所以自上而下的解析器前进到下一个输入字母（即'e'）。解析器尝试扩展非终结符“X”并从左侧检查其产生式 (X → oa)。它与下一个输入符号不匹配。因此自上而下的解析器回溯以获得X的下一个产生规则，(X → ea)。
现在解析器以有序的方式匹配所有输入字母。字符串被接受。
预测解析器
预测解析器是一种递归下降解析器，它能够预测将使用哪个产生式来替换输入字符串。预测解析器不受回溯的影响。
为了完成它的任务，预测解析器使用一个前瞻指针，它指向下一个输入符号。为了使解析器无需回溯，预测解析器对文法施加了一些约束，并且只接受称为 LL(k) 文法的一类文法。
预测解析使用堆栈和解析表来解析输入并生成解析树。堆栈和输入都包含一个结束符号$表示堆栈为空，输入已被消耗。解析器参考解析表来对输入和堆栈元素组合做出任何决定。
在递归下降解析中，对于单个输入实例，解析器可能有多个产生式可供选择，而在预测解析器中，每个步骤最多有一个产生式可供选择。可能存在没有匹配输入字符串的产品的情况，从而导致解析过程失败。
LL解析器
LL Parser 接受 LL 语法。LL文法是上下文无关文法的一个子集，但在获取简化版时有一些限制，以实现简单的实现。LL 语法可以通过两种算法来实现，即递归下降或表驱动。
LL 解析器表示为 LL(k)。LL(k) 中的第一个 L 是从左到右解析输入，LL(k) 中的第二个 L 代表最左推导，k 本身代表前瞻的数量。一般k = 1，所以LL(k)也可以写成LL(1)。
LL解析算法
我们可能会坚持使用确定性 LL(1) 来解释解析器，因为表的大小随着 k 的值呈指数增长。其次，如果给定的文法不是 LL(1)，那么对于任何给定的 k，它通常都不是 LL(k)。
下面给出的是 LL(1) 解析的算法：
Input:
string ω
parsing table M for grammar G
Output:
If ω is in L(G) then left-most derivation of ω,
error otherwise.
Initial State : $S on stack (with S being start symbol)
ω$ in the input buffer
SET ip to point the first symbol of ω$.
repeat
let X be the top stack symbol and a the symbol pointed by ip.
if X∈ Vt or $
if X = a
POP X and advance ip.
else
error()
endif
else /* X is non-terminal */
if M[X,a] = X → Y1, Y2,... Yk
POP X
PUSH Yk, Yk-1,... Y1 /* Y1 on top */
Output the production X → Y1, Y2,... Yk
else
error()
endif
endif
until X = $ /* empty stack */
如果 A → α | 则文法 G 是 LL(1) β 是 G 的两种不同产生式：
