程序设计语言编译原理(第三版)第4章.ppt

《程序设计语言编译原理(第三版)第4章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章　语法分析—自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL（1）分析法4.4递归下降分析程序构造4.5预测分析程序4.6LL（1）分析中的错误处理(略)§4.1语法分析器的功能1.任务：在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。2.语法分析器的地位：单词符号取下一单词符号语法分析树符号表词法分析器语法分析器编译程序后续部分源程序§4.1语法分析器的功能3.本质：按文法的产生式，识别输入符号串是否为一个句子。4.语法分析方法分类：自上而下分析法

2、自下而上分析法§4.2自上而下面临的问题一、基本思想：1.自上而下：从文法的开始符号出发，向下推导，推出句子2.主旨：对任何输入串，试图用一切可能的办法，从开始符号出发，自上而下地为输入串建立一棵语法树。§4.2自上而下面临的问题二、举例：自上而下方法的分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。§4.2自上而下面临的问题SSxAySxAy*例：文法SxAyA**

3、*输入串α:x*yxAy**§4.2自上而下面临的问题实现上述带回溯试探法的简单途径：让每个非终结符对应一个递归子

4、程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。§4.2自上而下面临的问题三、困难和缺点1.文法的左递归性问题使自上而下的分析过程陷入无限循环2.回溯问题;3.虚假匹配难以消除;4.当最终报告分析不成功时,难于知道输入串中出错的确切位置;5.采用了一种穷尽一切可能的试探法,效率很低,代价极高.§4.3LL(1)分析法一、左递归的消除：1.规则:（直接左递归消除）Pβ1p’

5、β2P’

6、…

7、

8、βnP’P’α1P’

9、α2P’

10、…

11、αmP’

12、ℇPβP’P’αP’

13、ℇPPα｜βPPα１

14、Pα２

15、…Pαｍ

16、β１

17、β２

18、…

19、βｎ§4.3LL(1)分析法例题：已经文法：ＥＥ+Ｔ｜ＴＴＴ＊Ｆ｜ＦＦ(Ｅ)｜ｉＥＴＥ’Ｅ’+ＴＥ’｜ℇＴＦＴ’Ｔ’*ＦＴ’｜ℇＦ(Ｅ)

20、ｉ§4.3LL(1)分析法２.消除间接左递归：（１）把文法Ｇ的所有ＶＮ按任一种顺序排列成P1,P2,…,Pn;按此顺序执行:（２）FORi=1TonDoBeginForj:=1Toi-1Do把形如PiPjγ的规则改写成Pi

21、δ1γ

22、δ2γ

23、…

24、δkγ其中Pjδ1

25、δ2

26、…

27、δk是关于Pj的所有规则；消除关于Pi规则的直接左递归性End§4.3LL(1)分析法例题:（间接左递归）已知文法G:SQc

28、cQRb

29、bRSa

30、a试消除其左递归?解答（３）化简由（２）所得的文法,即去除那些从开始符号出发永远无法到达的非终结符的产生规则.解答:令非终结符排序为R、Q、Si=1，无法执行fori=2，j=1QRb

31、bRSa

32、aQSab

33、ab

34、b§4.3LL(1)分析法G:SQc

35、cQRb

36、bRSa

37、ai=3，j=1无关系i

38、=3，j=2SQc

39、cQSab

40、ab

41、bSSabc

42、abc

43、bc

44、c消除S的直接左递归SabcS’

45、bcS’

46、cS’S’abcS’

47、ℇ返回SabcS’

48、bcS’

49、cS’S’abcS’

50、ℇ故SabcS’

51、bcS’

52、cS’S’abcS’

53、ℇQSab

54、ab

55、bRSa

56、a§4.3LL(1)分析法二、消除回溯,提取公共左因子§4.3LL(1)分析法１.消除回溯必须保证:对文法的任何非终结符,当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确

57、信无疑的。即：若此候选获得成功匹配，那么，这种匹配决不会是虚假的；若此候选无法完成匹配任务，则任何其它候选也肯定无法完成。例：Ａα１｜α２｜…｜αｎ设Ａ所面临的第一个输入符号为ａ，若Ａ能根据不同的输入符号指派相应的候选αｉ作为全权代表去执行任务，那就肯定无需回溯。在这里Ａ已不再是让某个候选去试探性地执行任务，而是根据所面临的输入符号ａ准确地指派唯一的一个候选。§4.3LL(1)分析法２.当不得回溯时，对文法有什么要求？∀非终结符Ａ的各个候选的首符集的交集均为空。分析：Ａαfirst(α)={a

58、α⇒a…,

59、a∈VT}若α⇒ℇ,则规定ℇ∈first(α)**§4.3LL(1)分析法此时，当要求A匹配输入串时，A根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务；这个候选就是那个终结首符集含a的α.即:first(α)是α的所有可能推导的开头终结符或可能的ℇ。3.提取公共左因子A.事实上，许多文法均存在这样的非终结符，其所有候选的终结首符集并非两两不相交。例如：语句if条件then语句el