哈工大编译原理.ppt

《哈工大编译原理.ppt》由会员分享，可在线阅读，更多相关《哈工大编译原理.ppt（65页珍藏版）》请在三一办公上搜索。

1、1,第六章 中间代码,辛明影,2,中间代码生成 6.1 中间语言 6.2 常用语句的翻译 6.2.1 说明语句 6.2.2 赋值语句 6.2.3 布尔表达式 6.2.4 过程语句,辛明影,3,序“中间代码生成”程 序的任务是：,方法：语法制导翻译。,采用独立于机器的中间代 码的好处：,把经过语法分析和语义分析而获得的源程序中间表 示翻译为中间代码表示。,1.便于编译系统建立和编译系统的移植；,2.便于进行独立于机器的代码优化工作。,辛明影,4,6.1 中间语言 语法树 后缀式 三地址代码表示,6.1.1 图表示法 语法树，有向非循环图和后缀式表示源程序的自然层次结构，例如：a:=b*-c+b*

2、-c,辛明影,5,=,a,+,*,b,c,-,(a)语法树,*,-,c,b,辛明影,6,赋值语句：中 缀式：a:=b*-c+b*-c后缀式：a b c-*b c-*+=,辛明影,7,=,a,+,*,b,c,-,(b)dag(Directed Acyclic Graph),辛明影,8,6.1.2 三地址代码 一般形式 x：y op z,相应于图6.1的树和dag的三地址代码,t1：-c t2：b*t1 t5：t2+t2 a：=t5 对于dag的代码,t1：-c t2：b*t1 t3：-c t4：b*t3 t5：t2+t4 a：t5 对于语法树的代码,辛明影,9,（3）无条件转移语句goto L;

3、,（4）条件转移语句 if x relop y goto L，关系运算符号relop(，=，=等等）;,（2）赋值语句 x：op y，op为一目算符，如一目减uminus、逻辑非not、移位算符及转换算符;,（1）赋值语句 x：y op z，op为二目算术算符或逻辑算符;,6.1.3 三地址语句的种类,辛明影,10,（5）复制语句 x：y;,（8）地址和指针赋值 xy，x*y 和*xy。,（7）索引赋值 x:=yi 及 xi:=y;,（6）过程调用语句 param x 和 call p,n;过程返回语句 return y;,辛明影,11,6.1.4 三地址代码的具体实现,1四元式 op,arg

4、1,arg2,result 2三元式 op,arg1,arg2 3间接三元式 间接码表+三元式表,四元式需要利用较多的临时单元,四元式之 间 的联系通过临时变量实现。,中间代码优化处理时，四元式比三元式方便的多,间接三元式与四元式同样方便，两种实现方式需要的存储空间大体相同。,辛明影,12,1、x=y op z,常用三地址码的四元式表示：,2、x=op y,3、goto L,4、if x rop y goto L,5、x=y,6、parm x call p,n,（op,y,z,x),（op,y,x),（j,L),(jrop,x,y,L),(=,y,x),(param,x),(=,yi,x),(

5、=&,y,x),8、x=&y x=*y,7、x=yi xi=y,辛明影,13,对于语句a:=b*-c+b*-c 的三种表示方法,三地址语句的四元式表示,(-,c,t1)(*,b,t1,t2)(-,c,t3)(*,b,t1,t4)(+,t2,t4,t5)(=,t5,a),辛明影,14,(0)(1)(2)(3)(4)(5),uminus*uminus*+assign,cbcb（1）a,arg1,(0)(2)(3)(4),arg2,op,三地址语句的三元式表示,三元式中使用指向三元式语句的指针。,辛明影,15,arg1,arg2,op,statement,(14)(15)(14)(15)(16)(1

6、7),(0)(1)(2)(3)(4)(5),三地址语句的间接三元式表示,语句的移动仅改变左边的语句表,-c*b 14+14 15=15 a,辛明影,16,相对地址：相对静态数据区基址,6.2.1 说明语句,6.2 常用语句的翻译,说明语句的翻译：,对每个局部名字，,在符号表中建立相应的表项，,填写有关的信息.,如类型、嵌套深度、相对地址,内情向量等。,或活动记录中局部数据区基址,的一个偏移值,辛明影,17,一、过程中的说明语句,下面是类型说明和数组说明的文法和翻译方案,PD DD;D Did：TTintegerTreal,x:integer;y:real,一个过程中的所有说明语句作为一个类集来

