编译原理第七章中间代码生成

第七章中间代码生成本章内容介绍几种常用的中间表示：后缀表示、图形表示和三地址代码用语法制导定义和翻译方案的方法来说明程序设计语言的结构怎样被翻译成中间形式分析器静态检查器中间代码生成器中间代码记号流代码生成器抽象语法树后缀式DAG图表示三地址代码（包括三元式、四元式、间接三元式）7.1中间语言后缀式后缀式表示又称逆波兰表示法。这种表示法是：把运算量（操作数）写在前面，把算符写在后面（后缀）。一个表达式的后缀形式可以如下定义：如果E是一个变量或常量，则E的后缀式是E自身如果E是E1opE2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’op。这里E1’和E2’分别是E1和E2的后缀式。如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式只要知道每个算符的目数，对于后缀式，无论从那一端进行扫描，都能对它正确的进行唯一分解后缀式表达式翻译为后缀式的语义规则描述：其中E.code表示E的后缀式，op表示任何二元操作符，“||”表示后缀形式的连接产生式语义规则E→E1opE2E.code=E1.code||E2.code||opE→(E1)E.code=E1.codeE→idE.code=id图表示法图表示法主要包括DAG(DirectedAcyclicGraph)与抽象语法树语法树描述了源程序的自然层次结构。DAG以更紧凑的形式给出了相同的信息。两者不同的是：在一个DAG中代表公共子表达式的结点具有多个父结点在一颗抽象语法树中公共子表达式被表示为重复的子树。assign+a**uminusbcuminusbca=b*-c+b*-cassign+a*uminusbcabcuminus*bcnuminus*+assign抽象语法树构造赋值语句语法树的语法制导定义：如果函数mknode(op,child)和mknode(op,left,right)尽可能返回一个指向已经存在结点的指针以代替建立新的结点，那么就会生成DAG图。产生式语义规则S→id=ES.nptr=mknode(‘assign’,mkleaf(id,id.place),E.nptr)E→E1+E2E.nptr=mknode(‘+’,E1.nptr,E2.nptr)E→E1*E2E.nptr=mknode(‘*’,E1.nptr,E2.nptr)E→-E1E.nptr=mknode(‘uminus’,E1.nptr)E→(E1)E.nptr=E1.nptrE→idE.nptr=mkleaf(id,id.place)抽象语法树的表示形式assign••ida+*••*••uminus•uminus•idbidbidcidc••0idb1idc2uminus13*024idb5idc6uminus57*468+379ida10assign9811…a=b*-c+b*-c三地址代码三地址代码是下列形式的语句序列x=yopz其中，x、y和z是名字，常量或编译器生成的临时变量op代表任何操作符（定点运算符、浮点运算符、逻辑运算符等）像x+y*z这样的表达式要翻译为:T1=y*zT2=x+T1其中T1

