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

翻译方式有两种:,第四章 中间代码生成,中间代码的特点:结构简单,功能明确,易于优化,易于翻译.,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,12,第四节 简单算术表达式 和赋值语句的翻译,简单算术赋值语句的文法可表示为:Si:=EEE+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.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+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:=E,E.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.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(省略)goto,1 if 语句的翻译 在程序设计种,if 语句可以表示为:if B then S1 else S2;if 语句翻译后,将得到一组四元式,其流程可以表示为:,18,分析是从前向后进行的,按四元式流程的要求,(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:=4,x:=2 else y:=4,C,CS1else,T,TS2,x:=2 else y:=4,y:=4,if B then,四元式序列(1)(,A,1,T1)(2)(Jz,T1,xxxx)(5)(3)(:=,2,x)(4)(J,xxxx)(6)(5)(:=,4,y)(6),y:=4,S,C.chain=(2);Gen(Jz,T1,xxxx),T.chain=(4);Gen(J,xxxx);backpatch(2),(5),backpatch(4),(6),NXQ,21,2 标号及转移语句的翻译 处理标号包括三个含义:标号说明 标号定义 标号引用(1)标号说明的翻译 标号说明语句的语法如下:Lablabel c|Lab,c 标号说明语句用于说明程序中使用的所有标号,翻译时只需将所有标号登记在标号表中.标号表的内容如右图所示:Lablabel c fill(c,未,0)Lab Lab,c fill(c,未,0),22,(2)标号定义及引用 标号定义是指:确定标号所代表的某个四元式地址.一般形式为:c:S c 这一标号代表了S的第一条四元式地址.标号引用一般通过 goto c 实现.一般程序设计中,允许标号的引用及定义交叉进行,如下所示:,goto c;goto c;c:S;goto c;,因此,当翻译到第一个 goto 语句时,标号 c 还未定义,goto 语句的转移地址 不确定,只有翻译到标号定义时,才能回 过头来回填地址.,23,可以利用标号表地址栏,当标号已定义时,地址栏就是标号所代表的地址;当标号未定义时,地址栏用于连接所有转移到该标号的转移四元式,当翻译到标号定义时,以便回填所有转移到该标号的转移四元式.文法及语义动作如下:S goto c 若 c 已定义 则 Gen(J,entry(c).addr)否则 Gen(J,entry(c).addr);entry(c).addr:=NXQ-1 Ldefc:令 entry(c).定义否:=已定义;用 NXQ 回填 entry(c).addr 链中所有 转移四元式,24,示例：if x1 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 y1 then goto c else y:=1;,(1)(,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 的翻译 该语句翻译为如右图所示的四元式系列.从流程图中可以看出,有两处的四元式地址需特殊处理:,*,*,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 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,数组相对地址的计算：一维：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,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+varpartconspart=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|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,36,Elist 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.place,37,3 含数组元素的赋值语句的翻译 赋值语句的文法扩充如下:(对比前面的赋值语句)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,