哈工大编译原理6-11.ppt

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 *

2、 - c+b * -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 ：

3、t5 对于语法树的代码,辛明影,9,（3）无条件转移语句goto L;,（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;,在设计中间代码形式时，选择多少种算 符 需 要 trade off .,（8）地址和指针赋值 xy，x* y 和 * xy。,（7）索引赋值 x:=yi 及 xi :=y ;,（6

4、）过程调用语句 param x 和 call p, n ; 过程返回语句 return y;,辛明影,11,(1)E.place表示存放E值的名字。,6.1.4 语法制导翻译生成三地址代码,几个用到的量：,(2)E.code表示对E求值的三地址语句序列。,(3) newtemp是个函数，对它的调用将产生 一个新的临时变量。,辛明影,12,S.code:=E.code gen(id.place:=E.place),产生式,语义规则,EE1+E2,Sid:=E,E.place:=newtemp; E.code:=E1.codeE2.code gen(E.place:= E1.place +E2.p

5、lace),辛明影,13,EE1*E2,E.place:=newtemp; E.code:=E1.codeE2.code gen(E.place:= E1.place *E2.place),语义规则,产生式,E-E1,E.place:=newtemp; E.code:=E1.codegen( E.place:=uminusE1.place),辛明影,14,产生式,语义规则,E.place:=E1.place; E.code:=E1.code,E(E1),产生赋值语句三地址代码的语法制导定义,Eid,E.place:=id.place; E.code:=,辛明影,15,三地址语句序列是语法树的线

6、性表示，用临时变量代替语法树中的结点。,实际实现中，三地址语句序列往往是被存放到一个输出文件中，而不是将三地址语句序列置入code属性之中,辛明影,16,6.1.5 三地址代码的具体实现,1四元式 op, arg1, arg2, result 2三元式 op, arg1, arg2 3间接三元式 间接码表+三元式表,四元式需要利用较多的临时单元,四元式之 间 的联系通过临时变量实现。,中间代码优化处理时，四元式比三元式方便的多,间接三元式与四元式同样方便，两种实现方式需要的存储空间大体相同。,辛明影,17,1、 x=y op z,常用三地址码的四元式表示：,2、 x=op y,3、goto L

7、,4、if x rop y goto L,5、x=y,6、parm x call p,n 7、x=yi xi=y 8、x= D Did ：T Tinteger Treal,x:integer;y:real,一个过程中的所有说明语句作为一个类集来处理。,用一个全程变量Offset来记录下 一个数据在符号表中的相对地址。,Tarraynumof T1,T T1,辛明影,23,PD,DD; D,Did ：T,Tinteger,Treal,Tarraynumof T1,T T1,offset：0D,enter（，T.type，offset）; offset:=offsetT.width,

8、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）； T.width ：= 4,辛明影,24,Name type kind addr X Y ,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,Off

9、set=12,Int,real,T.type T.width,T.type T.width,T.type=int T.width=4,T.type=real T.width=8,辛明影,25,1 .问题的提出,二、 保留作用域信息,一般的语言中，标识符的作用在程序正文中有一个确定的范围。,因此，同一个标识符在不同的程序正文中可能标识不同的对象，,具有不同的性 质，要求分配不同的存储空间。,辛明影,26,于是提出下面的问题：,如何组织符号表，,使得同一个标识符在不同的作用域中得到正确的引用而不产生混乱。,进一步我们考虑一下具有嵌套定义的程序结构,辛明影,27,2. 嵌套的程序结构,program

10、 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： integer； begin end；,procedure exchange； begin end；,procedure partition （y ，z ：integer ） var i，j ： integer； begin end;,辛明影,28,嵌套说明的文法：,PD DD;

11、 D Did ：T Dproc id;D;S .,此处的T用于产生类型； S用于产生语句,辛明影,29,嵌套说明的程序结构首先要解决的问题是：非局部数据的访问,综合上述情况，对于程序结构采用分程 序结构的程序来说，要解决的问题是：,局部数据的访问,2.非局部数据的访问,解决方法:为每一个过程建立一个符号表,辛明影,30,具体翻译时，每当碰到过程说明Dproc id;D1;S时,便创建一张符号表,并且把D1中的所有说明都填入此符号表中,新表中有一个指针，指向其直接外围过程符号表,用于解决非局部数据的访问,同时还要在直接外围过程符号表中增加一个指向该过程D1符号表的指针,过程名id 作为直接外围过