，T2为编译时产生的临时变量。三地址语句的类型三地址语句类似于汇编语言代码。语句可以有符号标号，而且存在各种控制流语句。本书中使用的三地址语句：形如x=yopz的赋值语句，其中op为二元算术算符或逻辑算符形如x=opy的赋值语句，其中op为一元算符。形如x=y的赋值语句，将y的值赋给x形如gotoL的无条件跳转语句，即下一条将被执行的语句是带有标号L的三地址语句三地址语句的类型形如ifxrelopygotoL或ifagotoL的条件跳转语句。第一种形式使用关系运算符号relop（<，>等）第二种a为布尔变量或常量用于过程调用的语句paramx和callp,n，以及返回语句returny。源程序中的过程调用p(x1,x2,…,xn)：paramx1paramx2……paramx2callp,nn表示实参个数。returny中y为过程返回的一个值形如x=y[i]及x[i]=y的索引赋值。形如x=&y,x=*y和*x=y的地址和指针赋值。三地址语句的实现三地址语句是中间代码的一种抽象形式。这些语句可以以带有操作符和操作数域的记录来实现。四元式、三元式及间接三元式是三种这样的表示。四元式 一个四元式是带有四个域的记录结构，这四个域分别称为op,arg1,arg2及result。域op包含一个代表运算符的内部码三地址语句x=yopz通过将y放入arg1，z放入arg2，并且将x放入result，=为算符。像x=y或x=-y这样的一元操作符语句不使用arg2像param这样的运算符仅使用arg1域。条件和无条件语句将目标标号存入result域。临时变量也要填入符号表中。三元式为了避免把临时变量填入符号表，可以通过计算临时值语句的位置来引用该临时变量。这样三地址代码的记录只需要三个域op,arg1和arg。对于单目运算符op,arg1和arg2只需用其一。四元式/三元式举例oparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5)assignT5aoparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4)a=b*-c+b*-c三元式三元式举例oparg1arg2(0)[]=xi(1)assign(0)yoparg1arg2(0)=[]yi(1)assignx(0)x[i]=yx=y[i]间接三元式为了便于代码优化处理，有时不直接使用三元式表，而是另设一张指示器（称为间接码表），它将运算的先后顺序列出有关三元式在三元表中的位置。即，用一张间接码表辅以三元式表来表示中间代码。这种表示方法称为间接三元式。间接三元式举例X=(A+B)*CY=D^(A+B)oparg1arg2(1)+AB(2)*(1)C(3)=X(2)(4)^D(1)(5)=Y(4)间接代码(1)(2)(3)(1)(4)(5)当在代码优化过程中需要调整运算顺序时，只需重新安排间接码表，无需改动三元式表对于间接三元式表示，语义规则中应增添产生间接码表的动作，并且在向三元式表填进一个三元式之前，必须先查看一下此式是否已在其中，就无须填入。7.2

声明语句为局部名字建立符号表条目为它分配存储单元符号表中包含名字的类型和分配给它的存储单元的相对地址等信息7.2

声明语句7.2.1

过程中的声明计算被声明名字的类型和相对地址P {offset=0} DSD

D;D

Did:T {enter(,T.type,offset); offset=offset+T.width}Tinteger {T.type=integer;T.width=4}Treal{T.type=real;T.width=8}Tarray[num]ofT1 {T.type=array(num.val,T1.type);

T.width=num.val

T1.width}T

T1{T.type=pointer(T1.type);T.width=4}7.2

声明语句7.2.2作用域信息的保存所讨论语言的文法 P

DS DD;D|id:T|procid;D;S语义动作用到的函数mktable(previous)enter(table,name,type,offset)

addwidth(table,width)enterproc(table,name,newtable)7.2

声明语句P

MDS

{addwidth(top(tblptr),top(offset));

pop(tblptr);pop(offset)}M

{t=mktable(nil); push(t,tblptr);push(0,offset)}D

D1;D2Dprocid;ND1;S{t=top(tblptr);addwidth(t,top(offset));pop(tblptr);pop(offset); enterproc(top(tblptr),,t)}Did:T{enter(top(tblptr),,T.type,top(offset)); top(offset)=top(offset)+T.width}N

{t=mktable(top(tblptr)); push(t,tblptr);push(0,offset)}*7.3

赋值语句7.3.1符号表中的名字Sid=E {p=lookup(); ifp

nilthen emit(p,‘=’,E.place) elseerror}E

E1+E2

{E.place=newtemp;

emit(E.place,‘=’,E1.place,‘+’,E2.place)}E

E1{E.place=newtemp; emit(E.place,‘=’,‘uminus’,E1.place)}E(E1){E.place=E1.place}Eid{p=lookup(); ifp

nilthenE.place=pelseerror}7.3

赋值语句7.3.2临时名字的重新使用大量临时变量的使用对优化有利大量临时变量会增加符号表管理的负担也会增加运行时临时数据占的空间7.3

赋值语句7.3.3数组元素的地址计算一维数组A的第i个元素的地址计算

base+(i

low)

w7.3

赋值语句7.3.3数组元素的地址计算一维数组A的第i个元素的地址计算

base+(i

low)

w

重写成

i

w+(base

low

w)可减少了运行时的计算量7.3

赋值语句二维数组列为主

A[1,1],A[2,1],A[1,2],A[2,2],A[1,3],A[2,3]7.3

赋值语句二维数组列为主

A[1,1],A[2,1],A[1,2],A[2,2],A[1,3],A[2,3]行为主

