第5章自顶向下语法分析方法PPT课件

1、 程序设计语言的语法结构是用上下文无关文法描述的，因此，语法分析器的实现原理就是按所给定的文法G，识别输入符号串是否为一个句子（即L(G)成立吗？），同时检查和处理语法错误。语法分析的关键是句型识别问题。给定一串单词（即文法的终结符），怎样知道它是不是该文法产生的一个句子呢？可以利用推导，或者利用语法树来进行判断。一般来说，语法分析的过程就是为一个句子建立语法树的过程。第1页/共147页 语法分析的方法很多，按照建立语法树的不同方向，通常将语法分析分为两类，一类是自顶向下分析法，另一类是自底向上分析法。 本章主要介绍自顶向下分析法，自底向上分析法。第2页/共147页第4章教学内容 语法分析的任

2、务； 确定的自顶向下语法分析的基本思想； LL(1)文法的定义和判别方法； 非LL(1)文法到LL(1)文法的等价变换； 确定的自顶向下分析方法： 递归下降分析法 预测分析法第3页/共147页 自底向上语法分析的基本思想； 短语、直接短语和句柄的定义，以及如何利用语法树寻找短语、直接短语和句柄。 自底向上语法分析方法： 优先分析法 LR分析法第4页/共147页一、自顶向下的语法分析思自顶向下的语法分析思想想 【自顶向下（top - down ）分析法的基本思想】自顶向下语法分析的基本思想是以文法的开始符号为树根，采用最左推导，试图自上而下地为输入的单词串构造一棵语法树。若语法树的端末节点从左向

3、右排列恰好是输入串，则该输入串就是文法的句子，否则就不是。 这种分析过程实质是一种试探过程，是反复使用不同产生式来匹配输入串的过程。第5页/共147页示例【例4.1】设有以下文法G1S: SaAB AbA|c BdBe|de 输入串abbcde的最左推导如下：S aAB abAB abbAB abbcB abbcde 因此，输入串abbcde是该文法G1的句子。第6页/共147页 下面从建立语法树来看句子的推导过程。为了自顶向下地构造输入串abbcde的语法树，首先按文法的开始符号产生根节点S，再根据产生式规则自顶向下地生长这棵语法树。语法树的建立过程如图所示。Sa A B b Ab Acd

4、e第7页/共147页 自顶向下分析法也称面向目标的分析方法，在对输入串进行最左推导的过程中，在选择产生式时其实是一种试探方法，如果每一步选择产生式来匹配的时候都能够每选必中，则这种方法称为确定的分析方法；否则在选择产生式时面临多种可能，不知道选择哪一个产生式合适，就是不确定的分析方法。 因此自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。第8页/共147页1. 1. 不确定的自

5、顶向下分析 不确定的自顶向下分析法的基本思想是，对任何输入串试图用一切可能的办法，从文法的开始符号出发，自上而下的为它建立一棵语法树。如果试探成功，则为相应文法的句子，否则就不是文法句子。这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。因此这种匹配过程往往一次不能成功，需要重新匹配，称为回溯。 引起回溯的原因在于文法中关于某个非终结符的产生式有多个时，而根据面临的输入符无法唯一确定选择哪个产生式来匹配，从而引起回溯。第9页/共147页自顶向下分析法中存在的问题 回溯问题 左递归问题 第10页/共147页回溯问题 回溯时需要恢复到出错点位置，删去曾经匹配过的符号，

6、还包括一些语义处理。因此处理回溯是一项复杂的工作，在回溯时，要清除在回溯之前编译程序所做的大量记录工作，然后重新开始记录，这就降低了语法分析的效率。避免回溯是自顶向下语法分析中需要解决的问题之一。 第11页/共147页回溯的具体表现 回溯具体表现为下列两种情况：1. 由于相同左部的产生式的候选式的FIRST集交集不为空而引起回溯。2.由于相同左部非终结符的候选式存在能推导出的产生式，且该非终结符的FOLLOW集中含有其它候选式的FIRST集的元素。第12页/共147页表现一示例 由于相同左部的产生式的候选式的FIRST集交集不为空而引起回溯：【例46】设有文法G6S为：SxAyA*|*第13页

