编译技术 张莉第一部分-基础篇 电子教案-第4章-语法分析(一).ppt

《编译技术 张莉第一部分-基础篇 电子教案-第4章-语法分析(一).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析语法分析的功能、基本任务自顶向下分析法＞自底向上分析法＞编译过程是指将高级语言程序翻译为等价的目标程序的过程。复习：第一章概述词法分析语法分析语义分析、生成中间代码代码优化生成目标程序习惯上是将编译过程划分为5个基本阶段：4.1语法分析概述功能：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。基本任务：识别符号串S是否为某语法成分。两大类分析方法：自顶向下分析自底向上分析主要问题:左递归问题回溯问题若ZS则SL(G[Z])否则SL(G[Z])G[Z]主要方法:递归子程序法LL分析法自顶向下分析算法的基本思想为：+自底向上分析算法的基本思想为：+若Z

2、S则SL(G[Z])否则SL(G[Z])G[Z]主要问题:句柄的识别问题主要方法:算符优先分析法LR分析法4.2自顶向下分析4.2.1自顶向下分析的一般过程可以通过一例子来说明语法分析过程给定符号串S，若预测是某一语法成分，则可根据该语法成分的文法,设法为S构造一棵语法树，若成功,则S最终被识别为某一语法成分,即SL(G[Z])，其中G[Z]为某语法成分的文法若不成功,则SL(G[Z])例：S=cadG[Z]:Z∷=cAdA∷=ab

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

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

5、a自顶向下分析方法特点:1.分析过程是带预测的，对输入符号串要预测属于什么语法成分，然后根据该语法成分的文法建立

6、语法树。2.分析过程是一种试探过程，是尽一切办法(选用不同规则)来建立语法树的过程,由于是试探过程,难免有失败,所以分析过程需进行回溯,因此也称这种方法是带回溯的自顶向下分析方法。最左推导可以编写程序来实现,但带溯的自顶向下分析方法在实际上价值不大,效率低。4.2.2自顶向下分析存在的问题及解决方法1、左递归文法：自顶向下分析的基本缺点是：不能处理具有左递归性的文法这个文法是左递归的。有如下文法：令U是文法的任一非终结符，文法中有规则U∷=U¨¨或者UU¨¨+为什么？如果在匹配输入串的过程中，假定正好轮到要用非终结符U直接匹配输入串，即要用U的右部符号串U¨¨去匹配，为了用U¨¨去匹

7、配，又得用U去匹配，这样无限的循环下去将无法终止。如果文法具有间接左递归，则也将发生上述问题，只不过环的圈子兜得更大。要实行自顶向下分析，必须要消除文法的左递归，下面将介绍直接左递归的消除方法，在此基础上再介绍一般左递归的消除方法。消除直接左递归方法一，使用扩充的BNF表示来改写文法例：(1)E∷=E+T

8、TE∷=T{+T}(2)T∷=T*F

9、T/F

10、FT∷=F{*F

11、/F}a.改写以后的文法消除了左递归。b.可以证明，改写前后的文法是等价的，表现在L(G改前)=L(G改后)如何改写文法能消除左递归，又前后等价，可以给出两条规则:规则一（提因子）若：U∷=xy

12、xw

13、….

14、xz则可

15、改写为：U∷=x(y

16、w

17、….

18、z)若：y=y1y2,w=y1w2则U∷=x(y1(y2

19、w2)

20、….

21、z)若有规则：U∷=x

22、xy则可以改写为：U∷=x(y

23、ε)注意：不应写成U∷=x(ε

24、y)使用提因子法，不仅有助于消除直接左递归，而且有助于压缩文件的长度，使我们能更有效地分析句子。规则二UUvUvvUvvv……∴可以改写为U∷=(x

25、y

26、……

27、z){v}其特点是：具有一个直接左递归的右部并位于最后，这表明该语法类U是由x或y……或z其后随有零个或多个v组成。通过以上两条规则，就能消除文法的直接左递归，并保持文法的等价性。若有文法规则：U∷=x

28、y

29、……

30、z

31、Uv方法二，将

32、左递归规则改为右递归规则规则三若：P∷=P

33、则可改写为：P∷=P’P’∷=P’

34、ε例1E∷=E+T

35、T右部无公因子，所以不能用规则一。为了使用规则二，令E∷=T

36、E+T∴由规则二可以得到E∷=T{+T}例2T∷=T*F

37、T/F

38、FT∷=T(*F

39、/F)

40、F规则一T∷=F

41、T(*F

42、/F)T∷=F{(*F

43、/F)}规则二即T∷=F{*F

44、/F}右递归：T::=FT’T’::=*FT’

45、/FT’

46、ε规则一：（提因子）规则二：U∷=x

47、y

48、…