第5章自顶向下语法分析方法.ppt

《第5章自顶向下语法分析方法.ppt》由会员分享，可在线阅读，更多相关《第5章自顶向下语法分析方法.ppt（147页珍藏版）》请在三一办公上搜索。

1、第5章自顶向下语法分析方法,语法分析（Syntax Analysis）是编译程序的核心部分。词法分析只是将字符形式的源程序中的各个单词识别出来，形成单词的机内表示形式，但是这些单词串如何构成更大的语法成分语句，那就由语法分析来完成。语法分析的主要任务就是“组词成句”，即在词法分析识别出单词串的基础上，根据语言的语法规则，识别出各类语法成分，如“语句”、“程序”等。将完成语法分析任务的程序称为语法分析程序，也称为语法分析器或简称分析器。,程序设计语言的语法结构是用上下文无关文法描述的，因此，语法分析器的实现原理就是按所给定的文法G，识别输入符号串是否为一个句子（即L(G)成立吗？），同时检查和处

2、理语法错误。语法分析的关键是句型识别问题。给定一串单词（即文法的终结符），怎样知道它是不是该文法产生的一个句子呢？可以利用推导，或者利用语法树来进行判断。一般来说，语法分析的过程就是为一个句子建立语法树的过程。,语法分析的方法很多，按照建立语法树的不同方向，通常将语法分析分为两类，一类是自顶向下分析法，另一类是自底向上分析法。本章主要介绍自顶向下分析法，自底向上分析法。,第4章教学内容,语法分析的任务；确定的自顶向下语法分析的基本思想；LL(1)文法的定义和判别方法；非LL(1)文法到LL(1)文法的等价变换；确定的自顶向下分析方法：递归下降分析法预测分析法,自底向上语法分析的基本思想；短语、

3、直接短语和句柄的定义，以及如何利用语法树寻找短语、直接短语和句柄。自底向上语法分析方法：优先分析法LR分析法,一、自顶向下的语法分析思想,【自顶向下（top-down）分析法的基本思想】自顶向下语法分析的基本思想是以文法的开始符号为树根，采用最左推导，试图自上而下地为输入的单词串构造一棵语法树。若语法树的端末节点从左向右排列恰好是输入串，则该输入串就是文法的句子，否则就不是。这种分析过程实质是一种试探过程，是反复使用不同产生式来匹配输入串的过程。,示例,【例4.1】设有以下文法G1S:SaAB AbA|c BdBe|de输入串abbcde的最左推导如下：S aAB abAB abbAB abb

4、cB abbcde因此，输入串abbcde是该文法G1的句子。,下面从建立语法树来看句子的推导过程。为了自顶向下地构造输入串abbcde的语法树，首先按文法的开始符号产生根节点S，再根据产生式规则自顶向下地生长这棵语法树。语法树的建立过程如图所示。,S,a A B,b A,b A,c,d e,自顶向下分析法也称面向目标的分析方法，在对输入串进行最左推导的过程中，在选择产生式时其实是一种试探方法，如果每一步选择产生式来匹配的时候都能够每选必中，则这种方法称为确定的分析方法；否则在选择产生式时面临多种可能，不知道选择哪一个产生式合适，就是不确定的分析方法。因此自顶向下分析法又可分为确定的和不确定的

5、两种，确定的分析方法对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。,1.不确定的自顶向下分析,不确定的自顶向下分析法的基本思想是，对任何输入串试图用一切可能的办法，从文法的开始符号出发，自上而下的为它建立一棵语法树。如果试探成功，则为相应文法的句子，否则就不是文法句子。这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。因此这种匹配过程往往一次不能成功，需要重新匹配，称为回溯。引起回溯的原因在于文法中关于

6、某个非终结符的产生式有多个时，而根据面临的输入符无法唯一确定选择哪个产生式来匹配，从而引起回溯。,自顶向下分析法中存在的问题,回溯问题 左递归问题,回溯问题,回溯时需要恢复到出错点位置，删去曾经匹配过的符号，还包括一些语义处理。因此处理回溯是一项复杂的工作，在回溯时，要清除在回溯之前编译程序所做的大量记录工作，然后重新开始记录，这就降低了语法分析的效率。避免回溯是自顶向下语法分析中需要解决的问题之一。,回溯的具体表现,回溯具体表现为下列两种情况：1.由于相同左部的产生式的候选式的FIRST集交集不为空而引起回溯。2.由于相同左部非终结符的候选式存在能推导出的产生式，且该非终结符的FOLLOW集