7、处理。,用一个全程变量Offset来记录下 一个数据在符号表中的相对地址。,Tarraynumof T1,T T1,辛明影,18,PD,DD;D,Did：T,Tinteger,Treal,Tarraynumof T1,T T1,offset：0D,enter（id.name，T.type，offset）;offset:=offsetT.width,T.type：=integer;T.width：=4,T.type：real;T.width：8,T.type:array（num.val,T1.type);T.width：num.val*T1.width,T.type:pointer（T1type

8、）；T.width：=4,辛明影,19,Name type kind addrXY,real 简单变量 4,int 简单变量 0,x:integer;y:real,P,Offset=0,D,D,D,;,x,:,T,Y,:,T,Enter;offset,Enter;offset,Offset=0,Offset=4,Offset=12,Int,real,T.typeT.width,T.typeT.width,T.type=intT.width=4,T.type=realT.width=8,辛明影,20,1.问题的提出,二、保留作用域信息,一般的语言中，标识符的作用在程序正文中有一个确定的范围。,因

9、此，同一个标识符在不同的程序正文中可能标识不同的对象，,具有不同的性质，要求分配不同的存储空间。,辛明影,21,于是提出下面的问题：,如何组织符号表，,使得同一个标识符在不同的作用域中得到正确的引用而不产生混乱。,进一步我们考虑一下具有嵌套定义的程序结构,辛明影,22,2.嵌套的程序结构,program sort（input，output）；var x,a：array0.10 of integer；begin end.,procedure readarray；var i：integer；begin end；,procedure quicksort（m，n：integer）；var i,k：in

10、teger；begin end；,procedure exchange；begin end；,procedure partition（y，z：integer）var i，j：integer；begin end;,辛明影,23,嵌套说明的文法：,PD DD;D Did：TDproc id;D;S.,此处的T用于产生类型；S用于产生语句,辛明影,24,嵌套说明的程序结构首先要解决的问题是：非局部数据的访问,综合上述情况，对于程序结构采用分程序结构的程序来说，要解决的问题是：,局部数据的访问,2.非局部数据的访问,解决方法:为每一个过程建立一个符号表,辛明影,25,具体翻译时，每当碰到过程说明Dpr

11、oc id;D1;S时,便创建一张符号表,并且把D1中的所有说明都填入此符号表中,新表中有一个指针，指向其直接外围过程符号表,用于解决非局部数据的访问,同时还要在直接外围过程符号表中增加一个指向该过程D1符号表的指针,过程名id 作为直接外围过程的局部名字记录在直接外围过程符号表中；,辛明影,26,Nil header x a readarray exchange quicksort,sort,header i,header,readarray,exchange,Header I k patition,Header I j,quicksort,patition,嵌套过程的符号表,辛明影,27,

