编译原理中间代码生成7.ppt

《编译原理中间代码生成7.ppt》由会员分享，可在线阅读，更多相关《编译原理中间代码生成7.ppt（85页珍藏版）》请在三一办公上搜索。

1、第七章 中间代码生成,本章内容介绍几种常用的中间表示：后缀表示、图形表示和三地址代码用语法制导定义和翻译方案的方法来说明源语言的各种构造怎样被翻译成中间形式,7.1 中 间 语 言,7.1.1 后缀表示表达式E的后缀表示可以如下归纳定义如果E是变量或常数，那么E的后缀表示就是E本身,7.1 中 间 语 言,7.1.1 后缀表示表达式E的后缀表示可以如下归纳定义如果E是变量或常数，那么E的后缀表示就是E本身如果E是形式为E1 opE2的表达式，那么E的后缀表示是E1 E2 op，其中E1和E2分别是E1和E2的后缀表示,7.1 中 间 语 言,7.1.1 后缀表示表达式E的后缀表示可以如下归纳定

2、义如果E是变量或常数，那么E的后缀表示就是E本身如果E是形式为E1 opE2的表达式，那么E的后缀表示是E1 E2 op，其中E1和E2分别是E1和E2的后缀表示如果E是形式为(E1)的表达式，那么E1的后缀表示也是E的后缀表示,7.1 中 间 语 言,后缀表示不需要括号(8 4)+2 的后缀表示是8 4 2+,7.1 中 间 语 言,后缀表示不需要括号(8 4)+2 的后缀表示是8 4 2+后缀表示的最大优点是便于计算机处理表达式,7.1 中 间 语 言,后缀表示不需要括号(8 4)+2 的后缀表示是8 4 2+后缀表示的最大优点是便于计算机处理表达式后缀表示很容易拓广到含一元算符的表达式,

3、7.1 中 间 语 言,后缀表示不需要括号(8 4)+2 的后缀表示是8 4 2+后缀表示的最大优点是便于计算机处理表达式后缀表示很容易拓广到含一元算符的表达式 后缀表示也可以拓广到表示赋值语句和控制语句，但很难用栈来描述它的计算,7.1 中 间 语 言,7.1.2 图形表示语法树是一种图形化的中间表示,7.1 中 间 语 言,7.1.2 图形表示语法树是一种图形化的中间表示有向无环图也是一种中间表示,7.1 中 间 语 言,构造赋值语句语法树的语法制导定义,7.1 中 间 语 言,7.1.3 三地址代码一般形式：x=y op z表达式x+y z翻译成的三地址语句序列是t1=y z t2=x+

4、t1,7.1 中 间 语 言,三地址代码是语法树或dag的一种线性表示a=(b+cd)+cd语法树的代码t1=bt2=c dt3=t1+t2t4=c dt5=t3+t4a=t5,7.1 中 间 语 言,三地址代码是语法树或dag的一种线性表示a=(b+cd)+cd语法树的代码dag的代码t1=bt1=bt2=c dt2=c dt3=t1+t2t3=t1+t2t4=c dt4=t3+t2t5=t3+t4 a=t4a=t5,7.1 中 间 语 言,本书常用的三地址语句赋值语句x=y op z，x=op y，x=y无条件转移goto L条件转移if x relop y goto L过程调用param

5、 x 和call p,n过程返回 return y索引赋值x=yi和 xi=y地址和指针赋值x=&y，x=y和x=y,7.1 中 间 语 言,7.1.4 静态单赋值形式一种便于某些代码优化的中间表示和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值三地址代码静态单赋值形式p=a+bp1=a+b q=p cq1=p1 c p=q dp2=q1 d p=e pp3=e p2 q=p+q q2=p3+q1,7.1 中 间 语 言,7.1.4 静态单赋值形式一种便于某些代码优化的中间表示和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值一个变量在不同路径上都定值的解决办法if(

6、flag)x=1;else x=1;y=x a;的条件语句改成if(flag)x1=1;else x2=1;x3=(x1,x2);/由flag的值决定用x1还是x2,7.2 声 明 语 句,为局部名字建立符号表条目为它分配存储单元符号表中包含名字的类型和分配给它的存储单元的相对地址等信息,7.2 声 明 语 句,7.2.1 过程中的声明,7.2 声 明 语 句,计算被声明名字的类型和相对地址P offset=0D;SD D;D D id:Tenter(id.lexeme,T.type,offset);offset=offset+T.width T integer T.type=integer;

