4章语法分析-自上而下分析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 语法分析,-,自上而下分析,4.1,几个重要集合,语法分析,是整个编译过程的核心部分，它完成的任务是：,按照文法从源程序单词串,(,符号串,),中识别各类语法成分，判断所给出的单词串是否是给定文法的正确句子,，并为语义分析和代码生成做准备。,一、,首符号集,：,设有文法,G=(V,T, V,N, S, P),是上下文无关文法，则符号串,x,的首符号集合定义为：,First(x)=a |x,*,ay, a,V,T, yV,*,，,*,若x,则,First(x).,First(x)=a |x,*,a, a,V,T,，,例如,：有如下文法,GE,：,E,E+T | TTT,*,F | FF(E) | i,则有：,First(E,)=,(, i,First(T)=,(, i,First(i*i)=,i,二、,后继符号集,：,设有文法,G=(V,T, V,N, S, P),是上下文无关文法，,U,V,N,则非终结符号,U,的,后继符号集定义为：,Follow(U)=a | S,*,Ua,a,V,T,*,若S,U,则,#,Follow(U).,#,是指输入串的括号，如,#,abcd,#,例如,：有文法,GE,：,E,E+T | TTT,*,F | FF(E) | i,因有,E,*,E,所以有：,#,Follow(E),因有,E,*,E+T,所以有：,+,Follow(E),因有,E,*,(E),所以有：,),Follow(E),故，,Follow(E)=,#, +, ),因有,E,*,T,同理，,所以有：,#,Follow(T),因有,E,*,T+T,所以有：,+,Follow(T),因有,E,*,T,*,T,所以有：,*,Follow(T),因有,E,*,(T),所以有：,),Follow(T),故，,Follow(T)=,#, +,*, ),LL(1),文法：,如果一个文法满足以下条件：,1,、文法不含左递归。,2,、对文法中每一个非终结符,A,的各个产生式的候选首,符集两两不相交。,3,、对文法中每一个非终结符,A,，若,存在某个候选首,符集包含,，则,First(A), Follow(A)=,LL(1),中第一个,L,表明自左,(,L,eft),向右扫描输入串，第二个,L,表明分析过程采用最左,(,L,eft),推导，括号中的,1,表明只需向右,看一个符号便可决定选择哪个产生式进行推导。,二、,可选集,：,设有文法上下文无关文法,GS,，并有,产生式,U,u,U,V,N, u V,*,则,该产生式的可选集定义为：,Select(U,u,),=,First(u) u,*,*,First(u),Follow(U),u,例如,：有文法,GS,：,S,aBc,|,bB,BbB,| d | ,由,定义知：,Select(S,aBc,)=,First(,aBc,)= a ,Select(S,bB,)=,First(b,B,)= b ,Select(B,bB,)=,First(b,B,)= b ,Select(B,d,)=First(d,)= d ,Select(B,)=First(,),Follow(B),=, c,#,=, c,#,第四章 自顶向下语法分析方法,语法分析,是整个编译过程的核心部分，它完成的任务是：,按照文法从源程序单词串,(,符号串,),中识别各类语法成分，判断所给出的单词串是否是给定文法的正确句子,，并为语义分析和代码生成做准备。,4.1,语法分析器的功能：,p66,4.2,不确定的自顶向下分析,一、,算法思想,：,对于任一输入符号串，试用一切可能的办法从树根结点出发,根据文法自上向下的为输入串建立一棵语法树,。,二、,举例,：设有文法,GS:(1),S,cAd,(2),Aab|a,给定输入串,w=cad,试给出分析过程,S cad,(1),据识别符号产生根结点,S,并让读指针指向输入串首符号,c,S cad,(2),据,S,的产生式发展语法树,c,A,d,S cad,(3),用,S,的子结点,(,cAd,),匹配输入串，首符号匹配，读指针向下移动,c,A,d,S cad,(4)A,有两个选择，选择第一个进行试探，发展语法树。,c,A,d,a,b,c,S cad,(5),子树,A,的最左子结点与指针所指符号匹配，指针移动，与,A,的第二个结点匹配，失败！回溯。,A,d,a,b,S cad,(6),回溯要把,A,的,第一个选择所生长的子树销掉，并把分析指针恢复到进入,A,时的值。,c,A,d,S cad,(7),用,A,的,第二个选择生成语法树,c,A,d,a,S cad,(8)A,的子结点与当前符号匹配，指针移动，,S,的第三结点,d,进入工作，匹配成功,c,A,d,a,三、,对应最左推导,：,以上为输入符号串建立语法树的过程，实际上也是一个,建立最左推导序列的过程，显然有：,S,cAdcad,，,之所以使用最左推导，是因为我们对输入串是从左到右扫描的，只有使用最左推导，才能按扫描顺序去匹配输入串。,四、,存在问题,：,p68,1.,左递归问题,：自顶向下分析方法，在匹配过程中，假若用到非终结符号,U,去匹配输入串，而,U,为,左递归的,(,例如：,U,U,),，,那么为了用它的右部匹配输入串，又要用到非终结符号,U,，,循环往复，没有终止。若文法存在间接递归，也有相同问题发生。,2.,回溯问题,：对某个非终结符，当有多条规则时，需采用逐个选择的方法，若不能匹配需要回溯，代价高，效率低。,4.3,确定的自顶向下分析思想,一、,算法思想,：,对于任一输入符号串，从文法的识别符号出发，根据当前的输入符号，唯一的确定一个产生式，用产生式的右部的符号串替代相应的非终结符往下推导，或构造一棵语法树。若能推导出输入串或构造语法树成功则输入串是句子，否则不是。,二、,举例,：,(1),文法,GS:,S,pA,|,qB,AcAd|a,输入串,w=,pccadd,S,p,A,A,c,d,A,c,d,a,对应最左推导：,S,pApcAdpccAddpccadd,文法特点,：,(1),每个产生式的右部都由终结符号开始；,(2),两个产生式若左部相同，则其,右部以不同的终结符号开始,；,(3),无空产生式,U,方法,：根据产生式右部的首符号选择产生式。,(2),文法,GS:,S,Ap,|,Bq,AcA,| aBdB | b,输入串,w=,ccap,S,A,p,c,A,c,A,a,对应最左推导：,S,ApcApccApccap,文法特点,：,(1),每个产生式的右部并非都由终结符号开始；,(2),两个产生式若左部相同，则其右部以不同的终结符号或非终结符号开始，且,首符号集不相交,；,(3),无空产生式,U,方法,：根据产生式右部的首符号选择产生式。,(3),文法,GS:,S,aA,| d,AbAS,| ,输入串,w=,abd,S,a,A,A,b,S,d,对应最左推导：,S,aAabASabSabd,文法特点,：,(1),有空产生式,U,；,(2),两个产生式若左部相同，则其对应的可选集不相交；,方法,：根据产生式的可选集选择产生式。,例题,(1)(2)(3),的共同特点：,1),每个非终结符号的两个产生式的可选集不相交；,2),在每一步推导中，都可以根,据输入串的当前符号和产生式,的可选集唯一的确定一个产生,式去匹配。,4.4,LL(,1,),文法,一、,定义,：,上下文无关文法,G,是,LL(1),文法的充要条件是对每个,UV,N,，,若有产生式,Uu|v,，,u,v V,*,则有 ：,Select(U,u,),Select(U,v,)=,二、,“,LL(1)”,的含义,：,LL(1),中第一个,L,表明自左,(,L,eft),向右扫描输入串，第二个,L,表明分析过程采用最左,(,L,eft),推导，括号中的,1,表明只需向右看一个符号便可决定选择哪个产生式进行推导。,三、,举例,：,对于前例文法,GS:,S,aA,| d,AbAS,| ,Select(S,aA,)=,First(aA,)=,a,Select(S,d,)=First(d)=,d,Select(A,bAS,)=,First(bAS,)=,b,Select(A,)=Follow(A),First(,),=a,d,#,=,a,d,#, , =, =,所以,：,GS,是,LL(1),文法。,重要结论：若能使用自顶向下,分析方法进行确定的分析，则,文法必须是,LL(1),文法。,4.5,非,LL(1),文法转换为,LL(1),文法,对某个语言来说其文法不一定是,LL(1),文法，而非,LL(1),文法将无法采用确定的自顶向下分析方法进行分析，但我们可以通过对文法进行等价变换，在有些情况下使其成为,LL(1),文法。,一、,提取左公共因子,：,设文法中有,U,xy|xw,( UV,N, x,y,wV,*,),形式的产生式，从而导致了,:,First(xy)First(xw,)=First(x),因而使：,Select(,U,xy,) ,Select(,U,xw,) ,1.,方法,：若有产生式,U,xy|xw,|,xz,，,则提取左公共因子并用,EBNF,表示为：,U,x(y|w|z),再,引入另一个非终结符号,V,，,将产生式变为：,U,xV,V y|w|z,若在,y,w,z,中仍然有左公共因子，可以再次提取。注意，若有：,U,xy|x,则提取后：,Ux(y|),2.,举例,：,设有产生式：,S,if B then S,1,else S,2,| if B then S,1,其中，,S,表示两种类型的条件语句。,提取公因子，改成：,Sif B then S,1,( else S,2,|,),引入非终结符号,R,：,Sif B then S,1,R,Relse S,2,|,文法中，,if , then, else,V,T,3.,说明,：,文法提取左公共因子后，只能使相同左部的产生式右部的,First,集不相交，不能保证相同左部产生式的,Select,集不,相交。,文法提取左公共因子后，若文法中无空产生式，且无左递归，则改写后的文法为,LL(1),文法。,有些文法，不能在有限步骤内改写为无左公共因子的文法。,二、,消除左递归,：,左递归文法的分析程序可能进入死循环，可以证明，左递归文法不可能是,LL(1),文法。,1.,消除直接左递归,：若有产生式,U,x|y|,z|Uv, UV,N, x,y,z,vV,*,则改写并用,EBNF,表示为：,U,（x|y|z|)v,或,改为右递归的形式：,U,（x|y|z|),U ,U ,v,U ,|,举例,：设有文法,GEEE+T|TTT*F|F F(E)|i,ET|E+T,ET+T,ETEE+TE|,或,TF|T*F,TF*F,TFTT*FT|,或,2.,消除间接左递归,：先将间接左递归变为直接左递归，再按消除直接左递归的方法进行。,举例,：设有文法,GA(1)ABc(2)Ad(3)BaA(4)BAb,将,(3)(4),带入,(1),AaAc,AAbc,Ad,直接左递归,AaAc|d|Abc,A(aAc|d)bc,3.,消除文法中全部左递归的算法,：,若,文法中没有回路,(A,A),则：,(1),把文法中的非终结符，按某种顺序进行排列,(,顺序任意,),，如，,A,1, A,2, , A,n,；,(2),对,每个非终结符号用排在它前面的其它非终结符号的产生式表示出来，并消除产生式中的直接左递归,。,for i:=1 to n do,begin,for j:=1 to i-1 do,begin,把行如,P,i,P,j,的产生式改成,P,i,1,|,2,|,k,其中,P,j,1,|,2,|,k,是关于,P,j,的所有产生式。,end,消除关于,P,i,产生,式的直接左递归,end,(3),化简由,(2),所得文法，即去掉多余产生式。,举例,：有文法,GS,:,SQc|c,QRb|b,RSa|a,该文法无直接左递归，但，,S,Qc,Rbc,Sabc,故有间接左递归，所以文法,GS,为左递归文法。,(1),对非终结符号排序：,R, Q, S,(2),逐个消除直接左递归,：,R,：,RSa|a,无直接左递归,Q,： 将,R,带入,Q,中：,Q,Sab|ab|b,无直接左递归,S,： 将,R,Q,带入,S,中：,S,Sabc|abc|bc|c,消除,S,的,直接左递归：,S,(abc|bc|c,) S,SabcS,|,QSab|ab|b,RSa|a,所以文法成为：,(3),去掉多余产生式,：,S,(abc|bc|c,) S,SabcS,|,注意：对非终结符号的排序是任意的,(,但要保证识别符号不变,),，不同的排序最后所得文法得形式可能不同，但它们是等价的。,文法,GE,：,E,TE,E,+,TE|,TF,T,T,*FT,|,F(E)|i,4.4,确定的自顶向下分析方法举例,一、递归子程序法,递归子程序法是比较简单直观易于构造的一种语法分析方法，其方法思想是对源程序中每个语法成分编制一个处理子程序，即对,每个非终结符号编制一个递归过程，每个子程序的功能是识别由该非终结符号推出的串,。它要求文法满足,LL(1),文法，以便当某个非终结符号有多条产生式时，可以根据当前的输入符号唯一地确定选择某个产生式进行匹配。,4.5,预测分析程序,LL(1),分析器,：,预测分析程序也是一种自顶向下分析程序，预测分析要求文法是,LL(1),文法，它由,分析栈、分析表和分析程序,三部分组成，其中分析表的构成与文法有关。下面举例说明分析器的构造过程：,设有文法,GE:EE+T|TTT*F|FF(E)|i,(1),消除左递归：,E,TE,E,+,TE|,TF,T,T,*FT,|,F(E)|i,1.,判断是否,LL(1),文法,(,2),找出能推出,的非,终结符号：,E, T,(3),求,非终结符号的,First,集：,p,79,First(E)=(,iFirst(E)=+,First(T)=(,iFirst(T)=*,First(F)=(,i,(,4),求,非终结符号的,Follow,集：详见,p,79,Follow(E)=),#Follow(E)=),#Follow(T)=+,),#Follow(T)=+,),#Follow(F)=*,+,),#,文法是,LL(1),文法。,(2),表示：预测分析表可用一矩阵,M,表示，矩阵的行表示非终结符号，矩阵的列表示输入符号或,#,，矩阵的元素,MU,a,表示对非终结符号，当面临输入符号,a,时，它向下推导所应采取的产生式。,(3),构造方法：对每个终结符号,a(,包括,#),若,a,Select(U,u,),，,则把产生式,U,u,放入预测分析表,MU,a,中。（,详见,P79,）,例,，对于上例中的文法,GE,预测分析表为：,i,+,*,(,),#,E,E,TE,E,TE,E,E,+,TE,E,E,T,TF,T,TF,T,T,T,T,*FT,T,T,F,Fi,F(E),2.,构造预测分析表,定义：,预测分析表与文法有关，它说明当某个非终结符号,U,向下推导时，面临输入符号,a,时，所应选用的产生式。,当,元素内无产生式时，表明用非终结符号,U,向下推导时，遇到了不该出现的输入符号。所以元素内容可以存放转向出错处理的错误信息。,3.,分析过程：,#,为输入串括号，,S,为文法开始符号,X,用于保存分析栈栈顶元素,a,当前输入符号,分析栈到栈底,输入串到右括号,#,为什么逆序？,什么情况出错？,举例,：分析输入串,i+i,是否为文法,GE(,上例,),的句子。,首先为输入串,i+i,加上括号，即被分析的串变为,#i+i#,，,分析过程如下：,步骤,分析栈,当前输入,a,剩余输入串,所用产生式,1,#,E,i,i,+i#,X=E,E,TE,2,#,E,T,i,i,+i#,TFT,3,#,ET,F,i,i,+i#,Fi,4,#,ET,i,i,i,+i#,X=i=a,匹配,5,#,E,T,+,+,i#,T,i,+,*,(,),#,E,TE,TE,E,+,TE,T,F,T,F,T,T,*FT,F,i,(E),6,#,E,+,+,i#,E+TE,7,#ET,+,+,+,i#,X=+=a,匹配,8,#E,T,i,i,#,TFT,9,#ET,F,i,i,#,Fi,10,#ET,i,i,i,#,X=i=a,匹配,11,#E,T,#,#,T,12,#,E,#,#,E,13,#,#,#,分析成功,X=a=#,