12、翻译时常用操作：,4.enterproc（table,name,newtable）在外围过程符号表中建立内嵌过程的新表项,1.mktable(previous）创建一张新符号表,2.Enter(table，name，type，offset)插入表项,3.addwidth（table，width）记录总域宽,指向直接外层符号表,指向当前过程符号表,指向直接外层符号表,指向内层过程的符号表,指向当前外层符号表,内嵌过程名字,辛明影,28,Tblptr是一个栈，用于存放指向嵌套外层过程的符号表指针,Offset是一个栈，用于存放变量的相对地址，当过程结束时，offset里记录的是过程占用的所有字节数

13、。,翻译时用到的数据结构：,辛明影,29,处理嵌套过程中的说明语句翻译方案,PMDaddwidth(top(tblptr),top(offset);pop();pop(offset),M t:=mktable（nil）；push(t,tblptr);push(0,offset),DD1；D2,Dproc id;N D1；St:top（tblptr);addwidth(t,top(offset);pop（tblptr）；pop（offset);enterproc(top（tblptr），id.name，t),辛明影,30,D id:T enter(top(tblptr),id.name,T.ty

14、pe,top(offset);top(offset）：=top(offset)T.width,例：,procedure quicksort（m，n：integer）；var i：integer；begin end；,procedure partition（y，z：integer）var i，j，x，v：integer；begin end;,N t：mktable(top（tblptr)；push(t，tblptr）；push（0，offset),辛明影,31,P,M,D,proc,Q,;,N,D,;,S,proc,P,;,N,D,;,S,j,:,T,int,辛明影,32,上述语法树对应的语句：

15、Proc Q;proc R;j:int;S;S,遍历语法树所得到的翻译序列：,执行上面翻译序列符号表及栈的变化,辛明影,33,tabptr offset,t,主,0,主,T=Q,Q,0,Q,T=p,P,0,*,t.type=intt.width=4,J int 0,4,t,4,R,t,0,Q,0,M t:=mktable（nil）；push(t,tblptr);push(0,offset),N t：mktable(top（tblptr)；push(t，tblptr）；push（0，offset),N t：mktable(top（tblptr)；push(t，tblptr）；push（0，off

16、set),TintegerT.type：=integer;T.width：=4,D id:T enter(top(tblptr),id.name,T.type,top(offset);top(offset）：=top(offset)T.width,Dproc id;N D1；St:top（tblptr);addwidth(t,top(offset);pop（tblptr）；pop（offset);enterproc(top（tblptr），id.name，t),Dproc id;N D1；St:top（tblptr);addwidth(t,top(offset);pop（tblptr）；pop

17、（offset);enterproc(top（tblptr），id.name，t),PMDaddwidth(top(tblptr),top(offset);pop(tblptr);pop(offset),辛明影,34,一组嵌套过程，每个过程说明为局部名字建立一个符号表，所有正在翻译过程的符号表组成整个源程序的符号表。,翻译语句部分时查找符号表，查找过程的符号表的路线相当于当前被 翻译过程的静态链。,辛明影,35,三、记录中的域名 T record LD end T.type:=record（top（tblptr)；T.width:top(offset)；pop（tblptr);pop(offs

18、et)L t:=mktable(nil);push(t,tblptr);push(0,offset)为个记录中的域名建立一张符号表 该翻译模式强调了作为一个语言结构的记录的设计与活动记录之间的相似处.,辛明影,36,一、符号表中的名字,6.2.2 赋值语句,赋值语句的翻译：,如何根据名字查找符号表的表项？,表达式的成分可以是整型量、实型量、数组 元素和记录,名字可以理解为指向符号表中相应该名字表项的指针,过程lookup(id.name)检查是否在符号表中存在相应此名字的表项。,辛明影,37,用最近嵌套作用域规则查找非局部名字,若找到，返回有关信息。,lookup过程先通过top(tblptr

19、）指针在当前符号表中查找名字为name的表项。,若未找到，lookup就利用当前符号表表头的指针找到该符号表的外围符号表，,然后在那里查找名字为name的表项，,直到所有外围过程的符号表中均无此name表项，,则lookup返回nil,表明查找失败。,辛明影,38,lookup(id.name)=id.entry nil,emit 它将生成的三地址代码送到输出文件上。例：emit(E.place:=E1.place+E2.place)或emit(=,E1.place，E2.place，E.place),二、简单算术表达式及赋值语句,辛明影,39,Sid:=E,产生赋值语句三地址代码的翻译模式,

20、EE1+E2,EE1*E2,p:=lookup(id.name);if pnil then emit(p:=E.place)else error,E.place=newtemp;emit(E.place:=E1.place+E2.place),E.place=newtemp;emit(E.place:=E1.place+E2.place),辛明影,40,E(E1),Eid,E-E,E.place:=newtemp;emit(E.place:=uminusE1.place,E.place:=E1.place,p:=lookup(id.name);if pnil then E.place:=p e

21、lse error,辛明影,41,语义动作应包括类型分析，文法符号应有类型属性，在类型分析的基础上，进行相容和赋值相容检查，生成类型转换的三地址代码。,辛明影,42,数组元素的目标代码是什么？,三、数组元素地址分配（复杂赋值语句）,如何生成数组元素的三地址代码?,数组元素的三地址代码是什么？,回顾一下，数组元素的地址计算公式：,辛明影,43,任一数组元素Ai1,i2,in的地址为：D=a+(i1-l1)d2d3 dn+(i2-l2)d2 d2 dn+(in-1-ln-1)dn+(in-ln),整理后C=(l1 d2+l2)d3+l3)d4+ln-1)dn+ln,C是数组计算中不变的部分,辛明影

22、,44,变量部分：v=(i1 d2+i2)d3+i3)d4+in-1)dn+in,i1地址：v=i1 i1,i2地址：v=i1 d2+i2=ai1 d2+i2i1,i2，i3地址：v=(i1 d2+i2)d3+i3=i1,i2 d3+i3i1,i2,i3,.,in地址:v=(i1 d2+i2)d3+i3)d4+in-1)dn+in=i1,i2,i3,.,in-1 dn+in,辛明影,45,1、数组元素地址的计算公式,每个数组元素的宽度,数组首地址,=bace-low*w+i*w,一维数组的数组元素计算公式,VAR a:ARRAY low.high OF int;,求 ai的地址：,base（i

