语法制导翻译及中间代码生成.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章,语义分析和中间代码的表示,语义分析的概念,语法制导翻译方法,属性文法,几种常见的中间代码表示,第一节 语义分析的概念,语义分析：,即审查每个语法成分的静态语义。,在早期的一些编译程序中，是在语法分析的基础上根据源程序中各语法成份的语义，直接产生机器语言或汇编语言形式的,目标代码,。,现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的,中间语言代码,，然后再将其翻译为目标代码。,优点,：,使编译程序各组成部分,功能更单一,;,使得编译程序的,逻辑结构更为清晰,，从而使编译程序更,易于编写与调整,;同时为代码优化和程序的,可移植性,提供了条件,在语义分析时也要进行语义检查，编译时的语,义检查是静态语义检查，包括：,类型检查，如参与运算的操作数的类型应相容。,控制流检查，用以保证控制语句有合法的转向点。如C语言中不允许goto语句转入case语句流。,一致性检查，如case语句的标号不能相同。,第二节 语法制导翻译,对文法中的每个产生式都附加一个语义动作或语义子程序,在语法分析过程中，每当需要使用一个产生式进行,推导,或,归约,，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。,这种模式实际上是对前后文无关文法的一种扩充。,例如,文法,GE,:,产生式 语义动作,EE,(1),+TE.Val=E,(1),.val+T.val;,ET E.Val=T.Val;,TdigitT.Val=digit;,为了能在语法分析过程中平行地进行语义处理，可在语法分析栈旁边并行地设置一个,语义信息栈。,语法分析栈,语义分析栈,T,T.Val,+,+,E,#,产生式的语义,是由组成该产生式的,文法符号的语义,所决定的。,我们可将这些语义以“,属性,”的形式附加到各个文法符号上，再根据产生式所蕴含的语义，给出每个文法符号的属性的,求值规则,，从而形成一种附带有,语义属性,的前后文无关文法，即,属性文法,。,第三节 属性文法,属性文法=上下文无关文法+属性+求值规则,属性,是用来描述文法符号的语义特征，如,常量的“值”、变量的类型和存储位置等。,求值规则（属性计算规则）,与产生式相关联的反映文法符号属性之间关系的,“规则”。,求值规则还可进一步扩展为语义规则（语义动作）。,1、定义,例：简单表达式的属性文法。,语 义 规 则,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,产 生 式,若产生式A,X,1,X,2,X,n,，与之相关的属性计算规则 b:=f(c,1,c,2,)，,其中,f,是函数，,b,和,c,1,c,2,c,k,是该产生式文法符号的属性，,如果属性b是产生式,左部符号A的属性，,c,1,c,2,c,k,是产生式右部文法符号的属性或,A,的其它属性,则称其为A的,综合属性,；,如果属性b是产生式,右部符号X,i,的属性，,c,1,c,2,c,k,是产生式右部文法符号的属性或,A,的属性,则称其为,X,i,的,继承属性,；,终结符仅有综合属性,如digit.lex_val。通常由词法程序提供。而开始符号没有继承属性。,2、属性的分类,继承属性,用于“自上而下”传递信息。,继承属性,由相应语法树中结点的父结点和/或兄弟结点属性计算得到，它反映了对上下文依赖的特性。,继承属性,可以很方便地用来表示程序设计语言上下文的结构关系。,几点说明：,几点说明（续）：,综合属性,用于“自下而上”传递信息。,综合属性,由相应语法树中结点的分枝结点属性计算得到，即沿语法树向上传递，从分枝（子）结点到根结点。,思考：简单表达式文法中的属性各是什么类型的？,A.b,X,1.,c,1,X,2.,c,2,Xn,综合属性A.b的计算,A,X,1.,c,1,X,2.,c,2,继承属性X,k,.b的计算,X,k.,b,Xn,在语法树中,将每个结点均视为由若干个域组成的,结构,则可将其中的一些域用来存放相应文法符号诸属性之值，并可用,属性,来为这些域命名。通常我们将每个结点都标注相应属性值的语法树称为,注释分析树,（,Decorated Syntax Tree,）。,属性求值的过程：,在,注释分析树,中，一个文法符号,X,在相应结点的,综合属性,之值，由其子结点的属性和（或）X的其它属性，通过相关属性规则经计算而得，故,综合属性,的求值在语法树中是按,自下而上,的方式进行的；,X,的,继承属性,之值则由,X,的父结点和(或)其它兄弟结点来定义,故,继承属性,的求值将按,自上而下,的方式进行。,注释分析树,例：8+5*2 的注释分析树。（综合属性）,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,语义分析：即审查每个语法成分的静态语义。,(2)(*,b,t1,t2),(*,),如果属性b是产生式左部符号A的属性，c1,c2,ck 是产生式右部文法符号的属性或A的其它属性,则称其为A的综合属性；,元式的结果作为运算对象。,in=integer,如果属性b是产生式右部符号Xi的属性，c1,c2,ck 是产生式右部文法符号的属性或A的属性则称其为Xi的继承属性；,其中E1、E2分别是E1和E2的后缀表示。,type:=real,根据属性和计算规则，进行语义分析,8)addtype(id2.,L L1,id,语法制导翻译可以基于分析树，也可以基于语法树。,(1)(+,c,d,t1),A+B*CABC*+,若op是一元运算符，则视E1和E1为空。,EE(1)+TE.,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,分析树各结点属性的计算可以自下而上地完成,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,注释分析树:,结点的属性值都标注出来的分析树,digit.,lexval,=2,L,E,.,val,=18,T,.,val,=10,E,.,val,=8,T,.,val,=8,F,.,val,=8,digit.,lexval,=8,T,.,val,=5,+,*,F,.,val,=5,F,.,val,=2,digit.,lexval,=5,例：语句int id,id,id的语义分析。（继承属性）,产 生 式,语,义,规,则,D,TL,L,.,in,:=,T,.,type,T,int,T,.,type,:=,integer,T,real,T,.,type,:=,real,L,L,1,id,L,1,.in,:=,L,.,in,;,addtype,(id.,entry,L,.,in,),L,id,addtype,(id.,entry,L,.,in,),1、int id,1,id,2,id,3,的,注释分析树,D,int,T,.,type,=,integer,id,3,L,.,in,=,integer,L,.,in,=,integer,L,.,in,=,integer,id,2,id,1,2、int id,1,id,2,id,3,的分析树的,属性依赖图,D,int,T,id,3,L,L,L,id,2,id,1,entry,entry,entry,in,in,in,type,对结点进行拓扑排序，按拓扑排序的次序计算属性。,拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点。,3、属性计算次序,D,int,T,id,3,L,L,L,id,2,id,1,1,entry,10,2 entry,3,entry,in,9,8,in,7,6,in,5,4,type,属性计算次序为1，2，3，4，5，6，7，8，9，10,在上例中，按照拓扑排序可以得到下面的程序,段（用an来代表依赖图中与序号n的结点有关,的属性）：,4)a4:=int,5)a5:=a4,6)addtype(id,3,.entry,a5),7)a7:=a5,8)addtype(id,2,.entry,a7),9)a9:=a7,10)addtype(id,1,.entry,a9),思考：,如何通过对注释分析树进行树遍历的方,法计算属性值？,最常用的是深度优先、从左到右的遍历,方法。,小结：语法制导翻译的一般过程,语义规则和产生式联系起来：,对翻译给出高级说明,根据属性和计算规则，进行语义分析,输入单词符号串,构造注释分析树,构造属性依赖图，对结点进行拓扑排序,根据语义规则的进行计算和处理,第四节 中间代码的形式,抽象语法树,逆波兰式,三地址代码,（四元式、三元式）,addtype(id.,(1)(+,c,d,t1),(A+B)*(C+D)AB+CD+*,分析树各结点属性的计算可以自下而上地完成,分析树各结点属性的计算可以自下而上地完成,分析树各结点属性的计算可以自下而上地完成,2、int id1,id2,id3的分析树的属性依赖图,产生式的语义是由组成该产生式的文法符号的语义所决定的。,8)addtype(id2.,如果属性b是产生式右部符号Xi的属性，c1,c2,ck 是产生式右部文法符号的属性或A的属性则称其为Xi的继承属性；,8)addtype(id2.,使得编译程序的逻辑结构更为清晰，从而使编译程序更易于编写与调整;同时为代码优化和程序的可移植性提供了条件,addtype(id.,分析树各结点属性的计算可以自下而上地完成,四元式是一种更接近目标代码的中间代码形式，由于这种形式的中间代码便于优化处理，因此，在目前的许多编译程序中得到了广泛的应用。,语法树是分析树的浓缩表示,：,算符和关键字是作为内部结点。,语法制导翻译可以基于分析树，也可以基于语法树。,在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其他内部结点则表示运算符。,1、抽象语法树,语法树的例子：,if-then-else,B,S,1,S,2,+,*,2,5,8,2、,逆波兰表示,波兰逻辑学家,J.Lukasiewicz,于,1929,年提出的一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为,后缀表示,。,表达式E的后缀表示递归定义如下：,（1）如果E是变量或常数，则E的后缀表示即E自身。,（2）如果E为E1 op E2形式，则它的后缀表示为E1E2op；其中E1、E2分别是E1和E2的后缀表示。若op是一元运算符，则视E1和E1为空。,（3）如果E为(E1)形式，则E1的后缀表示即为E的后缀表示。,特点:,操作数出现的顺序与原来一致，而运算符则按运算先后的顺序放到相应的操作数之后，即运算符先后的顺序发生了变化，表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号来指示运算顺序。,例：,中缀表示后缀表示,A+BAB+,A+B*CABC*+,(A+B)*(C+D)AB+CD+*,x/yz-d*exyz/de*-,程序语句的逆波兰表示略去。,3、三地址代码（四元式和三元式）,四元式,是一种更接近目标代码的中间代码形式，由于这种形式的中间代码便于优化处理，因此，在目前的许多编译程序中得到了广泛的应用。,四元式,是一种“,三地址语句,”的等价表示。,它的一般形式为：(,op,arg1,arg2,result,),其中，,op,为一个二元(也可是一元或零元)运算符;,arg1,arg2,分别为它的两个运算对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入,result,中。四元式还可写为类似于,PASCAL,语言的赋值语句的形式：,result,:=,arg1,op,arg2,每个四元式只能有一个运算符，所以，一个复杂的表达式只能由多个四元式构成的序列表示。,例如，表达式,A+B*C,可写为序列,T,1,:=,B,*,C,T,2,:=,A,+,T,1,当,op,为一元、零元运算（如无条件转移）时，,arg2,甚至,arg1,应缺省，即,result,:=,op,arg1,或,op,result,；对应的一般形式为：,(,op,arg1,-,result,),或,(,op,-,-,result,)。,例 赋值语句a=b*(c+d)相应的四元式代码为,：,(1)(+,c,d,t1),(2)(*,b,t1,t2),(3)(=,t2,_,a),为了节省临时变量的开销，有时也可采用一种,三,元式,结构来作为中间代码，其一般形式为：,(,i,)(,op,arg1,arg2,),其中，(,i,)为三元式的编号，也代表了该式的运,算结果；,op,arg1,arg2,的含义与四元式类似。,区别,在于,arg,可以是某三元式的序号，表示用该三,元式的结果作为运算对象。,例如，对于赋值语句a:=-b*(c+d)，若用三,元式表示，则可写成,(,U_minus,b,-),(,+,c,d,),(,*,),(,:=,a,),式中的运算符,U_minus,表示一元减运算。,除前面所述的,抽象语法树、逆波兰式、四元式、三元式,外，常见的中间语言还有接近,PASCAL,形式的,P-代码,，接近,C,格式的,C-代码,等等。,4、其它表示法,