7、T.width=4 T real T.type=real;T.width=8 T array num of T1T.type=array(num.val,T1.type);T.width=num.val T1.widthT T1 T.type=pointer(T1.type);T.width=4,7.2 声 明 语 句,7.2.2 作用域信息的保存所讨论语言的文法P D;SD D;D|id:T|proc id;D;S 语义动作用到的函数mkTable(previous)enter(table,name,type,offset)addWidth(table,width)enterProc(tab

8、le,name,newtable),7.2 声 明 语 句,P M D;S addWidth(top(tblptr),top(offset);pop(tblptr);pop(offset)M t=mkTable(nil);push(t,tblprt);push(0,offset)D D1;D2D proc id;N D1;S t=top(tblptr);addWidth(t,top(offset);pop(tblptr);pop(offset);enterProc(top(tblptr),id.lexeme,t)Did:T enter(top(tblptr),id.lexeme,T.type,

9、top(offset);top(offset)=top(offset)+T.width N t=mkTable(top(tblptr);push(t,tblptr);push(0,offset),7.2 声 明 语 句,7.2 声 明 语 句,7.2.3 记录的域名T record D endT record L D endT.type=record(top(tblptr);T.width=top(offset);pop(tblptr);pop(offset)L t=mkTable(nil);push(t,tblprt);push(0,offset),7.3 赋 值 语 句,7.3.1 符号表

10、的中名字S id:=E p=lookup(id.lexeme);if p!=nil thenemit(p,=,E.place)else error E E1+E2E.place=newTemp();emit(E.place,=,E1.place,+,E2.place),7.3 赋 值 语 句,7.3.1 符号表的中名字E E1 E.place=newTemp();emit(E.place,=,uminus,E1.place)E(E1)E.place=E1.place E id p=lookup(id.lexeme);if p!=nil then E.place=p else error,7.3

11、 赋 值 语 句,7.3.2 数组元素的地址计算一维数组A的第i个元素的地址计算base+(i low)w,7.3 赋 值 语 句,7.3.2 数组元素的地址计算一维数组A的第i个元素的地址计算base+(i low)w 重写成i w+(base low w)减少了运行时的计算,7.3 赋 值 语 句,二维数组A:array1.2,1.3 of T列为主A1,1,A2,1,A1,2,A2,2,A1,3,A2,3,7.3 赋 值 语 句,二维数组A:array1.2,1.3 of T列为主A1,1,A2,1,A1,2,A2,2,A1,3,A2,3行为主A1,1,A1,2,A1,3,A2,1,A2

12、,2,A2,3,7.3 赋 值 语 句,二维数组A:array1.2,1.3 of T列为主A1,1,A2,1,A1,2,A2,2,A1,3,A2,3行为主A1,1,A1,2,A1,3,A2,1,A2,2,A2,3base+(i1 low1)n2+(i2 low2)w（其中n2=high2 low2+1）,7.3 赋 值 语 句,二维数组A:array1.2,1.3 of T列为主A1,1,A2,1,A1,2,A2,2,A1,3,A2,3行为主A1,1,A1,2,A1,3,A2,1,A2,2,A2,3base+(i1 low1)n2+(i2 low2)w（其中n2=high2 low2+1）(

13、i1 n2)+i2)w+(base(low1 n2)+low2)w),7.3 赋 值 语 句,多维数组下标变量Ai1,i2,.,ik 的地址表达式(i1 n2+i2)n3+i3)nk+ik)w+base(low1 n2+low2)n3+low3)nk+lowk)w,7.3 赋 值 语 句,7.3.3 数组元素地址计算的翻译方案下标变量访问的产生式L id Elist|idElist Elist,E|E改成L Elist|idElist Elist,E|id E,7.3 赋 值 语 句,所有产生式S L:=EE E+EE(E)E LL Elist L idElist Elist,EElist i