7、中含有其它候选式的FIRST集的元素。,表现一示例,由于相同左部的产生式的候选式的FIRST集交集不为空而引起回溯：【例46】设有文法G6S为：SxAyA*|*,串x*y的分析过程,S,x A y,*,(S,x)选择产生式SxAy,当前要替换的非终结符,当前要匹配的输入符,(A,*)可选择两个产生式 A*或A*,回溯：回到出错点，重新选择产生式A*，成功,原因,上述文法发生回溯的原因就在于A的两个产生式的候选式的第一个符号都是*，从而根据输入符*来选择A的产生式时有多种可能，因此会引起回溯。即：关于A的产生式的可选集交集不为。SELECT(A*)SELECT(A*)=*,表现二示例,由于相同左

8、部非终结符的候选式存在能推导出的产生式，且该非终结符的FOLLOW集中含有其它候选式的FIRST集的元素。【例如】例4.5的文法G5：SaAS Sb AbA A,对输入串ab#的试探推导过程,S,a A S,S,a A S,b A,S,a A S,b,原因,上述文法发生回溯的原因就在于选择产生式A相当于与A的后随符号FOLLOEW（A）a,b匹配，但是由于A的后随符号b与A的第一个候选式的第一个符号b相同，从而根据输入符b来选择A的产生式时有多种可能，因此会引起回溯。即：关于A的产生式的可选集交集不为。SELECT(AbA)SELECT(A)=b,左递归问题,【例4.7】算术表达式的文法G7E

9、为：E ET|TT T*F|FF i|（E）,对输入串i*i+i进行试探推导,结论,当一个文法是左递归的，采用自顶向下分析法会使分析过程陷入无限循环之中。回溯会使语法分析动作不确定，而左递归会使语法分析程序陷入无限循环之中，这些都使得语法分析的动作是不确定的。,不确定的语法分析方法带回溯的自顶向下分析法实际上是一种穷举的试探方法，当分析不成功时则推翻以前的分析退回到适当位置再重新试探其余候选式可能的推导，这样需要记录已选过的产生式，直到把所有可能的推导序列都试完仍不成功才能确认输入串不是该文法的句子而报错。由于在编译程序真正实现时往往是边分析边插入语义动作，因而带回溯的语法分析方法代价很高，效

10、率很低，在实用编译程序中几乎不用，因此对它实现的详细算法不做介绍。,2.确定的自顶向下的分析,确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树。,【例4.2】若有文法G2S：SaABAbB AcABaBd文法G2的句子acbad的自顶向下分析过程如下：,示例一,注意：#是输入结束符,以上最左推导所建立输入串acbad的语法树如图所示。,S,a A B,c A,b B,a,d,选择产生式是唯一的,在第2步推导时，当前要替换的非终结符为A，面临的输入符为c，所以选择A的产生式来推导时，

11、只能选产生式AcA，而不能选AbB。同样，在第5步推导时，当前要替换的非终结符为B，面临的输入符为d，所以选择B的产生式来推导时，只能选产生式Bd，而不能选Ba。这样就保证上述每一步推导都是确定的。,文法的特点,文法G2有以下两个特点：(1)每个产生式的右部都由终结符号开始；(2)如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。对于这样的文法显然在推导过程中完全可以根据当前要替换的非终结符和输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。,示例二,【例4.3】若有文法G3S为：SAaSBbAcAdABeBfB,文法G3的句子ddca的自顶向下分析过程如下：,以上最左

12、推导所建立输入串ddca的语法树如图所示。,S,A a,d A,d A,c,文法的特点,这个文法的特点是：（1）产生式的右部不全是由终结符开始。（2）如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。（3）文法中无空产生式。,讨论,对于产生式中相同左部含有非终结符开始的产生式，在推导过程中选用哪个产生式不像G2文法那样直观。对于输入串ddca，其第一个符号是d，这时从S出发选择SAa还是选择SBb时，需要知道Aa或Bb能推导出的首终结符号集合是什么（即Aad，还是Bbd）。若Aad成立，则选择SAa往下推导；若Bbd成立，则选择SBb往下推导；其它情况则为不确定推导或出错。

