《编译原理与技术》讲义.ppt

1、2020/6/19,编译原理与技术讲义,1,编译原理与技术,中间代码生成,2020/6/19,编译原理与技术讲义,2,中间代码生成,中间代码形式控制流语句翻译,2020/6/19,编译原理与技术讲义,3,中间代码生成,中间代码的种类后缀式（逆波兰式）e.g.1a+b*-cabc*+e.g.21）a:=b*-c+b*-c，其后缀式为abc*bc*+assign2）ifabthenc:=c+1abcc1+assignIF语法树vs.分析树e.g.31）a:=b*-c+b*-c，其语法树为,2020/6/19,编译原理与技术讲义,4,e.g.31）a:=b*-c+b*-c语法树vs.分析树,中间代码

2、的种类,assign,a,+,*,b,c,*,b,c,assign,E,E,E,+,E,*,E,b,E,E,a,赋值语句,c,E,*,E,b,E,c,2020/6/19,编译原理与技术讲义,5,e.g.32）a:=b*-c+b*-c语法树vs.DAG,中间代码的种类,assign,a,+,*,b,c,*,b,c,assign,a,+,*,b,c,2020/6/19,编译原理与技术讲义,6,中间代码的种类,e.g.4构造表达式的语法树（DAG）产生式语义规则EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr)EE1-E2E.nptr:=mknode(-,E1.nptr,

3、E2.nptr)EE1*E2E.nptr:=mknode(*,E1.nptr,E2.nptr)EE1/E2E.nptr:=mknode(/,E1.nptr,E2.nptr)E(E1)E.nptr:=E1.nptrE-E1E.nptr:=mknode(,E1.nptr,)EnumberE.nptr:=mkleaf(NUM,number.lex_val)EidE.nptr:=mkleaf(ID,id.entry),2020/6/19,编译原理与技术讲义,7,中间代码的种类,e.g.4构造表达式的语法树（DAG）E.nptrE的语法树（根结点指针）mknode(op,left,right)建立一个表

4、达式语法树结点，它的运算符为op，左、右运算对象是left和right所指的语法树。mkleaf(NUM,number.lex_val)mkleaf(ID,id.entry)建立表达式语法树的叶子结点。,2020/6/19,编译原理与技术讲义,8,e.g.4构造表达式a+b*-4的语法树（DAG）,中间代码的种类,2020/6/19,编译原理与技术讲义,9,中间代码的种类,三地址代码一般形式：x:=yopz或x:=opye.g.5a:=b*-c+b*-c的三地址代码1）t1:=-c1）t1:=-c2）t2:=b*t12）t2:=b*t13）t3:=-c3）t3:=t2+t24）t4:=b*t3

5、4）a:=t35）t5:=t2+t46）a:=t5,2020/6/19,编译原理与技术讲义,10,中间代码的种类,常用的三地址代码x:=yopz二元运算x:=opy单目运算x:=y值拷贝gotoL无条件转移到代码标号L处ifxRELOPygotoL条件转移代码：若x和y满足RELOP关系，则转移至代码标号L处paramX参数XCALLproc，N调用过程proc，参数个数为N,2020/6/19,编译原理与技术讲义,11,中间代码的种类,常用的三地址代码（续）returny过程返回，返回值为yx:=yixi:=y变址语句x:=DDid:TTint|real|arraynumberofT1|T1

6、,2020/6/19,编译原理与技术讲义,16,e.g.8一个说明语句的翻译方案（续）,有关符号的属性T.type变量所具有的类型，如整型INT实型REAL数组类型array（元素个数，元素类型）指针类型pointer（所指对象类型）T.width该类型数据所占的字节数offset变量的存储偏移地址,2020/6/19,编译原理与技术讲义,17,e.g.8一个说明语句的翻译方案（续）,2020/6/19,编译原理与技术讲义,18,e.g.8一个说明语句的翻译方案（续）,（1）PMD（2）DD1;D2（3）Did:T/填入变量的相关属性enter(,T.type,offset)/计

7、算下一可用偏移位置offset=offset+T.width（4）Moffset:=0/偏移初始为0,2020/6/19,编译原理与技术讲义,19,e.g.8一个说明语句的翻译方案（续）,（5）TintT.type:=INT;T.width:=4（6）TrealT.type:=REAL;T.width:=4（7）TarraynumberofT1T.type:=array(number.val,T1.type);T.width:=number.val*T1.width（8）Tpointer(T1)T.type:=pointer(T1.type);T.width:=4,2020/6/19,编译原理

