编译 第四章 中间代码生成.ppt

1 翻译方式有两种: 第四章 中间代码生成中间代码生成 源语言目标语言 源语言 1) 2) 目标语言 中间代码 中间代码的特点: 结构简单,功能明确,易于优化,易于翻译. 2 第一节 中间代码简介 1) 逆波兰表示法 运算量在前,运算符在后的后缀式表示法. 例如: 表达式后缀式 a+bab+ (a+b)*cab+c* a*(b+c)abc+* (a+b)*(c+d)ab+cd+* 3 2) 三元式表示法 三元式就是三元组: ( 操作符,操作数1,操作数2) 例如: 语句 d:=a+b*c 可翻译为下述三元式表: (1) (*,b,c) (2) (+,a,(1) (3) (:=,d,(2) 三元式没有明确指出结果放在何处. 4 3) 四元式表示法 四元式就是四元组: ( 操作符,操作数1,操作数2,结果) 例如: 语句 d:=a+b*c 可翻译为下述四元式表: (1) (* ,b ,c ,t1) (2) (+ ,a ,t1,t2) (3) (:= ,t2, , d ) 四元式间通过临时变量传值. 操作符实现的运算也非常简单, 本章主要介绍各种语句到四元式的翻译. 5 第二节 语法制导翻译的基本思想 1 何谓语法制导翻译 在语法分析的每次归约或推导时,根据产生式的语义进行 翻译的一种方法. 翻译时,除了产生中间代码外,还有许多辅助工作,包括: 改变语法变量的值;查填符号表;诊查与报告源程序错误等. 2 与翻译相关的若干约定 1) 临时变量 在翻译中,可能会引入许多临时变量存放中间结果. 通过调用 newtemp() 返回一个临时变量 ti . 6 2) 分析栈 分析栈中的内容为语法单位,每个语法单位包含两个部分: (语法单位名称,语法单位属性),属性可能有多个值. 例如: e 为表达式的语法单位, e.place 代表了该表达式值 存放的地方. 3) 符号表 符号表用于存放变量及属性值,由如干项构成,每个项为: (变量名, 变量信息). 4) 四元式表 四元式表用于存放翻译中产生的四元 式,通过过程 gen( 操作符,操作数1,操作数2,结果) 把四元式存入四元式表的 nxq 所指 空间中, nxq 自动加 1. 四元式表 nxq 7 5 一些基本操作 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:real x,y,z:t x,y,d x,d d t.att=real d.att=real;fill(z,real) d.att=real;fill(y,real) d.att=real;fill(z,real) 最终,符号表中包含了 x,y,z 三个变量及属性 real. 12 第四节 简单算术表达式 和赋值语句的翻译 简单算术赋值语句的文法可表示为: si:=e ee+e | e-e | e*e | e/e | (e) | i 该文法为二义文法,但如果规定每个终结符的优先关系,并按 优先关系进行归约,则可以避免二义性. 赋值语句的含义是:计算出 e 的值,并写入变量 i 中. 编译中,并不关心值是多少,而关心的是怎样计算值的过程; 也即,哪些变量参加运算,怎样运算? 上面文法的各产生式语义子程序如下: 13 ei e.place:=entry(i) /e.place 表示了表达式e 的值放在什么变量中 e(e1) e.place:= e1.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) e e1 / e2 e.place:=newtemp( ) gen( / , e1 .place, e2.place, e.place) s i := e gen( := , e.place , ,entry( i ) 四元式中的操作数及结果,实质上是一指向变量的指针. 14 示例: x:=y+z x:=y+z x:=y x:=e x:=e+z x:=e1+e2 e.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= 或 =或 16 bi b.place:=entry(i) /b.place 表示了表达式b 的值放在什么变量中 b(b1) b.place:= b1.place b 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 第六节 分支语句的翻译 分支语句包括: if case(省略) goto 1 if 语句的翻译 在程序设计种,if 语句可以表示为: if b then s1 else s2; if 语句翻译后,将得到一组四元式,其流程可以表示为: 18 b 的四元式 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 goto c else x:=1; if y1 then goto c else y:=1; c:x:=1; y:=1; if x,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 s repeat s until b for i:=e1 to e2 do s 1 while b do s 的翻译 该语句翻译为如右图所示的 四元式系列. 从流程图中可以看出,有两处 的四元式地址需特殊处理: b 的四元式 b为真? s 的四元式 f * * 26 while 语句的文法及语义子程序如下: 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 的第一条四元式地址 27 2 repeat s until b 的翻译 sr s until b gen(jz, b.place, ,r.q) rrepeat r.q:=nxq *s 可以是复合语句 s 的四元式 b为真? b的四元式 f t 28 3 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+1 29 第八节 数组的翻译 这节讨论三个问题: 数组说明的翻译 数组元素的翻译 含数组元素的赋值语句的翻译 1 数组说明语句的翻译 进行数组说明语句的 翻译时,要把数组名填入符号表, 并建立一内情向量表,记录维数,下标上下界,类型等. 简单起见,只考虑如下的数组说明: a:arrayl1:u1, l2:u2,. ln:un of type 30 文法如下: di:array list of t listi(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 数组相对地址的计算： 一维：ai的相对地址为：base+(i-low)*w，其中 ：w为每个元素的宽度，low为数组的下界，base为 分配给数组元素的相对地址。 原式可以变形为：i*w+(base-low*w)，可以设 a= base ,c=low*w,则原式等价为：i*w+a-c 二维：ai1,i2的相对地址为： base+(i1-low1)*d2+i2-low2)*w 其中：d2为i2可以取值的个数，可以变行为： (i1*d2)+i2)*w+(base-(low1*d2)+low2)*w) 以此类推n维： (i1d2+i2)d3+i3)dn+in)*w+ base-(low1d2+low2)d3+low3)dn+lown)*w 32 l1 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 *elemlength 33 2 数组元素的翻译 设数组元素为: a e1,e2,en, 要取得该元素值,首先要计算 出该元素的地址: addr=conspart+varpart conspart =a -c varpart = (.(e1d2+e2)d3+e3)d4+e4) dn + en *elemlength conspart 的 a c 已经通过数组说明语句的翻译登记在内 情向量表中; 而 varpart 中含有未知数,只能在程序运行时通过如 下算法实现: 34 varpart:=e1;k:=1; while kn do varpart:=varpart*dk +1 + ek +1; k:=k+1 varpart:=varpart*elemlength 下面是包含数组元素的变量的文法: vi | i e1,e2,en 为了便于翻译上面的算法,文法改为如下形式: vi | elist elisti 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 的维数 eli