第五章 自顶向下的语法分析方法5.1-5.2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章 自顶向下的语法分析方法,语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子,(,程序,),。,目前语法分析常用的方法有,:,1,、自顶向下（自上而下）分析,2,、自底向上（自下而上）分析,自顶向下分析法也就是,从文法的开始符号出发,企图,推导出与输入的单词串完全相匹配的句子,，若输入串是给定文法的句子，则必能推出，反之必然出错。,回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。,句型,:,有文法,GS,， 若,S x,，且,x V*,则称,x,是文法,GS,的句型。符号 表示经过,0,步或若干步的推导。,句子,:,有文法,GS,，若,S x,，且,xV,T,*,，,则称,x,是文法,GS,的句子。例：,GS,：,S0S1,，,S01,可有推导,S 0S1 00S11 000S111 00001111,说明,00001111,是,GS,的句子。,句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程,。,最左（最右）推导,：在推导的任何一步, ,，,都是对,中的最左（右）非终结符进行替换。,最右推导被称为规范推导。由规范推导所得的句型称为规范句型。,句型分析的有关问题, 如何选择使用哪个产生式进行推导？,假定要被替换的最左非终结符号是,V,，,且左部为,V,的规则有,n,条：,VA,1,|A,2,|A,n,，,那么如何确定用哪个右部去替换,V,呢？, 如何识别可归约的串？,在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。,5.1,确定的自顶向下分析思想,确定的自顶向下分析方法,:,从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号,(,单词符号,),唯一地确定选用哪个产生式替换相应非终结符以往下推导。,例,5.1,若有文法,G1S:,S ,pA,|,qB,A ,cAd|a,B d B |c,识别输入串,w=,pccadd,是否是,G1S,的句子,试探推导过程：,S,pA,pcAd,pccAdd,pccadd,试探成功。,例,5.1,若有文法,G1S:,S ,pA,|,qB,A ,cAd|a,B d B |c,这个文法有以下两个特点： 每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的,右部由不同的终结符开始。即每个产生式的右部的开始终结符不同,。,对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。,例,5.2,若有文法,G2S:,S ,Ap,|,Bq,A ,a|cA,B ,b|dB,识别输入串,w=,ccap,是否是,G2S,的句子，那么试探推出输入串的推导过程为 ：,S,Ap,cAp,ccAp,ccap,试探推导成功。,例,5.2,若有文法,G2S:,S ,Ap,|,Bq,A ,a|cA,B ,b|dB,此文法的特点是：, 产生式的右部不全是由终结符开始。 如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。, 文法中无空产生式。,例,5.2,若有文法,G2S:,S ,Ap,|,Bq,A ,a|cA,B ,b|dB,对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪个产生式不像例,5.1,文法那样直观，对于,W=,ccap,为输入串时，其第一个符号是,c,，这时从,S,出发选择,SAp,还是选择,SBq,，,需要知道，,Ap,或,Bq,它们的,开始终结符号集合,是什么？因为,c,是包含在,Ap,的,开始终结符号集合中,，且不包含在,Bq,的,开始终结符号集合中,，则选择,SAp,往下进行推导。,一个文法符号串的终结符的首符集,定义如下：,定义5.1,设G=(V,T,，V,N,，S，P)是上下文无关文法FIRST()=a| a,aV,T,，,V*若 ,则规定FIRST(),。,FIRST(Ap,)=a,c,FIRST(Bq,)=b,d,因此有,FIRST(Ap)(FIRST(Bq,)=,此时,可以根据当前的输入符号是属于哪个产生式的,FIRST,集而决定选择相应产生式进行推导，因此仍能构造确定的自顶向下分析。,例,5.2,G2,：,S ,Ap,|,Bq,A ,a|cA,B b|dB,例,5.3,若有文法,G3S:,S ,aA|d,A ,bAS|,识别输入串,w=,abd,是否是,G3S,的句子,试探推导出,abd,的推导过程为：,S,aA,abAS,abS,abd,试探推导成功。,当一个文法中相同左部非终结符的右部存在能,的情况则必须知道,该非终结符的后跟符号的集合中的符号是否可以唯一地确定选择哪个产生式。,一个文法非终结符的后跟符号的集合如下：,定义,5.2,：,设,G=(V,T,，,V,N,，,S,，,P),是上下文无关文法，,AV,N,，,S,是开始符号,FOLLOW(A)=,a|S,A,且,aV,T,，,aFIRST(),V,T,* ,V,+,若,S,A,且, ,则,#FOLLOW(A),。,也可定义为：,FOLLOW(A)=,a|S,Aa,a V,T,若有,S A,，则规定,#FOLLOW(A),这里我们用,#,作为输入串的结束符，或称为句子括号，如：,#,输入串,#,。,因此当文法中含有形如：,A,A,的产生式时，其中,AV,N,，,V,*,，当,不同时推导出空时，设,则当,FIRST(,)(,FIRST()FOLLOW(A,)=,时，对于非终结符,A,的替换仍可唯一地确定候选。,综合以上情况可定义,选择集合,SELECT,如下：,定义,5.3,给定上下文无关文法的产生式,A,AV,N,V,*,若, ,则,SELECT(A,)=,FIRST(,),如果, ,则：,SELECT(A,)=,（,FIRST(,) ,）,FOLLOW(A,),5.2 LL(1),文法的定义和判别,一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当某个非终结符能推出,时则与该非终结符的后跟符号集合也有关。综合以上两点，即一个文法能否用确定的自顶向下分析与产生式的,Select,集有关。此外在产生式中不存在左递归。,1,、,LL(1),文法的定义,定义,5.4,一个上下文无关文法是,LL(1),文法的充分必要条件是：对每个非终结符,A,的两个不同产生式，,A,A,满足,SELECT(A)SELECT(A,)=,其中,，,不同时能,LL(1),文法的含义：,第一个,L,从左到右扫描输入串,第二个,L,生成的是最左推导,1,向右看一个输入符号便可,决定选择哪个产生式。,例：判断下列文法是否是,LL(1),文法,G,：,S,aA,Sd,AbAS,A,解：,select(SaA,)=a,select(S d)=d,select (,SaA,),select(S d)=,select(AbAS,)=b,select(A,),=First(,)-,Follow(A),=Follow(A)=a,d,#,select (,AbAS,),select(A ,)=,所以，该文法是,LL,（,1,）,文法。,2,、,LL(1),文法的判别,当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是,LL(1),文法。因而我们对任给文法需计算,FIRST,、,FOLLOW,、,SELECT,集合，进而判别文法是否为,LL(1),文法。,（,1,）计算,FIRST,集,1.,若,X,V,T,，则,FIRST(X),X,。,2.,若,X,V,N,，且有产生式,Xa,，,a,V,T,则把,a,加入到,FIRST(X),中；,3.,若,X,是一条产生式，则把,加到,FIRST(X),中。,4.,若,XY,是一个产生式且,Y,V,N,，则把,FIRST(Y),中的所有非,-,元素都加到,FIRST(X),中；,5.,若,XY,1,Y,2,Y,k,是一个产生式，,Y,1,，,，,Y,i-1,都是非终结符，而且，对于任何,j,，,1,j,i-1,，,FIRST(Y,j,),都含有,(,即,Y,1,Y,i-1,),， 则把,FIRST(Y,i,),中的所有非,-,元素都加到,FIRST(X),中；特别是，若所有的,FIRST(Y,j,),均含有,，,j,1,，,2,，,，,k,，则把,加到,FIRST(X),中。,反复使用上述,(2),(5),步直到每个符号的,FIRST,集合不再增大为止。,例,5.5,若文法,GS,为：,SAB,SbC,A,Ab,B,BaD,CAD,Cb,DaS,Dc,求每个非终结符的,First,集。,FIRST(S)=FIRST(A),FIRST(B,),b,=,b,a,FIRST(A)=,b,=,b,FIRST(B),a,a,FIRST(C)=FIRST(A),FIRST(D)FIRST(b,)=,b,a,c,FIRST(D)=,ac,=,a,c,（,2,）计算,FOLLOW,集,对于文法,G,的每个非终结符,A,构造,FOLLOW(A),的办法是，连续使用下面的规则，直至每个,FOLLOW,不再增大为止：,1.,对于文法的开始符号,S,，置于,FOLLOW(S),中；,2.,若,A,B,是一个产生式，则把,FIRST(,)-,加至,FOLLOW(B),中；,3.,若,A,B,是一个产生式，或,A,B,是一个产生式而, ,(,即,FIRST(,),，,则把,FOLLOW(A),加至,FOLLOW(B),中。,例,5.5,若文法,GS,为：,SAB,SbC,A,Ab,B,BaD,CAD,Cb,DaS,Dc,求每个非终结符的,Follow,集。,FOLLOW(S)=# FOLLOW(D),#,FOLLOW(A)=(FIRST(B),), FOLLOW(S) FIRST(D),a,#,c,FOLLOW(B)=FOLLOW(S)=#FOLLOW(C)=FOLLOW(S)=#FOLLOW(D)=#,例,5.5,若文法,GS,为：,SAB,SbC,A,Ab,B,BaD,CAD,Cb,DaS,Dc,判断它是否是,LL(1),文法。,每个产生式的,SELECT,集合计算为：,SELECT(SAB)=,（,FIRST(AB)- ) FOLLOW(S)=b,a,#,SELECT(SbC,)=,FIRST(bC,)=b,SELECT(A)=(FIRST() - ) FOLLOW(A)=a,c,#,SELECT(Ab)=FIRST(b)=b,SELECT(B)=(FIRST() - ) FOLLOW(B)=#,SELECT(BaD,)=,FIRST(aD,)=a,SELECT(CAD)=FIRST(AD)=a,b,c,SELECT(Cb)=FIRST(b)=b,SELECT(DaS,)=,FIRST(aS,)=a,SELECT(Dc)=FIRST(c)=c,文法,G S,为：,SAB,SbC,A,Ab,B,BaD,CADCb,DaS,Dc,由以上计算结果可得相同左部产生式的,SELECT,交集为：,SELECT(SAB)SELECT(SbC,)=b,a,#b=b,SELECT(A)SELECT(Ab)=a,c,#b=,SELECT(B)SELECT(BaD,)=#a=,SELECT(CAD)SELECT(Cb),b,a,cb,b,SELECT(DaS)SELECT(Dc,)=ac,由,LL(1),文法定义知该文法不是,LL(1),文法，因为关于,S,和,C,的相同左部其产生式的,SELECT,集的交集不为空。,