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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第4章 自顶向下语法分析方法,确定的自顶向下分析思想,文法,G1S:SpASqBAcAdAaBdBBb,W=pccadd,自顶向下的推导过程：,S,pA pcAd pccAdd pccadd,语法树：,S,p,A,S,p,A,c,A,d,S,p,A,c,A,d,c,A,d,S,p,A,c,A,d,c,A,d,a,2,这个文法的特点：,每个产生式的右部都由,终结符号,开始。,如果两个产生式有相同的左部，那么它们的右部由,不同的,终结符开始。,文法,G1S:SpASqBAcAdAaBdBBb,3,文法,G2S:SApSBqAaAcABbBdB,W=ccap,自顶向下的推导过程：,S,Ap cAp ccAp ccap,语法树：,S,A,p,S,A,p,c,A,S,A,p,c,A,c,A,S,A,p,c,A,c,A,a,4,这个文法的特点：,每个产生式的右部不全是由,终结符号,开始。,如果两个产生式有相同的左部，那么它们的右部由,不同的,终结符,或,非终结符,开始。,文法中无空产生式。,文法,G1S:SApSBqAaAcABbBdB,5,定义：设,G=(V,T,V,N,S,P),是上下文无关文法，,FIRST(),=a|,a,a V,T,V*,若,，,则规定,FIRST(),*,*,调用返回,6,FIRST(Ap)=a,c,FIRST(Bq)=b,d,文法,G2S:SApSBqAaAcABbBdB,7,文法,G3S:SaASdAbASA,W=abd,试图,推导的过程：,S,aA abAS abS abd,8,大家学习辛苦了，还是要坚持,继续保持安静,9,定义：设,G=(V,T,V,N,S,P),是上下文无关文法，,AV,N,S,是开始符号。,FOLLOW(A),=,a|,S A,且,a,FRIST(,),V,T,*,V,+,若,S A,且,，则规定#,FOLLOW(A),即：,FOLLOW(A)=a|S Aa,a,V,T,若,S A，,则规定#,FOLLOW(A),#作为输入串的结束符，或称为句子括号，如：#输入串#,*,*,*,*,*,调用返回,10,对,AA,其中,AV,N,V,N,*,当,和,不同时推导出空时（设,不推导出空，,推导出空），则当,FIRST()(FIRST()FOLLOW(A)=,时，对于非终结符,A,的替换仍可唯一地确定候选。,11,定义：给定上下文无关文法的产生式,A，AV,N,V*，,若,，,则,SELECT(A),=FIRST(),如果,，,则,SELECT(A),=FIRST()FOLLOW(A),*,*,调用返回,12,定义：一个上下文无关文法是,LL(1),文法,的充要条件是：对每个非终结符,A,的两个不同产生式,A,和,A，,满足,SELECT(A)SELECT(A)=,其中,不同时能,*,13,LL(1),文法的含义：,第一个,L,表示：自顶向下分析是,从左向右扫描输入串,。,第二个,L,表示：分析过程中将用,最左推导,。,1,表示：只需,向右看一个符号,便可决定如何推导（即选择哪个产生式进行推导）。,类似也可以有,LL(K),文法：需向前查看,K,个符号才可确定选用哪个产生式。,14,文法,GS,是否是,LL(1),文法:,SaASdAbASA,SELECT(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,#,SELECT(SaA)SELECT(Sd)=a,d=SELECT(AbAS)SELECT(A)=ba,d,#,=,所以该文法是,LL(1),文法。,15,设文法,GS,为:,SaASSbAbAA,SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b,SELECT(SaAS)SELECT(Sb)=a,b=SELECT(AbA)SELECT(A)=ba,b,所以该文法不是,LL(1),文法。,16,GS,:,SaASSbAbAA,对输入串,W=ab,进行推导：,S,aAS abAS abS,出错,S,aAS aS ab,17,LL(1),文法的判别,求出能推出,的非终结符,计算,FIRST,集,计算,FOLLOW,集,计算,SELECT,集,判别是否是,LL(1),文法,18,例：设文法,GS,为:,SABSbCAAbBBaDCADCbDaSDc,判断它是否是,LL(1),文法。,19,1.求出能推出,的非终结符,SABSbCAAbBBaDCADCbDaSDc,20,2.计算,FIRST,集,1.若,X,V,则,FIRST(X)=X,2.,若,X,V,N,且有产生式,X,a,，,则,aFIRST(X),;若,X,也是一条产生式,则,FIRST(X),.,3.若,X,Y,是一个产生式且,Y,V,N,则把,FIRST(Y),中的所有非,元,素都加到,FIRST(X),中;若,X,Y,1,Y,2,Y,K,是一个产生式,Y,1,Y,2,Y,(i-1),都是非终结符,而且,对于任何,j,1,j,i,-1,FIRST(Y,j,),都含有,(即,Y,1,.Y,(i-1),),则把,FIRST(Y,j,),中的所有非,元素都加到,FIRST(X),中;特别是,若所有的,FIRST(Y,j,j=1,2,K),均含有,则把,加到,FRIST(X),中.,*,21,SABSbCAAbBBaDCADCbDaSDc,FIRST(S)=(FIRST(A)-)FIRST(B)-)b=a,b,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,c,FIRST(D)=a,c,FIRST(AB)=a,b,FIRST(AD)=a,b,c,22,3.计算,FOLLOW,集,1.对于文法的开始符号,S,置,#,于,FOLLOW(,S,),中;,2.若,B,是一个产生式,则把,FIRST(),加至,FOLLOW(B),中;,3.若,B,是一个产生式,或,B,是,一个产生式而,(,即,FIRST()），,则把,FOLLOW（A），,加至,FOLLOW（B）,中,*,23,SABSbCAAbBBaDCADCbDaSDc,FOLLOW(S)=#FOLLOW(D),FOLLOW(A)=aa,cFOLLOW(S),FOLLOW(B)=FOLLOW(S),FOLLOW(C)=FOLLOW(S),FOLLOW(D)=FOLLOW(B)FOLLOW(C),FOLLOW(S)=#,FOLLOW(A)=a,c,#,FOLLOW(B)=#,FOLLOW(C)=#,FOLLOW(D)=#,24,4.计算,SELECT,集,SABSbCAAbBBaDCADCbDaSDc,FIRST(S)=a,b,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,c,FIRST(D)=a,c,FIRST(AB)=a,b,FIRST(AD)=a,b,c,SELECT(SAB)=a,b,#,SELECT(SbC)=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,FOLLOW(S)=#,FOLLOW(A)=a,c,#,FOLLOW(B)=#,FOLLOW(C)=#,FOLLOW(D)=#,该文法不是,LL(1),文法。,25,某些非,LL(1),文法到,LL(1),文法的等价变换,提取左公共因子,消除左递归,26,提取左公共因子,A|,导致,SELECT(A)SELECT(A)，,因此非,LL(1),文法。,等价变换为,A(|)，,然后：,AAA|,A,1,|,2,|,n,变换为,A(,1,|,2,|,n,),，,然后：,AAA ,1,|,2,|,n,27,例：文法,G1S,为:,SaSbSaSS,化为：,SaS(b|)S,进一步化为：,SaSA,Ab,A,S,结果仍然不是,LL(1),文法。因此，文法中不含左公共因子只是,LL(1),文法的必要条件。,w=aabb,S=aSA=aaSAA=aaAA=aabA(aaA),28,例：文法,G2,为:,AadABcBaABbB,1.化为：,Aad,AaAc,AbBc,BaABbB,2.化为：,Aa(d|Ac),AbBc,BaABbB,3.化为：,AaA,AbBc,Ad,AAc,BaABbB,结果是,LL(1),文法。,29,例：文法,G3S,为:,SaSdSAcAaSAb,1.化为：,SaSdSaSc,Sbc,AaSAb,2.化为：,SaS(d|c)Sbc,AaSAb,3.化为：,SaSA,Sbc,Ad,Ac,AaSAb,结果中,A,是不可达到的符号。,30,例：文法,G4S,为:,SAp|BqAaAp|dBaBq|e,1.化为：,SaApp|aBqq|dq|eqAaAp|dBaBq|e,2.化为：,Sa(App|Bqq)Sdq|eq,AaAp|dBaBq|e,3.化为：,SaS,Sdq|eq,SApp|BqqAaAp|dBaBq|e,4.化为：,SaS,Sdq|eq,S aAppp|aBqqq|dpp|eqqAaAp|dBaBq|e,利用提取左公共因子无法在有限步骤内替换成无左公共因子的文法,31,结论,不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。,一个文法提取了左公共因子后，只解决了相同左部产生式右部的,FIRST,集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是,LL(1),文法，否则还需用,LL(1),文法的判别方式进行判断才能确定是否为,LL(1),文法。,32,消除左递归,直接左递归：,AA A,V,N,V*,间接左递归：,ABBA A,B,V,N,V*,33,文法,G5,含有直接左递归：,SSaSb,所能产生的语言,L=ba,n,|n0,输入串,baaaa#,是该语言的句子，但如何用自顶向下分析呢？,34,文法,G6,含有间接左递归：,AaBABbBAcBd,输入串,adbcbcbc#AaBadAaBaAcaBbcaAcbc,35,消除直接左递归,把直接左递归改写为右递归。如,G5:SSaSb(L=ba,n,|n0),改为：,SbSSaS|,36,消除直接左递归的一般方法：,AA,1,|A,2,|A,m,|,1,|,2,|,n,其中：,i,不等于,，,j,不以,A,开头。改为：,A,1,A|,2,A|,n,A A,1,A|,2,A|,m,A|,37,消除间接左递归,将间接左递归变为直接左递归，然后消除直接左递归。如文法,G6,含有间接左递归：,AaBABbBAcBd,BaBcBBbcBd,BaBcB|dB BbcB|,38,消除文法中一切左递归的算法,1.无回路(,A(A(A)2.,无空产生式,（1）,以某种顺序将文法非终结符排列,A,1,A,2,A,n,（2）,for i:=1 to n do,begin,for j:=1 to i-1 do,用,A,i,-,1,|,2,r|,k,r,替代,形如,A,i,-A,j,r,的规则,其中,A,j,-,1,|,2,|,k,是关于,A,j,的全部产生式;,消除,A,i,规则的直接左递归;,end;,（3）,化简由2得到的文法,+,39,例：,文法,G:SQc|cQRb|bRSa|a,R,Qca,|ca|a,R,Rbca|bca,|ca|a,R(bca|ca|a)R,R bcaR|,参考,P.84,40,不确定的自顶向下分析思想,1.由于相同左部的产生式的右部,FIRST,集交集不为空引起回溯。,SxAy,Aab|a,w=xay,S,x A y,S,x A y,a b,S,x A y,a,试探,回溯,试探,41,2.由于相同左部非终结符的右部能,且该非终结符,FOLLOW,集中含有其右部,FIRST,集的元素。,设文法,GS,为:,SaASSbAbASA,*,w=ab#,S,a A S,S,a A S,b A S,S,a A S,b,试探再试探,回溯,42,3.由于文法含有左递归而引起回溯。,设文法,GS,为:,SSaSb,w=baa#,S,b,S,S a,S,S a,b,S,S a,S a,S,S a,S a,b,43,确定的自顶向下分析方法,1.递归子程序法,实现思想：对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按,LL(1),形式可唯一地确定选择某个候选进行推导。,限制：对文法要求高，必须满足,LL(1),文法；由于递归调用多，速度慢，占用空间多。,44,2.预测分析法,预测分析器：,预测分析程序（,P.88）,先进后出栈,预测分析表,45,预测分析表的构造,表达式文法：,E E+T|T,T T*F|F,F i|(E),46,构造过程,1.判断文法是否为,LL(1),文法,消除左递归：,E E+T|T,T T*F|F,F i|(E),E TEE +TE|,T FTT *FT|,F i|(E),47,可推出,的非终结符表：,E TEE +TE|,T FTT *FT|,F i|(E),48,各非终结符的,FIRST,集和,FOLLOW,集：,FIRST(E)=(,i,FIRST(E)=+,FIRST(T)=(,i,FIRST(T)=*,FIRST(F)=(,i,FOLLOW(E)=),#,FOLLOW(E)=),#,FOLLOW(T)=+,),#,FOLLOW(T)=+,),#,FOLLOW(F)=*,+,),#,E TEE +TE|,T FTT *FT|,F i|(E),查看,FOLLOW,定义,查看,FIRST,定义,49,各产生式的,SELECT,集：,E TEE +TE|,T FTT *FT|,F i|(E),SELECT(E TE)=(,i ,SELECT(E +TE)=+,SELECT(E )=,),#,SELECT(T FT)=(,i ,SELECT(T *FT)=*,SELECT(T )=,+,),#,SELECT(F (E)=(,SELECT(F i)=i ,FIRST(E)=(,i,FIRST(E)=+,FIRST(T)=(,i,FIRST(T)=*,FIRST(F)=(,i,FOLLOW(E)=),#,FOLLOW(E)=),#,FOLLOW(T)=+,),#,FOLLOW(T)=+,),#,FOLLOW(F)=*,+,),#,查看,SELECT,定义,是,LL(1),文法。,50,2.构造预测分析表,SELECT(E TE)=(,i ,SELECT(E +TE)=+,SELECT(E )=,),#,SELECT(T FT)=(,i,SELECT(T *FT)=*,SELECT(T )=,+,),#,SELECT(F (E)=(,SELECT(F i)=i ,51,