A[1,1],A[1,2],A[1,3],A[2,1],A[2,2],A[2,3]

7.3

赋值语句二维数组列为主

A[1,1],A[2,1],A[1,2],A[2,2],A[1,3],A[2,3]行为主

A[1,1],A[1,2],A[1,3],A[2,1],A[2,2],A[2,3]

base+((i1

low1)

n2+(i2

low2))

w

（其中n2=high2

low2+1）7.3

赋值语句二维数组列为主

A[1,1],A[2,1],A[1,2],A[2,2],A[1,3],A[2,3]行为主

A[1,1],A[1,2],A[1,3],A[2,1],A[2,2],A[2,3]

base+((i1

low1)

n2+(i2

low2))

w

（其中n2=high2

low2+1） ((i1

n2)+i2)

w+

(base

((low1

n2)+low2)

w)7.3

赋值语句多维数组A[i1,i2,...,ik

]的地址表达式((…((i1

n2+i2

)

n3

+i3)…)

nk

+ik)

w

+base

((…((low1

n2+low2)

n3

+low3)…)

nk

+lowk)

w7.3

赋值语句7.3.4数组元素地址计算的翻译方案下标变量访问的产生式

Lid[Elist]|id Elist

Elist,E|E改成

L

Elist]|id Elist

Elist,E|id[E7.3

赋值语句所有产生式S

L=EE

E+EE(E)E

LL

Elist]LidElist

Elist,EElist