7、/共147页串x* *y y的分析过程的分析过程Sx A y* * * *(S,x) 选择产生式选择产生式SxAy SxAy 当前要替换的非当前要替换的非终结符终结符当前要匹配的输当前要匹配的输入符入符 (A, * *) 可选择两个产生式可选择两个产生式 AA* * *或AA* *Sx A y* *回溯：回到出错点，重新回溯：回到出错点，重新选择产生式选择产生式AA* *，成功第14页/共147页原因 上述文法发生回溯的原因就在于A的两个产生式的候选式的第一个符号都是*，从而根据输入符*来选择A的产生式时有多种可能，因此会引起回溯。 即：关于A的产生式的可选集交集不为。SELECT(A*)SE

8、LECT(A*)=*第15页/共147页表现二示例 由于相同左部非终结符的候选式存在能推导出的产生式，且该非终结符的FOLLOW集中含有其它候选式的FIRST集的元素。【例如】例4.5的文法G5： SaAS Sb AbA A第16页/共147页对输入串对输入串ab#ab#的试探推导过程的试探推导过程Sa A SSa A Sb ASa A Sb第17页/共147页原因 上述文法发生回溯的原因就在于选择产生式A相当于与A的后随符号FOLLOEW（A）a,b匹配，但是由于A的后随符号b与A的第一个候选式的第一个符号b相同，从而根据输入符b来选择A的产生式时有多种可能，因此会引起回溯。 即：关于A的产

9、生式的可选集交集不为。SELECT(AbA)SELECT(A)=b第18页/共147页左递归问题 【例4.7】算术表达式的文法G7E为：E ET|TT T*F| FF i |（E）第19页/共147页对输入串i i* *i+ii+i进行试探推导 EE + TE + TEE + TEE + TE + TE + T第20页/共147页结论 当一个文法是左递归的，采用自顶向下分析法会使分析过程陷入无限循环之中。 回溯会使语法分析动作不确定，而左递归会使语法分析程序陷入无限循环之中，这些都使得语法分析的动作是不确定的。第21页/共147页 不确定的语法分析方法带回溯的自顶向下分析法实际上是一种穷举的试

10、探方法，当分析不成功时则推翻以前的分析退回到适当位置再重新试探其余候选式可能的推导，这样需要记录已选过的产生式，直到把所有可能的推导序列都试完仍不成功才能确认输入串不是该文法的句子而报错。由于在编译程序真正实现时往往是边分析边插入语义动作，因而带回溯的语法分析方法代价很高，效率很低，在实用编译程序中几乎不用，因此对它实现的详细算法不做介绍。第22页/共147页2.确定的自顶向下的分析 确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树。 第23页/共147页【例4.2】若有文法G2S

11、：SaABAbB AcABaBd文法G2的句子acbad的自顶向下分析过程如下：示例一第24页/共147页注意：#是输入结束符 最左推导最左推导过程过程所选产生式所选产生式输入串输入串( (当前要替换的非当前要替换的非终结符终结符, ,输入符输入符) )1Sacbad#(S,a)2aABSaABacbad#(A,c)3acABAcAacbad#(A,b)4acbBBAbBacbad#(B,a)5acbaBBaacbad#(B,d)6acbadBdacbad#推导成功推导成功第25页/共147页以上最左推导所建立输入串acbad的语法树如图所示。Sa A B c Ab Bad第26页/共147页

12、选择产生式是唯一的 在第2步推导时，当前要替换的非终结符为A，面临的输入符为c，所以选择A的产生式来推导时，只能选产生式AcA，而不能选AbB。同样，在第5步推导时，当前要替换的非终结符为B，面临的输入符为d，所以选择B的产生式来推导时，只能选产生式Bd，而不能选Ba。这样就保证上述每一步推导都是确定的。第27页/共147页文法的特点文法G2有以下两个特点：(1)每个产生式的右部都由终结符号开始；(2)如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。 对于这样的文法显然在推导过程中完全可以根据当前要替换的非终结符和输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。 第