8、与技术讲义,20,e.g.9一个嵌套说明语句的翻译方案,文法G2如下：PDDD1;D2Did:TDprocid;D1;STint|real|arraynumberofT1|T1Sa,2020/6/19,编译原理与技术讲义,21,e.g.9一个嵌套说明语句的翻译方案,产生式Dprocid;D1;S引入过程id的声明；D1为其局部说明语句，可以声明变量或嵌套定义其它过程；约定每个过程有自己独立的符号表且嵌套定义的过程符号表头有指针指向外围（父）过程的符号表；而父过程符号表中有该嵌套子过程的条目（涉及子过程名和子过程符号表的指针等属性）。,2020/6/19,编译原理与技术讲义,22,相关定义：/*

9、在父过程符号表中建立子过程名的条目*/enter-proc（parent-table,sub-proc-name,sub-table）/*将所声明变量的类型、偏移填入当前符号表*/enter（current-table,name,type,current-offset）/*建立新的符号表，其表头指针指向父过程符号表*/mktable（parent-table）addwidth（table，offset）/记录变量占用的总空间符号表栈tblptr和偏移栈offset（栈顶值分别表示当前分析的过程的符号表及可用变量偏移位置）,2020/6/19,编译原理与技术讲义,23,e.g.9一个嵌套说明语句