12、程的局部名字记录在直接外围过程符号表中；,辛明影,31,Nil header x a readarray exchange quicksort,sort,header i,header,readarray,exchange,Header I k patition,Header I j,quicksort,patition,嵌套过程的符号表,辛明影,32,翻译时常用操作：,4. enterproc（table,name, newtable） 在外围过程符号表中建立内嵌过程的新表项,1. mktable( previous）创建一张新符号表,2. Enter(table，name，type，off

13、set)插入表项,3. addwidth（table，width）记录总域宽,指向直接外层符号表,指向当前过程符号表,指向直接外层符号表,指向内层过程的符号表,指向当前外层符号表,内嵌过程名字,辛明影,33,Tblptr是一个栈，用于存放指向嵌套外层过程的符号表指针,Offset是一个栈，用于存放变量的相对地址，当过程结束时，offset里记录的是过程占用的所有字节数。,翻译时用到的数据结构：,辛明影,34,处理嵌套过程中的说明语句翻译方案,PMDaddwidth(top(tblptr),top(offset); pop();pop(offset),M t:=mktable（nil）； pus

14、h(t,tblptr);push(0,offset),DD1；D2,Dproc id; N D1；S t:top（tblptr); addwidth(t,top(offset); pop（tblptr）；pop（offset); enterproc(top（tblptr），，t),辛明影,35,D id: T enter(top(tblptr),,T.type, top(offset); top(offset）：= top(offset) T.width,例：,procedure quicksort（m，n ： integer）； var i ： integer；

15、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),辛明影,36,P,M,D,proc,Q,;,N,D,;,S,proc,P,;,N,D,;,S,j,:,T,int,辛明影,37,上述语法树对应的语句： Proc Q;proc R;j:int;S;S,遍历语法树所得到的翻译序列： ,执行上面翻译序列符号表及栈的变化,辛明影,38,tabptr offset,t,主,0,主,

16、T=Q,Q,0,Q,T=p,P,0,*,t.type=int t.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，offset),TintegerT.type ：=integer; T.width：= 4,D id: T enter(top(tblptr),,T.

17、type, top(offset); top(offset）：= top(offset) T.width,Dproc id; N D1；S t:top（tblptr); addwidth(t,top(offset); pop（tblptr）；pop（offset); enterproc(top（tblptr），，t),Dproc id; N D1；S t:top（tblptr); addwidth(t,top(offset); pop（tblptr）；pop（offset); enterproc(top（tblptr），，t),PMDaddwidth(top(tbl

18、ptr),top(offset); pop(tblptr);pop(offset),辛明影,39,使用两个栈，分别保存刚编译过的符号表箭头table和offset的值。,进入过程partition，quicksort过程的编译并未结束，活动记录的设计和符号表的建立尚未完成，因此，要把quicksort过程使用的table和offset保存于栈中。,编译过程：用先根次序遍历上一页中的树，用栈来存储编译过程中使用的量，象table和offset。,辛明影,40,一组嵌套过程，每个过程说明为局部名字建立一个符号表，所有正在翻译过程的符号表组成整个源程序的符号表。,翻译语句部分时查找符号表，查找过程的

19、符号表的路线相当于当前被 翻译过程的静态链。,辛明影,41,三、 记录中的域名 T record LD end T.type:=record（top（tblptr)； T.width:top(offset)； pop（tblptr);pop(offset) L t:=mktable(nil); push(t,tblptr);push(0,offset) 为个记录中的域名建立一张符号表 该翻译模式强调了作为一个语言结构的记录的设计与活动记录之间的相似处.,辛明影,42,一、 符号表中的名字,6.2.2 赋值语句,赋值语句的翻译：,如何根据名字查找符号表的表项？,表达式的成分可以是整型量、实型量、

20、数组 元素和记录,名字可以理解为指向符号表中相应该名字表项的指针,过程lookup()检查是否在符号表中存在相应此名字的表项。,辛明影,43,用最近嵌套作用域规则查找非局部名字,若找到，返回有关信息。,lookup过程先通过top(tblptr）指针在当前符号表中查找名字为name的表项。,若未找到，lookup就利用当前符号表表头的指针找到该符号表的外围符号表，,然后在那里查找名字为name的表项，,直到所有外围过程的符号表中均无此name表项，,则lookup返回nil,表明查找失败。,辛明影,44,lookup()= id.entry nil,emit 它将生

21、成的三地址代码送到输出文件上。例： emit(E.place:=E1.place+E2.place) 或 emit(= , E1.place，E2.place， E.place),二、简单算术表达式及赋值语句,辛明影,45,Sid:=E,产生赋值语句三地址代码的翻译模式,EE1+E2,EE1*E2,p:=lookup(); 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.pla

22、ce+E2.place),辛明影,46,E(E1),Eid,E -E, E.place:=newtemp;emit(E.place := uminusE1.place,E.place:=E1.place,p:=lookup(); if pnil then E.place:=p else error,辛明影,47,语义动作应包括类型分析，文法符号应有类型属性，在类型分析的基础上，进行相容和赋值相容检查，生成类型转换的三地址代码。,辛明影,48,1、数组元素地址的计算公式,数组元素的三地址代码是什么？,三、 数组元素地址分配（复杂赋值语句）,每个数组元素的宽度,数组首地址,=bace

23、-low*w + i*w,如何生成数组元素的三地址代码?,一维数组的数组元素计算公式,VAR a:ARRAY low.high OF real;,求 ai的地址：,base（ilow ）* w,辛明影,49,对于一个二维数组，可以按行或按列存放。,若按行存放，则可用如下公式计算：,数组地址计算：,可在编译时计算出来,常量部分+变量部分：,bace-low*w + i*w,辛明影,50,base（i1 一low1）* n2i2 一low2）*w）,令c= （low1 *n2）low2）*w 则常量部分=alow1,low2-c,A1,1 A1,2 A1,3 A2,1 A2,2 A2,3,A2,3

24、按行存放,Ai1,i2 的地址：,A1,2=,base-(1*3+1)+(1*3+2),= base+1,= base（low1 *n2）low2）*w, （i1*n2）i2)* w,辛明影,51,整理后：常量部分： c=(.(low1*n2+low2)*n3+low3).)*nk +lowk) * w 变量部分v= (.(i1*n2+i2)*n3+i3.)*nk+ik)*w,多维数组Ai1,i2,.,ik 的地址的计算,(.(i1*n2+i2)*n3+i3.)*nk+ik)*w+base-(.(low1*n2+low2)*n3+low3.)*nk+lowk)*w,ai1,i2,in的地址 =

