Q: 研究自顶向下的分析方法的作用是什么？#

作用是通过预先让计算机了解语法规则(文法)，当用户给一串输入(源程序)时，能够分析出语法含义以及判断是否符合要求。通过自顶向下的分析方法，可以根据文法规则，将文法开始符号S，一步一步推导出输入的词串w

Q: 从文法开始符号S开始，采用什么样的过程，最后得到输入的词串w？#

在含有非终结符的开头开始，到最后得到确定的句子，不外乎就确定两件事：1.每次选择替换哪个非终结符 2.选择非终结符的哪个候选式替换。这时候我们可以有多种选择，比如，面对多个非终结符，总选择最左边的那个非终结符进行替换，这个就是最左推导。

Q: 计算机如何完成从S推导到最后词串的过程？#

现在有一组文法规则，有一个词串，如果运用程序能够能够应用文法规则扫描完整个词串，那么计算完成了语法分析的任务。可以这样进行语法分析，让开始指针，指向词串第一个符号，推导从开始符号S开始，如果当前遇到的是非终结符，那么就调用对应非终结符的处理程序，如果当前遇到的是和词串指的符号是一样的，说明匹配成功，箭头往后移动一位，如果当前是终结符，还和词串指向的符号不一样，说明发生了错误，就这样可以完成推导的过程。可以看出，这其中有递归结构，并且，有时有好几个相同终结符打头的候选式，可能一开始选择的候选式并不是正确答案，这需要程序回溯然后再次尝试。所以看来，直接这样做递归下降分析往往不是最优解。

Q: 如何在遍历过程中，选择候选式时不需要回溯呢？#

为了不让遍历的过程中出现回溯，也就是不让遍历时选择了错误的候选式，可以通过看输入中固定个数个符号来确定使用哪个产生式，一般我们是通过看输入中的前一位来确定选用什么产生式，当选择了正确的产生式，也就不会出现回溯了。

具体的，根据看输入前一位来确定选用什么产生式，可以转化为：构建一个预测分析表，表的纵轴是所有可能出现的非终结符，横轴表示所有可能出现的符号。这样，如果能够得到一个确定的表，就可以根据当前出现的非终结符和遍历到的字符来从表中选择合适的产生式，也就是查表来看当前应该选用哪个产生式。

但是，不是你随便定义一个文法，就能得到符合要求的预测分析表，比如你定义的文法让表中的格子填入的内容不止一个。所以文法也要进行约束，比如我们规定的LL(1)文法，就支持构建预测分析表。于是乎，有时我们要先判断给定的文法是不是LL(1)文法，如果不是，那么得不到预测分析表就没办法做接下来的工作了。如果给定的文法不是LL(1)文法，我们可以想着怎么转化为LL(1)文法。

于是，为了让分析过程中不出现回溯，我们需要：1.给的文法需要满足一些规范(比如LL(1))，2.建立预测分析表 3.根据表的内容进行递归下降过程。这样，过程中就不会出现任何回溯的步骤，也就达到了要求。

以上的过程中，为了分析语法任务，我们选择了递归下降分析法；为了让递归下降过程不出现回溯，我们根据向前看k个符号来确定使用哪个产生式。能够通过向前看k个符号来确定产生式而不需要回溯要求了文法需要满足LL(1)规范，那么：LL(1)规范的内容是什么？为什么LL(1)规范能够完成这个任务？LL(1)规范是怎么一步步得到的？

LL(1) 文法#

为了让选择候选式的时候是唯一选择的，很容易想到这样的文法可以达到要求：

1. 每个产生式的右部以终结符开始
2. 同一个非终结符的各个候选式的首终结符都不同

这样的文法称之为S_文法。

但它的问题在于不能出现空产生式。因为当非终结符能够推出来空时，不能确定这个非终结符后边能不能跟接下来的符号。

如何能解决这个问题呢？那么只需要能够知道非终结符后面都能跟什么终结符，就可以了。也就是说，通过提前计算非终结符后面能跟什么终结符，来处理空产生式的情况。于是乎，这里的非终结符后面能跟什么终结符，被定义为了非终结符的FOLLOW集¹。

非终结符的FOLLOW集，是给定一个非终结符，有一个FOLLOW集。而为了知道某个产生式在遇到哪个输入符号才可以使用，引入了产生式的可选集，称之为产生式的SELECT集，表示只有出现了这些输入符号，才选择这个产生式。

于是乎，现在可以来尝试解决出现空产生式的问题了。对于相同的非终结符推导的产生式，如果它们的SELECT集不相交，那么就可以得到预测分析表。 (因为产生式的SELECT集表示只有出现了这些符号，才选择这个产生式。如果SELECT集不相交，意味着给了一个符号，都可以确定性的选择一个产生式)。这个便到达了q_ 文法：1.每个产生式的右部为空，或者终结符开头 2.相同的左部有不相交的可选集

但是这里q_文法还有不足的地方，便是，产生式的右部的开头要不是空，要不是终结符，不能是非终结符。这样就引入了LL(1)！

为了得到预测分析表，需要保证同一非终结符的各个产生式的可选集互不相交。当产生式的右部的开头会出现非终结符时，就要保证右部开头的非终结符推出来的所有可能的终结符是不能相交的，这里”右部开头的非终结符推出来的所有可能的终结符”被称之为这个非终结符的 First集，即同一非终结符的各个产生式的 First 集互不相交²，就满足了条件。现在需要考虑推导出空的情况，因为空会引来FOLLOW集，所以很显然：A -> α|β时，α β至多只能让一个推导出ε，因为如果两个都推导出ε，那么他们的First集就都会有A的FOLLOW集，这样他们的FIRST集就会相交了。在出现只有一个能推导出ε的情况时，也要保证另一个的FIRST集的元素不要和FOLLOW(A)重叠，要不然也会出现相交的情况，就不满足”同一非终结符的各个产生式的可选集互不相交”的条件了。