编译原理第四章自上而下语法分析总结
知识点：
什么是语法分析，语法分析就是在词法分析识别出单词符号的基础上，分析并判断程序的语法结构是否符合语法规范。语法分析的方法有两种类型的方法，自上而下推导和自下而上规约，本章主要讲的是自上而下的推到方法。那语法分析是如何判断输入串是否符合语法规则呢，对于自上而下分析而言，从文法的起始符出发进行对句子进行推导，从而进行语法规则的验证，最终产生一个颗正确的语法树。
自上而下分析的基本思想，将输入的一个字符串从文法的根节点开始，根据文法自上而下的为输入串建立一颗语法树，即为输入串寻找一个左推导。其本质思想是一个探索过程，是反复使用不同产生式谋求匹配输入串的过程。
具体方法为为每一个非终结符号对应一个递归子程序，每个子程序根据判断返回真或假。但这种方法存在许多问题，如：
- 文法左递归问题：如果P=>Pa，则在没有识别任何输入符号的情况下，又得重新要求P去重新进行新的匹配，这样就造成了无限循环。
- 回溯成本问题:匹配不成功，则需要回溯，既费时又费力。
- 虚假匹配问题：设有文法(1) S → xAy；(2) A →* | **；分析输入串x**y。若判断A->*,再对下一个*进行匹配时，由于没有了A，则只能推出y。
- 不易知出错位置：当最终报告分析不成功是，难以知道输入串中出错的确切位置。
- 效率低：因为以上问题，所以得出效率低。
未解决以上问题，则使用LL(1)分析法，可称为不带回溯的自上而下分析法，即要消除文法的左递归，并找出客服回溯的充分必要条件。
- 消除左递归：
例： 设有产生式
P→Pα|β （1）
其中β不以P开头，α不为ε。那么，我们可以把P的规则改为如下的非直接左递归形式：
P→βP’
P’→αP’|ε （2）
对于(1)式：P=>Pα=>Pαα=>…=>Pαα…α=>βαα…α
对于(2)式：P=>βP’=>βαP’=>βααP’=>…=>βαα…αP’=> βαα…α
由此可见，消除左递归后的效果与使用左递归的效果相同。
间接左递归：
例：考虑文法：
S->Qc|c
Q ->Rb|b
R ->Sa|a
把R带入到Q中有关的候选式： Q -> Sab|ab|b
现在Q同样不含直接左递归，把它带入S的有关候选式：S ->Sabc|abc|bc|c
2. 消除回溯：
之所以会出现回溯，是因为在分析对非终结符号进行递归时，若将错误的终结符被判断成正确，则会接着该错误的结果继续进行下去，如果对该非终结符号所有的候选式进行判断，以此来得到精准的匹配结果。未完成此任务，我们定义first集
同时将文法改造，提取出相同的左公因子。使得候选首符集两两不相交，但如果空字ε属于某个非终结符的候选式的首符集，就会有问题。
定义follow集：
LL(1)文法的使用条件：
(1)文法不含左递归
(2)对于文法中每一个非终结符A的各个产生式的候选式的FIRST集两两不相交。即，若A→α1|α2|…|αn
则 FIRST(αi)∩FIRST(αj)=Φ (i≠j)
(3)对于文法中的每个非终结符A，若它的某个候选首符集包含ε,则
FIRST(A)∩FOLLOW(A)=Φ
如果一个文法G满足以上条件，则称该文法G为LL(1)文法(第1个L代表从左到右扫描输入串，第2个L代表最左推导，1表示分析时每一步只看1个符号)
LL(1)文法的使用方法：
对于LL(1)文法，假设要用非终结符A进行匹配，面临输入符号为a，A的所有产生式为 A→α1|α2|…|αn
(1)若a ∈ FIRST(αi) ，则指派αi去匹配(2)若a不属于任何一个候选首符集，则：
①若ε属于某个 FIRST(αi)且a∈FOLLOW(A)，则让A与ε自动匹配；
②否则，a的出现是一种语法错误
3.预测分析程序：使用分析表和栈对文法进行分析。
习题：
感想：
从这一刻起，我们学会了在编译程序中如何判断语句是否符合语法规范。这一章的重点在于最后的如何构造first集合和follow集合以及如何得到最后的预测分析表。简单来说，first（x）集合是x产生式中第一个终结符，若x产生式中某候选式第一个字符是非终结符号，则将该非终结符号的first集合去掉空集后加入x的候选式中。follow集合，若该符号是开始符号，则加入#，若该符号X中产生式的某一候选式中的最后一个符号是终结符，则将该终结符的first集加入X的follow集合中，若最后一个符号是非终结符号，这将该非终结符号的follow集合加入X的follow集合中去。分析表由文法的所有产生式构造的。