编译原理-第4章+语法分析

《编译原理-第4章+语法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析§4.1引言§4.2自顶向下语法分析§4.3自底向上语法分析§4.4语法分析程序的自动生成1§4.1引言一、语法分析任务1.语法检查2.根据语法符号进行一定处理加工二、语法分析方法1.自顶向下语法分析方法2.自底向上语法分析方法2一、语法分析任务词法分析阶段，主要介绍了单词符号的结构、识别（用状态转换图），描述（通过正规式）以及有限自动机DFA和NFA。在一个编译程序对某个源程序完成了词法工作以后,就进入了语法分析阶段。由词法分析程序所产生的单词符号流，作为语法分析程序的输入串，按文法规则分析检查是否构成了合法的句子。首先来了解一下语法分析的任务。31.语法检查根据语法

2、规则对各种语法成分进行分析，确定它们的语法关系以检查语法上的正确和错误，并指出错误的性质和出错位置。如：ifBthenS1elseS2若写成ifBthenelseS2就错了（then后少一个S1）42.根据语法符号进行一定语义处理加工如语法分析过程得到一个合法的句子时，往往同时进行必要的语义分析等如：当遇到处理表达式a+b*c时，若该表达式语法关系正确，就可以进行语义处理加工，可将该表达式变成中间语言，以便以后生成目标程序5二、语法分析方法语法分析方法很多，但能够产生计算机程序并能得到广泛应用的主要有两大类，按照生成语法树的顺序，分别称为自顶向下和自底向上分析方法。61.自顶向下语法

3、分析方法（1）递归下降分析法（2）LL（1）分析法72.自底向上语法分析方法（1）简单优先分析法（2）算符优先分析法（3）LR分析法8§4.2自顶向下语法分析一、消除左递归二、消除回溯三、递归下降分析法四、LL(1)分析法9一、消除左递归（1）问题的提出在自顶向下分析过程中，假定现在轮到要用非终结符U去匹配输入串，而在文法中第一条规则是U∷＝U…这样会产生什么问题呢？10若文法具有间接左递归，即有U＋U…那么，也会发生上述问题。11例如：已知文法G[S]S∷＝ABA∷＝bB

4、Aa(存在直接左递归）B∷＝Sb

5、a现分析符号串baabaab是否是文法G的句子。其分析过程如下：12（2）

6、消除左递归方法1）用重复表示法（扩充的ＢＮＦ表示法）改写语法规则假定一个文法中有关于非终结符的规则为Ａ∷＝Ａα｜β其中α非空，β不以Ａ开头，则等价地改写为Ａ∷＝β｛α｝13例如，下述直接左递归规则：Ｅ∷＝Ｅ＋Ｔ｜Ｔ可改写为Ｅ∷＝Ｔ｛＋Ｔ｝EET＋ET＋ET＋T等价ET+T+T+TT+T+T+T14同样，规则Ｔ∷＝Ｔ*Ｆ｜Ｔ／Ｆ｜Ｆ等价于Ｔ∷＝Ｔ（*Ｆ｜／Ｆ）｜Ｆ可改写为Ｔ∷＝Ｆ｛*Ｆ｜／Ｆ｝这样，改写后的文法消除了直接左递归。可以证明，改写前后的文法是等价的。152）改写方法规则消除直接左递归还可用另一种方法来改写形如文法规则Ａ∷＝Ａα｜β的直接左递归。对Ａ引入一个新的非终结符Ａ′，

7、将Ａ∷＝Ａα｜β等价写成Ａ∷＝βＡ′Ａ′∷＝αＡ′｜ε由于β不以Ａ开头，α不以Ａ′开头，因此改写后两条规则不是直接左递归。同样可以证明这种形式和原来形式是等价的。16AAαβAαAαβααα等价AβA’αA’αA’αA’εβααα17就一般而言，关于Ａ的规则具有下面形式：Ａ∷＝Ａα１｜Ａα２｜…｜Ａαn｜β１｜β２｜…｜βn这时可改写成如下形式：Ａ∷＝A(α１｜α２｜…｜αn｜)｜β１｜β２｜…｜βn由消除直接左递归方法，得Ａ∷＝(β１｜β２｜…｜βn)Ａ′Ａ′∷＝(α１｜α２｜…｜αn)Ａ′｜ε18例如：A∷＝Ac

8、Aad

9、bd

10、e等价于A∷＝A（c

11、ad）

12、bd

13、e，所以可以改写

14、成：A∷＝（bd

15、e）A’A’∷＝（c

16、ad）A’

17、ε19例如：有文法Ｅ∷＝Ｅ＋Ｔ｜Ｔ，Ｔ∷＝T*Ｆ｜Ｆ，Ｆ∷＝（Ｅ）｜i用上述方法可改写成：Ｅ∷＝ＴＥ′，Ｅ′∷＝＋ＴＥ′｜εＴ∷＝ＦＴ′，Ｔ′∷＝*ＦＴ′｜ε，Ｆ∷＝（Ｅ）｜i20上述两种方法可消除任意直接左递归，但不能消除间接左递归例如，有文法Ｇ［Ｓ］Ｓ∷＝Ｑc｜cＱ∷＝Ｒb｜bＲ∷＝Ｓa｜a该文法无直接左递归，但有间接左递归，例如有ＳＱcＲbcＳabc即Ｓ＋Ｓabc213）消除间接左递归对于间接左递归先将间接左递归变成直接左递归，然后再消除直接左递归例如；A∷＝aB

18、Bb(1)B∷＝Ac

19、d(2)先将（1）代入（2）中，

20、得B∷＝Bbc

21、aBc

22、d(3)由此将(3)改写为；B∷＝（aBc

23、d)B’B’∷＝bcB’

24、加入文法开始符号的产生式得消除左递归后的等价文法为：A∷＝aB

25、BbB∷＝(aBc

26、d)B’B’∷＝bcB’

27、224)消除文法递归的一般算法要求：文法不含形如Ａ＋Ａ的推导，也不存在Ａ∷＝ε这样规则，算法思想如下：①将文法Ｇ的所有非终结符整理成某种顺序Ｕ１，Ｕ２，…Ｕn②从U1开始消除U1规则的直接左递归③用左部为U1的所有规则右部替换左部为U2，右部以U1开