13、,首终结符号集,【定义4.1】设G(VN,VT,P,S)是上下文无关文法，是由非终结符与终结符组成的任意符号串，用FIRST()表示的首终结符集，则FIRST()a|a,aVT,(VNVT)*若，则规定FIRST()(空集)。,*,求符号串Aa与Bb的首终结符集：因为Aaca，AadAa，所以FIRST(Aa)=c,d。因为Bbeb，BbfBb，所以FIRST(Bb)=e,f。但是FIRST(Aa)FIRST(Bb)=因而可以根据当前的输入符号是属于哪个产生式右部的首终结符集而决定选择相应产生式进行推导，即当前要替换的非终结符为S，面临的输入符为d时，只能选择产生式SAa（因为dFIRST(A

14、a)）。这样仍然是确定的自顶向下分析。,假如考虑文法中有_产生式时,将会产生什么问题呢？先看下面的例子：【例4.4】若有文法G4S：SaABAbB AcAABaBd,文法G4的句子aca的自顶向下分析过程如下：,以上最左推导所建立输入串aca的语法树如图所示。,S,a A B,c A,a,讨论,考查以上推导，在第3步到第4步的推导中，即acABacB时，因为当前要替换的最左非终结符为A，面临输入符为a，而关于A的产生式右部的首终结符集都不包含a，但有，因此对于a的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号，所以这时选用产生式A往下推导，而当前A后面的符号为B，B的产生式右部的首终结

15、符集包含了a，所以可匹配。由此可以看出，当前输入符a与A后面的非终结符B匹配。,当某一非终结符的产生式中含有_产生式时，它的非空产生式右部的首终结符集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的首终结符号集也不相交，则仍可构造确定的自顶向下分析。为此，我们为非终结符引入后随符号集的概念。,后随符号集,【定义4.2】设G(VN,VT,P,S)是上下文无关文法，A是G中的非终结符，用FOLLOW(A)表示A的后随符号集，则有：FOLLOW(A)a|S Aa，aVT特别地，若有SA,则规定FOLLOW(A)。换句话说，FOLLOW(A)是指在G的各个句型中位于A后面的那些终结符或。用作为

