第八章 语法制导翻译中间代码生成.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 语法制导翻译和中间代码生成,8.1,概述,8.2,属性文法和,语法制导翻译,8.3,语义分析,8.4,中间代码,8.5,一些语句的翻译,概述 语义处理,程序设计 语言的语义,静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域,/,可见性规则两大类 类型相容性 变量先声明后引用 名称相关要求,动态语义,程序单位描述的计算,编译程序的语义处理工作 静态语义审查 解释执行动态语义（计算）生成代码,.,语,法,分,析,后,的,源,程,序,语义处理,概述,语义形式化 语义建模,文法模型,-,属性文法,命令式或操作式模型,-,操作语义学,应用式模型,-,指称语义学,公理式模型,-,公理语义学,属性文法,表达式文法,ET+T|T or T Tn|b,E,T,1,+T,2,T,1,.type=,int,T,2,.type=T,1,.type E.type:=,int,E,T,1,or T,2,T,1,.type=,bool,T,2,.type=T,1,.type,E.type:=,bool,T,n,T.type:=,int,T,b,T.type:=,bool,操作语义,描述一段程序的含义是通过执行该段程序所改变的计算机（虚拟计算机）状态来反映。这个计算机的状态与程序执行时的状态相对应：包括变量的所有值，可执行程序本身，各种系统定义的内部数据结构。计算机里所有的寄存器的值和存储单元的值作为计算机的状态，用一组形式定义的操作来说明执行一条指令相应的状态怎样变化。,For,(expr1;expr2;expr3)expr1;,.,Loop:,if,expr2=0,goto,out,expr3;,goto,loop,out:,.,公理语义,一个语言的每个语法成分的含义定义为公理和演绎规则，用于推导出该成分执行的效果。,公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束,以此说明这个语句的含义。,一般的记号,P S Q,如果在语句,S,执行前,P,为真，则在语句,S,执行并终止后,Q,为真。,演绎规则的例子,规则 前驱 后继,赋值：,x:=,expr,P(expr)x,:=,exprP(x,),While:P B S P,P while B do S end P (,not,B),if-then-else,B P S,1,Q,(,not,B)P S,2,Q,P,if,B,then,S,1,else,S2Q,指称语义,指称语义的基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体实例向数学意义对象的映射的函数,特点：,不但对全部程序赋予全文而且对程序设计语法 每一个语法成分短语（表达式，命令，声明,）都给予含义。,每一个语法成分（短语）的含义是以它的自 成分的含义的术语来定义的。,即 语义结构 平行于语法结构。,语义函数：,程序设计语言的语义利用映射函数来证 明。,语义函数将短语映射到它的指称。,例：,二进制数语言,110,或,10101,语法实体,指称（自然数）,6,或,21,语义实体,二进制数文法,Numeral,:,=0,:,=1,:,=Numeral 0,:,=Numeral 1,自然数,Natrual,=0,1,2,3,语义函数,Valuation,:,Numeral,Natural,Valuation101,表示把,Valuation,施用于,101,ValuationN -,把它施用于,N,定义:,Valuation,（,用四个方程,),因为有四个形式,numeral,Valuation0,0,Valuation1,1,ValuationN0,2,Valuation N,ValuationN1,2,Valuation N+1,所以：,Valuation110=2,Valuation11,=2,(2,Valuation1+1),=2,(2,1+1),=6,属性文法和语法制导翻译,虽然形式语义学,(,如指称语义学、公理语义学、操作语义学等,),的研究已取得了许多重大的进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译方法,属性文法,属性文法,(attribute grammar),是一个三元组,:A=(G,V,F),其中,G:,是一个上下文无关文法,V:,有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等,.,属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。,F:,关于属性的属性断言或一组属性的计算规则,(,称为语义规则,).,断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性,.,属性有两种,继承的和综合的属性,属性通常分为两类：综合属性和继承属性。简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。,出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由生计算器的参数提供。,A,X1 X2,Xn,A,的综合属性,计算,S(A):=f(I(X1),I(Xn,),Xj,的继承属性,计算,T(Xj,):=f(I(A),.,I(Xn,),1),非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性,.,2),终结符只有综合属性,.,在一个属性文法中，对应于每个产生式,A,都有一套与之相关联的语义规则，每条规则的形式为,b:=f(c,1,c,2,c,k,),这里，,f,是一个函数，而且或者,（,1,）,b,是,A,的一个综合属性并且,c,1,c,2,c,k,是产生式右边文法符号的属性,;,或者,（,2,）,b,是产生式右边某个文法符号的一个继承属性并且,c,1,c,2,c,k,是,A,或产生式右边任何文法符号的属性。,在两种情况下，我们都说属性,b,依赖于属性,c,1,c,2,c,k,。,一个属性文法的例子 例,8.1,非终结符,E,、,T,及,F,都有一个综合属性,val,符号,digit,有一个综合属性，它的值由词法分析器提供。与产生式,LEn,对应的语义规则仅仅是打印由,E,产生的算术表达式的值的一个过程，我们可认为这条规则定义了,L,的一个虚属性。某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现,语 义 规 则,L E,E E,1,+T,E T,T T,1,*F,T F,F (E),F digit,Print(E.val,),E.val,:=E,1,.val+T.val,E.val,:=,T.val,T.val,:=T,1,.val,F.val,T.val,:=,F.val,F.val,:=,E.val,F.val,:=,digit.lexval,产 生 式,设表达式为,3,5+4,，则,语义动作,打印数值,19,.,L,E.val,=19,E.val,=15,T.val,=4,T.val,=15,F.val,=4,T.val,=3,F.val,=3,F.val,=5,digit.lexval,=4,digit.lexval,=5,digit.lexval,=3,+,*,3*5+4,的带注释的分析树,继承属性,一个结点的继承属性值是由此结点的父结点和,/,或兄弟结点的某些属性来决定的。,例,8.2,继承属性,L.in,生 产 式,语 义 规 则,D,TL,T,int,T,real,L,L1,id,L,id,L.in:=T.type,T.type=integer,T.type:=real,L1.in:=L.in,addtype(id.entry,L.in,),addtype(id.entry,L.in,),D,L.in=real,L.in=real,L.in=real,T.type=real,real,id,2,id,1,id,3,.,Real id1,id2,id3,，,，,例,8.3,P DS,D,var,V;D|,S V:=E;S|,V x|y|z,现在使用两个属性，,name,和,dl,，,每当一个新的变量声明时，就把它的,name,属性附给它，,name,属性是综合属性。,将所声明的变量都放到一个变量名字清单中（用语义函数,addlist,实现），用属性,dl,综合声明块中声明的所有变量。然后这个,dl,属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中,P DS,S.dl=D.dl,D1,var,V;D2|,D1.dl=,addlist(V.name,D2.dl)|D1.dl=NULL,S1 V:=E;S2|,check(V.name,S1.dl);S2.dl=S1.dl,V x|y|z,V.name=x|V.name=y|V.name=z,var,x,；,var,y,；,x:=e,；,P,D dl=x,y Sdl=x,y,var,V,；,D dl=y V :=e,；,S,x,var,V,；,D dl=y,y,语法制导的翻译,一个,翻译,是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。各个编译阶段定义一个翻译，词法分析：（字符串，单词串）语法分析：（单词串，语法树）代码生成（语法树，汇编语言）,设,是输入字母表且,是输出字母表。定义由语言,L1,*,到语言,L2,*,的一个翻译是由,*,到,*,的一个关系,T,使得,T,的定义域为,L1,且,T,的值域为,L2,。,使,(,x,y),T,的句子,y,叫做,x,的一个输出,.,语法制导的翻译,直观地说，一个语法制导翻译的基础是一个文法，其中翻译成分依附在每一产生式上。,例,8.4,：下列翻译模式，它定义翻译，即对每个输入,x,，,其输出,y,是,x,的逆转。定义此翻译的规则是,产生式,翻译规则,(1)s,0,s,(2)s,1,s,(,3)s,(1)s,=,s,0,(2)s,=s1,(3)s,=,输入输出对可由,(,),表示，其中,是输入句子形式而,是输出句子形式。,(,S,S),开始用产生式,s,0,s,来扩展得到,(0,S,S0).,再用一次规则,(1),，得到,(00,S,S00),。,再用规则(2)，就得到,(001,S,S100).,然后应用规则,(3),并得到,(00,1,100),。,例,8.5,：,把下述产生式定义的算术表达式映射到后缀波兰表示：,E,E+T,E T,T T,F,T F,F(E),F a,E=ET+,E=T,T=TF,T=F,F=E,F=a,产生式,翻译规则,确定输入,a+a,a,的输出：,(,E,E),(E+T,ET+),(T+T,TT+),(F+T,FT+),(a+T,aT,+),(a+TF,aFF,+),(a+FF,aFF,+),(a+aF,aaF,+),(a+aa,aaa,+),定义：,一个语法制导的翻译模式是一个五元组,T=(N,，,R,S),其中,(1),N,是非终结符的有限集。,(2),是有限的输入字母表。,(3),是有限的输出字母表。,(4),R,是形如,A,的规则的有限集,其中,(N,)*,(N,)*,且,中那组非终结符是,中,那组非终结符的置换。,(5),S,是,N,中一个特别的非终结符，即开始符。,定义：,若,T=(N,R,S),是,SDTS,(T),则称为语法制导的翻译,(,SDT),，,文法,Gi,=(N,P,S),，,其中,P=A,|,A,属于,R),，,称为,SDTS T,的基础（或输入）文法。文法,G,0,=(N,P,S),，,其中,P,=A,|,A,属于,R,，,称为,T,的输出文法。,把语法制导的翻译方法看成是将输入文法,Gi,中的推导树变换成输出文法,G,0,中的推导树。给了输入句子,x,，,可以按如下方式得到,x,的一个翻译：先为推导,x,构造一棵推导树，再变换该树到输出文法中的一棵树，然后取此输出树的边缘作为,x,的一个翻译。,语义制导翻译中的规则,A,对应于每一个文法产生式,A,都有与之相关联的一套语义描述,属性文法,(,attribute grammar),是一个三元组,:,A=(G,V,F),属性文法可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来,语法制导翻译实现,从概念上讲，语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算,输入符号串,分析树,属性依赖图,语义规则的计算顺序,依赖图,由称为依赖图的一个有向图 描述分析树中的继承属性和属性中间的相互依赖关系。,依赖图的构造算法：,for,分析树中每一个结点,n,do,for,结点的文法符号的每一个属性,a,do,为,a,在依赖图中建立一个结点；,for,分析树中每一个结点,n,do,for,结点,n,所用产生式对应的每一个语义规则,b:=f(c,1,c,2,c,k,),do,for,i:=1 to k,do,从,c,i,结点到,b,结点构造一条有向边,依赖图,-,例,8.2,例,8.2,继承属性,L.in,生 产 式,语 义 规 则,D,TL,T,int,T,real,L,L1,id,L,id,L.in:=T.type,T.type=integer,T.type:=real,L1.in:=L.in,addtype,(id.entry,L.in),addtype,(id.entry,L.in,),例,8.2,Real id1,id2,id3,分析树的依赖图,5,6,7,8,9,10,T,4,D,L,L,L,Real,type,in,in,in,3,entry,2,entry,entry,id,3,id,2,id,1,.,.,1,依赖图中的结点由数字来标识。从代表,T.type,的结点,4,有一条有向边连到代表,L.in,的结点,5,，因为根据产生式,ETL,的语义规则,L,1,.in=L.in,，,可知,L,1,.in,依赖于,L.in,，,所以有两条向下的有向边分别进入结点,7,和,9,。每一个与,L,产生式有关的语义规则,addtype,(id.Entry,L.in),都产生一个虚属性，结点,6,、,8,和,10,都是为这些虚属性构造的。,良定义的属性文法。,很显然，一条求值规则只有在其各变元值均已求得的情况下才可以使用。但有时候可能会出现一个属性对另一个属性的循环依赖关系。从事贸易如，,p,、,c,1,、,c,2,都是属性，若有下求值规则：,p:=f,1,(c,1,),、,c,1,:=f,2,(c,2,),、,c,2,:=f,3,(p),时，就无法对,p,求值。如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。,属性的计算顺序,一个有向非循环图的拓扑序是图中结点的任何顺序,m,1,m,2,m,k,，,使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果,m,i,m,j,是,m,i,到,m,j,的一条边，那么在序列中,m,i,必须出现在,m,j,之前。,一个依赖图的任何拓扑排序都给出一个分析树中结点的语义规则计算的有效顺序。,这就是说，在拓扑排序中，在一个结点，语义规则,b:=f(c,1,c,2,c,k,),中的属性,c,1,c,2,c,k,在计算,b,以前都是可用的。,属性文法,说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。,例,8.2,Real id1,id2,id3,分析树的依赖图,每一条边都是从序号较低的结点指向序号较高的结点。历此，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑排序中我们可以得到下列程序，用,a,n,来代表依赖图中与序号,n,的结点有关的属性：,a,4,:=real,a,5,:=a,4,addtype,(id,3,entry,a,5,);,a,7,:=a,5,;,addtype,(id,2,entry,a,7,),a,9,:=a,7,addtype,(id,1,entry,a,9,),这些语义规则的计算将把,real,类型填入到每个标识符对应的符号表项中。,属性计算方法,树遍历的属性计算方法设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍）。,一遍扫描的处理方法,与树遍历的属性计算文法不同，一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无无需构造实际的语法树。,因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切相关：,（,1,）所采用的语法分析方法,（,2,）属性的计算次序。,例：定义定点二进制数的,CFG:,(1)N,SS,(2)S,SB,(3)S,B,(4)B,0,(5)B,1,非终结符,N,表示整个二进制数的数值，综合属性,v,附加在,N,上：,N v,非终结符,B,表示一个二进制数字，它有自己的值,v,，,但该值分配给,N,的值与它的位置有关，是与,2,成比例，比例因子,f,是从,S,继承的属性,所以：,B v f,非终结符,S,表示一个二进制数字串，它也有值，但该值与串的位置有关，与,f,有关与串的长度,l,有关,:,S f v l,构造数值的属性断言可以如下,:,N vS f,1,v,1,l,1,S f,2,v,2,l,2,v=v,1,+v,2,;f,1,=1;f,2,=2,-l2,S f v l S f,1,v,1,l,1,B f,2,v,2,f,1,=2f;f,2,=f;v=v,1,+v,2;,l=l,1,+1,B f v l=1,B f v0 v=0,1 v=f,N,v,S,i,1,l,1,“”S,i,2,l,2,v=i,1,+2,-l2,i,2,S,i,l,S,i,1,l,1,B,i,2,i,=2 i,1,+i,2,;,;,l=l,1,+1,B,i l=1,B,i,“0”i=0,“1”,i=1,在某些情况下可用一遍扫描实现属性文法的语义规则计算。也就是说在语法分析的同时完成语义规则的计算，无须明显地构造语法树或构造属性之间的依赖图。因为单遍实现对于编译效率非常重要,具体的实现希望在单遍扫描中完成翻译,研究怎样实现这种翻译器。一个一般的属性文法的翻译器可能是很难建立的，然而有一大类属性文法的翻译器是很容易建立的,s-,属性,适用于,自底向上的计算,L-,属性 适用于自顶向下的分析，也可用于,自底向上。,S,属性文法的自下而上计算,S,属性文法，它只含有综合属性。,综合属性可以在分析输入符号串的同时自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。,S,属性文法的翻译器通常可借助于,LR,分析器实现。在,S,属性文法的基础上，,LR,分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。,产生式 语义规则,）（,.,）,）,1,.,1,.,.,）,.,.,l,）,1,*,.,1,.,.,）,F,.,F.,）（）,.,.,）,i,i,.,:,.,LR,分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。,LR,分析器,增加语义栈,*的分析和计值过程,步骤 动作 状态栈 语义栈,(,值栈,),符号栈 余留输入串,）,3*,）,3*,）*,）*,）*,）*,）*,）*,）*,）*,）*,）（）*,#,）（）,）（）,）接受,BOTTOMUP,语义处理是作类型检查，对二目运算符的运算对象进行类型匹配审查。,(,LR,分,析,）：增加语义栈,归约,时进行语义动作,.,例,8.7,GE:,(1)E,T+T,(2)E T or T,(3)T n,(4)T b,E,T,1,+T,2,if T,1,.,type=,int,and T,2,.,type=,int,then E,.,type:=,int,else error,E,T,1,or T,2,if T,1,.,type=,bool,and T,2,.,type=,bool,then E,.,type:=,bool,else error,T,n T.type:=,int,T,b T.type:=,bool,GE:,(1)E,T+T,(2)E T or T,(3)T n,(4)T b,L,属性文法和自顶向下翻译,一个属性文法称为,L,属性文法，如果对于每个产生式,AX,1,X,2,X,n,，,其每个语义规则中的每个属性或者是综合属性，或者是,X,j,（,1jn,）,的一个继承属性且这个继承属性仅依赖于：,（,1,）产生式,X,j,在左边符号,X,1,，,X,2,，,，,X,j,-1,的属性；,（,2,）,A,的继承属性。,S,属性文法一定是,L,属性文法，因为（,1,）、（,2,）限制只用于继承属性。,L,属性文法允许一次遍历就计算出所有属性值。,LL,（,1,）,这种自上而下分析文法的分析过程，从概念上说可以看成是深度优先建立语法树的过程，因此，我们可以在自上而下语法分析的同时实现,L,属性文法的计算。,例（中缀表达式翻译成相应的后缀表达式）,ETRR,addop,T print(,addop,.Lexeme)R,1,|,Tnum print(num.,val,),翻译模式（,Translation schemes,）,适合语法制导翻译的另一种描述形式。翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号括起来，插入到产生式右部的合适位置上,。,输入串,9,5+2,的语法树，每个语义动作都作为相应产生式左部符号的结点的儿子，按深度优先次序执行图中的动作后，打印输出,95,2+,。,E,T R,9 print(9)-T print(-)R,5 print(5)+T print(+)R,2 print(2),L,属性文法在自顶向下分析中的实现,带左递归的文法的翻译模式,EE,1,+T E.,val,:=E,1,.,val,+T.,val,EE,1,T E.,val,:=E,1,.,val,T.,val,ET E.,val,:=T.,val,T(E)T.,val,:=E.,val,Tnum T.,val,:=num.,val,消除左递归的同时考虑属性，构造新的,翻译模式,ETR.i:=T.,val,R E.,val,:=R.s,R+,T R,1,.i:=R.i+T.,val,R,1,R.s:=R,1,.s,R-,T R,1,.i:=R.i-T.,val,R,1,R.s:=R,1,.s,RR.s:=R.i,T(E),T.,val,:=E.,val,Tnum T.,val,:=num.,val,计算表达式,9-5+2,.,E,R.i=9,T.,val,=5,T.,val,=9,R.i=4,R.i=6,T.,val,=2,num.,val,=9,num.,val,=5,num.,val,=2,_,+,在上页的翻译模式中，每个数都是由,T,产生的，并且,T.,val,的值就是由属性,num.,val,给出的数的词法值。子表达式,9,5,中的数字,9,是由最左边的,T,生成的，但是减号和,5,是由根的右子结点,R,生成的。继承属性,R.i,从,T.,val,得到值,9,。计算,9,5,并把结果,4,传递到中间的,R,结点这是通过产生式中嵌入的下面动作实现：,R,1,.i:=R.i,T.,val,类似的动作把,2,加到,9,5,的值上，在最下面的,R,结点处产生结果,R.i,6,。,这个结将成为根结点处,E.,val,的值,R,的,综合属性,s,在图中没有表示出来，它用来向上复制这一结果一直到树根。,对于自顶向下分析，我们假设动作是在处于相同位置上的符号被展开（匹配成功）时执行的。如图中的第二个产生式中，第一个动作（对,R,1,.i,赋值）是在,T,被完全展开成终结符号后执行的，第二个动作是在,R,1,被完全展开成终结符号后执行的。正如前面我们所讨论的，一个符号的继承属性必须由出现在这个符号之前的动作来计算，产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来以后才能计算。,转换左递归翻译模式的方法推广到一般,假设翻译模式,1,：,AA,1,YA.a:=g(A,1,。,a,Y.y),AX A.a:=f(X.x),每个文法符号都有一个综合属性，用相应的小写字母表示，,g,和,f,是任意函数,消除左递归，文法转换成：,AXR RYR,再考虑语义动作，翻译模式变为,2,AXR.i:=f(X.x),R A.a:=R.s,RYR,1,.i:=g(R.i,Y.y),R,1,R.s:=R,1,.s,RR.s:=R.i,翻译模式,1,和翻译模式,2,的结果是一样的。可以给出串,XY,1,Y,2,两棵带注释的语法树看出来，一棵是根据翻译模式,1,自下而上计算属性的。一棵是根据翻译模式,2,自上而下计算的。,AA,1,YA.a:=g(A,1。,a,Y.y)AX A.a:=f(X.x),A.a=g(g(f(X.x,Y,1,.y),Y,2,.y),A.a=g(f(X.x,Y,1,.y)Y2,A.a=f(X.x)Y,1,X,A,A Y,A Y,X,AXR.i:=f(X.x),RYR,1,.i:=g(R.i),Y.y),R A.a:=R.s,R,1,R.s:=R,1,.s,AXR RYR,A,X R,Y,1,R,Y,2,R,A,X R.i=f(X.x),Y,1,R.i=g(f(X.x,Y,1,.y),Y,2,R.i=g(g(f(X.x,Y,1,.y),Y,2,.y),思考问题,-,把建立语法树的翻译模式变换成适合预测分析的模式,E,E,1,+T E.,nptr,:=,mknode,(+,E,1,.,nptr,T.,nptr,),E,E,1,-T E.,nptr,:=,mknode,(-,E,1,.,nptr,T.,nptr,),E,T E.,nptr,:=T.,nptr,),自下而上计算继承属性,讨论在自下而上的分析过程中实现,L,属性文法的方法。这种方法可以实现任何基于,LL,（,1,）,文法的,L,属性文法，它还可以实现许多（不是所有）基于,LR,（,1,）,文法的,L,属性文法。这种方法是,S-,属性文法的自下而上翻译技术的一般化,自下而上分析器对产生式,AXY,的右部是通过把,X,和,Y,从分析栈中移出并用,A,代替它们。假设,X,有一个综合属性,X.s,，,按照前面所介绍的方法我们把它与,X,一起放在分析栈中。,由于,X.s,的值在,Y,以下的子树中的任何归约之前已经放在栈中，这个值可以被,Y,继承。也就是说，如果继承属性,Y.i,是由复写规则,Y.i:=X.s,定义的，则可以在需要,y.i,值的地方使用,X.s,的值。在自下而上分析中计算属性值时复写规则起非常重要的作用。看下面例子。,假设某翻译模式为：,DTL.in:=T.type,L,T,int,T.type:=integer,TrealT.type:=real,LL,1,.in:=L.in,L,1,id,addtype,(id.entry,L.in),Lid,addtype,(id.entry,L.in),回顾例,8.2,Real id1,id2,id3,分析树的依赖图,5,6,7,8,9,10,T,4,D,L,L,L,Real,type,in,in,in,3,entry,2,entry,entry,id,3,id,2,id,1,.,.,1,例,8.2,输入串,real,Real id1,id2,id3,的,分析过程,当,L,的右部被归约时，,T,恰好在这个右部的下面,输入 状态,(,符号）使用产生式,Real id1,id2,id3#,id1,id2,id3#,real,id1,id2,id3#,T T,real,id2,id3#Tid1,id2,id3#TL,L,id,id2,id3#TL,id3#TL,id2,id3#TL,L,Li,d,id3#TL,#TL,id3,#TL,L,Li,d,#D,D,TL,用综合属性代替继承属性,有时，改变基础文法可能避免继承属性。例如，一个,Pascal,的说明由一标识符序列后跟类型组成，如,m,n:integer,。,这样的说明的文法可由下面形式的产生式构成,DL,：,T,Tinteger|char,LL,id|id,因为标识符由,L,产生而类型不在,L,的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。事实上，如果非终结符,L,从第一个产生式中它的右边,T,中继承了类型，则我们得到的属性文法就不是,L,属性的，因此，基于这个属性文法的翻译工作不能在语法分析的同时进行。,一个解决的方法是重新构造文法,使类型作为标识符表的最后一个元素：,Did L,L,id L|:T,Tinteger|char,这样，类型可以通过综合属性,L.type,进行传递，当通过,L,产生每个标识符时，它的类型就可以填入到符号表中。,语义制导翻译的,编译实现,:,例,8.6,E,TE,E A T E|,T FT,T M F T|,F (E)|,int,A +|-,M *|/,E-TE,E-A T E,rhs,=,PopOperand,();lhs=,PopOperand,();,switch(,PopOperator,(),case ADD:,PushOperand,(lhs+,rhs,);break;,case SUB:,PushOperand,(lhs-,rhs,);break;,|,/*empty,do nothing*/,T-FT,T-M F T,rhs,=,PopOperand,();lhs=,PopOperand,();,switch(,PopOperator,(),case MUL:,PushOperand,(lhs*,rhs,);break;,case DIV:,PushOperand,(lhs/,rhs,);break;,|,/*empty,do nothing*/,A-+,PushOperator,(ADD);|-,PushOperator,(SUB);,M-*,PushOperator,(MUL);|/,PushOperator,(DIV);,F-,int,PushOperand,(,intval,);|(E)/*handled during parsing of,E*/,parse,2+4*3,:,分析动作桥 分析栈 运算对象栈 运算符栈,Predict E TE,E#,Predict T FT,TE#,Predict F,int,FTE#,Match,int intT,E#,Predict T,TE#,2,Predict E ATE ATE#,2,Predict A +,ATE#,2,Match+,+TE#,2,Predict T FT,TE#,2 +,Predict F,int,FTE#,2 +,Match,int intT,E#,2,+,Predict T MFT,TE#,4 2 +,Predict M *MFTE#,4 2 +,Match*FTE#,4 2,+,Predict F,int,FTE#,4 2 *+,Match,int intT,E#,4 2 *+,Predict T,TE#,3 4 2 *+,Predict E,E#,12 2,+,Success!,#,14,Yacc,或,bison,作为编译程序的生成工具，利用的就是语法制导翻译方法。它使用符号,$,表示产生式左端的属性，,$,n,表示存取产生式右端第,n,个文法符号相联的属性,如,例,8.3,作为,Yacc,的输入，可写成：,P DS$2.dl=$1.dl,D1,var,V,；,D$.dl=,addlist,($2.name,，,$4.dl),|$.dl=null,S1 V:=e,；,Scheck($1.name,，,$.dl),；,$5.dl=$.dl,|,V x$.name=,x,|y$.name=,y,|z$.name=,z,如果数据结构,attribute,定义属性,name,和,dl,，,可以具体化为：,type,struct,_attribute,char*name,；,struct,_attribute*list,；,attribute,；,P DS$2.list=$1.list,D1,var,V,；,D$.list=add_to_list($2.name,，,$4.list),|$.list=null,S1 V:=e,；,Scheck($1.name,，,$.list),；,$5.list=$.list,|,V x$.name=,x,|y$.name=,y,|z$.name=,z,语义分析,语义分析,属性文法和语法制导翻译方法和技术应用于语义分析中。,语义分析,通常包括：,（,1,）类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程,.,，编译程序必须报告不符合类型系统的信息。,（,2,）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在,C,语言中,break,语句使控制跳离包括该语句的最小,while,、,for,或,switch,语句。如果不存在包括它的这样的语句，则就报错。,（,3,）一致性检查。在很多场合要求对象只能被定义一次。例如,Pascal,语言规定同一标识符在一个分程序中只能被说明一次，同一,case,语句的标号不能相同，枚举类型的元素不能重复出现等等。,（,4,）相关名字检查。有时，同一名字必须出现两次或多次。例如，,Ada,语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。,(5),名字的作用域分析,类型和声明（,Types and declarations,）,一个类型是一组值和在这些值上的一组操作，程序设计语言中有三种类型,:,基本类型,：,int,float,double,char,bool,等等,.,也可能允许在,基本类型基础上,用户自己定义的类型，如枚举型,.,复合类型：数组,指针，记录,/,结构,/,联合,类等等,.,这些类型由基本类型构成,.,复杂类型：链表，栈，队，树，堆，表格等等,.,可以把它们组织成,ADT.,一个语言不一定支持这类高级的抽象。,声明是程序中的一个语句,是把数据对象的名称和类型，以及生命周期信息传给编译,，,声明的地方传递生命周期信息,也有些语言允许声明初始化变量,。,如,:,double calculate(,int,a,double b);/function prototype,int,x=0;/global variables available throughout,double y;/the program,int,main(),int,m3;/local variables available only in main,char*n;,.,强类型的,-任何数据,类型都可以在 编译时确定,弱类型的,.,进行类型检查的时间：编译时，运行时，或者两者结合,.,静态类型检查 编译时进行类型检查,动态类型检查，将类型信息并到运行时每个数据单元中,.,隐含类型转换,.,P,D,；,E,D,D,；,|id:T,T,char|integer|,aray,numof T|,T,E,lit