10、的翻译方案,PMDaddwidth(top(tblptr),top(offset),pop(tblptr);pop(offset)/*保留变量分配空间大小并清空符号表和偏移栈*/Mt:=mktable(null);push(t,tblptr);push(0,offset)/*建立主程序（最外围）的符号表偏移从0开始*/DD1;D2,2020/6/19,编译原理与技术讲义,24,Dprocid;ND1;St:=top(tblptr);addwidth(t,top(offset);pop(tblptr);pop(offset);enter-proc(top(tblptr),,t)/*

11、保留当前（子）过程声明变量的总空间；弹出符号表和偏移栈顶（露出父过程的符号表和偏移）；在父过程符号表中填写子过程名有关条目*/Nt:=mktable(top(tblptr);push(t,tblptr);push(0,offset)/*建立子过程的符号表和偏移从0开始*/,2020/6/19,编译原理与技术讲义,25,Did:Tenter(top(tblptr),,T.type,top(offset);top(offset):=top(offset)+T.width;/*将变量name的有关属性填入当前符号表*/*以下产生式的翻译方案略*/Tint|real|arraynumbe

12、rofT1|T1Sa,2020/6/19,编译原理与技术讲义,26,i:int;j:int;PROCP1;k:int;f:real;PROCP2;l:int;a1;a2;PROCP3;temp:int;max:int;a3;,e.g.10过程嵌套声明,P0,P1,P3,P2,过程声明层次图,2020/6/19,编译原理与技术讲义,27,初始：M,e.g.10过程嵌套声明（续）,符号栈,偏移栈,P0,0,top,null,总偏移：,P0,2020/6/19,编译原理与技术讲义,28,i:int;j:int;,e.g.10过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P

13、0,i,INT,0,j,INT,4,2020/6/19,编译原理与技术讲义,29,PROCP1;（N）,e.g.10过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,P1,0,总偏移：,P1,2020/6/19,编译原理与技术讲义,30,k:int;f:real;,e.g.10过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,P1,8,总偏移：,P1,k,INT,0,f,real,4,2020/6/19,编译原理与技术讲义,31,PROCP2;（N）,e.g.10过程嵌套

14、声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,P1,8,总偏移：,P1,k,INT,0,f,real,4,P2,0,总偏移：,P2,2020/6/19,编译原理与技术讲义,32,l:int;,e.g.10过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,P1,8,总偏移：,P1,k,INT,0,f,real,4,P2,4,总偏移：,P2,l,INT,0,2020/6/19,编译原理与技术讲义,33,a1;,e.g.10过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,nu

15、ll,总偏移：,P0,i,INT,0,j,INT,4,P1,8,总偏移：,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,2020/6/19,编译原理与技术讲义,34,a2;,e.g.10过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,总偏移：8,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,P1,proc,2020/6/19,编译原理与技术讲义,35,PROCP3;（N）,e.g.10过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,nul

16、l,总偏移：,P0,i,INT,0,j,INT,4,总偏移：8,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,P1,proc,P3,0,总偏移：,P3,2020/6/19,编译原理与技术讲义,36,temp:int;max:int;,e.g.10过程嵌套声明（续）,符号栈,偏移栈,P0,8,top,null,总偏移：,P0,i,INT,0,j,INT,4,总偏移：8,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,P1,proc,P3,8,总偏移：,P3,temp,INT,0,max,INT,4,2020/6

17、/19,编译原理与技术讲义,37,a3;,e.g.10过程嵌套声明（续）,符号栈,偏移栈,top,null,总偏移：,P0,i,INT,0,j,INT,4,总偏移：8,P1,k,INT,0,f,real,4,总偏移：4,P2,l,INT,0,P2,proc,P1,proc,P0,8,总偏移：8,P3,temp,INT,0,max,INT,4,P3,proc,2020/6/19,编译原理与技术讲义,38,PMD；,e.g.10过程嵌套声明（续）,符号栈空,偏移栈空,top,null,总偏移：8,P0,i,INT,0,j,INT,4,总偏移：8,P1,k,INT,0,f,real,4,总偏移：4,

18、P2,l,INT,0,P2,proc,P1,proc,总偏移：8,P3,temp,INT,0,max,INT,4,P3,proc,2020/6/19,编译原理与技术讲义,39,记录的说明,记录（record）语法如下：TrecordDend说明D含义同前面。（一般不含有过程声明，但C+可以）可以将记录中的域变量声明放在单独的符号表中（参照嵌套过程声明的做法，但外围过程指针为空）。,2020/6/19,编译原理与技术讲义,40,记录说明的翻译,TrecordLDendT.type:=record(top(tblptr);/记录类型定义T.width:=top(offset);/记录的占用空间大小

19、pop(tblptr);pop(offset)Lt:=mktable(null);/无外围“过程”push(t,tblptr);push(0,offset);/域变量偏移从0开始D的翻译同前。,2020/6/19,编译原理与技术讲义,41,有2个C语言的结构定义如下：structAstructBcharc1;charc1;charc2;longl;longl;charc2;doubled;doubled;S1;S2;,e.g.11记录域的偏移,2020/6/19,编译原理与技术讲义,42,e.g.11记录域的偏移,数据（类型）的对齐alignment在X86-Linux下：char：对齐1，起

20、始地址可分配在任意地址int，long，double：对齐4，即从被4整除的地址开始分配注*：其它类型机器，double可能对齐到8，如sunSPARC,2020/6/19,编译原理与技术讲义,43,e.g.11记录域的偏移,结构A和B的大小分别为16和20字节(Linux),0,4,8,12,16,结构A,0,4,8,12,16,结构B,20,衬垫padding,2020/6/19,编译原理与技术讲义,44,2个结构中域变量的偏移如下：structAstructBcharc1;0charc1;0charc2;1longl;4longl;4charc2;8doubled;8doubled;12

21、S1;S2;,e.g.11记录域的偏移,2020/6/19,编译原理与技术讲义,45,含简单变量的赋值语句，如id:=E，其中，id为普通变量，而E是简单的算术表达式。文法定义如下：Aid:=EEE1+E2EE1*E2E-E1E(E1)Eid,赋值语句的翻译,1)E的属性定义：E.place:存放表达式E“值”的场所2)newtemp获取临时变量以存放中间结果3)emit产生三地址码（TAC）的过程4)lookup(name)检查name是否在符号表中有定义（条目）,2020/6/19,编译原理与技术讲义,46,含简单变量的赋值语句的翻译Aid:=Ep=lookup()；if(p

22、!=null)emit(p:=E.place)elseerrorEE1+E2t:=newtemp;E.place:=t;emit(t:=E1.place+E2.place)EE1*E2t:=newtemp;E.place:=t;emit(t:=E1.place*E2.place)E-E1t:=newtemp;E.place:=t;emit(t:=-E1.place)E(E1)E.place:=E1.placeEidp=lookup()；if(p!=null)E.place:=pelseerror,2020/6/19,编译原理与技术讲义,47,e.g.12赋值语句a:=-b*c+d

23、的翻译,a,:=,-,b,E.place=b,E.place=t1,TAC:,1)t1:=-b,*,c,E.place=c,E.place=t2,2)t2:=t1*c,+,d,E.place=d,E.place=t3,3)t3:=t2+d,A,4)a:=t3,2020/6/19,编译原理与技术讲义,48,e.g.13赋值语句后缀式代码生成,AL:=Eprint(:=)EE1+E2print(+)EE1*E2print(*)E-E1print()E(E1)Eidp=lookup(name)；if(p!=null)print(p)elseerrorLidp=lookup(name)；if(p!=n

24、ull)print(p)elseerror,2020/6/19,编译原理与技术讲义,49,数组元素的翻译,数组类型的声明e.g.Pascal的数组声明，A:arraylow1.high1,lown.highnofinteger;数组元素：Ai,j,k,或Aijk（下界）low1ihigh1（上界）,e.g.C的数组声明，intA100100100;数组元素：Ai30400i(100-1),2020/6/19,编译原理与技术讲义,50,数组元素的翻译,数组元素的地址计算仅讨论按行优先排列（即行主序）。约定数组名，如A，表示整个数组的起始地址（偏移）；w表示数组元素所占字节数。一维：Ai的地址ad

