编译原理课程总结——第4章

语法分析：是编译过程的核心部分。

它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。

.基本思想：

对任何一个输入串，试图用一切可能的办法，从文法的开始符号(根节点)出发，根据文法自上而下地为输入串建立一棵语法树，

即为输入串寻找一个最左推导。

思想本质：是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。

语法分析器的构造方法：

让每个非终结符号对应一个递归子程序。每个子程序可以作为一个布尔过程(返回“真”或“假”)：
(1)一旦发现该非终结符的某个候选式与输入串相匹配，就用这个候选式去扩展语法树，并返回“真”值；

(2)该候选式和输入串不匹配，则保持原来的语法树和IP值不变(IP回溯)，并返回“假”值。

自上而下分析面临的问题：

1.文法左递归：P =》Pα
当试图用P去匹配输入串时，在没有识别任何输入符号的情况下，又得重新要求P去进行新的匹配，这样一来，使推导无限循环下去。

2.回溯问题

匹配不成功，需要回溯。需要把已经做过的一大堆工作(各种表格工作、语义分析等)推倒重来

3.虚假匹配

4.不易知道错误位置

当最终报告分析不成功时，难于知道输入串中出错的确切位置

5.效率极低

由于带回溯，实际上才用了一种穷尽一切可能的试探法，因此，效率很低，代价极高。该方法只有理论意义，在实践上价值不大

分析中的错误处理：

1.消除直接左递归

设有产生式
P→Pα|β (1)
其中β不以P开头，α不为ε。那么，我们可以把P的规则改为如下的非直接左递归形式：
P→βP’
P’→αP’|ε (2)

(1)式和(2)式是等价的

P→Pα|β (1)

P→βP’
P’→αP’|ε (2)
对于(1)式：
P=>Pα=>Pαα=>…=>Pαα…α=>βαα…α
对于(2)式：
P=>βP’=>βαP’=>βααP’=>…=>βαα…αP’

=> βαα…α

2.消除回溯：

消除回溯的要求
对文法的任何非终结符，当要它去匹配输入串时，能够根据该非终结符所面临的输入符号准确地指派它的一个候选式去匹配，并且此候选式匹配后得到的工作结果应该是确信无疑的，即：

(1)若该候选式匹配成功，那么该匹配不是虚假匹配

(2)若该候选式无法完成最终的匹配任务，则其他任何候选式肯定也无法完成

3.改造文法

改造方法：提取公共左因子
假设A的产生式为
A→δβ1|δβ2|…|δβn|γ1| γ2|…|γm
其中每个γ不以δ开头
那么把这些产生式改写为:
A→δA’ |γ1| γ2|…|γm
A’→β1|β2|…|βn

反复提取左因子(包括对新引进的非终结符，例如A’)

递归下降分析程序构造：

当一个文法满足LL(1)条件时，我们就可以构造一个不带回溯的自上而下分析程序，
这个分析程序由一组（可能的）递归程序组成，
每个过程对应文法的一个非终结符。

这样一个分析程序称为递归下降分析器。

具体做法：
对文法的每一个非终结符都编一个分析程序

当根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时，就调用该非终结符的分析程序。

预测分析程序：

使用高级语言的递归过程描述递归下降分析器，只有当具有实现这种过程的编译系统时才有实际意义。

实现LL(1)分析的另一种有效方式是使用一张分析表和一个栈进行联合控制。我们现在介绍的预测分析程序就是属于这种类型的LL(1)分析器。

本章课后作业：

个人总结：第4章的语法分析感觉掌握的不好，还要多复习多做做题理解深入，凭课上那点时间感觉还不够。上课还是要注意力集中，尽量不走神。