编译原理课件第五章中间代码生成

1、翻译方式有两种:,第五章 中间代码生成,中间代码的特点: 结构简单,功能明确,易于优化,易于翻译.,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) 四元式表示法 四元式就是四元组:

2、 ( 操作符,操作数1,操作数2,结果) 例如: 语句 D:=A+B*C 可翻译为下述四元式表: (1) (* ,B ,C ,T1) (2) (+ ,A ,T1,T2) (3) (:= ,T2, , D ) 四元式间通过临时变量传值. 操作符实现的运算也非常简单, 本章主要介绍各种语句到四元式的翻译.,5,第二节 语法制导翻译的基本思想,1 何谓语法制导翻译 在语法分析的每次归约或推导时,根据产生式的语义进行 翻译的一种方法. 翻译时,除了产生中间代码外,还有许多辅助工作,包括: 改变语法变量的值;查填符号表;诊查与报告源程序错误等. 2 与翻译相关的若干约定 1) 临时变量 在翻译中,可能会

3、引入许多临时变量存放中间结果. 通过调用 newtemp() 返回一个临时变量 Ti .,6,2) 分析栈 分析栈中的内容为语法单位,每个语法单位包含两个部分: (语法单位名称,语法单位属性),属性可能有多个值. 例如: E 为表达式的语法单位, E.place 代表了该表达式值 存放的地方. 3) 符号表 符号表用于存放变量及属性值,由如干项构成,每个项为: (变量名, 变量信息). 4) 四元式表 四元式表用于存放翻译中产生的四元 式,通过过程 Gen( 操作符,操作数1,操作数2,结果) 把四元式存入四元式表的 NXQ 所指 空间中, NXQ 自动加 1.,四元式表,NXQ,7,5 一些

4、基本操作,newtemp( ) 产生一临时变量; gen(操作符,操作数1,操作数2,结果) 填入四元式表; fill( i,属性)填入符号表; entry( i )查符号表,返回 i 在符号表中的位置; backpatch( m,n) 把 n 填入 四元式表第 m 个四元式中;,8,第三节 简单变量说明语句的翻译,程序设计中,首先应该对程序中使用的变量进行说明.其目的 是规定变量所占用空间的大小. 编译时, 对变量说明语句的翻译工 作,本质上就是把变量名及属性登记在符号表中,以便后续工作中 使用. pascal 语言的简单变量说明语句为: x,y,z:real; 语法可表示为: D NAME

5、LIST:T NAMELIST NAMELIST,i | i T integer|real|boolean|char,该文法代表了所有 非结构型变量的说明语 句.,9,当然,也可以用如下文法表示: Di:T | i,D T integer|real|boolean|char 我们已经知道用该文法如何分析一个说明语句,下面要解决 的是,怎样在分析的过程中, 把该语句表达的意思完整的翻译清楚. 说明语句的含义是: 说明的变量具有给定类型; 编译时则翻译为:把每个变量及类型登记在符号表中. 语法制导翻译就是为每一条产生式配一个子程序,当用某个 产生式归约时,就调用相应的子程序进行适当的翻译工作. 这

6、些子程序称为语法单位的语义子程序(或语义动作).,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,第四节 简单算术表达式 和赋值

7、语句的翻译,简单算术赋值语句的文法可表示为: 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:=new

8、temp( ) 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 ) 四元式中的

9、操作数及结果,实质上是一指向变量的指针.,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 | = | 该文法也为二义文法,但如果规定每个终结符的优先关系,并按 优先关系

10、进行归约,则可以避免二义性. 各产生式语义子程序如下: 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(

11、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,分析是从前向后进行的,按四元式 流程的要求, (1)首先归约布尔表达式,产生B的四元式; (2)在归约S1之前,应产生条件转移语句,

12、也即 当归约 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, ,

13、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)

14、(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 f

15、ill(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,可以利用标号表地址栏,当标号已定义时,地址栏就是标号 所代表的地址;当标号未定义

16、时,地址栏用于连接所有转移到该 标号的转移四元式,当翻译到标号定义时,以便回填所有转移到 该标号的转移四元式. 文法及语义动作如下: 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,第七节 循环语句的翻译,循环语句有三种方式: while B do S repeat S until B for i:=E1 to E2 do

17、 S 1 while B do S 的翻译 该语句翻译为如右图所示的 四元式系列. 从流程图中可以看出,有两处 的四元式地址需特殊处理:,*,*,25,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 的第一条四元式地址,26,2 repeat S until B 的翻译 SR S until B Gen(Jz, B.

18、place, ,R.q) Rrepeat R.q:=NXQ *S 可以是复合语句,S 的四元式,B为真?,B的四元式,F,T,27,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.p

19、lace :=entry(i) ,E1的四元式,i E2?,E2的四元式,T,i:=E1,S的四元式,i:=i+1,28,第八节 数组的翻译,这节讨论三个问题: 数组说明的翻译 数组元素的翻译 含数组元素的赋值语句的翻译 1 数组说明语句的翻译 进行数组说明语句的 翻译时,要把数组名填入符号表, 并建立一内情向量表,记录维数,下标上下界,类型等. 简单起见,只考虑如下的数组说明: A:arrayL1:U1, L2:U2,. Ln:Un of TYPE,29,文法如下: Di:array LIST of T LISTi(1):i(2)| LIST (1) , i(1):i(2) Tinteger

20、|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 填入内情向量表. 数组说明语句不产生四元式.,30,c = ( L1 )*d2d3d4.dn + ( L2 )* d3d4.

21、dn + ( Ln-1)* dn + ( Ln ) *elemlength = (.(L1d2+L2)d3+L3)d4+L4).) dn + Ln *elemlength,31,2 数组元素的翻译 设数组元素为: A E1,E2,.En, 要取得该元素值,首先要计算 出该元素的地址: addr=conspart+varpart conspart =a -c varpart = (.(E1d2+E2)d3+E3)d4+E4).) dn + En conspart 的 a c 已经通过数组说明语句的翻译登记在内 情向量表中; 而 varpart 中含有未知数,只能在程序运行时通过如 下算法实现:,

22、32,varpart:=E1;k:=1; while kn do varpart:=varpart*dk +1 + Ek +1; K:=k+1 下面是包含数组元素的变量的文法: 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;,33,Elist 有三个值 : Elist.array/ i 在符号表中的位置 Elist.dim/ i 的维数 Elist.