第4章        语法分析－自上而下的分析：
说明：这一次的更新，确实有点慢了，距上次已经有了20天的时间，这段时间主要因为sodme所在的公司在进行搬迁事宜，所以心境和环境都不太安定，让大家久候了，以后我尽量在一到两周左右的时间里把这个贴子更新完毕，今天是10月12日，请大家监督，这个贴子最晚截止更新时间是10月26日。

大家在参阅编译原理的这个重点归纳贴子时，可能会感觉与数据结构规纳贴子风格不太一致，在编译的总结里，我较多地讲解了书上的一些我认为是较难理解的内容，而不仅仅是给出考点。因为从我接触的网友反映的情况看来，大家对编译还是比较头疼的，所以，我希望通过这样的规纳同时帮助大家从另外一个角度或以另外一种思维来看待编译原理课程。

当词法分析器对源程序进行了词法分析，获得了一个个独立的单词符号后，编译程序总控模块就会调用语法分析子程序对这些单词符号集进行语法分析，也就是：利用该文法的产生式来判断这些单词符号是否足以构成一个在语法上正确的程序。如果可以构成一个在语法上正确的程序，则接着作编译下面的工作，比如：语法制导翻译，中间代码生成、代码优化等工作；而如果不能构成一个在语法上正确的程序，则给出相应的错误提示并将错误信息记入对应的数据记录中。

语法分析的规则主要基于两种：自上而下分析和自下而上分析。这一章，主要讲解自上而下的分析方法。自上而下分析的大致思路是：根据产生式规则，从产生式的开始符号进行推导，一直推导到可以产生当前要判断的这个句子为止。如果推导了所有可能情况，但没有推出这样的句子，那么这个句子就是不符合该语言的语法规则的（产生式即定义了语言的语法规则）。

在陈火旺老师的编译教材上，详细描述了一种自上而下的分析方法：LL(1)分析法，陈老教材的这一章也是围绕这一点而展开的。下面，我们介绍一下本章的主要常考知识点及考查角度：
1.给定一文法，要求将其改造成可以进行自上而下分析的形式。这里面涉及到两方面的知识点：左递归的去除及公因子的提取。所谓的左递归是指产生式是形如：P->Pab...的形式，即：产生式右边的第一个字符就是该产生式左边的那个非终结符。当一个文法中有左递归的产生式时，是无法进行自上而下推导的，因为只要这个产生式被推导，就势必会使这种推导过程陷入一种递归循环无休止推导的情形。去除左递归的方法是比较简单的，其基本思路是将左递归通过转化变成与之等价的右递归。即将形如：P->Pa|b 形式的左递归变成如下形式：P->bP',P'->aP'|e(注：e表示空)。这一点只要多作练习，很快就会掌握。提取公因子的目的是为了避免推导过程中的回溯，也就是使每一次的向下推导是唯一的，而不是有多个选择，因为有多个选择的话就可能出现回溯。
2.给定一文法，要求判断其是否为LL(1)文法。判断一个文法是否为LL(1)文法主要有两种方法：一种是判断文法是否二义，如果二义，则文法必定不为LL(1)（注意：此命题的否合命题不真）；二是根据陈老教材P73页：关于LL(1)文法成立的三个条件。显然，第一种判断方法效率是比较高的，但是，其只能判断文法“不为”LL(1)的，并不能判定文法“是”LL(1)的，要判断文法“是”LL(1)的，就得用第二种方法，但在考题中，如果要求你判断某文法是否为LL(1)的，则该文法多半不是LL(1)的，而且此点可以很容易地用二义性来证明，这是一种常考形式。
3.给定一文法，要求构造LL(1)分析表。LL(1)分析的重点和难点内容都在其分析表的构造上，后面要讲的LR分析也是，它的难点也在于其分析表的构造。构造LL(1)分析表是一个常考点，也是大分值题的可能出题点，对于普通学校而言，相比于LR分析，他们更喜欢考LL(1)，因为LR要比LL(1)复杂得多，而名校则更喜欢考LR，当然，这只是针对于较普遍的情况作的总结，并不是一定成立的推论。LL(1)分析表构造前，需要先弄清FIRST集和FOLLOW集的构造方法，简单地说，FIRST集是用于求非终结符推出的产生式中的第一个终结符的，而FOLLOW集是用于求与该非终结符后紧邻的那个终结符的。FIRST集的构造方法见教材P78页，在构造的三个规则中，前两个规则都是比较容易理解的，第三个规则看上去就有点复杂了，我们简单地来看第三条规则，就是：当由X推出的产生式中前面若干个非终结符，其FIRST集均含有空时，就取这若干个非结符的后一个字符的FIRST集，当然，这“后一个字符”可能是终结符，也可能是非终结符，只要其FIRST集不为空就行；而当X推出的右边全是非终结符，且这些非终结符的FIRST集全含有空时，就把空加到FIRST(X)中。FOLLOW集的构造方法很简单，不作详细讲解了。LL(1)分析表的构造方法见教材P79页，构造规则主要有3条。说到这里，大家应该明确分析表中的各个单元到底代表什么含义，我作一下简单的介绍：分析表中的最顶一行，是产生式中所有的终结符；分析表中的最左一列，是产生式中所有的非终结符；而产生式中间的诸多单元格则可以存放该文法的产生式或特殊标志(比如成功和错误标志)。这样的二维表格构成的单元格的含义是：当左边的非终结符遇到最上一行中的某个终结符时应该选择哪个产生式进行向下的推导，这个产生式就是放在对应二维坐标处的产生式。
4.给定一文法，先要求求解其LL(1)分析表，然后要求给出针对于某一个句子的具体分析过程。这个考点的第二问主要就是考查考生对预测分析程序的工作过程的理解了，预测分析程序完全是按照分析表机械工作的，针对于考生而言，要明确何时出栈，何时入栈，以及如何入栈，这些细节信息都是要通过作题掌握的，只理解而不会熟练解答是没有用的。
5.给定一文法，要求给出其递归下降分析程序。递归下降分析的条件也是无左递归及不带回溯，其构造的过程比较简单，就是将每个非终结符处理成可以互相递归调用的过程体。详细过程参照P74到P75的例子，你可以试着写一下P76页教材上未列出的F过程的实现。

下一次，我们会详细讲解LR分析，敬请期待。如果网友对讲解有什么意见或建议，也欢迎跟贴指出，谢谢大家。

后续内容：
第5章        语法分析－自下而上的分析：
第6章        属性文法和语法制导翻译：
第7章        语义分析和中间代码生成：
第8章        符号表：
第9章        运行时存储空间组织：
第10章        优化：
第11章        目标代码生成：
第12章        并行编译基础：