id[E7.3

赋值语句Lid{L.place=id.place;L.offset=null}7.3

赋值语句Lid{L.place=id.place;L.offset=null}Elist

id[E{Elist.place=E.place;Elist.ndim=1; Elist.array=id.place}7.3

赋值语句Lid{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(t,‘=’,Elist1.place,‘’,limit(Elist1.array,m));

emit(t,‘=’,t,‘+’,E.place);

Elist.array=Elist1.array;

Elist.place=t;Elist.ndim=m}7.3

赋值语句Lid{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(t,‘=’,Elist1.place,‘’,limit(Elist1.array,m));

emit(t,‘=’,t,‘+’,E.place);

Elist.array=Elist1.array;

Elist.place=t;Elist.ndim=m}L

Elist] {L.place=newtemp;emit(L.place,‘=’,base(Elist.array),‘’, invariant(Elist.array));L.offset=newtemp;emit(L.offset,‘=’,Elist.place,‘’,w)}7.3

赋值语句E

L{ifL.offset==nullthen/

L是简单变量

/

E.place=L.place

elsebeginE.place=newtemp;

emit(E.place,‘=’,L.place,‘[’,L.offset,‘]’)end}7.3

赋值语句E

L{ifL.offset==nullthen/

L是简单变量

/

E.place=L.place

elsebeginE.place=newtemp;

emit(E.place,‘=’,L.place,‘[’,L.offset,‘]’)end}E

E1+E2{E.place=newtemp; emit(E.place,‘=’,E1.place,‘+’,E2.place)}7.3

赋值语句E

L{ifL.offset==nullthen/

L是简单变量

/

E.place=L.place

elsebeginE.place=newtemp;

emit(E.place,‘=’,L.place,‘[’,L.offset,‘]’)end}E

E1+E2{E.place=newtemp; emit(E.place,‘=’,E1.place,‘+’,E2.place)}E(E1){E.place=E1.place}

7.3

赋值语句E

L{ifL.offset==nullthen/

L是简单变量

/

E.place=L.place

elsebeginE.place=newtemp;

emit(E.place,‘=’,L.place,‘[’,L.offset,‘]’)end}E

E1+E2{E.place=newtemp; emit(E.place,‘=’,E1.place,‘+’,E2.place)}E(E1){E.place=E1.place}S

L=E {ifL.offset==nullthen/

L是简单变量/

emit(L.place,‘=’,E.place) else

emit(L.place,‘[’,L.offset,‘]’,‘=’, E.place)}7.3

赋值语句S=L.place=xL.offset=nullxE.place=t4L.place=t2L.offset=t3Elist.place=t1Elist.ndim=2Elist.array=A,Elist.place=yElist.ndim=1Elist.array=AE.place=zL.place=zL.offset=nullE.place=yL.place=yL.offset=nullA[z]y

x=A[y,z]的注释分析树7.3

赋值语句S=L.place=xL.offset=nullxE.place=t4L.place=t2L.offset=t3Elist.place=t1Elist.ndim=2Elist.array=A,Elist.place=yElist.ndim=1Elist.array=AE.place=zL.place=zL.offset=nullE.place=yL.place=yL.offset=nullA[z]y

x=A[y,z]的注释分析树t1=y20t1=t1+z

7.3

赋值语句S=L.place=xL.offset=nullxE.place=t4L.place=t2L.offset=t3Elist.place=t1Elist.ndim=2Elist.array=A,Elist.place=yElist.ndim=1Elist.array=AE.place=zL.place=zL.offset=nullE.place=yL.place=yL.offset=nullA[z]y

x=A[y,z]的注释分析树t1=y20t1=t1+z

t2=A84t3=4t1

7.3

赋值语句S=L.place=xL.offset=nullxE.place=t4L.place=t2L.offset=t3Elist.place=t1Elist.ndim=2Elist.array=A,Elist.place=yElist.ndim=1Elist.array=AE.place=zL.place=zL.offset=nullE.place=yL.place=yL.offset=nullA[z]y

x=A[y,z]的注释分析树t1=y20t1=t1+z

t2=A84t3=4t1

t4=t2[t3]7.3

赋值语句S=L.place=xL.offset=nullxE.place=t4L.place=t2L.offset=t3Elist.place=t1Elist.ndim=2Elist.array=A,Elist.place=yElist.ndim=1Elist.array=AE.place=zL.place=zL.offset=nullE.place=yL.place=yL.offset=nullA[z]y

x=A[y,z]的注释分析树t1=y20t1=t1+z

t2=A84t3=4t1

t4=t2[t3]x=t4

7.4

布尔表达式和控制流语句布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式7.4

布尔表达式和控制流语句布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式布尔表达式的完全计算布尔表达式的“短路”计算B1orB2定义成ifB1thentrueelseB2B1andB2定义成

ifB1thenB2elsefalse7.4

布尔表达式和控制流语句7.4.1布尔表达式的翻译B

B

orB|BandB|notB|(B) |idrelopid|true|falsea<b的翻译100:ifa<bgoto103101:t=0102:goto104103:t=1104:7.4

布尔表达式和控制流语句B

B1orB2

{B.place=newtemp;

emit(B.place,‘=’,B1.place,‘or’B2.place)}Bid1relopid2

{B.place=newtemp;emit(‘if’,id1.place,relop.op,id2.place,‘goto’,nextstat+3);

emit(B.place,‘=’,‘0’);emit(‘goto’,nextstat+2);emit(B.place,‘=’,‘1’)}7.4

布尔表达式和控制流语句7.4.2控制流语句的翻译SifBthenS1 |ifBthenS1

elseS2 |whileBdoS1 |S1;S2

7.4

布尔表达式和控制流语句B.codeS1.codeB.true:...指向B.true指向B.false(a)if-thenB.codeS1.codeB.true:...指向B.true指向B.falseB.false:gotoS.nextS2.code(b)if-then-elseB.codeS1.codeB.true:...指向B.true指向B.falsegotoS.beginS.begin:(c)while-doS1.codeS2.codeS1.next:...(d)S1;S27.4

布尔表达式和控制流语句S

ifBthenS1{B.true=newlabel;

B.false=S.next;

S1.next=S.next;

S.code=B.code||gen(B.true,‘:’)||S1.code}B.codeS1.codeB.true:...指向B.true指向B.false(a)if-then7.4

布尔表达式和控制流语句SifBthenS1elseS2{B.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}B.codeS1.codeB.true:...指向B.true指向B.falseB.false:gotoS.nextS2.code(b)if-then-else7.4

布尔表达式和控制流语句SwhileBdoS1

{S.begin=newlabel;

B.true=newlabel;

B.false=S.next;

S1.next=S.begin;

S.code=gen(S.begin,‘:’)||B.code||

gen(B.true,‘:’)||S1.code||gen(‘goto’,S.begin)}B.codeS1.codeB.true:...指向B.true指向B.falsegotoS.beginS.begin:(c)while-do7.4

布尔表达式和控制流语句S

S1;S2{S.code=S1.code||gen(S1.next,‘:’)||S2.code}S1.codeS2.codeS1.next:...(d)S1;S27.4

布尔表达式和控制流语句7.4.3布尔表达式的控制流翻译如果B是a<b的形式，那么代码是：ifa<bgotoB.true gotoB.false7.4

布尔表达式和控制流语句表达式

a<borc<dande<f的代码是： ifa<bgotoLtrue gotoL1L1: ifc<dgotoL2 gotoLfalseL2: ife<fgotoLtrue gotoLfalse7.4

布尔表达式和控制流语句B

B1orB2{B1.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

B1orB2{B1.true=B.true;

B1.false=newlabel;

B2.true=B.true;

B2.false=B.false;

B.code=B1.code||gen(B1.false,‘:’)||B2.code}BnotB1{B1.true=B.false;

B1.false=B.true;

B.code=B1.code}7.4

布尔表达式和控制流语句B

B1andB2{B1.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

B1andB2{B1.true=newlabel;

B1.false=B.false;

B2.true=B.true;

B2.false=B.false;

B.code=B1.code||gen(B1.true,‘:’)||B2.code}B(B1

){B1.true=B.true;

B1.false=B.false;

B.code=B1.code}7.4

布尔表达式和控制流语句Bid1relopid2{B.code=gen(‘if’,id1.place,relop.op,id2.place, ‘goto’,B.true)||

gen(‘goto’,B.false)}7.4

布尔表达式和控制流语句Bid1relopid2{B.code=gen(‘if’,id1.place,relop.op,id2.place, ‘goto’,B.true)||

gen(‘goto’,B.false)}Btrue{B.code=gen(‘goto’,B.true)}Bfalse{B.code=gen(‘goto’,B.false)}布尔表达式的语法制导定义B

B1orB2B1.true=B.true;

B1.false=newlabel;

B2.true=B.true;

B2.false=B.false;

B.code=B1.code||gen(B1.false,‘:’)||B2.codeBnotB1B1.true=B.false;

B1.false=B.true;

B.code=B1.codeB

B1andB2B1.true=newlabel;

B1.false=B.false;

B2.true=B.true;

B2.false=B.false;

B.code=B1.code||gen(B1.true,‘:’)||B2.codeB(B1

)B1.true=B.true;

B1.false=B.false;

B.code=B1.codeBid1relopid2B.code=gen(‘if’,id1.place,relop.op,id2.place,‘goto’,B.true)||gen(‘goto’,B.false)BtrueB.code=gen(‘goto’,B.true）BfalseB.code=gen(‘goto’,B.false)控制流语句的语法制导定义SifBthenS1B.true=newLabel;B.false=S.next;S1.next=S.next;S.code=B.code||gen(B.true,‘:’)||S1.code

SifBthenS1elseS2B.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.codeSwhileBdoS1

S.begin=newlabel;B.true=newlabel;B.false=S.next;S1.next=S.begin;S.code=gen(S.begin,‘:’)||B.code||gen(B.true,‘:’)||

S1.code||gen(‘goto’,S.beginS

S1;S2S.code=S1.code||gen(S1.next,‘:’)||S2.code例考虑语句whilea<bdoifc<dthenx=y+zelsex=y-z7.4

布尔表达式和控制流语句7.4.4开关语句的翻译switchE begin caseV1:S1 caseV2:S2 ... caseVn-1:Sn–1 default:Sn end7.4

布尔表达式和控制流语句分支数较少时 t=E的代码 |Ln-2:ift!=

Vn-1gotoLn-1

ift!=

V1gotoL1

|

Sn-1的代码

S1的代码 | gotonext gotonext |Ln-1:Sn的代码

L1: ift!=

V2gotoL2|next: S2的代码 gotonextL2: ... ...7.4

布尔表达式和控制流语句分支较多时，将分支测试代码集中在一起，便于生成较好的分支测试代码 t=E的代码 |Ln: Sn的代码 gototest

| gotonext

L1: S1的代码 |test:ift==V1gotoL1

gotonext | ift==V2gotoL2

L2: