资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,自顶向下语法分析方法,第,4,章,4.1 确定的自顶向下分析思想,确定的自顶向下分析方法,首先要解决从文法的开始符号出发,如何,根据当前的输入符号(单词符号)唯一地确定选用哪个产生式,替换相应非终结符往下推导,或构造一棵相应的语法树。,例,4.1,设文法,G1S,:,S,pA|qBA cAd|aB dB|b,考虑对输入串,w=pccadd,的分析。,这个文法有以下两个特点:,每个产生式的右部都由终结符号开始。,如果两个产生式有相同的左部,那么它们的右部由不同的终结符开始。,这个文法有以下两个特点:,产生式的右部不全是由终结符开始,如果两个产生式有相同的左部,它们的右部是由不同的终结符或非终结符开始。,文法中无空产生式,定义,4.1,设,G=(V,T,V,N,P,,,S),是上下文无关文法,FIRST(,)=a|a,a,V,T,V*,若,,则规定,FRIST(,),。如:,FIRST(Ap)=a,cFIRST(Bq)=b,d,例,4.3,设文法,GS,:,S,aASdAbASA,考虑对输入串,w=abd,的分析。,定义,4.2,设,G=(V,T,V,N,P,S),是上下文无关文法,对,A,V,N,定义,FOLLOW(A)=aS A,且,a,V,T,,,a,FRIST(,),,,V,*,,,V,+,若,S,uA,,,且,,则规定,#F,OLLOW(A),如:,F,OLLOW(A)=FIRST(S)#=a,d,#,定义,4.3,给定上下文无关文法的产生式,A,,,AV,N,,,V,*,若,,则,SELECT(,A,)=FIRST(),若如果,,则,SELECT(,A,)=(FIRST()-)FOLLOW(A),LL(1),文法的含义,第,1,个“,L”,指的是由左向右地处理输入。,第,2,个“,L”,指的是它为输入串描绘出一个最左推导。,括号中的数字,1,意味着它只需向右看,1,个符号便可决定如何推导即选择哪个产生式(规则)进行推导。,例:设文法,GS,为,:SABSbCA,AbB,B,aD,C,AD,C,bDaS,D,c,判断它是否是,LL(1),文法。,1.求出能推出的非终结符,SAB,SbC,A,Ab,B,BaD,CAD,Cb,DaS,Dc,非终结符,S,A,B,C,D,初值,未定,未定,未定,未定,未定,第一次扫描,是,是,否,第二次扫描,是,否,用关系图法求文法符号的FIRST集(自学),3.计算FOLLOW集,根据定义计算,1.,对于文法的开始符号,S,置,#,于,FOLLOW(S),中,;2.,若,B,是一个产生式,则把,FIRST()-,加至,FOLLOW(B),中,;3.,若,B,是一个产生式,或,B,是一个产,生式而,,则把,FOLLOW(A),加至,FOLLOW(B),中,用关系图法求非终结符的FOLLOW集(自学),4.计算SELECT集,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,5.判别是否是LL(1)文法,所以文法,GS,不是,LL(1),文法。,1.提取左公共因子,例,4.6,文法,G1S:,SaSbSaS,S,化为:,SaS,(b|),S,进一步化为:,SaS,A,Ab,A,S,结果仍然不是,LL(1),文法。因此,文法中不含左公共因子只是,LL(1),文法的必要条件。,A,1,|,2,|,n,变换为,A(,1,|,2,|,n,),,即,AA,A ,1,|,2,|,n,例4.7文法G2A:AadABcBaABbB,1.,化为:,Aad,A,aAc,A,bBc,BaABbB,2.,化为:,Aa(d|Ac),AbBc,BaABbB,3.,化为:,AaA,AbBc,Ad,AAc,BaABbB,例4.9文法G4S:SAp|BqAaAp|dBaBq|e,1.,化为:,S,aApp|aBqq,|dp|eqAaAp|dBaBq|e,2.,化为:,Sa(App|Bqq),Sdp|eq,AaAp|dBaBq|e,3.,化为:,SaS,Sdq|eq,SApp|Bqq,AaAp|dBaBq|e,4.,化为:,SaS,Sdp|eq,S,aAppp|aBqqq,|dpp|eqqAaAp|dBaBq|e,结论,不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。,一个文法提取了左公共因子后,只解决了相同左部产生式右部的,FIRST,集不相交问题,当改写后的文法不含空产生式,且无左递归时,则改写后的文法是,LL(1),文法,否则还需用,LL(1),文法的判别方式进行判断才能确定是否为,LL(1),文法。,例,4.10G5S:SSaSb,考虑对输入串,baaaa#,的分析,例,4.11G6A,:,AaBABbBAcBd,考虑对输入串,adbcbcbc#,的分析,SbSSaS|,BaBcBBbcBd,BaBcB|dB BbcB|,消除直接左递归,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,|,消除间接左递归,将间接左递归变为直接左递归,然后消除直接左递归。,消除文法中一切左递归的算法,1.,以某种顺序将文法非终结符排列,A,1,A,2,A,n,2.,for i:=1 to n do,begin,for j:=1 to i-1 do,用,A,j,-,1,|,2,|,k,关于,A,j,的全部产生式替代,形如,A,i,-A,j,r,的,产生式为,:,A,i,-,1,r,|,2,r|,k,r;,end;,消除,A,i,的直接左递归,;,3.,化简由,2,得到的文法,例,文法,GS:,SQc|c,QRb|b,R,Sa,|a,R,Qca,|ca,|a,R,Rbca|bca|ca,|a,R(bca|ca|a)R,R bcaR|,将非终结符排序为,S,、,Q,、,R,4.5 LL(1)分析的实现,递归下降LL(1)分析程序,表驱动LL(1)分析程序,4.5.2表驱动LL(1)分析程序,一个预测分析器是由三个部分组成,预测分析程序,符号栈,预测分析表,预测分析程序,预测分析表,输入单词流,符号栈,ip,top,输出,预测分析表,预测分析表可用一个矩阵,M,表示。矩阵的元素,MA,a,中的内容为一条关于,A,的产生式,表明当用非终结符,A,向下推导且面临输入符,a,时,所应采取的候选产生式,当元素内容无产生式时,则出错。,一个文法的预测分析表不含有多重入口,当且仅当该文法是,LL(1),的。,预测分析表的构造算法,若,a,SELECT(A),,则把,A,放入,MA,a,中。,把所有无定义的,MA,,,a,标上出错标记。,例文法,GE,:,E TEE+TE|,T FTT*FT|,F i|(E),构造过程:,1.,判断文法是否为,LL(1),文法,2.,构造预测分析表,预测分析程序算法,分析栈,#E,#ET,#ETF,#ET,i,#ET,#E,#ET,+,#ET,#ETF,#ET,i,#ET,#ETF,*,#ETF,#ET,i,#ET,#E,#,剩余串,i+i*i#,i+i*i#,i+i*i#,i,+i*i#,+i*i#,+i*i#,+,i*i#,i*i#,i*i#,i,*i#,*i#,*,i#,i#,i,#,#,#,#,产生式,ETE,TFT,F i,i,匹配,T,E,+TE,+,匹配,T FT,F i,i,匹配,T *FT,*,匹配,F i,i,匹配,T,E,接受,例对输入串,i+i*i,的分析,4.5.1,递归下降,LL(1),分析程序(自学),实现思想,对文法中每个非终结符编写一个递归过程,每个过程的功能是识别由该非终结符推出的串,当某非终结符的产生式有多个候选时能够按,LL(1),形式可唯一地确定选择某个候选进行推导。,限制,对文法要求高,必须满足,LL(1),文法;,速度慢,占用空间多。,
展开阅读全文