23、low）*w,任一数组元素Ai1,i2,in的地址:addr=a-c+v,辛明影,46,对于一个二维数组，可以按行或按列存放。,若按行存放，则可用如下公式计算：,数组地址计算：,可在编译时计算出来,常量部分+变量部分：,bace-l1*w+i*w,辛明影,47,base（i1 一l1）*d2i2 一l2）*w）,令c=（l1*d22）l2）*w 则常量部分=al1,l2-c,A1,1 A1,2 A1,3 A2,1 A2,2 A2,3,A2,3按行存放,Ai1,i2 的地址：,A1,2=,base-(1*3+1)+(1*3+2),=base+1,=base（low1*d2）low2）*w,（i1

24、*d2）i2)*w,辛明影,48,整理后：常量部分：c=(.(l1*d2+l2)*d3+l3).)*dk+lk)*w 变量部分v=(.(i1*n2+i2)*n3+i3.)*nk+ik)*w,多维数组Ai1,i2,.,ik 的地址的计算,(.(i1*d2+i2)*d3+i3.)*dk+ik)*w+base-(.(l1*d2+l2)*d3+l3.)*dk+lk)*w,ai1,i2,in的地址=base-c+v,辛明影,49,x:=ai1,.,in的目标代码结构：,t1:=v,t2:=base-c,t3:=t2t1,x:=t3,辛明影,50,2、数组的类型信息：,a 嵌套深度 偏移量 类型,名字表,

25、内情向量,C=84l1=1u1=10d1=10l2=1u2=20d2=20基类型,int标准类型,VAR a:ARRAY 1.10,1.20 OF int;,符号表中的信息可组织如下：,辛明影,51,地址计算变量部分：(i1*d2+i2)*d3+i3)*d4+可利用递归公式计算：e1=i 1,3、引用数组元素的文法 L id Elist|id ElistElist,E|E,为了便于语义处理，上述方法改写为：LElist|id ElistElist,E|id E,e2=e1*d2+i2；,e3=e2*d3+i3,em=em-1*dm+im,辛明影,52,Elist 引进综合属性array，指向数

26、组名a在符号表中的入口地址.,Elist.place：临时变量，用来临时存放由 Elist 中的下标表达式计算出来的值;,函数limit（array，j）：返回nj，即由 array所指示的数组的第j维长度;,4、有关变量与函数的说明Elist.ndim：记录Elist中的下标表达式的 个数，即维数,对于A1.10,1.20，Limit(A,2)=20Limit(A,1)=10,辛明影,53,L有两个属性值：L.Place和L.offset,L.offset=null:表示L为一个简单名字L.offset不为空，表示数组元素引用,L.Place:如果L为一个简单名字，则L.Place为指向该名

27、字在符号表中的入口的指针；,如果L不为一个简单名字，则L.Place为数组计算中的常数部分，base-c,辛明影,54,5、访问数组元素的翻译模式 给定文法G(S)：(0)M（1）SL：M E（2）EEE（3）E（E）（4）EL（5)LElist（6）Lid（7）ElistElist，E（8）Elistid E,辛明影,55,6、相应语义动作 若L是一个简单的名字，将生成一般的赋值；,若L为数组元素引用，则生成对L所指示地址的索引赋值,0M S.place：L.place;S.offset=L.offset,辛明影,56,2EE1E2 E.place：newtemp;emit（E.place：