16、输入串的结束符，或称为句子括号，如：输入串。,*,对于例4.4中的文法G4，可用观察法求得FOLLOW(A)a,d。在自顶向下分析过程中，如果当前要替换的非终结符A面临输入符a或d时，应该选择产生式A去匹配，而当面临b或c时，则分别选择产生式AbB 或AcA去匹配。,因此当文法中还有形如：AA的产生式时，其中AVN,V*，当和不同时推导出时，设,则当FIRST()(FIRST()FOLLOW(A)）时，对于非终结符A的替换仍可唯一地确定产生式。,*,*,SELECT集,在自顶向下分析过程中，对每个产生式的选择都可由输入符来决定。综合以上情况，为每个产生式定义一个可选集（SELECT）如下：,可

17、选集的定义,【定义4.3】给定上下文无关文法的产生式A，AVN,V*,则定义：如果,则SELECT(A)=FIRST()；如果，则SELECT(A)=FIRST()FOLLOW(A)；特别地，如果，则SELECT(A)=FOLLOW(A)。,*,*,可选集的含义,可选集的含义如下：在自顶向下分析过程中，如果当前要替换的最左非终结符为A，面临输入符为aSELECT(A)时，则可以选择产生式A来匹配。因此，只要文法G的某一个非终结符A的各个可选集互不相交，则语法分析程序就可以根据当前输入符和A的可选集来唯一正确的选择A的某个产生式去匹配。,LL(1)文法,【定义4.4】一个上下文无关文法是LL(1

18、)文法的充分必要条件是关于同一非终结符的各个产生式的可选集互不相交。LL(1)文法的含义是：第一个L表明自顶向下分析过程中是从左到右扫描输入串，第二个L表明分析过程中采用最左推导，1表明只需向前查看一个输入符号便可决定选择哪个产生式（规则）进行推导。类似地，也可以有LL(k)文法，也就是需要向前查看K个符号才能够确定选择哪个产生式。通常采用K=1，个别情况采用K=2。,示例,【例4.4】文法G4S：SaABAbB AcAABaBd,计算可选集：SELECT(SaAB)aSELECT(AbB)bSELECT(AcA)cSELECT(A)FOLLOW(A)a,dSELECT(Ba)aSELECT(

19、Bd)d显然有：SELECT(AbB)SELECT(AcA)bc SELECT(AbB)SELECT(A)ba,d SELECT(AcA)SELECT(A)ca,d SELECT(Ba)SELECT(Bd)ad 所以，该文法是LL(1)文法。,示例,【例4.5】设文法G5S为：SaASSbAbAA,因为有：SELECT(SaAS)FIRST(aAS)aSELECT(Sb)FIRST(b)bSELECT(AbA)FIRST(bA)bSELECT(A)FOLLOW(A)FIRST(S)a,b所以：SELECT(SaAS)SELECT(Sb)abSELECT(AbA)SELECT(A)ba，b因此，

20、该文法不是LL(1)文法，因而也就不可能进行确定的自顶向下语法分析。,原因,从对输入串ab的下列两种不同推导过程来看：第一种推导过程可为：S aAS abAS abS 在句型abS中由于S不能推出，所以第一种推导过程推不出ab；第二种推导过程可为：S aAS aS ab 第二种推导过程推出了ab。,以上两种推导中，当第二步推导时当前输入符为b，对句型aAS中的A用哪个产生式推导不能唯一确定，也就是导致了这个文法不能进行确定的自顶向下分析。也即非LL（1）文法是不能进行确定的自顶向下分析。,结论,确定的自顶向下语法分析要求文法是LL（1）文法。,二、LL（1）文法,LL(1)文法是一类可以进行确

21、定的自顶向下语法分析的文法。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A和A，都要满足：SELECT(A)SELECT(A)这样，当前非终结符A面临输入符a时，如果aSELECT(A)，则可以选择产生式A去准确匹配，从而解决回溯问题。,LL（1）文法的判别,采用确定的自顶向下分析技术时，首先必须判别所给文法是否是LL（1）文法。因而对任何给定的文法需要计算FIRST、FOLLOW、SELECT集合，进而判别该文法是否为LL（1）文法。,1.构造FIRST集,符号串的首终结符集为FIRST()，定义：FIRST()a|a,aVT,(VNVT)*若，则规定FIRST()。,*,构

22、造FIRST集的算法,对于文法符号串(VNVT)*，构造FIRST()的算法如下：反复使用如下规则，直至FIRST集不再增大为止。若a,且a是终结符,则FIRST()a；若X,X是非终结符,且有Xb,则把b加入FIRST()中；若X1X2Xk,X1,X2,Xk都是非终结符，首先把FIRST(X1)加入FIRST()中；若X1X2Xi,则把FIRST(Xi1Xi2Xk)加入FIRST()中，其中1ik1；若X1X2Xk,则把FIRST()加入FIRST()中。,+,+,在构造FIRST集的算法中，第条规则中的情况最复杂，下面具体说明一下。设ABC，A，B，C都是非终结符，则分情况讨论：若A，则F

23、IRST()FIRST(A)；若A，但B，则FIRST()FIRST(A)FIRST(BC)；若AB，但是C，则FIRST()FIRST(A)FIRST(B)FIRST(C)；若ABC，但是，则FIRST()FIRST(A)FIRST(B)FIRST(C)FIRST()。,+,+,+,+,+,+,+,示例一,【例4.8】若文法G8S为：SAB SbCA AbB BaDCAD CbDaS Dc,求各非终结符的FIRST集,FIRST（S）FIRST（AB）FIRST（bC）(SAB，SbC)FIRST（A）FIRST（B）b(A)b,abb,a,FIRST（A）FIRST（b）b(Ab)FIRS

24、T（B）FIRST（aD）a(BaD),FIRST（C）FIRST（AD）FIRST（b）(CAD，Cb)FIRST（A）FIRST（D）b(A)b,a,cbb,a,c,FIRST（D）FIRST（aS）FIRST（c）(DaS，Dc)aca,c,结果,所以最终求得：FIRST（S）b,aFIRST（A）bFIRST（B）aFIRST（C）b,a,cFIRST（D）a,c,2.构造FOLLOW集,非终结符A的后随符号集的定义为：FOLLOW(A)a|S Aa，aVT特别地，若有S A,则规定FOLLOW(A)。,*,*,构造FOLLOW集的算法,对文法中每一非终结符A，构造FOLLOW(A)的

25、算法如下：反复使用如下规则，直至FOLLOW集不再增大为止。若A是文法的开始符号,则把输入结束符加入FOLLOW(A)中；若BAa,a是终结符,则把a加入FOLLOW(A)中；若BAX,X是非终结符,则把FIRST(X)加入FOLLOW(A)中；若BA或BA,且，则把FOLLOW(B)加入FOLLOW(A)中。,*,注意,在构造FOLLOW集的算法中，将第条规则解释一下：如果有句型Ba，显然a是B的后随符号，aFOLLOW(B)，而BA，用它往下进行推导有SBaAa，那么a也是A的后随符号，aFOLLOW(A)即FOLLOW(B)中的后随符号都是FOLLOW(A)中的后随符号。,+,同样的，如

26、果有BA，且，用它往下进行推导有：SBaAaAa，即也有FOLLOW(B)中的后随符号都是FOLLOW(A)中的后随符号。,*,示例一,【例4.8】若文法G8S为：SAB SbCA AbB BaDCAD CbDaS Dc,求各非终结符的FOLLOW集,FOLLOW(S)FOLLOW(D)(S是文法的开始符号，DaS)FOLLOW(S)FOLLOW(A)FIRST（B）FIRST(D)FOLLOW(S)(SAB,且B,CAD)a，c，,FOLLOW(B)FOLLOW(S)(SAB)FOLLOW(C)FOLLOW(S)(SbC)FOLLOW(D)FOLLOW(B)FOLLOW(C)(BaD，CAD

27、)FOLLOW(S),结果,所以最终求得：FOLLOW(S)FOLLOW(A)a，c，FOLLOW(B)FOLLOW(C)FOLLOW(D),计算此文法各个产生式的可选集SELECT集,首先考虑计算产生式的右部是终结符开头的，其可选集只包含这一个终结符。SELECT(SbC)FIRST(bC)bSELECT(Ab)FIRST(b)bSELECT(BaD)FIRST(aD)aSELECT(Cb)FIRST(b)bSELECT(DaS)FIRST(aS)aSELECT(Dc)FIRST(c)c,再来考虑计算产生式是_产生式，其可选集为相应产生式左部的FOLLOW集。SELECT(A)FOLLOW(

28、A)a，c，SELECT(B)FOLLOW(B),再考虑复杂的情况，产生式的右部是非终结符开头的，其可选集的计算要取决于相应产生式右部的符号是否能够推导出。AB SELECT(SAB)FIRST(AB)FOLLOW(S)b,a,AD SELECT(CAD)FIRST(AD)a,b,c,*,*,结果,最后将产生式的可选集整理如下：SELECT(SAB)b,a,SELECT(SbC)bSELECT(A)a，c，SELECT(Ab)bSELECT(B)SELECT(BaD)aSELECT(CAD)a,b,cSELECT(Cb)bSELECT(DaS)aSELECT(Dc)c,判断是否为LL(1)文法

29、,因为：SELECT(SAB)SELECT(SbC)b,a,bb SELECT(A)SELECT(Ab)a，c，b SELECT(B)SELECT(BaD)a SELECT(CAD)SELECT(Cb)a,b,cb SELECT(DaS)SELECT(Dc)ac,结论：不是LL(1)文法,由于关于非终结符S的产生式的可选集的交集不为空集，即意味着当前的最左非终结符为S，面临的输入符为b时，可以选择产生式SAB或者SbC来匹配。同样，关于非终结符C的产生式的可选集的交集也不为空集。因此，这个文法的自顶向下语法分析动作是不确定。所以，该文法不是LL(1)文法。,三、某些非LL(1)文法到LL(1)

30、文法的等价转换,LL(1)文法的性质：LL(1)文法是无二义性的；LL(1)文法不含左递归；LL(1)文法没有公共左因子。,非LL(1)文法的改造,消除左递归消除回溯：提取左公因子,1.消除文法的左递归,当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进人无穷循环之中。文法左递归是指文法中的某个非终结符A存在推导A A，而自顶向下分析法是采用最左推导，即每次替换的都是当前句型中的最左非终结符，当试图用非终结符A去匹配输人串时，结果使当前句型的最左非终结符仍然为 A，也就是说，在没有读进任何输人符号的情况下，又重新要求A去进行新的匹配，于是造成无穷循环。所以采用自顶向下分析法进行语法分析

31、需要消除文法的左递归性。,+,递归文法,【递归文法】递归文法是指对文法中任一非终结符A，若存在一个推导序列，在推出的符号串中又出现了该非终结符本身，即AA，则该文法是递归的。若文法中对任一非终结符A有推导AA，则称该文法是左递归的。若文法中对任一非终结符A有推导AA，则称该文法是右递归的。,+,+,+,左递归,左递归又可以分为直接左递归和间接左递归。【直接左递归】若文法中的某一产生式形如AA，V*，则称该文法是直接左递归的。【间接左递归】若文法中存在某一非终结符A，使得AA至少需要两步推导，则称该文法是间接左递归的。,+,消除直接左递归的方法一,【方法一】只需将产生式进行改写，使之不含左递归。

32、为此需要引进一个新的非终结符，把含有左递归的产生式改写成右递归的产生式即可。设有产生式是关于非终结符A的直接左递归 AA|（,V*，且不以A开头）对A引入一个新的非终结符A，把上式改写为：A A AA|,改写前后产生式是等价的。前式推导：A AA Ann后式推导：AAAAnA n从A推出的符号串的集合是相同的，也就是说，它们是等价的。,+,+,一般情况,若某文法中非终结符A的产生式形如：AA1|A2|An-1|An|1|2|m-1|m其中：i、jV*，i=1,n，j=1,m，且j不以A开头，则可用下述方法消除直接左递归：引入一个新的非终结符A A 1A|2A|m-1A|mA A1A|2A|n-

33、1A|nA|,示例,【例410】算术表达式文法G7E：EE+T|T TT*F|F Fi|（E）消除直接左递归后，文法变成：ETE E+T E|TFT T*FT|Fi|（E）,消除直接左递归的方法二,【方法二】采用扩充BNF表示法改写含直接左递归的产生式。在扩充的BNF表示中，有如下约定：花括号：表示符号串的可出现0次或多次，即表示*。：表示符号串的可出现m次至n次，m为最小次数，n为最大次数。【例如】AA|可改写为：A,m,n,方括号：表示10即的出现可有可无，它用来表示可供选择的符号串。【例如】A|可改写为：A圆括号（）利用圆括号可在产生式右部中提取公共因子。【例如】A1|2|m-1|m可改

34、写为：A（1|2|m-1|m）,示例,【例411】算术表达式的文法G7E为：E ET|TT T*F|FF i|（E）对文法G7用扩充BNF表示法对其进行改写。,示例,因为产生式EET|T表示E所生成的符号串由T开头且后跟0个或多个十T；而产生式TT*F|F表示T所生成的符号串由F开头且后面跟0个或多个*F，所以该文法可改写成如下形式：E T+T T F*F F i|（E）,消除间接左递归的方法,消除直接左递归是比较容易的，但是消除间接左递归就不是那么容易的事。【方法一】采用代入法把间接左递归变成直接左递归。【方法二】直接改写文法。,示例,【例412】设有文法G10S：S A|A S 因为S A

35、 S，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将式代入式，即可得到与原文法等价的文法（可以证明）：S S|式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：S S S S|,2消除回溯,在自顶向下分析过程中，当某个非终结符A对应多个候选式时，如果其中有几个候选式的左端第一符号相同，那么就会使得语法分析程序无法根据当前要替换的非终结符和当前输人符唯一地决定选用哪个候选式来替换A，只能采用试探的办法，任选某个候选式去试探一次。如果不能导致最终正确地匹配，只得再换另一个候选式去试探，从而引起回溯。,在自顶向下分析过程中，由于回溯需要推翻前面的分析，包

36、括已做的一大堆语义工作，重新去进行试探，这样大大降低了语法分析器的工作效率，因此，需要消除回溯。对于上述情况（即，同一非终结符有多个候选式的首符相同），可以采用提“左因子”的方法来改造文法，使得文法的每个非终结符的各个候选式的首符都不相同，从而可以消除上面所说的回溯现象。,提取公共左因子,若A的产生式为：A1|2经过提取公共左因子，原产生式变为：AA A1|2,一般情况,若A的产生式为：A1|2|k-1|k经过提取公共左因子，原产生式变为：AA A1|2|k-1|k 如果m、n（其中1m、nk）中仍然含有公共左因子，则可反复提取它们的共同左因子，直到每个新引入的非终结符的产生式再无公共左因子为

37、止。,示例,【例415】前面例46中的文法G6S为：Sx A y A*|*关于A的产生式有公共左因子，提取公共左因子a后，文法改写为：Sx A yA*AA*|,计算该文法的可选集,SELECT（Sx A y）xSELECT（A*A）*SELECT（A*）*SELECT（A）FOLLOW（A）FOLLOW（A）y因为：SELECT（A*）SELECT（A）*y 所以，上述文法是LL（1）文法，这时再用自顶向下分析方法分析符号串x*y，就不会产生回溯了。,示例,【例415】设有文法G13S为：Sa S b Sab关于S的产生式有公共左因子，提取公共左因子a后，文法改写为：Sa（S b|b）进一步变

38、换为文法G13 S,其产生式为：Sa S SS b|b,计算该文法的可选集,SELECT（Sa S）aSELECT（SS b）FIRST（Sb）FIRST（S）aSELECT（Sb）b因为：SELECT（SSb）SELECT（Sb）ab所以，上述文法是LL（1）文法，可以进行确定的自顶向下的语法分析。,三、确定的自顶向下分析方法,特征根据下一个输入符号为当前要处 理的非终结符选择产生式要求文法是LL(1)的语法分析方法：1 递归下降分析法 2 预测分析法,1.递归下降分析法,递归子程序法是比较简单直观易于构造的一种语法分析方法。实现思想：文法中每个非终结符对应一个递归过程(子程序)，每个过程的

39、功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时能够按LL(1)形式可唯一地确定选择某个候选式进行推导。,示例,【例410】算术表达式文法G7E：EE+T|T TT*F|F Fi|（E）消除直接左递归后，文法变成：ETE E+T E|TFT T*FT|Fi|（E）,计算FIRST集与FOLLOW集,各非终结符的FIRST集为：FIRST(E)=(,iFIRST(E)=+FIRST(T)=(,iFIRST(T)=*FIRST(F)=(,i,各非终结符的FOLLOW集合为：FOLLOW(E)=),FOLLOW(E)=)，FOLLOW(T)=，)，FOLLOW(T)=,)，#FOL

