编译原理 之 自顶向下语法分析方法.ppt

1、第五章自顶向下语法分析方法,本章要点LL(1)分析First集合和Follow集合使用递归下降分析算法进行自顶向下的分析预测分析程序非LL(1)文法的改造,自上而下分析算法,自顶向下分析法也称面向目标的分析方法,也就是从文法的开始符号出发企图推导出与输入的单词串完全匹配的句子,若输入串是给定的句子,则必能推出,反之必然出错。自顶向下分析法又分为确定的和不确定的两种。,5.1确定的自顶向下分析思想,确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树。,例5.1,若有文法G1S：SpA|

2、qBAcAd|aBdB|b若输入串W=pccadd。自顶向下推导过程为S=pA=pcAd=pccAdd=pccadd,这个文法有以下两个特点：,每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。,例5.2,若有文法G2S为：SApSBqAaAcABbBdb,当输入串W=ccap，那么试图推出输入串的推导过程为：S=Ap=cAp=ccAp=ccap,例5.2文法的特点是：,产生式的右部不全是由终结符开始如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。文法中无空产生式,定义5.1,设G=(VT,VN,P，S)是上下文无关文法FIR

3、ST（）=a|a,aVT,V*若则规定FRIST（）不难求出在文法G2中FIRST(Ap)=a,cFIRST(Bq)=b,d,例5.3,若有文法GS:SaASdAbASA若输入串W=abd，则试图推导出abd串的推导过程为：S=aA=abAS=abS=abd,从例5.3可以得出下列结论,当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。,定义5.2,设G=(VT,VN,P，S)是上下文无关文法,AVN,S是文法开始符号FOLLOW(A)=aSA且aVTaFRIST()，V*

4、，V+若SA,且，则#FOLLOW(A),定义5.3,给定上下文无关文法的产生式A,AVN,V*,若*，则SELECT(A)=FIRST()如果，则SELECT(A)=(FIRST()-)FOLLOW(A),定义5.4,一个上下文无关文法是LL（1）文法的充分必要条件是，对每个非终结符A的两个不同产生式，A，A，满足SELECT(A)SELECT(A)=其中、不能同时。,LL(1)文法的含义：,第1个“L”指的是由左向右地处理输入。第2个“L”指的是它为输入串描绘出一个最左推导。括号中的数字1意味着它只需向右看一个符号便可决定如何推导即选择哪个产生式（规则）进行推导。,例5.3的文法,SaAS

