编译原理与技术中间代码生成

2024/4/7《编译原理与技术》讲义1编译原理与技术中间代码生成2024/4/7《编译原理与技术》讲义2中间代码生成

－中间代码形式 －控制流语句翻译2024/4/7《编译原理与技术》讲义3中间代码生成中间代码的种类 －后缀式（逆波兰式）

e.g.1a+b*-cabc@*+ e.g.21）a:=b*-c+b*-c，其后缀式为

abc@*bc@*+assign

2）ifa>bthenc:=c+1

ab>

c

c1+assign

IF

－语法树vs.分析树

e.g.31）a:=b*-c+b*-c，其语法树为

2024/4/7《编译原理与技术》讲义4

－e.g.31）a:=b*-c+b*-c

语法树vs.分析树

中间代码的种类assigna+*b@c*b@cassignEEE+E*EbE@Ea赋值语句cE*EbE@c2024/4/7《编译原理与技术》讲义5

－e.g.32）a:=b*-c+b*-c

语法树vs.DAG

中间代码的种类assigna+*b@c*b@cassigna+*b@c2024/4/7《编译原理与技术》讲义6中间代码的种类e.g.4构造表达式的语法树（DAG） 产生式 语义规则EE1+E2E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)EE1-E2E.nptr:=mknode(‘-’,E1.nptr,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)2024/4/7《编译原理与技术》讲义7中间代码的种类e.g.4构造表达式的语法树（DAG）

E.nptr

－E的语法树（根结点指针）

mknode(op,left,right)－建立一个表达式语法树结点，它的运算符为op，左、右运算对象是left和right所指的语法树。

mkleaf(‘NUM’,number.lex_val)－

mkleaf(‘ID’,id.entry)－ 建立表达式语法树的叶子结点。2024/4/7《编译原理与技术》讲义8e.g.4构造表达式a+b*-4的语法树（DAG）

中间代码的种类+

IDa*

IDb@

NUM42024/4/7《编译原理与技术》讲义9中间代码的种类三地址代码 一般形式：x:=yopz 或 x:=opy e.g.5a:=b*-c+b*-c的三地址代码

1）t1:=-c 1’）t1:=-c 2）t2:=b*t1 2’）t2:=b*t1 3）t3:=-c 3’）t3:=t2+t2 4）t4:=b*t3 4’）a:=t3 5）t5:=t2+t4 6）a:=t5

2024/4/7《编译原理与技术》讲义10中间代码的种类常用的三地址代码 －x:=yopz二元运算 －x:=opy单目运算 －x:=y 值拷贝 －gotoL 无条件转移到代码标号L处 －ifxRELOPygotoL条件转移代码：若x和y满足RELOP关系，则转移至代码标号L处 －paramX参数X

－CALLproc，N 调用过程proc，参数个数为N2024/4/7《编译原理与技术》讲义11中间代码的种类常用的三地址代码（续） －returny过程返回，返回值为y

－x:=y[i] x[i]:=y变址语句 －x:=&y*x:=yx:=*y指针操作语句三地址代码实现形式 －四元式：（op,arg1,arg2,result） －三元式：（op,arg1,arg2

） －间接三元式（三元式的指针表）2024/4/7《编译原理与技术》讲义12中间代码的种类e.g.6a:=b*-c+b*-c的四元式和三元式

四元式 vs.三元式

1）（@,c,－,t1）①（@,c,－）

2）（*,b,t1,t2）②（*,b,①）

3）（@,c,－,t3）③（@,c,－）

4）（*,b,t3,t4）④（*,b,③）

5）（+,t2,t4,t5）⑤（+,②,④）

6）（:=,t5,－,a）⑥（:=,a,⑤）2024/4/7《编译原理与技术》讲义13中间代码的种类e.g.7a:=b*c+d/f的间接三元式间接三元式/调整次序 三元式⑴⑬ ⑭ ⑬（*,b,c）⑵⑭ ⑬ ⑭（/,d,f）⑶⑮ ⑮ ⑮（+,⑬,⑭）⑷

⑯

⑯ ⑯

（:=,a,⑮）

2024/4/7《编译原理与技术》讲义14中间代码的种类四元式按编号次序计算计算结果存于result方便移动，计算次序容易调整大量引入临时变量三元式按编号次序计算由编号代表不方便移动在代码生成时进行临时变量的分配间接三元式按编号次序计算方便移动，计算次序容易调整在代码生成时进行临时变量的分配2024/4/7《编译原理与技术》讲义15说明语句的翻译一般不产生代码；仅将有关变量的属性填入符号表（如类型、存储偏移位置－offset）e.g.8一个说明语句的翻译方案 文法G1如下：