25、dr为，addr=A+(i-low1)*w=i*w+(A-low1*w)二维：Ai1,i2的地址addr为，(n2=high2-low2+1)addr=A+(i1-low1)*n2+(i2-low2)*w=(i1*n2+i2)*w+(A-(low1*n2+low2)*w),2020/6/19,编译原理与技术讲义,51,数组元素的地址计算（行主序）多维（K维）：Ai1,i2,ik的地址，addr=(i1*n2+i2)*n3+i3)*nk+ik)*w+(A-(low1*n2+low2)*n3+low3)*nk+lowk)*w)数组元素的地址addr由可变部分var-part和常量值const-pa

26、rt相加而得，即addr=“可变部分”+“常量值”两部分可以由以下递推式计算（nmhighm-lowm+1）V1=i1Vm=Vm-1*nm+im1mKC1=low1Cm=Cm-1*nm+lowm1mK当mK时，Vk*w即为可变部分；而A-Ck*w为常量值。“常量值”可以在编译时刻计算；而“可变部分”则必须生成代码在运行时刻加以计算（所有下标是常量的数组元素可以除外。Why?）。,2020/6/19,编译原理与技术讲义,52,数组元素的翻译,含有数组元素的赋值语句文法G3(1)SV:=E(2)VidElist(3)Vid(4)ElistElist1,E(5)ElistE(6)EV(7)EE1+E

27、2|E1*E2|(E1)|-E1,2020/6/19,编译原理与技术讲义,53,输入串Ax,y:=z的分析树,S,V,:=,E,A,Elist,Elist,E,E,V,x,V,y,V,z,当分析到下标（表达式）x和y时，要计算地址中的“可变部分”。这时需要知晓数组A的有关的属性，如nm，类型宽度w等，而这些信息存于在结点A处。若想使用必须定义有关继承属性来传递之。但在移进归约分析不适合继承属性的计算！,2020/6/19,编译原理与技术讲义,54,改进后的含有数组元素的赋值语句文法G3(1)SV:=E(2)VElist(3)Vid(4)ElistidE(5)ElistElist1,E(6)EV

28、(7)EE1+E2|E1*E2|(E1)|-E1,数组元素的翻译,修改文法，使数组名id成为Elist的子结点（类似于前面的类型声明），从而避免继承属性的出现,2020/6/19,编译原理与技术讲义,55,数组元素的翻译,相关符号属性定义：V.place，V.offset:若V是简单变量，V.place为其“值”的存放场所，而V.offset为空（null）；当V表示数组元素时，V.place是其地址的“常量值”部分；而此时V.offset为数组元素地址中可变部分的“值”存放场所，数组元素的表示为：V.placeV.offsetElist.place:“可变部分”的值Elist.array:数

29、组的属性Elist.dim:当前处理的维数,2020/6/19,编译原理与技术讲义,56,数组元素的翻译,翻译方案如下：(1)SV:=EifV.offset=null/简单变量emit(V.place“:=”E.place)elseemit(V.placeV.offset“:=”E.place)/取数组元素的左值(2)VElist/*获取数组元素地址的常量值和可变部分*/t:=newtemp;emit(t“:=”Elist.array-get-CONST(Elist.array)V.place:=t;t:=newtemp;emit(t“:=”Elist.place*w)V.offset:=t,2020/6/19,编译原理与技术讲义,57,数组元素的翻译,翻译方案如下（续）：(3)Vidp:=lookup();if(p=null)error()else