25、base-c+v,辛明影,52,x:=ai1,.,in的三地址代码结构：,t1: =v,t2:=base-c,t3:=t2t1,x:=t3,辛明影,53,2、数组的类型信息：,a 嵌套深度 偏移量 类型,名字表,内情向量,C=84 low1=1 high1=10 n1=10 low2=1 high2=20 n2=20 基类型,int 标准类型 8,VAR a:ARRAY 1.10,1.20 OF int;,符号表中的信息可组织如下：,辛明影,54,地址计算变量部分： (i1*n2+i2)*n3+i3)*n4+ 可利用递归公式计算： e1= i 1,3、引用数组元素的文法 L id Elist

26、| id ElistElist,E|E,为了便于语义处理，上述方法改写为： LElist| id ElistElist,E|id E,e2=e1*n2+i2；,e3=e2*n3+i3,em=em-1*nm+im,辛明影,55,Elist 引进综合属性array，指向数组名a在符号表中的入口地址.,Elist.place：临时变量，用来临时存放由 Elist 中的下标表达式计算出来的值;,函数limit（array，j）：返回nj ，即由 array所指示的数组的第j维长度;,4、 有关变量与函数的说明 Elist.ndim：记录Elist中的下标表达式的 个数，即维数,对于A1.10,1.20

27、， Limit(A,2)=20 Limit(A,1)=10,辛明影,56,L有两个属性值： L.Place和L.offset,L.offset=null:表示L为一个简单名字 L.offset不为空，表示数组元素引用,L.Place:如果L为一个简单名字，则L.Place为指向该名字在符号表中的入口的指针；,如果L不为一个简单名字，则L.Place为数组计算中的常数部分，base-c,辛明影,57,5、访问数组元素的翻译模式 给定文法G(S)： (0) M （1）SL： M E （2）EEE （3）E（E） （4）EL （5) LElist （6）Lid （7）ElistElist，E （8）

28、Elistid E,辛明影,58,6、相应语义动作 若L是一个简单的名字，将生成一般的赋值；,若L为数组元素引用，则生成对L所指示地址的索引赋值,1SL ： ME if S. offsetnull then emit(S.place ： E.place) else emit（S.placeS.offset：= E. Place）,辛明影,59,2EE1E2 E.place：newtemp; emit（E.place： E1placeE2.place）,3E（E1） E.place ：E1.place,0M S.place：L.place; S.offset=L.offset,辛明影,60,使用

29、索引来获得地址L.placeL.offset 的内容： 4 EL if L.offsetnull then E.place:L.place * L is a simple id */ else begin E.place:=newtemp; emit(E.place:=L.placeL.offset) end,辛明影,61,一个空的offset表示一个简单的名字： 6 Lld （L.place:=id.place;L.offset:=null,5 LElist L.place:=newtemp; emit（L.place:=Elist.array c) L.offset:=newtemp; e

30、mit（L.offset:=w*Elist.place),辛明影,62,应用递归公式扫描下一个下标表达式 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; Elist.ndim：m,em-1*nm,em-1*nm+im,辛明影,63,8 ElistidE Elist.place:=E.place; Elist.ndim:=1： Elist.

31、array：id.place,例:设A为一个10*20的数组，,C=（low1*n2）low2）*w =(1*20 1）*484。,设w4，,若数组第一个元素为 A1，1 。则有，,即n1=10, n2= 20;,辛明影,64,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,z的带注释的分析树如图所示。,辛明影,65,Act61 act0 Act62 act41 Act8 Act63 Act42 Act7 Act5 Act43

32、 act1,遍历后得属性计算顺序：,act61,L.place L.offset E.place Elist.place Elist.ndim Elist.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,act0,t4,s.place x,s.offset null,X=t4,m,6 Lld （L.place:=id.place;L.offset:=null,0 M s.place=L.place S.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 E