5、dAbASA,不难看出：SELECT(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,#所以SELECT(SaA)SELECT(Sd)=SELECT(AbAS)SELECT(A)=,例5.4,设文法GS为：SaASSbAbAA,则SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,bSELECT(SaAS)SELECT(Sb)=SELECT(AbA)SELECT(A),5.2LL(1)文法的判别,1求出推出的非终结符2计算FIRST集3计算FOLLOW集4计算SELECT集,1求出推出的非终结符,扫描

6、文法中的产生式删除所有右部含有终结符的产生式,若这使得以某个非终结符为左部的所有产生式都被删除，说明该非终结符不能推出.若某个非终结符的某个产生式的右部为,说明该非终结符能推出.删除以该非终结符为左部的所有产生式.扫描产生式右部的每一个符号若扫描到的非终结符能推出,则删除该非终结符，如这样使产生式右部为空，说明该非终结符能推出.删除以该非终结符为左部的所有产生式.若扫描到的非终结符不能推出,则删除该产生式，如这样使以该非终结符为左部的所有产生式都被删除，说明该非终结符不能推出.重复，直到扫描完文法的产生式，数组中非终结符的特征在没有改变为止.,例5.5若文法GS为：,SABSbCAAbBBaD

7、CADCbDaSDc,SABABCAD,SABCAD,CAD,Step1,Step2,Step3,定义法：求文法符号FIRST(X),若XV，则FIRST(X)=X；若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若XVN，X也是一条产生式，则把也加到FIRST(X)中；若XVN，XY1Y2Yn是一个产生式，Y1,Y2,Yi-1(1in)都是非终结符，而且对于任何j，1ji-1,FIRST(Yj)都含有(即Y1，.，Yi-1)，则把FIRST(Yj)（1ji-1）中的所有非元素以及FIRST(Yi)，都加到FIRST(X)中；在(d)中，若所有的FIRST(Yj,j=1,2,n)均能

8、推出，则FIRST(X)=FIRST(Y1)FIRST(Y2)FIRST(Yn)。反复使用上述(b)-(e)步骤，直到每个符号的FIRST集合不再增大为止。,求符号串的FIRST(),=Y1Y2Yn当Y1*时，FIRST()=FIRST(Y1).对于任何j，1ji-1,2in，FIRST(Yj)都含有(即Y1，.，Yi-1)，则:FIRST()=(FIRST(Y1)-)(FIRST(Yi-1)-)FIRST(Yi).当所有Yi（1in），则FIRST()=FIRST(Y1)FIRST(Yn).,例5.5若文法GS为：,SABSbCAAbBBaDCADCbDaSDc,文法GS的每个非终结符的FI

9、RST集：FIRST(S)=FIRST(A)FIRST(B)=a,b,FIRST(A)=b,FIRST(B)=a,FIRST(C)=(FIRST(A)-)FIRST(D)bFIRST(D)=a,cFIRST(C)=a,b,c,例5.5若文法GS为：,SABSbCAAbBBaDCADCbDaSDc,文法GS的每个产生式右部符号串的FIRST集：FIRST(AB)=FIRST(A)FIRST(B)=a,b,FIRST(bC)=bFIRST()=FIRST(b)=bFIRST(aD)=aFIRST(AD)=(FIRST(A)-)FIRST(D)=a,b,cFIRST(aS)=aFIRST(c)=c,

10、关系图法：求文法符号FIRST(X),文法符号X对应图中一个结点，若XV，用X表示；若XVN，用FIRST(X)表示。若X是文法的一个产生式,且，则FIRST(A)FIRST(X),XVN;或FIRST(A)X,XVT.凡是从FIRST(A)结点有路径可到达的终结符结点的终结符都属于FIRST(A).A，则FIRST(A)=FIRST(A),例5.5若文法GS为：（关系图法）,SABSbCAAbBBaDCADCbDaSDc,FIRST(S),FIRST(A),FIRST(B),b,a,FIRST(C),FIRST(D),c,FIRST集：FIRST(S)=a,b,FIRST(A)=b,FIRS

11、T(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c,3计算FOLLOW集,(1)定义法：对于文法的开始符号S,置#于FOLLOW(S)中；若B是一个产生式,则把FIRST()-加至FOLLOW(B)中；如，则把FOLLOW（A）加至FOLLOW(B)中；这是因为当有形如：D1A1，B的产生式，A,B,DVN，1,1,V*,在推导过程中可能出现如下的句型序列：S1A1=1B1=1B1有：FOLLOW(A)FOLLOW(B)反复使用(b)步骤，直到每个非终结符号的FOLLOW集合不再增大为止。,例5.5若文法GS为：,SABSbCAAbBBaDCADCbDaSDc,文法GS的每个非

12、终结符的FOLLOW集：FOLLOW(S)=#FOLLOW(D)FOLLOW(A)=FIRST(B)-FOLLOW(S)FIRST(D)FOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FOLLOW(B)FOLLOW(C)FOLLOW(S)=#;FOLLOW(A)=a,#,cFOLLOW(B)=#;FOLLOW(C)=#FOLLOW(D)=#,(2)关系图法：S是开始符号，FOLLOW(X)#.若BX是文法的一个产生式,且，则FOLLOW(B)FIRST(X),XVN;或FOLLOW(B)X,XVT.若B是文法的一个产生式,且，则FOLLOW(B)

13、FOLLOW(A).对图中每个FIRST(A)结点，若X是文法的一个产生式,且，则FIRST(A)FIRST(X),XVN;或FIRST(A)X,XVT.凡从FOLLOW(A)结点有路径可到达的终结符或#的结点，其标记的终结符或#都属于FOLLOW(A).,例5.5若文法GS为：（关系图法）,SABSbCAAbBBaDCADCbDaSDc,FOLLOW(A),FIRST(B),FOLLOW(S),a,c,FOLLOW集：FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#,FOLLOW(B),FOLLOW(C),FOLLOW(D

14、),FIRST(D),#,4计算SELECT集,给定上下文无关文法的产生式A,AVN,V*,若*，则SELECT(A)=FIRST()如果，则SELECT(A)=(FIRST()-)FOLLOW(A),FOLLOW集：FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#,文法GS的每个产生式右部符号串的FIRST集：FIRST(AB)=FIRST(A)FIRST(B)=a,b,FIRST(bC)=bFIRST()=FIRST(b)=bFIRST(aD)=aFIRST(AD)=(FIRST(A)-)FIRST(D)=a,b,cFI

15、RST(aS)=aFIRST(c)=c,文法GSSABSbCAAbBBaDCADCbDaSDc,文法GS的SELECT集：SELECT(SAB)=(FIRST(AB)-)FOLLOW(S)=a,b,#SELECT(SbC)=FIRST(bC)=bSELECT(A)=(FIRST()-)FOLLOW(A)=a,c,#SELECT(Ab)=FIRST(b)=bSELECT(B)=(FIRST()-)FOLLOW(B)=#SELECT(BaD)=FIRST(aD)=aSELECT(CAD)=FIRST(AD)=a,b,cSELECT(Cb)=FIRST(b)=bSELECT(DaS)=FIRST(a

16、S)=aSELECT(Dc)=FIRST(c)=c,相同左部产生式的SELECT集的交集为：SELECT(SAB)SELECT(SbC)=bSELECT(A)SELECT(Ab)=SELECT(B)SELECT(BaD)=#a=SELECT(CAD)SELECT(Cb)=a,b,cbSELECT(DaS)SELECT(Dc)=ac=关于S和C的相同左部，其产生式的SELECT集的交集不为空，该文法不是LL(1)文法.,5.3某些非LL(1)文法到LL(1)文法的等价变换,提左公因子A|A(|)消除左递归,例5.6若文法G1的产生式为：,SaSbSaSS,对产生式(1)、(2)提取左公共因子后得