14、d E,7.3 赋 值 语 句,L id L.place=id.place;L.offset=null,7.3 赋 值 语 句,L id L.place=id.place;L.offset=null Elist id E Elist.place=E.place;Elist.ndim=1;Elist.array=id.place,7.3 赋 值 语 句,L id L.place=id.place;L.offset=null Elist id E Elist.place=E.place;Elist.ndim=1;Elist.array=id.place Elist Elist1,E t=newTe

15、mp();m=Elist1.ndim+1;emit(t,=,Elist1.place,limit(Elist1.array,m);emit(t,=,t,+,E.place);Elist.array=Elist1.array;Elist.place=t;Elist.ndim=m,7.3 赋 值 语 句,L id L.place=id.place;L.offset=null Elist id E Elist.place=E.place;Elist.ndim=1;Elist.array=id.place Elist Elist1,E t=newTemp();m=Elist1.ndim+1;emit(

16、t,=,Elist1.place,limit(Elist1.array,m);emit(t,=,t,+,E.place);Elist.array=Elist1.array;Elist.place=t;Elist.ndim=mL Elist L.place=newTemp();emit(L.place,=,base(Elist.array),invariant(Elist.array);L.offset=newTemp();emit(L.offset,=,Elist.place,width(Elist.array),7.3 赋 值 语 句,E Lif L.offset=null then/L是简

17、单变量/E.place=L.place else begin E.place=newTemp();emit(E.place,=,L.place,L.offset,)end,7.3 赋 值 语 句,E Lif L.offset=null then/L是简单变量/E.place=L.place else begin E.place=newTemp();emit(E.place,=,L.place,L.offset,)end E E1+E2E.place=newTemp();emit(E.place,=,E1.place,+,E2.place),7.3 赋 值 语 句,E Lif L.offset=

18、null then/L是简单变量/E.place=L.place else begin E.place=newTemp();emit(E.place,=,L.place,L.offset,)end E E1+E2E.place=newTemp();emit(E.place,=,E1.place,+,E2.place)E(E1)E.place=E1.place,7.3 赋 值 语 句,E Lif L.offset=null then/L是简单变量/E.place=L.place else begin E.place=newTemp();emit(E.place,=,L.place,L.offse

19、t,)end E E1+E2E.place=newTemp();emit(E.place,=,E1.place,+,E2.place)E(E1)E.place=E1.place S L=Eif L.offset=null then/L是简单变量/emit(L.place,=,E.place)else emit(L.place,L.offset,=,E.place),7.3 赋 值 语 句,7.3 赋 值 语 句,t1=y 20 t1=t1+z,7.3 赋 值 语 句,t1=y 20 t1=t1+z,t2=A 84 t3=4 t1,7.3 赋 值 语 句,t1=y 20 t1=t1+z,t2=A

20、 84 t3=4 t1,t4=t2 t3,7.3 赋 值 语 句,t1=y 20 t1=t1+z,t2=A 84 t3=4 t1,t4=t2 t3,x=t4,7.3 赋 值 语 句,7.3.4 类型转换x=y+i j（x和y的类型是real，i和j的类型是integer）中间代码t1=i int jt2=inttoreal t1 t3=y real+t2 x=t3,7.3 赋 值 语 句,E E1+E2E.place=newTemp();if E1.type=integer E.type=realend.,7.4 布尔表达式和控制流语句,7.4.1 布尔表达式布尔表达式有两个基本目的计算逻辑值

21、在控制流语句中用作条件表达式本节所用的布尔表达式文法B B or B|B and B|not B|(B)|E relop E|true|false,7.4 布尔表达式和控制流语句,7.4.1 布尔表达式布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式布尔表达式的完全计算值的表示数值化，其计算类似于算术表达式的计算,7.4 布尔表达式和控制流语句,7.4.1 布尔表达式布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式布尔表达式的完全计算值的表示数值化，其计算类似于算术表达式的计算布尔表达式的“短路”计算 B1 or B2 定义成 if B1 then true els

22、e B2 B1 and B2 定义成 if B1 then B2 else false用控制流来实现，即用程序中的位置来表示值,7.4 布尔表达式和控制流语句,7.4.2 控制流语句的翻译S if B then S1|if B then S1 else S2|while B do S1|S1;S2,7.4 布尔表达式和控制流语句,7.4 布尔表达式和控制流语句,S if B then S1B.true=newLabel();B.false=S.next;S1.next=S.next;S.code=B.code|gen(B.true,:)|S1.code,7.4 布尔表达式和控制流语句,S if

23、 B then S1 else S2B.true=newLabel();B.false=newLabel();S1.next=S.next;S2.next=S.next;S.code=B.code|gen(B.true,:)|S1.code|gen(goto,S.next)|gen(B.false,:)|S2.code,7.4 布尔表达式和控制流语句,S while B do S1 S.begin=newLabel();B.true=newLabel();B.false=S.next;S1.next=S.begin;S.code=gen(S.begin,:)|B.code|gen(B.true

24、,:)|S1.code|gen(goto,S.begin),7.4 布尔表达式和控制流语句,S S1;S2S1.next=newLabel();S2.next=S.next;S.code=S1.code|gen(S1.next,:)|S2.code,7.4 布尔表达式和控制流语句,7.4.3 布尔表达式的控制流翻译如果B是a b的形式，那么代码是：if a b goto B.truegoto B.false,7.4 布尔表达式和控制流语句,表达式a b or c d and e f的代码是：if a b goto Ltruegoto L1L1:if c d goto L2goto Lfalse

25、L2:if e f goto Ltruegoto Lfalse,7.4 布尔表达式和控制流语句,B B1 or B2B1.true=B.true;B1.false=newLabel();B2.true=B.true;B2.false=B.false;B.code=B1.code|gen(B1.false,:)|B2.code,7.4 布尔表达式和控制流语句,B B1 or B2B1.true=B.true;B1.false=newLabel();B2.true=B.true;B2.false=B.false;B.code=B1.code|gen(B1.false,:)|B2.code B no

26、t B1B1.true=B.false;B1.false=B.true;B.code=B1.code,7.4 布尔表达式和控制流语句,B B1 and B2B1.true=newLabel();B1.false=B.false;B2.true=B.true;B2.false=B.false;B.code=B1.code|gen(B1.true,:)|B2.code,7.4 布尔表达式和控制流语句,B B1 and B2B1.true=newLabel();B1.false=B.false;B2.true=B.true;B2.false=B.false;B.code=B1.code|gen(B1

27、.true,:)|B2.code B(B1)B1.true=B.true;B1.false=B.false;B.code=B1.code,7.4 布尔表达式和控制流语句,B E1 relop E2B.code=E1.code|E2.code|gen(if,E1.place,relop.op,E2.place,goto,B.true)|gen(goto,B.false),7.4 布尔表达式和控制流语句,B E1 relop E2B.code=E1.code|E2.code|gen(if,E1.place,relop.op,E2.place,goto,B.true)|gen(goto,B.fals

28、e)B trueB.code=gen(goto,B.true)B falseB.code=gen(goto,B.false),7.4 布尔表达式和控制流语句,7.4.4 开关语句的翻译switch Ebegincase V1:S1case V2:S2.case Vn-1:Sn 1default:Snend,7.4 布尔表达式和控制流语句,分支数较少时t=E的代码|Ln-2:if t!=Vn-1 goto Ln-1 if t!=V1 goto L1|Sn-1的代码 S1的代码|goto nextgoto next|Ln-1:Sn的代码 L1:if t!=V2 goto L2|next:S2的代码

29、goto nextL2:.,7.4 布尔表达式和控制流语句,分支较多时，将分支测试的代码集中在一起，便于生成较好的分支测试代码。t=E的代码|Ln:Sn的代码goto test|goto nextL1:S1的代码|test:if t=V1 goto L1 goto next|if t=V2 goto L2 L2:S2的代码|.goto next|if t=Vn-1 goto Ln-1.|goto LnLn-1:Sn-1的代码|next:goto next,7.4 布尔表达式和控制流语句,中间代码增加一种case语句，便于代码生成器对它进行特别处理 test:case V1 L1case V2

30、L2.case Vn-1 Ln-1case t Ln next:,7.4 布尔表达式和控制流语句,7.4.5 过程调用的翻译S call id(Elist)Elist Elist,EElist E,7.4 布尔表达式和控制流语句,过程调用id(E1,E2,En)的中间代码结构E1.place=E1的代码E2.place=E2的代码.En.place=En的代码param E1.placeparam E2.place.param En.placecall id.place,n,7.4 布尔表达式和控制流语句,S call id(Elist)为长度为n的队列中的每个E.place，emit(par

31、am,E.place);emit(call,id.plase,n)Elist Elist,E把E.place放入队列末尾Elist E将队列初始化，并让它仅含E.place,本 章 要 点,中间代码的几种形式，它们之间的相互转换符号表的组织和作用域信息的保存数组元素定址的翻译方案，布尔表达式的两种不同实现方式赋值语句和各种控制流语句的中间代码格式和生成中间代码的翻译方案过程调用的中间代码格式和生成中间代码的翻译方案,例 题 1,Pascal语言的标准将for语句for v:=initial to final do stmt定义成和下面的代码序列有同样的含义：begint1:=initial;t

32、2:=final;if t1 t2 do beginv:=succ(v);stmtendendend,例 题 1,Pascal语言的标准将for语句for v:=initial to final do stmt能否定义成和下面的代码序列有同样的含义？begint1:=initial;t2:=final;v:=t1;while v=t2 do beginstmt;v:=succ(v)endend,例 题 1,Pascal语言for语句for v:=initial to final do stmt的中间代码结构如下:t1=initialt2=finalif t1 t2 goto L1v=t1 L2

33、:stmtif v=t2 goto L1v=v+1goto L2 L1:,例 题 2,C语言的for语句有下列形式for(e1;e2;e3)stmt它和e1;while(e2)do beginstmt;e3;end,例 题 2,C语言的for语句for(e1;e2;e3)stmt的中间代码结构如下 e1的代码L1:e2的代码L2:e3的代码 goto L1 stmt的代码 goto L2,例 题 3,Pascal语言var a,b:array1.100 of integer;a:=b允许数组之间赋值若a和b是同一类型记录，也允许C语言数组类型不行，结构类型可以为这种赋值选用或设计一种三地址语句

34、，它要便于生成目标代码,例 题 3,Pascal语言var a,b:array1.100 of integer;a:=b允许数组之间赋值若a和b是同一类型记录，也允许仍然用中间代码复写语句 x=y，在生成目标代码时，必须根据它们类型的size，产生一连串的值传送指令,例 题 4,下面的翻译方案使用了变量offset，请重写该翻译方案，它完成同样的事情，但只使用文法符号的属性，而不使用变量offsetP offset=0 DD D;D D id:T enter(id.lexeme,T.type,offset);offset=offset+T.width T integerT.type=integ

35、er;T.width=4 T realT.type=real;T.width=8,例 题 4,P D.offset1=0 D P.offset=D.offset2 D D1.offset1=D.offset1 D1;D2.offset1=D1.offset2 D2 D.offset2=D2.offset2 D id:Tenter(id.lexeme,T.type,D.offset1);D.offset2=D.offset1+T.width T integer T.type=integer;T.width=4 T realT.type=real;T.width=8,习 题,第一次：7.1第二次：7.4,7.8,7.10,