PD DD;D Did:T Tint|real|array[number]ofT1|T12024/4/7《编译原理与技术》讲义16e.g.8一个说明语句的翻译方案（续）－有关符号的属性

T.type －变量所具有的类型，如 整型INT

实型 REAL

数组类型array（元素个数，元素类型） 指针类型pointer（所指对象类型）

T.width －该类型数据所占的字节数

offset－变量的存储偏移地址2024/4/7《编译原理与技术》讲义17e.g.8一个说明语句的翻译方案（续）T.typeT.width整型INT4实型REAL4数组array（number,T1）number.val*T1.width指针pointer（T1）4enter(name,type,offset)－将类型type和偏移offset填入符号表中name所在的表项。2024/4/7《编译原理与技术》讲义18e.g.8一个说明语句的翻译方案（续）（1）P

MD（2）DD1;D2（3）Did:T {//填入变量的相关属性

enter(,T.type,offset) //计算下一可用偏移位置

offset=offset+T.width }（4）M{offset:=0//偏移初始为0}2024/4/7《编译原理与技术》讲义19e.g.8一个说明语句的翻译方案（续）（5）Tint{T.type:=INT;T.width:=4}（6）Treal{T.type:=REAL;T.width:=4}（7）Tarray[number]ofT1{ T.type:=array(number.val,T1.type); T.width:=number.val*T1.width }（8）Tpointer(T1) {T.type:=pointer(T1.type);T.width:=4}2024/4/7《编译原理与技术》讲义20e.g.9一个嵌套说明语句的翻译方案文法G2如下：

PD DD1;D2 Did:T Dprocid;D1;S Tint|real|array[number]ofT1|T1

Sa2024/4/7《编译原理与技术》讲义21e.g.9一个嵌套说明语句的翻译方案产生式Dprocid;D1;S引入过程id的声明；D1为其局部说明语句，可以声明变量或嵌套定义其它过程；约定每个过程有自己独立的符号表且嵌套定义的过程符号表头有指针指向外围（父）过程的符号表；而父过程符号表中有该嵌套子过程的条目（涉及子过程名和子过程符号表的指针等属性）。2024/4/7《编译原理与技术》讲义22相关定义：

/*在父过程符号表中建立子过程名的条目*/enter-proc（parent-table,sub-proc-name, sub-table）

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

MD{addwidth(top(tblptr),top(offset)), pop(tblptr);pop(offset) }/*保留变量分配空间大小并清空符号表和偏移栈*/

M{t:=mktable(null); push(t,tblptr);push(0,offset) }/*建立主程序（最外围）的符号表 偏移从0开始*/ DD1;D22024/4/7《编译原理与技术》讲义24Dprocid;ND1;S{t:=top(tblptr); addwidth(t,top(offset)); pop(tblptr);pop(offset); enter-proc(top(tblptr),,t)}/*保留当前（子）过程声明变量的总空间；弹出符号表和偏移栈顶（露出父过程的符号表和偏移）；在父过程符号表中填写子过程名有关条目*/N{t:=mktable(top(tblptr)); push(t,tblptr);push(0,offset)

}/*建立子过程的符号表和偏移从0开始*/2024/4/7《编译原理与技术》讲义25Did:T{enter(top(tblptr),, T.type,top(offset)); top(offset):=top(offset)+T.width;}/*将变量name的有关属性填入当前符号表*//*以下产生式的翻译方案略*/Tint|real|array[number]ofT1|T1Sa2024/4/7《编译原理与技术》讲义26i:int;j:int;PROCP1; k:int;f:real; PROCP2; l:int; a1; a2;PROCP3; temp:int;max:int; a3;

e.g.10过程嵌套声明P0P1P3P2过程声明层次图2024/4/7《编译原理与技术》讲义27初始：M

e.g.10过程嵌套声明（续）符号栈偏移栈P00topnull总偏移：P02024/4/7《编译原理与技术》讲义28i:int;j:int;e.g.10过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT42024/4/7《编译原理与技术》讲义29PROCP1;（N

）e.g.10过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4P10总偏移：P12024/4/7《编译原理与技术》讲义30k:int;f:real;e.g.10过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4P18总偏移：P1kINT0freal42024/4/7《编译原理与技术》讲义31PROCP2;（N

）e.g.10过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4P18总偏移：P1kINT0freal4P20总偏移：P22024/4/7《编译原理与技术》讲义32l:int;e.g.10过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4P18总偏移：P1kINT0freal4P24总偏移：P2lINT02024/4/7《编译原理与技术》讲义33a1;e.g.10过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4P18总偏移：P1kINT0freal4总偏移：4P2lINT0P2proc

2024/4/7《编译原理与技术》讲义34a2;e.g.10过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4总偏移：8P1kINT0freal4总偏移：4P2lINT0P2proc

P1proc

2024/4/7《编译原理与技术》讲义35PROCP3;（N

）e.g.10过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4总偏移：8P1kINT0freal4总偏移：4P2lINT0P2proc

P1proc

P30总偏移：P32024/4/7《编译原理与技术》讲义36temp:int;max:int;e.g.10过程嵌套声明（续）符号栈偏移栈P08topnull总偏移：P0iINT0jINT4总偏移：8P1kINT0freal4总偏移：4P2lINT0P2proc

P1proc

P38总偏移：P3tempINT0maxINT42024/4/7《编译原理与技术》讲义37a3;e.g.10过程嵌套声明（续）符号栈偏移栈topnull总偏移：P0iINT0jINT4总偏移：8P1kINT0freal4总偏移：4P2lINT0P2proc

P1proc

P08总偏移：8P3tempINT0maxINT4P3proc

2024/4/7《编译原理与技术》讲义38PMD

；e.g.10过程嵌套声明（续）符号栈空偏移栈空topnull总偏移：8P0iINT0jINT4总偏移：8P1kINT0freal4总偏移：4P2lINT0P2proc

P1proc

总偏移：8P3tempINT0maxINT4P3proc

2024/4/7《编译原理与技术》讲义39记录的说明记录（record）语法如下：

TrecordDend

说明D含义同前面。（一般不含有过程声明，但C++可以）可以将记录中的域变量声明放在单独的符号表中（参照嵌套过程声明的做法，但外围过程指针为空）。

2024/4/7《编译原理与技术》讲义40记录说明的翻译TrecordLDend{ T.type:=record(top(tblptr));//记录类型定义

T.width:=top(offset);//记录的占用空间大小

pop(tblptr);pop(offset)}L{t:=mktable(null);//无外围“过程”

push(t,tblptr); push(0,offset);//域变量偏移从0开始

}D的翻译同前。2024/4/7《编译原理与技术》讲义41有2个C语言的结构定义如下：structA{ structB{ charc1; charc1; charc2; longl; longl; charc2; doubled; doubled;}S1; }S2;e.g.11记录域的偏移2024/4/7《编译原理与技术》讲义42e.g.11记录域的偏移数据（类型）的对齐－alignment

在X86-Linux下：

char：对齐1，起始地址可分配在任意地址

int，long，double：对齐4，即从被4整除的地址开始分配注*：其它类型机器，double可能对齐到8，如sun－SPARC2024/4/7《编译原理与技术》讲义43e.g.11记录域的偏移结构A和B的大小分别为16和20字节(Linux)c1c2

l0l1l2l3d0d1d2d3d4d5d6d7

0481216结构Ac1

l0l1l2l3c2

d0d1d2d3d4d5d6d70481216结构B20衬垫padding2024/4/7《编译原理与技术》讲义442个结构中域变量的偏移如下：structA{ structB{ charc1;0 charc1;0 charc2;1 longl;4 longl; 4 charc2;8 doubled;8 doubled;12}S1; }S2;e.g.11记录域的偏移2024/4/7《编译原理与技术》讲义45含简单变量的赋值语句，如id:=E，其中，

id为普通变量，而E是简单的算术表达式。文法定义如下：

A

id:=E EE1+E2 EE1*E2 E-E1 E(E1) Eid

赋值语句的翻译1)E的属性定义：E.place:存放表达式E“值”的场所2)newtemp－获取临时变量以存放中间结果3)emit－产生三地址码（TAC）的过程4)lookup(name)－检查name是否在符号表中有定义（条目）2024/4/7《编译原理与技术》讲义46含简单变量的赋值语句的翻译

