,单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,编 译 原 理,Principle of Compiling,郭 一 晶,厦门大学嘉庚学院,2008 年 9 月,11/18/2024,1,编 译 原 理 Principle of Compi,4.3 几种常见的中间语言,4.3.1,抽象,语法树,4.3.2,逆波兰,表示法,4.3.3,三地址,代码,11/18/2024,2,4.3 几种常见的中间语言4.3.1 抽象语法树10/,为什么使用中间代码?,Intermediate code；Intermediate representation；Intermediate language,使用中间代码的,优点,与机器无关，便于移植。,便于进行独立于机器的代码优化。,介绍几种常用的中间表示,图形表示:语法树,逆波兰,表示法:,后缀表示,三地址代码,用语法制导定义和翻译方案的方法将源程序翻译成中间形式,11/18/2024,3,为什么使用中间代码?Intermediate code；In,4.3.1,抽象,语法树,抽象,语法树(Abstract syntax tree)：,每一个,叶结点,都表示诸如常量或变量这样的运算对象(,操作数,)，而其它,内部结点,则表示,运算符,(,操作符,),。,注意，语法树是分析树的压缩表示：算符和关键字作为内部结点。,11/18/2024,4,4.3.1 抽象语法树抽象语法树(Abstract s,语法规则中包含的某些符号可能起,标点符号,作用也可能起,解释,作用。,如,赋值语句,语法规则：,SV=e,其中的赋值号“=”仅起,标点符号,作用，其目的是把V与e分开；,如,条件语句,语法规则：,Sif(e)S,1,;else S,2,保留字符号if和else起,注释,作用，说明当布尔表达式e为真时执行S,1,，否则执行S,2,；而“,；,”仅起,标点符号,作用。,11/18/2024,5,语法规则中包含的某些符号可能起标点符号作用也可能起解释作用。,赋值语句x=ab*c的,抽象语法树,如图44(a)所示，而图44(b)则是该赋值语句的,普通语法树,。,assign,x,-,a,*,b,c,(,a,),S,V,E,=,x,E,E,E,E,*,a,b,c,(,b,),11/18/2024,6,赋值语句x=ab*c的抽象语法树如图44(a)所示，而图,If(e)S,1,;else S,2,和8+5*2 对应的语法树：,if-then-else,e,S,1,S,2,+,*,2,5,8,龙书,P190提到了如何构造表达式的语法树。,11/18/2024,7,If(e)S1;else S2 和8+5*2 对应的,4.3.2,逆波兰,表示法,逆波兰表示法是波兰逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示表达式的方法，这种表示法,把运算量(操作数)写在,前面,，把运算符写在,后面,，因而又称,后缀表示法,。,例如，把a+b写成ab+，把a*(b+c)写成abc+*。,11/18/2024,8,4.3.2逆波兰表示法逆波兰表示法是波兰逻辑学家卢卡西维奇,1,表达式,的逆波兰表示,表达式E的后缀表示的,递归,定义如下：,(1)如果E是变量或常数，则E的后缀表示即E自身。,(2)如果E为E,1,op E,2,形式，则它的后缀表示为E,1,E,2,op；其中op是,二元,运算符，而,E,1,、,E,2,分别又是E,1,和E,2,的,后缀,表示。若op为,一元,运算符，则,E,1,和E,1,为空,。,(3)如果E为(E,1,)形式，则E,1,的后缀表示即为E的后缀表示。,P96,例4.1,。,11/18/2024,9,1表达式的逆波兰表示表达式E的后缀表示的递归定义如下：10,上述定义的,实质,：,操作数,出现的顺序与原来,一致,，而,运算符,则按,运算先后的顺序,放入相应的操作数之后(即运算符先后的顺序发生变化)。,这种表示已,不需要用括号,来规定运算的顺序。,后缀表示中的计值,用栈实现非常方便,。一般的,计算过程,是自左至右扫描后缀表达式，每碰到运算数就把它推进栈，每碰到K目运算符就把它作用于栈顶的K个运算量，并用运算的结果(即一个运算量)来取代栈顶的K个运算数。,可以拓广到表示,赋值语句,和,控制语句,，但,很难,用栈来描述它的计算。,11/18/2024,10,上述定义的实质：操作数出现的顺序与原来一致，而运算符则按运算,2程序语句的逆波兰表示,自学,11/18/2024,11,2程序语句的逆波兰表示自学10/6/202311,4.3.3,三地址,代码,1三地址代码的,形式,三地址代码语句的一般形式为,x=y op z,操作数,：名字、常量或编译时产生的临时变量；,op,：,运算符,，如+-*/%,uminus,not,and,or,xor,=,if-goto,三地址代码的每条语句通常包含三个地址，,两个,用来存放,运算对象,，,一个,用来存放,运算结果,。,11/18/2024,12,4.3.3 三地址代码1三地址代码的形式10/6/2,如表达式,x+y*z,的三地址代码为：,t,1,=y*z,t,2,=x+t,1,其中，t,1,和t,2,是编译时产生的,临时变量,。,三地址代码是语法树的一种线性表示，如图,44(a),所示的语法树用三地址代码表示为：,t,1,=b*c,t,2,=a t,1,x=t,2,11/18/2024,13,如表达式x+y*z的三地址代码为：10/6/202313,2三地址语句的种类,作为中间语言的三地址语句非常类似于,汇编代码,，它可以有符号标号和各种控制流语句。,常用的三地址语句有以下几种：,(1)x=y op z形式的,赋值,语句，其中op为二目的算术运算符或逻辑运算符。,(2)x=op y形式的,赋值,语句，其中op为一目运算符，如一目减uminus、逻辑否定not、移位运算符以及将定点数转换成浮点数的类型转换符。,(3)x=y形式的,赋值,语句，将y的值赋给。,11/18/2024,14,2三地址语句的种类作为中间语言的三地址语句非常类似于汇编代,(4)无条件转移语句,goto L,，即下一个将被执行的语句是标号为L的语句。,(5)条件转移语句,if x rop y goto L,，其中rop为关系运算符，如、=等。若x和y满足关系rop就转去执行标号为L的语句，否则按顺序执行本语句的下一条语句。,(6),过程调用,语句par X和call P,n。源程序中的P(X,1,、X,2,、，X,n,)可用下列三地址代码表示：,par X,1,par X,2,par X,n,call P,n,其中，整数n为实参个数。,过程返回,语句为,return y,，其中y为过程返回值。,11/18/2024,15,(4)无条件转移语句goto L，即下一个将被执行的语句是,(7),变址赋值,语句x=yi，其中x、y、i均代表数据对象，表示把从地址y开始的第i个地址单元中的值赋给x。xi=y则表示把y的值赋给从地址x开始的第i个地址单元。,(8),地址和指针赋值,语句 x=&y表示将y的地址赋给x，y可以是一个名字或一个临时变量，而x是指针名或临时变量；x=*y表示将y所指示的地址单元中的内容(值)赋给x，y是一个指针或临时变量；*x=y表示指将x所指对象的值置为y的值。,11/18/2024,16,(7)变址赋值语句x=yi，其中x、y、i均代表数据,3三地址代码的具体实现,三地址代码是中间代码的一种抽象形式。,在编译程序中，三地址代码语言的具体实现通常有,三种,表示方法：,四元式,、,三元式,和,间接三元式,。,1),四元式,(,quadruples),四元式是具有四个域的记录结构，这四个域为,(op，arg1，arg2，result),其中，op为运算符；arg1、arg2及result为指针，它们可指向有关名字在符号表中的登记项或一临时变量(也,可空缺,)。,11/18/2024,17,3三地址代码的具体实现三地址代码是中间代码的一种抽象形式,常用,的三地址语句与相应的四元式对应如下：,x=y op z 对应(op,y,z,x),x=y 对应(uminus,y,_,x),x=y 对应(=,y,_,x),par x1 对应(par,x1,_,_),call P 对应(call,_,_,P),goto L 对应(j,_,_,L),if x rop y goto L 对应(jrop,x,y,L),11/18/2024,18,常用的三地址语句与相应的四元式对应如下：10/6/20231,例如，赋值语句a=b*(c+d)相应的四元式代码为：,(+,c,d,t,1,),(*,b,t,1,t,2,),(=,t,2,_,a),t,1,:=-,c,t,2,:=,b,*,t,1,t,3,:=-c,t,4,:=,b,*,t,3,t,5,:=,t,2,+,t,4,a,:=,t,5,op,arg1,arg2,result,(0),uminus,c,t,1,(1)*,b,t,1,t,2,(2),uminus,c,t,3,(3)*,b,t,3,t,4,(4)+,t,2,t,4,t,5,(5):=,t,5,a,11/18/2024,19,例如，赋值语句a=b*(c+d)相应的四元式代码为：t1:,注意,：,凡只需,一个,运算量的算符一律使用,arg1,。,此外，注意这样一个规则：如果op是一个算术或逻辑运算符，则,result,总是一个,新引进的临时变量,，它用来,存放运算结果,。,由上例也可看出，四元式出现的顺序与,表达式计值,的顺序是一致的，四元式之间的联系是通过临时变量实现的。,四元式由于其表示更接近程序设计的习惯而成为一种,普遍采用,的中间代码形式。,11/18/2024,20,注意：10/6/202320,2),三元式,(,Triples,),三元式是具有三个域的记录结构，这三个域为,(op，arg1，arg2),其中，op为运算符；arg1、arg2既可指向有关名字在符号表中的登记项，也可以指向三元式表中的,某一个三元式,。,实际上，,三元式是,省去中间变量,，代之以产生中间变量值的三地址语句的地址。,11/18/2024,21,2)三元式(Triples)10/6/202321,例：,t,1,:=-,c,t,2,:=,b,*,t,1,t,3,:=-c,t,4,:=,b,*,t,3,t,5,:=,t,2,+,t,4,a,:=,t,5,op,arg1,arg2,(0),uminus,c,(1)*,b,(0),(2),uminus,c,(3)*,b,(2),(4)+(1)(3),(5),assign,a,(4),11/18/2024,22,例：t1:=-c op,3.,间接,三元式(Indirect triples),使用三元式虽然省去了中间变量,，但是要移动三元式就比较麻烦，因而不便于优化。解决的方法是引入,索引表间接码表,，当调整三元式的位置时，只改动间接码表中的,索引位置,。,注意，使用间接码表后，三元式表中的,重复,三元式可以,省去,；,注意，在前一种的,三元式,表示中，每个语句的,位置,同时有,两个作用,：一是可作为该三元式的结果被其它三元式引用；二是三元式位置顺序即为运算顺序。,11/18/2024,23,3.间接三元式(Indirect triples)10,例：,间接,三元式表示,op,arg1,arg2,(14),uminus,c,(15)*,b,(14),(16),uminus,c,(17)*,b,(16),(18)+(15)(17),(19),assign,a,(18),statement,(0)(14),(1)(15),(2)(16),(3)(17),(4)(18),(5)(19),11/18/2024,24,例：间接三元式表示 op,例：,合并,相同的三元式,op,arg1,arg2,(14),uminus,c,(15)