,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,4.1,带回溯的自上而下分析法概述,从文法的开始符号出发进行推导，最终推出确定的输入串（由单词种别构成的源程序）。,4.1,带回溯的自上而下分析法概述,从根结点出发，试图用一切可能的办法，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。,4.1,带回溯的自上而下分析法概述,分析过程概述,例已知文法,G,：,S,xAy,A*|*,和输入串,=x*y,。,4.1,带回溯的自上而下分析法概述,4.1,带回溯的自上而下分析法概述,4.1,带回溯的自上而下分析法概述,4.1,带回溯的自上而下分析法概述,4.1,带回溯的自上而下分析法概述,因,S,的第三个子结和指示器,P,所指的符号一致，故,是一个句子。,显然上述分析过程本质上是一个试探过程，是反复使用不同产生式谋求匹配输入串的过程。,4.1,带回溯的自上而下分析法概述,问题和困难,对于左递归文法定义的语言，不能采用自上而下的语法分析法。,例已知左递归文法,G,：,S,Sb,a,和输入串,=ab,，其分析过程如下所示：,4.1,带回溯的自上而下分析法概述,4.1,带回溯的自上而下分析法概述,试图用非终结去推导匹配输入串，而推导所得到的子树第一个子结是该非终结符本身，这样就陷入了死循环。,4.1,带回溯的自上而下分析法概述,存在虚假匹配，回溯不可避免。,编译程序的语法分析和语义分析通常是同时进行的。由于回溯，编译程序所做的一大堆语义分析工作必须推倒重来。,4.1,带回溯的自上而下分析法概述,当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。这种分析法最终只能告知输入串不是文法的一个句子，而无法告知输入串错在何处。,带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，因此效率很低，这种分析法几乎没有实用价值。,4.2,直接左递归的消除,直接左递归消除方法,假定关于非终结符,P,的规则为,P,P|,其中，,不以,P,开头。可以把关于,P,的规则变换为如下形式：,P,P,P,P|,由于二者推导出的句型均为,n,（,n,0,），故上述变换是等价的。,4.2,直接左递归的消除,例文法,G,E,E+T|T,T,T*F|F,F,(E)|i|x|y,经消除直接左递归后变成,E,TE,E,+TE|,T,FT,T,*FT|,F,(E)|i|x|y,4.3,不带回溯的自上而下分析法的基本原理,设文法,G,有产生式,A,1,|,2,|,|,n,带回溯的自上而下的分析法,采用试探法，对于,1,、,2,直至,n,逐一试探。,4.3,不带回溯的自上而下分析法的基本原理,不带回溯的自上而下的分析法,在推导时，根据面临的输入符号去找出,A,的那个唯一正确的候选式。,引入候选式,的,first,集定义,根据定义，求出每个候选式,i,的,first,集。,4.3,不带回溯的自上而下分析法的基本原理,根据当前输入符号，选择候选式进行推导。,进一步考虑（,A,）,引入非终结符,follow,集定义,修改分析算法,4.4,提取左因子,实例引入,例定义无符号整数的文法,N,DN|D,D,0|1|2|3|4|5|6|7|8|9|0,就是这样一种情形，,first(DN),first(D)=D,。,4.4,提取左因子,解决方法,提取左因子，引进,产生式，将文法改造为,G,。,N,DN,N,N|,D,0|1|2|3|4|5|6|7|8|9|0,提取左因子一般规则,4.5 first,集和,follow,集,4.5.1 first,集的定义及构造算法,first,集定义,是文法,G,的任一符号串（包括候选式），,(V,T,V,N,),*,first(,)=a,a,，,a,V,T,若,，则规定,first(,),。,4.5 first,集和,follow,集,文法符号,first,集构造算法,终结符的,first,集为终结符本身。,观察每个产生式，若有,X,a,，其中,a,V,T,，则,a,first(X),；若,X,，则,first(X),。,观察每个产生式，若有,XY,，其中,YV,N,，则将,first(Y),中的非,元素（记为,first(Y)/,）加到,first(X),中。,4.5 first,集和,follow,集,考虑更一般情况，,X,Y,1,Y,2,Y,i,Y,n,，其中,Y,1,、,Y,2,、,Y,i-1,V,N,。,l,若,first(Y,1,),中含有,，则将,first(Y,2,)/,加到,first(X),中，否则终止计算。,l,若,first(Y,1,),和,first(Y,2,),中含有,，则将,first(Y,3,)/,加到,first(X),中，否则终止计算。,l,若,first(Y,1,),、,first(Y,2,),、,first(Y,i-1,),均含有,，即,Y,1,Y,2,Y,i-1,，则把,first(Y,i,)/,加到,first(X),中，否则终止计算。,l,若所有,first(Y,j,),均含有,(1,j,n),，即,Y,1,Y,2,Y,n,，则,first(X),。,反复使用规则，直至每个非终结符的,first,集不再增长为止。,4.5 first,集和,follow,集,例，文法,G,如下所示,求文法符号的,first,集。,E,TE,E,+TE|,T,FT,T,*FT|,F,(E)|i|x|y,4.5 first,集和,follow,集,解：非终结符的,first,集计算过程如下,4.5 first,集和,follow,集,候选式,first,集构造算法,设,A,，,=X,1,X,2,X,n,，计算规则如下所示：,置,first(,)=first(X,1,)/,。,若,first(X,1,),，则把,first(X,2,)/,加至,first(,),中；若,first(X,1,),且,first(X,2,),，则把,first(X,3,)/,加至,first(,),；,；依次类推。,若所有的,first(X,i,),均含有,其中,1,i,n,，则,first(,),。特别当,=,则,first(,)=,。,4.5 first,集和,follow,集,接上例，求文法,G,候选式的,first,集：,E,TEfirst(TE)=first(T)/,=(,i,x,y,E,+TE|,first(+TE)=+,first(,)=,T,FTfirst(FT)=first(F)/,=(,i,x,y,T,*FT|,first(*FT)=*,first(,)=,F,(E)|i|x|yfirst(E)=(,、,first(i)=i,、,first(x)=x,、,first(y)=y,4.5 first,集和,follow,集,任一文法符号串的,first,集构造算法,设,A,X,1,X,2,X,i-1,X,i,X,i+1,X,n,，求,X,i,X,i+1,X,n,的,first,集。,令,=X,i,X,i+1,X,n,，参照即可。,4.5 first,集和,follow,集,4.5.2 follow,集的定义及构造算法,follow,集定义,设,S,是文法开始符号，对于文法的任何非终结符,A,follow(A)=a,S,Aa,，,a,V,T,特别是，若,S,A,，规定,#,follow(A),。,4.5 first,集和,follow,集,follow,集构造算法,对于文法开始符号,S,，因为,S,S,，故,#follow(S),。,观察每个产生式，若,AB,，其中,B,V,N,，,(V,T,V,N,),*,、,(V,T,V,N,),+,，则把,first()/,加至,follow(B),。,观察每个产生式，若,AB,或,AB(),，则把,follow(A),加至,follow(B),。反复使用第条规则，直至每个非终结符的,follow,集不再增长为止。,4.5 first,集和,follow,集,例，文法,G,如下所示，求非终结符的,follow,集。,1.,E,T Efirst(E)/,=+,2.,E,+TE,3.,E,4.,T,FTfirst(T)/,=*,5.,T,*FT,6.,T,7.,F,(E)first()=),8.,F,i,9.,F,x,10.,F,y,4.5 first,集和,follow,集,解：,计算过程如下,4.6,递归下降分析法,递归下降分析法思想是：让每个非终结符对应一个过程（函数）。根据上述文法，构造递归下降分析程序，程序用类,C,语言描述。,4.7,预测分析法,预测分析法基本原理,产生式的一般形式为：,A,1,|,2,|,|,n,|,设当前输入符号为,a,，根据下述原则,if(a,first(,i,),用,A,i,推导（,1,i,n,）,else if(a,follow(A),用,A,推导,else,报错,4.7,预测分析法,构造分析表如下,4.7,预测分析法,以输入串“,i+i#,”,为例，说明工作原理如下：,E,TE,FTE,iTE,iE,i+TE,i+FTE,i+iTE,i+iE,i+i,i i i+i,i#,4.7,预测分析法,分析表构造规则,构造所有候选式的,first,集，构造所有非终结符的,follow,集。,对于文法的每个产生式,A,执行和。,对于每个终结符,a,first(,),，把,A,加至,MAa,。,若,first(,),，则对于每个终结符,b,follow(A),，把,A,加至,MAb,。,把所有未定义的,MAc,标上“出错标志”（,c,V,T,）。,4.7,预测分析法,预测分析控制程序实现,数据结构,M,：二维数组，存放预测分析表。,stack,：符号栈，初始时为“,#S,”,（,S,为开始符号）。,X,：表示栈顶符号,t.code,：当前处理单词种别,4.7,预测分析法,算法描述,预测分析控制程序任何时刻的动作，都按照栈顶符号,X,和当前输入符号,t.code,行事，控制程序每次执行下述三种可能的动作之一（暂不考虑出错情况）。,l,若,X,和,t.code,均为,#,，则分析成功，输入串为合法句子，终止分析过程。,4.7,预测分析法,l,若,X,是终结符，并且,X,和,t.code,相等，表示期望的终结符号和输入符号相等。让,X,出,stack,栈，并输入下一个单词二元式。,l,若,X,是非终结符，则查预测分析表。若,MXt.code,存放着一条关于,X,的一个产生式，那么，让,X,出,stack,栈，然后把产生式右部符号串按反序一一推进,stack,栈。若,右部符号串,为空字,，则意味着,无任何文法符号进栈。,4.7,预测分析法,预测分析法讨论,预测分析法是由分析表和控制程序构成的，控制程序与文法无关，分析表随文法而异。,在预测分析表中，若某一单元持有一个以上产生式，则称该预测分析表含多重定义，多重定义使得控制程序无法工作。,一个文法，若它的预测分析表不含多重定义，则称该文法是,LL(1),文法、分析表为,LL(1),分析表。,4.7,预测分析法,一个文法是,LL(1),的，对于文法的每一个非终结符的任何两个不同候选式（,A|,），下述条件成立：,l,first(,),first(,)=,l,若,，则,first(,),follow(A)=,二义文法不是,LL(1),文法,4.7,预测分析法,讨论,If-then-else,结构的文法,文法,G,，,a,表示普通语句，,C,表示布尔表达式,S fCtS|fCtSeS|a,C I,