A

id:=E{p=lookup()；

if(p!=null)emit(p‘:=‘E.place) elseerror} EE1+E2

{t:=newtemp;E.place:=t;emit(t‘:=‘E1.place‘+’E2.place)} EE1*E2{t:=newtemp;E.place:=t;emit(t‘:=‘E1.place‘*’E2.place)} E-E1{t:=newtemp;;E.place:=t;emit(t‘:=‘‘-’E1.place)} E(E1){E.place:=E1.place} Eid{p=lookup()；

if(p!=null)E.place:=pelseerror}2024/4/7《编译原理与技术》讲义47e.g.12赋值语句a:=-b*c+d的翻译a:=-bE.place=bE.place=t1TAC:1)t1:=-b*cE.place=cE.place=t22)t2:=t1*c+dE.place=dE.place=t33)t3:=t2+dA4)a:=t32024/4/7《编译原理与技术》讲义48e.g.13赋值语句后缀式代码生成AL:=E{print(‘:=‘)} EE1+E2{print(‘+’)} EE1*E2{print(‘*’)} E-E1{print(‘@’)} E(E1) Eid{p=lookup(name)；

if(p!=null)print(p)elseerror}Lid{p=lookup(name)；

if(p!=null)print(p)elseerror}2024/4/7《编译原理与技术》讲义49数组元素的翻译数组类型的声明

