自顶向下语法分析
自顶向下语法分析可以被看做是为输入串构造语法分析树的问题，它从语法分析树的根节点开始，按照先根次序（深度优先地）创建棵语法分析树的各个节点。
自顶向下语法分析也可以被看作寻找输入串的最左推导的过程。
- 在每一步推导中，都需要做两个选择：
- 替换当前句型中的哪个非终结符。
- 用该非终结符的哪个候选式进行替换。
最左推导和最右推导
在最左推导（Left-most Derivation）中，总是选择每个句型的最左非终结符进行替换。最右规约是最左推导的逆过程。
在最右推导（Right-most Derivation）中，总是选择每个句型的最右非终结符进行替换。最左规约是最右推导的逆过程，也称为规范规约。因为在自底向上分析中，总是采用最左规约的方式。
最左推导和最右推导是唯一的。由于分析器是自左向右的扫描输入，所以自顶向下语法分析采用最左推导方式。
- 总是选择每个句型的最左非终结符进行替换。
- 根据输入流中的下一个终结符，选择最左非终结符的一个候选式。
递归向下的语法分析 和 预测分析法
递归下降分析方法(recursive-descent parsing)是一种自顶向下语法分析方法。它使用一组递归过程来处理输入，每个非终结符号对应一个过程，如果这个过程的过程体扫描了整个输入串，它就停止执行并宣布语法分析成功完成。
通用的递归向下分析技术可能需要回溯。也就是说，它可能需要重复扫描输入。然而，在对程序设计语言的构造进行语法分析时很少需要回溯，因此需要回溯的语法分析器并不常见。即使在自然语言分析这样的场合，回溯也不是很高效，因此人们更加倾向于基于表格的方法。
需要回溯的分析器称为不确定的分析器。如果在分析过程中能预测出正确的产生式，就不需要回溯，这种分析称为预测分析。
- 预测分析法
递归下降分析方法的一种简单形式称为预测分析法(predictive parsing)。通过在输入中向前看固定个数(通常是1)符号来选择正确的产生式。
可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k)文法类。
预测分析不需要回溯，它是一种确定的自顶向下分析方法。
在预测分析法中，各个非终结符号对应的过程中的控制流可以由向前看符号无二义地确定。
一个预测分析器程序由各个非终结符对应的过程组成。对应于非终结符A的过程完成以下两项任务：
- 检查向前看符号，决定使用A的哪个产生式。如果一个产生式的体为α（非空）且向前看符号在
FIRST(α)中，那么就选择这个产生式。对于任何向前看符号，如果两个非空产生式体之间存在冲突，我们就不能使用对这种文法使用预测语法分析。 - 然后，这个过程就模拟被选中的产生式的体。也就是说，从左边开始逐个“执行”此产生式体中的符号。“执行”一个非终结符号的方法是调用该非终结符号对应的过程。一个与向前看符号匹配的终结符号的“执行”方法则是读入下一个输入符号。如果在某个点上不匹配就会报语法错误。
- 回溯问题
同一非终结符的多个候选式存在共同前缀，将导致回溯现象。
- 左递归问题
含有A→Aa形式产生式的文法称为立即左递归的文法。
两步或以上推导出的左递归称为非立即左递归。
一个左递归的文法会使它的递归下降语法分析器进入一个无限循环，即使是带回溯的语法分析器也是如此。
左递归的消除过程就是转换为右递归的过程。
消除左递归是有代价的-引入了一些非终结符和ε产生式。
- 什么时候使用ε产生式
如果当前某非终结符A与当前输入符a不匹配时，若存在A->ε，可以通过检查a是否可以出现在A的后面，来决定是否使用ε产生式。
- 非终结符的后继符号集（FOLLOW）
可能在某个句型中紧跟在A后面的终结符号a的集合，记为FOLLOW(A)。
如果A是某个句型的最右符号，则将结束符
$添加到FOLLOW(A)中。
- 产生式的可选集（SELECT）
产生式A-β的可选集是指可以选用该产生式进行推导时对应的输入符号集合，记为SELECT(a→β)。
SELECT(A->aβ) = { a }
SELECT(A->ε) = FOLLOW(A)
- 串首终结符集（FIRST）
给定一个文法符号串α，α的串首终结符集FIRST(α)被定义为可以从α推导出的所有串首终结符构成的集合。如果α可以推导出ε(α=>*ε)，那么ε也在也在FIRST集中。
（END）