编译原理课件chap04(陈火旺)

《编译原理课件chap04(陈火旺)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章语法分析--自上而下分析第四章语法分析——自上而下分析高级语言的语法结构适合用上下无关文法描述，因此，我们将上下文无关文法作为语法分析的基础。本章和下一章，我们将介绍编译程序构造中的一些典型的语法分析方法4.1语法分析器功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。下图表明了语法分析器在编译程序中的地位。第四章语法分析--自上而下分析源程序词法分析单词符号取下一单词语法分析词法分析树编译后续符号表语法分析器在编译程序中地位第四章语法分析--自上而下分析语法分析是编译程序的核心部分：在词法分析的

2、基础上，识别单词符号序列是否是给定文法的正确句子（程序）。常用方法自顶向下分析自底向上分析确定不确定算符优先分析LR分析第四章语法分析--自上而下分析自顶向下语法分析方法自顶向下分析法就是从文法的开始符号出发，试图推导出与输入的单词串完全匹配的句子。如果能够推导出，则该输入串是给定文法的句子；如果不能推导出，则该输入串不是给定文法的句子。第四章语法分析--自上而下分析例：已知符号串S=cad文法G[Z]:Z→cAdA→ab

3、a求解SL(G[Z])分析过程是设法建立一棵语法树,使语法树的末端结点与给定符号串相匹配.1.开始:令Z为根结点Z2.用Z的右部,符号串去匹配输入串·

4、ZcAd完成一步推导ZcAd检查c-c匹配A是非终结符,将匹配任务交给A第四章语法分析--自上而下分析663.选用A的右部符号串匹配输入串A有两个右部,选第一个·cAdabZ完成进一步推导Aab检查,a-a匹配,b-d不匹配(失败)但是还不能冒然宣布SL(G[Z])4.回溯即砍掉A的子树改选A的第二右部·ZcAdaAa检查a-a匹配d-d匹配建立语法树,末端结点为cad与输入cad相匹配,建立了推导序列EcAdcad∴cadL(G(E))S=cadG[Z]:Z→cAdA→ab

5、a分析工作要部分地或全部地退回去重做叫回溯第四章语法分析--自上而下分析自顶向下语法

6、分析要解决的关键问题假定要被代换的最左非终结符号是B，且有n条规则：B→A1

7、A2

8、…

9、An，那么如何确定用哪个右部去替代B？第四章语法分析--自上而下分析1.分析过程是带有预测的，对输入符号串要预测属于什么语法成分，然后根据该语法成分的文法建立语法树。2.分析过程是一种试探过程，是尽一切办法(选用不同规则)设法建立语法树的过程，由于是试探过程，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。第四章语法分析--自上而下分析自顶向下分析存在的问题及解决方法自顶向下分析方法的基本缺点：不能处理具有左递归性的文法自顶向下分析为什么不能处理左递

10、归文法？文法G，存在U∈Vn，ifU==>U…,则G为左递归文法+1．左递归文法：左递归文法回溯问题第四章语法分析--自上而下分析1010如果我们在匹配输入串过程中，假定正好轮到要用非终结符U直接匹配输入串，即要用U的右部符号串U¨¨去匹配，为了用U¨¨去匹配，又得用U去匹配，这样无限的循环下去将无法终止。如果文法具有间接左递归，则也将发生上述问题，只不过环的圈子兜的更大。要实行自顶向下分析，必须要消除文法的左递归，下面我们将介绍直接左递归的消除方法，在此基础上再介绍一般左递归的消除方法。自顶向下分析为什么不能处理左递归文法？第四章语法分析--自上而下分析1111①消除直接

11、左递归:1111规则一（提因子）i)已知U→xy

12、xw

13、…

14、xz解：U→x(y

15、w

16、…

17、z)得：U→xU’U’→y

18、w

19、…

20、ziii)已知U→x

21、xy解：U→x(y

22、ε)使用提因子法，不仅有助于消除直接左递归。而且有助于压缩文件的长度，使我们更加有效的分析句子。ii)已知U→xy

23、xw

24、…

25、xzy→y1y2w→y1w2解：U→x(y1(y2

26、w2)

27、…

28、z)得：U→xU’U’→y1y1’

29、…

30、zy1’→y2

31、w2第四章语法分析--自上而下分析1212规则二将左递归规则改为右递归规则若：P→P

32、则可改写为：P→P’P’→P’

33、ε例2已知G[E]：E::=T*F

34、T/F

35、

36、FT::=F

37、T*F

38、T/F解：左递归改为右递归得：E::=T*F

39、T/F

40、FT::=FT’T’::=*FT’

41、/FT’

42、ε第四章语法分析--自上而下分析一般而言，假定关于P的全部产生式是PP1

43、P2

44、…

45、P1m

46、1

47、2

48、…

49、n其中，每个都不等于，而每个都不以P开头，那末，消除P的直接左递归性就是把这些规则改写成：P

50、1P’

51、2P’

52、…

53、nP’P’1P’

54、2P’

55、…

56、mP’

57、第四章语法分析--自上而下分析1414②消除一般左递归1.把G的非终结符整理成某种顺序A1，A2，