17、SaS(b|)S,进一步变换后为文法G1:SaSAAbAS,例5.7若文法G2的产生式为：,AadABcBaABbB,对右部以非终结符开始的产生式，用其相同左部而右部以终结符开始的产生式进行相应替换,(1)Aad(2)AaAc(3)AbBc(4)BaA(5)BbB,提取产生式(1)、(2)的左公共因子得：,Aa(d|Ac)AbBcBaABbB,引进新非终结符A后得G2：,AaAAbBcAdAAcBaABbB不难验证：G1仍不是LL(1)文法，而G2不是LL(1)文法.因此不含左公因子只是LL(1)文法的必要条件，不是充分条件.,文法G5含有直接左递归SSaSb为了消除左递归，将这个文法规则重写

18、为两个规则：SbSSaS|这两个文法表示的语言：ban|n0,不难验证改写后的文法为LL(1)文法.,情况1：简单直接左递归,情况2：普遍的直接左递归,这种情况发生在有如下格式的产生式AAa1|Aa2|.|Aam|b1|b2|.|bn中。其中a1,.,am不等于，b1,.,bn均不以A开头。在这种情况下，其解法与简单情况类似，只需将选择相应地扩展：Ab1A|b2A|.|bnAAa1A|a2A|.|amA|,情况3：消除间接左递归,先将间接左递归变为直接左递归，然后再消除直接左递归。,例消除下列文法中的左递归,AaBABbBAcBd,用产生式(1)、(2)的右部代替产生式(3)的右部得到：BaB

19、cBBbcBd,消除左递归后得：B(aBc|d)BBbcB|,将原来的产生式AaB,ABb加入，最终文法为：(1)AaB(2)ABb(3)B(aBc|d)B(4)BbcB|,需要验证改写后的文法是否为LL(1)文法？,5.5确定的自顶向下分析方法,特征根据下一个输入符号为当前要处理的非终结符选择产生式要求文法是LL(1)的预测分析程序的实现技术1预测分析法2递归子程序法,预测分析方法,一个预测分析器是由三个部分组成：预测分析程序先进后出栈预测分析表其中预测分析表可用一个矩阵M表示。矩阵的元素MA,a中的内容为一条关于A的产生式，表明当用非终结符A向下推导面临输入符a时，所应采取的候选产生式，当

20、元素内容无产生式时，则出错。,预测分析程序的框图,构造预测分析表,对每个终结符或“#”号用a表示。若aSELECT(A)，则把A放入MA,a中。把所有无定义的MA，a标上出错标记。,以表达式文法为例构造预测分析表：,GE:ETEE+TEETFTT*FTTF(E)Fi,GE:EE+T|TTT*F|FT*FTFi|(E),(1)判断文法是否LL(1)？,消除左递归,GE:ETEE+TEETFTT*FTTF(E)Fi,FIRST(E),Step1.判断是否LL(1)文法,可推出的非终结符表,非终结符FIRST集,FIRST(T),FIRST(E),+,FIRST(F),FIRST(T),*,(,i,

21、FIRST(E)=(,i,FIRST(T)=(,i,FIRST(F)=(,i,FIRST(E)=+,FIRST(T)=*,.,GE:ETEE+TEETFTT*FTTF(E)Fi,非终结符FOLLOW集,FOLLOW(E),#,FOLLOW(T),FIRST(E),FOLOW(E),FOLLOW(F),FIRST(T),FOLLOW(T),),+,*,FOLLOW(E)=),#,FOLOW(E)=),#,FOLOW(T)=),#,+,FOLOW(T)=),#,+,FOLOW(F)=),#,+,*.,GE:ETEE+TEETFTT*FTTF(E)Fi,各产生式的SELECT集,SELECT(ETE

22、)=(,iSELECT(E+TE)=+SELECT(E)=),#SELECT(TFT)=(,iSELECT(T*FT)=*SELECT(T)=),#,+SELECT(F(E)=(SELECT(Fi)=i,相同左部其产生式的SELECT集的交集为空,所以该文法是LL(1)文法.,Step1.构造预测分析表对每个非终结符或#用a表示,若aSELECT(Aa),则把Aa放入MA,a中,把所有无定义的MA,a标记出错.,表达式文法GE的预测分析表,对输入串i+i#的分析过程,递归子程序法,它的实现思想是对应文法中的每个非终结符编写一个递归过程，每个递归过程的功能是识别由该终结符推出的串，当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。,例如，考虑表达式文法：,expexpaddopterm|termaddop+|-termtermmulopfactor