编译 第四章中间代码生成

1 翻译方式有两种翻译方式有两种:第四章第四章 源语言源语言目标语言目标语言源语言源语言1)2)目标语言目标语言中间代码中间代码中间代码的特点中间代码的特点: 结构简单结构简单,功能明确功能明确,易于优化易于优化,易于翻译易于翻译.2第一节第一节 中间代码简介中间代码简介1) 逆波兰表示法逆波兰表示法 运算量在前运算量在前,运算符在后的后缀式表示法运算符在后的后缀式表示法.例如例如: 表达式表达式后缀式后缀式 a+bab+ (a+b)*cab+c* a*(b+c)abc+* (a+b)*(c+d)ab+cd+*32) 三元式表示法三元式表示法 三元式就是三元组三元式就是三元组: ( 操作符操作符,操作数操作数1,操作数操作数2)例如例如: 语句语句 D:=A+B*C 可翻译为下述三元式表可翻译为下述三元式表: (1) (*,B,C) (2) (+,A,(1) (3) (:=,D,(2) 三元式没有明确指出结果放在何处三元式没有明确指出结果放在何处.43) 四元式表示法四元式表示法 四元式就是四元组四元式就是四元组: ( 操作符操作符,操作数操作数1,操作数操作数2,结果结果)例如例如: 语句语句 D:=A+B*C 可翻译为下述四元式表可翻译为下述四元式表: (1) (* ,B ,C ,T1) (2) (+ ,A ,T1,T2) (3) (:= ,T2, , D ) 四元式间通过临时变量传值四元式间通过临时变量传值. 操作符实现的运算也非常简单操作符实现的运算也非常简单,本章主要介绍各种语句到四元式的翻译本章主要介绍各种语句到四元式的翻译.5第二节第二节 语法制导翻译的基本思想语法制导翻译的基本思想1 何谓语法制导翻译何谓语法制导翻译 在语法分析的每次归约或推导时在语法分析的每次归约或推导时,根据产生式的语义进行根据产生式的语义进行翻译的一种方法翻译的一种方法. 翻译时翻译时,除了产生中间代码外除了产生中间代码外,还有许多辅助工作还有许多辅助工作,包括包括: 改变语法变量的值改变语法变量的值;查填符号表查填符号表;诊查与报告源程序错误等诊查与报告源程序错误等.2 与翻译相关的若干约定与翻译相关的若干约定 1) 临时变量临时变量 在翻译中在翻译中,可能会引入许多临时变量存放中间结果可能会引入许多临时变量存放中间结果. 通过调用通过调用 newtemp() 返回一个临时变量返回一个临时变量 Ti .62) 分析栈分析栈 分析栈中的内容为语法单位分析栈中的内容为语法单位,每个语法单位包含两个部分每个语法单位包含两个部分: (语法单位名称语法单位名称,语法单位属性语法单位属性),属性可能有多个值属性可能有多个值. 例如例如: E 为表达式的语法单位为表达式的语法单位, E.place 代表了该表达式值代表了该表达式值 存放的地方存放的地方.3) 符号表符号表 符号表用于存放变量及属性值符号表用于存放变量及属性值,由如干项构成由如干项构成,每个项为每个项为: (变量名变量名, 变量信息变量信息).4) 四元式表四元式表 四元式表用于存放翻译中产生的四元四元式表用于存放翻译中产生的四元 式式,通过过程通过过程 Gen( 操作符操作符,操作数操作数1,操作数操作数2,结果结果) 把四元式存入四元式表的把四元式存入四元式表的 NXQ 所指所指 空间中空间中, NXQ 自动加自动加 1. 四元式表四元式表NXQ75 一些基本操作一些基本操作 newtemp( ) 产生一临时变量产生一临时变量;gen(操作符操作符,操作数操作数1,操作数操作数2,结果结果) 填入四元式表填入四元式表;fill( i,属性属性)填入符号表填入符号表;entry( i )查符号表查符号表,返回返回 i 在符号表中的位置在符号表中的位置;backpatch( m,n) 把把 n 填入填入 四元式表第四元式表第 m 个四元式中个四元式中;8第三节第三节 简单变量说明语句的翻译简单变量说明语句的翻译 程序设计中程序设计中,首先应该对程序中使用的变量进行说明首先应该对程序中使用的变量进行说明.其目的其目的是规定变量所占用空间的大小是规定变量所占用空间的大小. 编译时编译时, 对变量说明语句的翻译工对变量说明语句的翻译工作作,本质上就是把变量名及属性登记在符号表中本质上就是把变量名及属性登记在符号表中,以便后续工作中以便后续工作中使用使用. pascal 语言的简单变量说明语句为语言的简单变量说明语句为: x,y,z:real; 语法可表示为语法可表示为: D NAMELIST:T NAMELIST NAMELIST,i | i T integer|real|boolean|char 该文法代表了所有该文法代表了所有非结构型变量的说明语非结构型变量的说明语句句.9 当然当然,也可以用如下文法表示也可以用如下文法表示: Di:T | i,D T integer|real|boolean|char 我们已经知道用该文法如何分析一个说明语句我们已经知道用该文法如何分析一个说明语句,下面要解决下面要解决的是的是,怎样在分析的过程中怎样在分析的过程中, 把该语句表达的意思完整的翻译清楚把该语句表达的意思完整的翻译清楚. 说明语句的含义是说明语句的含义是: 说明的变量具有给定类型说明的变量具有给定类型; 编译时则翻译为编译时则翻译为:把每个变量及类型登记在符号表中把每个变量及类型登记在符号表中. 语法制导翻译就是为每一条产生式配一个子程序语法制导翻译就是为每一条产生式配一个子程序,当用某个当用某个产生式归约时产生式归约时,就调用相应的子程序进行适当的翻译工作就调用相应的子程序进行适当的翻译工作. 这些子程序称为语法单位的这些子程序称为语法单位的语义子程序语义子程序(或语义动作或语义动作).10 下面讨论如下文法的各产生式的语义子程序及翻译过程下面讨论如下文法的各产生式的语义子程序及翻译过程 Di:T | i,D T integer|real|boolean|char 1) T integer T.att:=integer; 2) T real T.att:=real; 3) T boolean T.att:=boolean; 4) T char T.att:=char; 5) Di:T D.att:= T.att ; fill(i,T.att) ; 6) Di:D D.att:= D .att ; fill(i, D .att) ;11示例示例: x,y,z:real;x,y,z:realx,y,z:Tx,y,Dx,DDT.att=realD.att=real;fill(z,real)D.att=real;fill(y,real)D.att=real;fill(z,real)最终最终,符号表中包含了符号表中包含了 x,y,z 三个变量及属性三个变量及属性 real.12第四节第四节 简单算术表达式简单算术表达式 和赋值语句的翻译和赋值语句的翻译 简单算术赋值语句的文法可表示为简单算术赋值语句的文法可表示为:Si:=EEE+E | E-E | E*E | E/E | (E) | i 该文法为二义文法该文法为二义文法,但如果规定每个终结符的优先关系但如果规定每个终结符的优先关系,并按并按优先关系进行归约优先关系进行归约,则可以避免二义性则可以避免二义性. 赋值语句的含义是赋值语句的含义是:计算出计算出 E 的值的值,并写入变量并写入变量 i 中中. 编译中编译中,并不关心值是多少并不关心值是多少,而关心的是怎样计算值的过程而关心的是怎样计算值的过程;也即也即,哪些变量参加运算哪些变量参加运算,怎样运算怎样运算? 上面文法的各产生式语义子程序如下上面文法的各产生式语义子程序如下:13Ei E.place:=entry(i) /E.place 表示了表达式表示了表达式E 的值放在什么变量中的值放在什么变量中 E(E1) E.place:= E1.placeE E1 + E2 E.place:=newtemp( ) Gen( + , E1 .place, E2.place, E.place) E E1 - E2 E.place:=newtemp( ) Gen( - , E1 .place, E2.place, E.place) E E1 * E2 E.place:=newtemp( ) Gen( * , E1 .place, E2.place, E.place) E E1 / E2 E.place:=newtemp( ) Gen( / , E1 .place, E2.place, E.place) S i := E Gen( := , E.place , ,entry( i ) 四元式中的操作数及结果四元式中的操作数及结果,实质上是一指向变量的指针实质上是一指向变量的指针.14示例示例: x:=y+zx:=y+z x:=y x:=Ex:=E+zx:=E1+E2E.place=entry(y)E1.place=entry(y); E2.place=entry(z)+z +z x:=EE .place=T1 ;Gen(+,y,z, T1) S Gen(:=, T1 , , x ) 15第五节第五节 布尔表达式的翻译布尔表达式的翻译 布尔表达式文法可表示为布尔表达式文法可表示为:Bnot B | B and B | B or B | (B) | i | E ROP E ROP | | = | 该文法也为二义文法该文法也为二义文法,但如果规定每个终结符的优先关系但如果规定每个终结符的优先关系,并按并按优先关系进行归约优先关系进行归约,则可以避免二义性则可以避免二义性. 各产生式语义子程序如下各产生式语义子程序如下: ROP | | = | ROP.val= 或或 或或 =或或 16Bi B.place:=entry(i) /B.place 表示了表达式表示了表达式B 的值放在什么变量中的值放在什么变量中 B(B1) B.place:= B1.placeB not B1 B.place:=newtemp( ) Gen( not , B1 .place, , B.place) B B1 and B2 B.place:=newtemp( ) Gen( and , B1 .place, B2.place, B.place) B B1 or B2 B.place:=newtemp( ) Gen( or, B1 .place, B2.place, B.place) B E1 ROP E2 B.place:=newtemp( ) Gen( ROP.val, E1 .place, E2.place, B.place) 17第六节第六节 分支语句的翻译分支语句的翻译分支语句包括分支语句包括: ifcase(省略省略)goto1 if 语句的翻译语句的翻译 在程序设计种在程序设计种,if 语句可以表示为语句可以表示为: if B then S1 else S2; if 语句翻译后语句翻译后,将得到一组四元式将得到一组四元式,其流程可以表示为其流程可以表示为:18B 的四元式的四元式B为真为真?S1 的四元式的四元式S2 的四元式的四元式F 分析是从前向后进行的分析是从前向后进行的,按四元式按四元式流程的要求流程的要求,(1)首先归约布尔表达式首先归约布尔表达式,产生产生B的四元式的四元式;(2)在归约在归约S1之前之前,应产生条件转移语句应产生条件转移语句,也即也即 当归约当归约 if B then 时时,产生条件转移语句产生条件转移语句; 由于由于 S1 S2 还未处理还未处理,因此因此,条件转移语句条件转移语句 的转移地址未知的转移地址未知,只有等到只有等到S1处理完毕并处理完毕并 产生了无条件转移语句产生了无条件转移语句,才能知道条件转才能知道条件转 移语句转移的确切地址移语句转移的确切地址.(3)归约归约S1;并在归约并在归约 S1 else 时时,产生无条件产生无条件 转移语句转移语句;此时此时,由于由于S2未处理未处理, 无条件转无条件转 移语句的转移地址不确定移语句的转移地址不确定;回填条件转移语句的地址回填条件转移语句的地址.(4)归约归约S2;回填无条件转移语句的地址回填无条件转移语句的地址.*19 从以上分析从以上分析,可以将文法设计为可以将文法设计为: STS2 TCS1else Cif B then 语义子程序为语义子程序为: Cif B then C.chain:=NXQ; Gen(Jz,B.place, ,xxxx) T CS1elseT.chain:=NXQ; Gen(J , , ,xxxx); backpatch(C.chain,NXQ) STS2backpatch (T.chain,NXQ)并设并设:T C 有属性值有属性值 T.chain及及C.chain,用于用于记录条件及无条件转移记录条件及无条件转移四元式的序号四元式的序号.20示例示例: if A1 then x:=2 else y:=4x:=2 else y:=4 C CS1elseTTS2x:=2 else y:=4 y:=4 if B then 四元式序列四元式序列(1) (1 then goto c else x:=1; if y1 then goto c else y:=1; c:x:=1; y:=1; if x1 then goto c else x:=1; if y,x,1,T1) (2)(JZ,T1,xxxx)(3)(J, , ,xxxx) (4)(J, , ,xxxx)(5)(:=,1, ,x) (6)(,y,1,T2) (7)(JZ,T2,xxxx) (8)(J, , ,xxxx)(9)(J, , ,xxxx) (10)(:=,1, ,y)(11)(:=,1, ,x) (12)(:=,1, ,y)(13)(,y,1,T4) (19)(JZ,T4,xxxx) (20)(J, , ,xxxx)(21)(J, , ,xxxx) (22)(:=,1, ,y)(23)(:=,1, ,x) (24)(:=,1, ,y)(c,否否,(3) (c,否否,(8)(c,已已,(11)(c,已已,(11)25第七节第七节 循环语句的翻译循环语句的翻译 循环语句有三种方式循环语句有三种方式:while B do Srepeat S until Bfor i:=E1 to E2 do S1 while B do S 的翻译的翻译 该语句翻译为如右图所示的该语句翻译为如右图所示的四元式系列四元式系列. 从流程图中可以看出从流程图中可以看出,有两处有两处的四元式地址需特殊处理的四元式地址需特殊处理:B 的四元式的四元式B为真为真?S 的四元式的四元式F*26while 语句的文法及语义子程序如下语句的文法及语义子程序如下:SWd S Gen(J , , , Wd .q ) backpatch(Wd .chain,NXQ) Wd W B do Wd .q := W.q /传递给传递给Wd. Wd .chain:=NXQ; Gen(Jz,B.place, , xxxx) Wwhile W.q:=NXQ /记住记住 B 的第一条四元式地址的第一条四元式地址272 repeat S until B 的翻译的翻译 SR S until B Gen(Jz, B.place, ,R.q) Rrepeat R.q:=NXQ*S 可以是复合语句可以是复合语句S 的四元式的四元式B为真为真?B的四元式的四元式FT283 for i:=E1 to E2 do S 的翻译的翻译SF2 do S Gen( inc, , , F2.place) Gen( J , , , F2.chain) backpatch(F2.chain, NXQ ) F2F1 to E2 F2.chain:=NXQ; F2.place:=F1.place Gen (Jg,F1.place ,E2.place, xxxx)F1for i:= E1 Gen (:= ,E1.place, ,entry(i) F1.place :=entry(i) E1的四元式的四元式i E2? E2的四元式的四元式T i:=E1 S的四元式的四元式 i:=i+129第八节第八节 数组的翻译数组的翻译 这节讨论三个问题这节讨论三个问题:数组说明的翻译数组说明的翻译数组元素的翻译数组元素的翻译含数组元素的赋值语句的翻译含数组元素的赋值语句的翻译1 数组说明语句的翻译数组说明语句的翻译 进行数组说明语句的进行数组说明语句的 翻译时翻译时,要把数组名填入符号表要把数组名填入符号表,并建立一内情向量表并建立一内情向量表,记录维数记录维数,下标上下界下标上下界,类型等类型等. 简单起见简单起见,只考虑如下的数组说明只考虑如下的数组说明:A:arrayL1:U1, L2:U2,. Ln:Un of TYPE30文法如下文法如下:Di:array LIST of TLISTi(1):i(2)| LIST (1) , i(1):i(2) Tinteger|real|char|boolean 语义子程序如下语义子程序如下:LISTi(1):i(2)建立一个仅含建立一个仅含 i(1):i(2) 的队列的队列LIST.Q LIST LIST (1) , i(1):i(2) 把把 i(1):i(2) 插入队列插入队列LIST.Q中中 Di:array LIST of T i 填入符号表并标志为数组填入符号表并标志为数组;开辟内情向量表开辟内情向量表, 把把LIST.Q 中的上下界对逐一取出中的上下界对逐一取出,计算计算 di, 并将并将 i(1),i(2) , di, 放入内情向量表放入内情向量表;计算维数计算维数 n 及及 c, 将将 T.attr,n,c 填入内情向量表填入内情向量表. 数组说明语句不产生四元式数组说明语句不产生四元式.31数组相对地址的计算：数组相对地址的计算： 一维一维：AiAi的相对地址为：的相对地址为：base+(i-low)base+(i-low)* *w w，其中：其中：w w为每个元素的宽度，为每个元素的宽度，lowlow为数组的下界，为数组的下界，basebase为分为分配给数组元素的相对地址。配给数组元素的相对地址。 原式可以变形为：原式可以变形为：i i* *w+(base-loww+(base-low* *w)w)，可以设可以设a= base ,c=lowa= base ,c=low* *w,w,则原式等价为：则原式等价为：i i* *w+a-cw+a-c 二维二维：AiAi1 1,i,i2 2 的相对地址为：的相对地址为： base+(ibase+(i1 1-low-low1 1) )* *d d2 2+i+i2 2-low-low2 2) )* *w w 其中：其中：d d2 2为为i i2 2可以取值的个数，可以变行为：可以取值的个数，可以变行为： ( (i1i1* *d2)+id2)+i2 2) )* *w+(base-(loww+(base-(low1 1* *d d2 2)+low)+low2 2) )* *w)w)以此类推以此类推n n维维： ( (i i1 1d d2 2+i+i2 2)d)d3 3+i+i3 3) )d)dn n+i+in n) )* *w+w+ base-( base-(low(low1 1d d2 2+low+low2 2)d)d3 3+low+low3 3) )d)dn n+low+lown n) )* *w w32L1 u1 d1 L2 u2 d2 Ln un dn a c n type c = ( L1 )*d2d3d4.dn + ( L2 )* d3d4.dn + ( Ln-1)* dn + ( Ln ) *elemlength = (.(L1d2+L2)d3+L3)d4+L4).) dn + Ln *elemlength332 数组元素的翻译数组元素的翻译 设数组元素为设数组元素为: A E1,E2,.En, 要取得该元素值要取得该元素值,首先要计算首先要计算出该元素的地址出该元素的地址:addr=conspart+varpartconspart =a -c varpart = (.(E1d2+E2)d3+E3)d4+E4).) dn + En *elemlength conspart 的的 a c 已经通过数组说明语句的翻译登记在内已经通过数组说明语句的翻译登记在内情向量表中情向量表中; 而而 varpart 中含有未知数中含有未知数,只能在程序运行时通过如只能在程序运行时通过如下算法实现下算法实现: 34varpart:=E1;k:=1;while kn do varpart:=varpart*dk +1 + Ek +1; K:=k+1 varpart:=varpart*elemlength 下面是包含数组元素的变量的文法下面是包含数组元素的变量的文法:Vi | i E1,E2,.En 为了便于翻译上面的算法为了便于翻译上面的算法,文法改为如下形式文法改为如下形式:Vi | ElistElisti E | Elist1,E V 有两个值有两个值 : V.place , V.off 对于简单变量对于简单变量 , V.place = entry(i),V.off=0; 对于数组变量对于数组变量 , V.place = a -c , V.off=varpart;35 Elist 有三个值有三个值 : Elist.array/ i 在符号表中的位置在符号表中的位置Elist.dim/ i 的维数的维数Elist.place/ 存放存放 varpart 的中间结果的中间结果 语义子程序如下语义子程序如下:Vi V.place:=entry(i); V.off:=0; Elisti E Elist.array:=entry(i);Elist.place:=E.place;Elist.dim:=1 36Elist Elist1,EElist.place:=newtemp( ); Elist.array:= Elist1.array ; Elist.dim:= Elist1.dim+1; dk:=get_dk(Elist.array, Elist.dim); gen(* , Elist1.place,dk, Elist.place); gen(+ , E.place,Elist.place, Elist.place);V Elist V.place:=newtemp( ); gen(-,Elist.array.a, Elist.array.c,V.place) V.off:=Elist.place373 含数组元素的赋值语句的翻译含数组元素的赋值语句的翻译 赋值语句的文法扩充如下赋值语句的文法扩充如下:(对比前面的赋值语句对比前面的赋值语句)SV:=EEE+E | E-E | E*E | E/E | (E) |V 只考虑如下两个产生式的语义子程序只考虑如下两个产生式的语义子程序:SV:=E若若V.off=0 则则 gen(:=,E.place, , V.place) 否则否则 gen(:=,E.place, , V.placeV.off E V若若V.off=0 则则 E .place:= V.place 否则否则 E.place:=newtemp( ); gen(:=, V.placeV.off, , E.place)38本章习题本章习题 P220 7.2 a,b 7. 3 翻译成四元式翻译成四元式 39