13、28页/共147页示例二【例4.3】若有文法G3S为：SAaSBbAcAdABeBfB第29页/共147页文法G G3 3的句子ddcaddca的自顶向下分析过程如下：最左推导最左推导过程过程所选产生式所选产生式输入串输入串( (当前要替换的非当前要替换的非终结符终结符, ,输入符输入符) )1Sddca#(S,d)2AaSAaddca#(A,d)3dAaAdAddca#(A,d)4ddAaAdAddca#(A,c)5ddcaAcddca#推导成功推导成功第30页/共147页以上最左推导所建立输入串ddca的语法树如图所示。SA a d Ad Ac第31页/共147页文法的特点 这个文法的特点

14、是：（1）产生式的右部不全是由终结符开始。（2）如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。（3）文法中无空产生式。第32页/共147页讨论 对于产生式中相同左部含有非终结符开始的产生式，在推导过程中选用哪个产生式不像G2文法那样直观。 对于输入串ddca，其第一个符号是d，这时从S出发选择SAa还是选择SBb时，需要知道Aa或Bb能推导出的首终结符号集合是什么（即Aad，还是Bbd）。若Aad成立，则选择SAa往下推导；若Bbd成立，则选择SBb往下推导；其它情况则为不确定推导或出错。 第33页/共147页首终结符号集 【定义4.1】设G( VN, VT , P,

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

16、仍然是确定的自顶向下分析。第35页/共147页 假如考虑文法中有_产生式时,将会产生什么问题呢？先看下面的例子：【例4.4】若有文法G4S：SaABAbB AcAABaBd第36页/共147页文法G4的句子aca的自顶向下分析过程如下：最左推导最左推导过程过程所选产生式所选产生式输入串输入串( (当前要替换的非当前要替换的非终结符终结符, ,输入符输入符) )1Saca#(S,a)2aABSaABaca#(A,c)3acABAcAaca#(A,a)4acBAaca#(B,a)5acaBaaca#推导成功推导成功第37页/共147页以上最左推导所建立输入串aca的语法树如图所示。Sa A Bc

17、Aa第38页/共147页讨论 考查以上推导，在第3步到第4步的推导中，即acABacB时，因为当前要替换的最左非终结符为A，面临输入符为a，而关于A的产生式右部的首终结符集都不包含a，但有，因此对于a的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号，所以这时选用产生式A往下推导，而当前A后面的符号为B，B的产生式右部的首终结符集包含了a，所以可匹配。由此可以看出，当前输入符a与A后面的非终结符B匹配。 第39页/共147页 当某一非终结符的产生式中含有_产生式时，它的非空产生式右部的首终结符集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的首终结符号集也不相交，则仍可构造确定的

18、自顶向下分析。为此，我们为非终结符引入后随符号集的概念。第40页/共147页后随符号集 【定义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后面的那些终结符或。用作为输入串的结束符，或称为句子括号，如：输入串。*第41页/共147页 对于例4.4中的文法G4，可用观察法求得FOLLOW(A)a,d。在自顶向下分析过程中，如果当前要替换的非终结符A面临输入符a或d时，应该选择产生

19、式A去匹配，而当面临b或c时，则分别选择产生式AbB 或AcA去匹配。 第42页/共147页 因此当文法中还有形如： A A 的产生式时，其中AVN, ,V*，当和不同时推导出时，设, ,则当FIRST()(FIRST()FOLLOW(A)） 时，对于非终结符A的替换仍可唯一地确定产生式。*第43页/共147页SELECT集 在自顶向下分析过程中，对每个产生式的选择都可由输入符来决定。综合以上情况，为每个产生式定义一个可选集（SELECT）如下： 第44页/共147页可选集的定义【定义4.3】给定上下文无关文法的产生式A，AVN, V*,则定义： 如果, 则SELECT(A)= FIRST()

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

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

22、然有：SELECT(AbB)SELECT(AcA)bc SELECT(AbB)SELECT(A)ba,d SELECT(AcA)SELECT(A)ca,d SELECT(Ba)SELECT(Bd)ad 所以，该文法是LL(1)文法。第49页/共147页示例【例4.5】 设文法G5S为：SaASSbAbAA第50页/共147页 因为有：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(Ab

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

24、 确定的自顶向下语法分析要求文法是LL（1）文法。第54页/共147页二、LLLL（1 1）文法 LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。 根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A和A，都要满足：SELECT(A)SELECT(A) 这样，当前非终结符A面临输入符a时，如果aSELECT(A)，则可以选择产生式A去准确匹配，从而解决回溯问题。 第55页/共147页LLLL（1 1）文法的判别 采用确定的自顶向下分析技术时，首先必须判别所给文法是否是LL（1）文法。因而对任何给定的文法需要计算FIRST、FOLLOW、SELECT集合，进而判别该文法是否为

25、LL（1）文法。第56页/共147页1.1.构造FIRSTFIRST集 符号串的首终结符集为FIRST()，定义： FIRST()a|a, aVT,(VNVT ) * 若，则规定FIRST()。*第57页/共147页构造FIRSTFIRST集的算法 对 于 文 法 符 号 串 ( VN VT )*， 构 造FIRST()的算法如下：反复使用如下规则，直至FIRST集不再增大为止。若a,且a是终结符,则FIRST()a；若X,X是非终结符,且有Xb,则把b加入FIRST ()中；若X1X2Xk,X1, X2,Xk都是非终结符，首先把FIRST(X1)加入FIRST()中；若X1X2Xi ,则把F

26、IRST (Xi1Xi2Xk)加入FIRST ()中，其中1ik1；若X1X2 Xk , 则 把 F I R S T ( ) 加 入FIRST()中。 +第58页/共147页 在构造FIRST集的算法中，第条规则中的情况最复杂，下面具体说明一下。 设ABC，A，B，C都是非终结符，则分情况讨论： 若A，则FIRST()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()。+

27、第59页/共147页示例一【例4.8】若文法G8S为：SAB SbCA AbB BaDCAD CbDaS Dc第60页/共147页求各非终结符的FIRST集 FIRST（S）FIRST（AB）FIRST（bC） ( SAB ，SbC )FIRST（A）FIRST（B）b ( A )b,abb,a第61页/共147页 FIRST（A）FIRST（b）b ( Ab ) FIRST（B）FIRST（aD）a (BaD )第62页/共147页 FIRST（C）FIRST（AD）FIRST（b） ( CAD ， Cb )FIRST（A）FIRST（D）b ( A )b,a,cbb,a,c第63页/共14

28、7页 FIRST（D）FIRST（aS）FIRST（c） ( DaS ，Dc )aca,c第64页/共147页结果 所以最终求得： FIRST（S）b,a FIRST（A）b FIRST（B）a FIRST（C）b,a,c FIRST（D）a,c第65页/共147页2.2.构造FOLLOWFOLLOW集 非终结符A的后随符号集的定义为： FOLLOW(A)a|S Aa，aVT 特别地，若有S A,则规定FOLLOW(A)。 *第66页/共147页构造FOLLOWFOLLOW集的算法 对文法中每一非终结符A，构造FOLLOW(A)的算法如下：反复使用如下规则，直至FOLLOW集不再增大为止。若A

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

30、下进行推导有：SBaAaAa， 即也有FOLLOW(B)中的后随符号都是FOLLOW(A)中的后随符号。 *第69页/共147页示例一【例4.8】若文法G8S为：SAB SbCA AbB BaDCAD CbDaS Dc第70页/共147页求各非终结符的FOLLOW集 FOLLOW(S)FOLLOW(D) ( S是文法的开始符号，DaS)FOLLOW(S) FOLLOW(A)FIRST（B）FIRST(D)FOLLOW(S) (SAB,且B , CAD) a ，c ，第71页/共147页 FOLLOW(B)FOLLOW(S) ( SAB) FOLLOW(C)FOLLOW(S) ( SbC ) F

31、OLLOW(D)FOLLOW(B)FOLLOW(C) ( BaD ，CAD ) FOLLOW(S)第72页/共147页结果 所以最终求得： FOLLOW(S) FOLLOW(A)a ，c ， FOLLOW(B) FOLLOW(C) FOLLOW(D)第73页/共147页计算此文法各个产生式的可选集SELECT集 首先考虑计算产生式的右部是终结符开头的，其可选集只包含这一个终结符。 SELECT(SbC)FIRST(bC)b SELECT(Ab)FIRST(b)b SELECT(BaD)FIRST(aD)a SELECT(Cb)FIRST(b)b SELECT(DaS)FIRST(aS)a SE

32、LECT(Dc)FIRST(c)c 第74页/共147页 再来考虑计算产生式是_产生式，其可选集为相应产生式左部的FOLLOW集。 SELECT(A)FOLLOW(A) a ，c ， SELECT(B)FOLLOW(B) 第75页/共147页 再考虑复杂的情况，产生式的右部是非终结符开头的，其可选集的计算要取决于相应产生式右部的符号是否能够推导出。 AB SELECT(SAB) FIRST(AB)FOLLOW(S) b,a, AD SELECT(CAD) FIRST(AD) a,b,c*第76页/共147页结果 最后将产生式的可选集整理如下： SELECT(SAB)b,a, SELECT(Sb

33、C)b SELECT(A)a ，c ， SELECT(Ab)b SELECT(B) SELECT(BaD)a SELECT(CAD)a,b,c SELECT(Cb)b SELECT(DaS)a SELECT(Dc)c第77页/共147页判断是否为LL(1)文法 因为： 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 第78页/共147页结论：不是LL(1)文法 由于关于非终结符S的产

34、生式的可选集的交集不为空集，即意味着当前的最左非终结符为S，面临的输入符为b时，可以选择产生式SAB或者SbC来匹配。同样，关于非终结符C的产生式的可选集的交集也不为空集。因此，这个文法的自顶向下语法分析动作是不确定。 所以，该文法不是LL(1)文法。 第79页/共147页三、某些非LL(1)文法到LL(1)文法的等价转换 LL(1)文法的性质： LL(1)文法是无二义性的； LL(1)文法不含左递归； LL(1)文法没有公共左因子。第80页/共147页非LL(1)文法的改造消除左递归消除回溯：提取左公因子第81页/共147页1.消除文法的左递归 当一个文法是左递归文法时，采用自顶向下分析法会

35、使分析过程进人无穷循环之中。文法左递归是指文法中的某个非终结符A存在推导A A，而自顶向下分析法是采用最左推导，即每次替换的都是当前句型中的最左非终结符，当试图用非终结符A去匹配输人串时，结果使当前句型的最左非终结符仍然为 A，也就是说，在没有读进任何输人符号的情况下，又重新要求A去进行新的匹配，于是造成无穷循环。所以采用自顶向下分析法进行语法分析需要消除文法的左递归性。 + +第82页/共147页递归文法 【递归文法】递归文法是指对文法中任一非终结符A，若存在一个推导序列，在推出的符号串中又出现了该非终结符本身，即AA，则该文法是递归的。 若文法中对任一非终结符A有推导AA，则称该文法是左递

36、归的。 若文法中对任一非终结符A有推导AA，则称该文法是右递归的。 + + + +第83页/共147页左递归 左递归又可以分为直接左递归和间接左递归。【直接左递归】若文法中的某一产生式形如AA，V*，则称该文法是直接左递归的。【间接左递归】若文法中存在某一非终结符A，使得AA至少需要两步推导，则称该文法是间接左递归的。+ +第84页/共147页消除直接左递归的方法一【方法一】只需将产生式进行改写，使之不含左递归。为此需要引进一个新的非终结符，把含有左递归的产生式改写成右递归的产生式即可。 设有产生式是关于非终结符A的直接左递归 AA| （,V*，且不以A开头） 对A引入一个新的非终结符A，把上

37、式改写为： A A AA| 第85页/共147页 改写前后产生式是等价的。 前式推导： A AA Ann 后式推导：AAAAnA n 从A推出的符号串的集合是相同的，也就是说，它们是等价的。 + + +第86页/共147页一般情况 若某文法中非终结符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-1A|nA|第87页/共147页示例【例410】算术表达式文法G7E： EE +T | T TT * F

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

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

40、变成直接左递归。 【方法二】直接改写文法。第93页/共147页示例【例412】设有文法G10S： S A| A S 因为S A S，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将式代入式，即可得到与原文法等价的文法（可以证明）： S S| 式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法： S S S S| 第94页/共147页2消除回溯 在自顶向下分析过程中，当某个非终结符A对应多个候选式时，如果其中有几个候选式的左端第一符号相同，那么就会使得语法分析程序无法根据当前要替换的非终结符和当前输人符唯一地决定选用哪个候选式来替换A，只能采用试探的办法

41、，任选某个候选式去试探一次。如果不能导致最终正确地匹配，只得再换另一个候选式去试探，从而引起回溯。第95页/共147页 在自顶向下分析过程中，由于回溯需要推翻前面的分析，包括已做的一大堆语义工作，重新去进行试探，这样大大降低了语法分析器的工作效率，因此，需要消除回溯。 对于上述情况（即，同一非终结符有多个候选式的首符相同），可以采用提“左因子”的方法来改造文法，使得文法的每个非终结符的各个候选式的首符都不相同，从而可以消除上面所说的回溯现象。第96页/共147页提取公共左因子 若A的产生式为： A1|2 经过提取公共左因子，原产生式变为： AA A1|2 第97页/共147页一般情况 若A的产

42、生式为： A1|2|k-1 |k 经过提取公共左因子，原产生式变为： AA A1|2|k-1 |k 如果m、n（其中1m、nk）中仍然含有公共左因子，则可反复提取它们的共同左因子，直到每个新引入的非终结符的产生式再无公共左因子为止。 第98页/共147页示例【 例415】前面例46中的文法G6S为： Sx A y A * * | * 关于A的产生式有公共左因子，提取公共左因子a后，文法改写为：Sx A yA * AA * |第99页/共147页计算该文法的可选集 SELECT（Sx A y）x SELECT（A* A）* SELECT（A*）* S E L E C T （ A ） F O L

43、LO W （ A ） FOLLOW（A）y 因为：SELECT（A*）SELECT（A）*y 所以，上述文法是LL（1）文法，这时再用自顶向下分析方法分析符号串x*y，就不会产生回溯了。第100页/共147页示例【例415】设有文法G13S为： Sa S b Sab 关于S的产生式有公共左因子，提取公共左因子a后，文法改写为： Sa（S b |b） 进一步变换为文法G13 S,其产生式为： Sa S SS b |b第101页/共147页计算该文法的可选集 SELECT（Sa S）a SELECT（SS b）FIRST（Sb）FIRST（S）a SELECT（Sb）b 因为： SELECT（SS

44、b）SELECT（Sb）ab 所以，上述文法是LL（1）文法，可以进行确定的自顶向下的语法分析。 第102页/共147页三、确定的自顶向下分析方法 特征根据下一个输入符号为当前要处 理的非终结符选择产生式 要求文法是LL(1)的 语法分析方法： 1 递归下降分析法 2 预测分析法第103页/共147页1.递归下降分析法 递归子程序法是比较简单直观易于构造的一种语法分析方法。 实现思想：文法中每个非终结符对应一个递归过程(子程序)，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时能够按LL(1)形式可唯一地确定选择某个候选式进行推导。第104页/共147页示例【例41

45、0】算术表达式文法G7E： EE +T | T TT * F | F Fi |（E） 消除直接左递归后，文法变成： ETE E+T E| TFT T * FT| Fi |（E）第105页/共147页计算FIRST集与FOLLOW集 各非终结符的FIRST集为： FIRST(E)=(,i FIRST(E)=+ FIRST(T)=(,i FIRST(T)=* FIRST(F)=(,i 各非终结符的FOLLOW集合为： FOLLOW(E)=), FOLLOW(E)=)， FOLLOW(T)=，)， FOLLOW(T)=,)，# FOLLOW(F)=*,，),#第106页/共147页计算SELECT集

46、 各产生式的 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 第107页/共147页该文法是LL(1)文法 因为： SELECT(E十TE)SELECT(E) SELECT(T * FT)SELECT(T) SELECT(F（E）)SELECT(Fi) 所以，该文法中关于同一个非终结符的产生式的SELECT集两两不相交，因此

47、，该文法是LL（1）文法，可以进行确定的自顶向下语法分析。第108页/共147页递归子程序E ETE 非终结符E对应的子程序为： E( ) T( ); E ( ); 第109页/共147页递归子程序E E+T E| 非终结符E对应的子程序为： E ( ) if sym+ read(sym);T( ); E ( ); else if symFOLLOW(E) return; else error( ); 第110页/共147页递归子程序T TFT 非终结符T对应的子程序为： T( ) F( ); T ( ); 第111页/共147页递归子程序T T * FT| 非终结符T对应的子程序为： T (

48、 ) if sym* read(sym);F( ); T ( ); else if symFOLLOW(T) return; else error( ); 第112页/共147页递归子程序F Fi |（E） 非终结符F对应的子程序为： F ( ) if sym=i read(sym); else if sym ( read(sym); E( ); if sym) read(sym); else error( ); 第113页/共147页主程序 main( ) read(sym); E( ); if (sym= =# ) printf(“分析成功”)； else printf(“分析失败”)；

49、第114页/共147页示例【例411 】算术表达式的文法G7E：E ET|TT T*F| FF i |（E） 对文法G7用扩充BNF表示法对其进行改写成如下形式： E T + T T F * F F i |（E）第115页/共147页递归子程序E E T + T 非终结符E对应的子程序为： E( ) T( ); while (sym= =+) read(sym); T( ); 第116页/共147页递归子程序T T F * F 非终结符T对应的子程序为： T( ) F( ); while (sym= =*) read(sym); F( ); 第117页/共147页递归子程序F Fi |（E）

50、非终结符F对应的子程序为： F ( ) if sym=i read(sym); else if sym ( read(sym); E( ); if sym) read(sym); else error( ); 第118页/共147页主程序 main( ) read(sym); E( ); if (sym= =# ) printf(“分析成功”)； else printf(“分析失败”)； 第119页/共147页2.预测分析法 预测分析法用一个分析栈存放当前要替换的非终结符的某个候选式的符号串（倒放在栈内），当非终结符呈现在栈顶时，它就是当前非终结符；此外，还使用一张矩阵形式的预测分析表，它是根

51、据可选集构造的，它的入口指出了某非终结符和某终结符匹配时所应选择的候选式和语义动作。预测分析程序的总控程序就是利用栈顶符号和当前输人符号对输人串进行预测分析，而预测的信息则存放在预测分析表的相应入口里。第120页/共147页 一个预测分析程序是由三个部分组成总控程序（表驱动程序）预测分析表先进后出的语法分析栈第121页/共147页预测分析程序的模型 预测分析程序实际上就是一个下推自动机，它是用下推自动机来识别输入符号串的。 a a1 1 a a2 2 a ai i a an n # #输入串输入串总控程序总控程序预测分析表预测分析表（LL(1)LL(1)分析表）分析表）栈顶符号栈顶符号# #x

52、 x1 1x xn n 分析栈分析栈第122页/共147页预测分析法表(LL(1)LL(1)分析表) ) 表示:一个矩阵（或二维数组）MA ，a 行:对应文法的一个非终结符A 列:对应一个终结符a或输入结束符“”。 大小: mn, m是文法中非终结符数，n是终结符数1（外加一个结束符“”）。 数组的值MA ，a ：存放着面临输人符号a时，所应选择A的某条产生式，即指出当前推导所应使用的产生式。数组中的空白入口中应填人适当的出错处理子程序名或编号，即此种情况下存在语法错误。第123页/共147页预测分析表的构造 预测分析法的实现关键在于预测分析表。 预测分析表是指分析栈中的文法符号与输入串中的符

53、号的一种匹配关系，记为MA，a，其中A为分析栈中的符号，a为输入符号。 可以由可选集直接来构造预测分析表。第124页/共147页预测分析表的构造算法 预测分析表的构造算法是：对每个终结符aSELECT（A），把A填入MA，a中；把所有无定义的MA，a均填上“出错标志”。 第125页/共147页结论 上述算法可应用于任何文法G以构造它的分析表M。但对于某些文法，有些MA，a中可能有若干个产生式，或者说有些MA，a可能是多重定义的。如果G是左递归或回溯的，那么M至少含有一个多重定义入口。因此，消除左递归和提取公共左因子将有助于获得无多重定义的分析表M。 可以证明： 一个文法G的预测分析表M不含多重

54、定义入口，当且仅当该文法是LL（l）文法。第126页/共147页示例【例419】前述算术表达式的文法G7E为： E TE E 十TE| T FT T *FT| F i |（E）第127页/共147页表达式文法的预测分析表 i+* *()#EETEETEEE+TEEETTFTTFTTTT* *FTTTFFiF(E)第128页/共147页预测分析程序的工作流程 预测分析程序在总控程序控制下进行对输入串的分析，利用分析栈记录分析过程中使用的文法符号。输入串中存放的终结符号串，分析栈中存放的是终结符和非终结符组成的符号串。 第129页/共147页预测分析表的工作流程-1 分析开始时，首先将栈底符号“”

55、及文法的开始符号S依次推入分析栈的栈底，并对各条指示器置初值，此时分析栈和输入串的格局为(用箭头表示输入串指针和栈顶指针当前所指向的位置) ：#S栈顶指针栈顶指针 a1 a2 an #输入串指针输入串指针 第130页/共147页预测分析表的工作流程-2 设在分析的某一步，分析栈和余留的输入符号串处于如下的格局： #X1 X2Xm-1 Xm 栈顶指针栈顶指针 a1 ai ai+1 an# 输入串指针输入串指针 此时，可根据栈顶的文法符号此时，可根据栈顶的文法符号X Xm m的不同的不同情况，分别处理：情况，分别处理： 第131页/共147页情形一若Xm为终结符，即xmVT，且Xmai“”时，则表

56、明栈顶符号已与当前正扫视的输入符号相匹配，此时应将Xm从栈中弹出，而且将输入指针向前移动一个位置至ai1。从而得到如下格局：a1 ai ai+1 an# 输入串指针输入串指针 #X1 X2Xm-1 栈顶指针栈顶指针 第132页/共147页情形二若Xm为非终结符，即X mVN，则以 Xm及 ai组成符号对（Xm，ai）查分析表 M，假设MXm，ai中存放着关于Xm的一个产生式Xm ABC，此时，首先将Xm从分析栈中弹出，并将该产生式右部ABC的逆替换栈顶符号，即把ABC按逆序推入栈中（此即用该产生式推导一步）。输入指针不动。从而得到新的格局如下： 否则出错，即MXm，ai“ERROR”，则调用出错处理程序来进行处理或宣告分析失败。 a1 ai ai+1 an# 输入串指针输入串指针 #X1 X2Xm-1 CB