e.g.Pascal的数组声明，

A:array[low1..high1,…,lown..highn]ofinteger;

数组元素：A[i,j,k,…]或A[i][j][k]…

（下界）low1

i

high1（上界）,… e.g.C的数组声明，

intA[100][100][100];

数组元素：A[i][30][40]0

i(100-1)2024/4/7《编译原理与技术》讲义50数组元素的翻译数组元素的地址计算 仅讨论按行优先排列（即行主序）。约定数组名，如A，表示整个数组的起始地址（偏移）；w表示数组元素所占字节数。 一维：A[i]的地址addr为，

addr=A+(i-low1)*w =i*w+(A-low1*w)

二维：A[i1,i2]的地址addr为，(n2=high2-low2+1) addr=A+((i1-low1)*n2+(i2-low2))*w =(i1*n2+i2)*w+(A-(low1*n2+low2)*w)2024/4/7《编译原理与技术》讲义51数组元素的地址计算（行主序） 多维（K维）：A[i1,i2,…,ik]的地址，

addr=((…((i1*n2+i2)*n3+i3)…)*nk+ik)*w

+

(A-((…((low1*n2+low2)*n3+low3)…)*nk+lowk)*w)数组元素的地址addr由可变部分－var-part和常量值－const-part相加而得，即addr=“可变部分”+“常量值” 两部分可以由以下递推式计算（nm＝highm-lowm+1）

V1=i1 Vm=Vm-1*nm+im1

mK C1=low1 Cm=Cm-1*nm+lowm1

mK

当m＝K时，Vk*w即为可变部分；而A-Ck*w为常量值。 “常量值”可以在编译时刻计算；而“可变部分”则必须生成代码在运行时刻加以计算（所有下标是常量的数组元素可以除外。Why?）。2024/4/7《编译原理与技术》讲义52数组元素的翻译含有数组元素的赋值语句文法G3(1) SV:=E(2) Vid[Elist](3) Vid(4) ElistElist1,E(5) ElistE(6)EV(7)EE1+E2|E1*E2|(E1)|-E1

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

(3) Vid(4) Elistid[E(5) ElistElist1,E(6) EV(7) EE1+E2|E1*E2|(E1)|-E1

数组元素的翻译修改文法，使数组名id成为Elist的子结点（类似于前面的类型声明），从而避免继承属性的出现2024/4/7《编译原理与技术》讲义55数组元素的翻译相关符号属性定义：

V.place ，V.offset:

若V是简单变量，V.place为其“值”的存放场所，而V.offset为空（null）；当V表示数组元素时，V.place是其地址的“常量值”部分；而此时V.offset为数组元素地址中可变部分的“值”存放场所，数组元素的表示为：V.place[V.offset] Elist.place:“可变部分”的值

Elist.array:数组的属性

Elist.dim :当前处理的维数2024/4/7《编译原理与技术》讲义56数组元素的翻译翻译方案如下：(1)SV:=E{ifV.offset==null//简单变量

emit(V.place“:=”E.place) elseemit(V.place‘[‘V.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}2024/4/7《编译原理与技术》讲义57数组元素的翻译翻译方案如下（续）：(3)Vid{p:=lookup(); if(p==null)error() elseV.place