40、LOW(F)=*,，),#,计算SELECT集,各产生式的 SELECT集为：SELECT(ETE)FIRST(TE)（,i SELECT(E 十TE)SELECT(E)FOLLOW(E)），SELECT(TFT)FIRST(FT)（，i SELECT(T*FT)*SELECT(T)FOLLOW(T)十，），SELECT(F（E）)（SELECT(Fi)i,该文法是LL(1)文法,因为：SELECT(E十TE)SELECT(E)SELECT(T*FT)SELECT(T)SELECT(F（E）)SELECT(Fi)所以，该文法中关于同一个非终结符的产生式的SELECT集两两不相交，因此，该文法是

41、LL（1）文法，可以进行确定的自顶向下语法分析。,递归子程序E,ETE非终结符E对应的子程序为：E()T();E();,递归子程序E,E+T E|非终结符E对应的子程序为：E()if sym+read(sym);T();E();else if symFOLLOW(E)return;else error();,递归子程序T,TFT非终结符T对应的子程序为：T()F();T();,递归子程序T,T*FT|非终结符T对应的子程序为：T()if sym*read(sym);F();T();else if symFOLLOW(T)return;else error();,递归子程序F,Fi|（E）非终结

42、符F对应的子程序为：F()if sym=i read(sym);else if sym(read(sym);E();if sym)read(sym);else error();,主程序,main()read(sym);E();if(sym=#)printf(“分析成功”)；else printf(“分析失败”)；,示例,【例411】算术表达式的文法G7E：E ET|TT T*F|FF i|（E）对文法G7用扩充BNF表示法对其进行改写成如下形式：E T+T T F*F F i|（E）,递归子程序E,E T+T 非终结符E对应的子程序为：E()T();while(sym=+)read(sym);

43、T();,递归子程序T,T F*F 非终结符T对应的子程序为：T()F();while(sym=*)read(sym);F();,递归子程序F,Fi|（E）非终结符F对应的子程序为：F()if sym=i read(sym);else if sym(read(sym);E();if sym)read(sym);else error();,主程序,main()read(sym);E();if(sym=#)printf(“分析成功”)；else printf(“分析失败”)；,2.预测分析法,预测分析法用一个分析栈存放当前要替换的非终结符的某个候选式的符号串（倒放在栈内），当非终结符呈现在栈顶时，

44、它就是当前非终结符；此外，还使用一张矩阵形式的预测分析表，它是根据可选集构造的，它的入口指出了某非终结符和某终结符匹配时所应选择的候选式和语义动作。预测分析程序的总控程序就是利用栈顶符号和当前输人符号对输人串进行预测分析，而预测的信息则存放在预测分析表的相应入口里。,一个预测分析程序是由三个部分组成总控程序（表驱动程序）预测分析表先进后出的语法分析栈,预测分析程序的模型,预测分析程序实际上就是一个下推自动机，它是用下推自动机来识别输入符号串的。,输入串,总控程序预测分析表（LL(1)分析表）,栈顶符号,#,x1,xn,分析栈,预测分析法表(LL(1)分析表),表示:一个矩阵（或二维数组）MA，

45、a行:对应文法的一个非终结符A列:对应一个终结符a或输入结束符“”。大小:mn,m是文法中非终结符数，n是终结符数1（外加一个结束符“”）。数组的值MA，a：存放着面临输人符号a时，所应选择A的某条产生式，即指出当前推导所应使用的产生式。数组中的空白入口中应填人适当的出错处理子程序名或编号，即此种情况下存在语法错误。,预测分析表的构造,预测分析法的实现关键在于预测分析表。预测分析表是指分析栈中的文法符号与输入串中的符号的一种匹配关系，记为MA，a，其中A为分析栈中的符号，a为输入符号。可以由可选集直接来构造预测分析表。,预测分析表的构造算法,预测分析表的构造算法是：对每个终结符aSELECT（

46、A），把A填入MA，a中；把所有无定义的MA，a均填上“出错标志”。,结论,上述算法可应用于任何文法G以构造它的分析表M。但对于某些文法，有些MA，a中可能有若干个产生式，或者说有些MA，a可能是多重定义的。如果G是左递归或回溯的，那么M至少含有一个多重定义入口。因此，消除左递归和提取公共左因子将有助于获得无多重定义的分析表M。可以证明：一个文法G的预测分析表M不含多重定义入口，当且仅当该文法是LL（l）文法。,示例,【例419】前述算术表达式的文法G7E为：E TE E 十TE|T FTT*FT|F i|（E）,表达式文法的预测分析表,预测分析程序的工作流程,预测分析程序在总控程序控制下进行

47、对输入串的分析，利用分析栈记录分析过程中使用的文法符号。输入串中存放的终结符号串，分析栈中存放的是终结符和非终结符组成的符号串。,预测分析表的工作流程-1,分析开始时，首先将栈底符号“”及文法的开始符号S依次推入分析栈的栈底，并对各条指示器置初值，此时分析栈和输入串的格局为(用箭头表示输入串指针和栈顶指针当前所指向的位置)：,预测分析表的工作流程-2,设在分析的某一步，分析栈和余留的输入符号串处于如下的格局：,此时，可根据栈顶的文法符号Xm的不同情况，分别处理：,情形一,若Xm为终结符，即xmVT，且Xmai“”时，则表明栈顶符号已与当前正扫视的输入符号相匹配，此时应将Xm从栈中弹出，而且将输

48、入指针向前移动一个位置至ai1。从而得到如下格局：,情形二,若Xm为非终结符，即X mVN，则以 Xm及 ai组成符号对（Xm，ai）查分析表 M，假设MXm，ai中存放着关于Xm的一个产生式Xm ABC，此时，首先将Xm从分析栈中弹出，并将该产生式右部ABC的逆替换栈顶符号，即把ABC按逆序推入栈中（此即用该产生式推导一步）。输入指针不动。从而得到新的格局如下：否则出错，即MXm，ai“ERROR”，则调用出错处理程序来进行处理或宣告分析失败。,情形三,若xmai“”，即输入串与分析栈均为空，则表明输入符号串已完全得到匹配，此时可宣告分析成功，结束工作，接收输入串。此时的格局如下：,反复使用

49、第二步进行处理，直至分析成功或者分析失败。,示例,【例419】算术表达式的文法G7E为：E TE E 十TE|T FTT*FT|F i|（E）给出输入串ii 的分析过程：,分析栈(栈顶符,输入符)剩余输入串#E(E,i)查表E TE i+i#2#ET(T,i)查表T FT i+i#3#ETF(F,i)查表F ii+i#4#ETi(i,i)匹配+i#ET(T,+)查表T+i#E(E,+)查表E+TE+i#7#ET+(+,+)匹配i#ET(T,i)查表T FT i#9#ETF(F,i)查表F i i#10#ETi(i,i)匹配#11#ET(T,#)查表T#12#E(E,#)查表E#13#(#,#)

50、成功接收#,示例,【例419】设有文法G16P为：P begin d；X endX d；XXsYY；sY Y用预测分析法分析的步骤分为四步：,1是否需要改写文法,如果文法是左递归的，或者具有公共左因子，则需要对文法进行改写。因为上述文法G16不具有左递归和公共左因子，所以不需要对文法进行改写，直接证明该文法是LL（1）文法即可。,2判断文法是否为LL(1)文法,该文法的各个产生式的 SELECT集为：SELECT（Pbegin d；X end）=beginSELECT（Xd；X）=dSELECT（XsY）=sSELECT（Y；sY）=；SELECT（Y）=FOLLOW（Y）=FOLLOW（X）