28、E1placeE2.place）,3E（E1）E.place：E1.place,1SL：ME if S.offsetnull then emit(S.place：E.place)else emit（S.placeS.offset：=E.Place）,辛明影,57,使用索引来获得地址L.placeL.offset 的内容：4 EL if L.offsetnull then E.place:L.place*L is a simple id*/else begin emit(E.place:=L.placeL.offset)end,辛明影,58,一个空的offset表示一个简单的名字：6 Lld（L

29、.place:=id.place;L.offset:=null,5 LElist L.place:=newtemp;emit（L.place:=Elist.array c)L.offset:=newtemp;emit（L.offset:=w*Elist.place),辛明影,59,应用递归公式扫描下一个下标表达式 7ElistElist1,E t：newtemp;m：Elist1ndim1；emit（t=Elist1.place*limit（Elist1.array,m）；emit（t=t E.place）；Elist.array：Elist1array;Elist.place：=t;Elis

30、t.ndim：m,em-1*dm,em-1*dm+im,辛明影,60,8 ElistidE Elist.place:=E.place;Elist.ndim:=1：Elist.array：id.place,例:设A为一个10*20的数组，,C=（l1*n2）l2）*w=(1*20 1）*484。,设w4，,若数组第一个元素为 A1，1。则有，,即n1=10,n2=20;,辛明影,61,S,L,X,=,E,L,E,EList,E,A,E,L,y,L,z,act61,act62,act41,act63,act7,act5,act43,act42,act1,act8,acc0,M,对赋值语句x：=Ay

31、,z的带注释的分析树如图所示。,辛明影,62,Act61act0Act62act41 Act8Act63Act42Act7Act5Act43act1,遍历后得属性计算顺序：,act61,L.placeL.offsetE.placeElist.placeElist.ndimElist.array,非终结符的属性值,x,null,四元式表,act62,y,null,act41,y,act8,y,1,A,act63,z,null,act42,z,act7,2,t1=y*20,t1=t1+z,A,t1,2,act5,t2=A-84,t3=4*t1,t3,act43,t4=t2t3,t2,act1,ac

32、t0,t4,s.place x,s.offset null,X=t4,m,6 Lld（L.place:=id.place;L.offset:=null,0 M s.place=L.placeS.offset=L.offset,6 Lld（L.place:=id.place;L.offset:=null,4if L.offsetnull(EL)then E.place:L.place else E.place:=newtemp;emit(E.place:=L.placeL.offset),8 ElistidE Elist.place:=E.place;Elist.ndim:=1：Elist.ar

33、ray：id.place,6 Lld（L.place:=id.place;L.offset:=null;,4if L.offsetnull(EL）then E.place:L.place else E.place:=newtemp；emit(E.place:=L.placeL.offset),7 t：newtemp;(ElistElist1,E)m：Elist1ndim1；emit（t：=Elist1.place*limit（Elist1.array,m）；,emit（t：=t E.place）；Elist.array：Elist1array;Elist.place：=t;Elist.ndim

34、：m,5 L.place:=newtemp;(LElist)emit（L.place:=Elist.array c)L.offset:=newtemp;emit（L.offset:=w*Elist.place),4if L.offsetnull(EL)then E.place:L.place else E.place:=newtemp;emit(E.place:=L.placeL.offset),1if S.offsetnull(SL：E)then emit(S.place：E.place)else emit（s.placeL.offset：=E.Place）,辛明影,63,该赋值语句在由底向

35、上的分析中被翻译成如下三地址语句序列：t1：=y*20 t1：=t1z t2：=A-84 t3:=4*t1 t4：=t2t3 x:=t4 注意：20、84、4都是编译中引入的常量。,辛明影,64,编译程序内部把 p表示为：pointer（record（t），域名info将可以在t所指向的符号表中查找。,例如：表达式：pinfo1 变量P是一个指向某个记录类型的指针，info 为其中一个算术型类型的域名。,编译器将记录的域的类型和相对地址保存在相应域名的符号表表项之中，可以把用在符号表中查找名字的程序同样用来查找域名。,四、访问记录中的域,辛明影,65,TYPE p link=node;node=RECORD info info:integer;next next:link END;VAR p:link;取 L(level,offsetp)取 L 0(L),