編譯原理第七章中間代碼生成

第七章中間代碼生成本章內容介紹幾種常用的中間表示：后綴表示、圖形表示和三地址代碼用語法制導定義和翻譯方案的方法來說明程序設計語言的結構怎樣被翻譯成中間形式分析器靜態(tài)檢查器中間代碼生成器中間代碼記號流代碼生成器抽象語法樹后綴式DAG圖表示三地址代碼（包括三元式、四元式、間接三元式）7.1中間語言后綴式后綴式表示又稱逆波蘭表示法。這種表示法是：把運算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）。一個表達式的后綴形式可以如下定義：如果E是一個變量或常量，則E的后綴式是E自身如果E是E1opE2形式的表達式，這里op是任何二元操作符，則E的后綴式為E1’E2’op。這里E1’和E2’分別是E1和E2的后綴式。如果E是(E1)形式的表達式，則E1的后綴式就是E的后綴式只要知道每個算符的目數(shù)，對于后綴式，無論從那一端進行掃描，都能對它正確的進行唯一分解后綴式表達式翻譯為后綴式的語義規(guī)則描述：其中E.code表示E的后綴式，op表示任何二元操作符，“||”表示后綴形式的連接產生式語義規(guī)則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抽象語法樹構造賦值語句語法樹的語法制導定義：如果函數(shù)mknode(op,child)和mknode(op,left,right)盡可能返回一個指向已經存在結點的指針以代替建立新的結點，那么就會生成DAG圖。產生式語義規(guī)則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的無條件跳轉語句，即下一條將被執(zhí)行的語句是帶有標號L的三地址語句三地址語句的類型形如ifxrelopygotoL或ifagotoL的條件跳轉語句。第一種形式使用關系運算符號relop（<，>等）第二種a為布爾變量或常量用于過程調用的語句paramx和callp,n，以及返回語句returny。源程序中的過程調用p(x1,x2,…,xn)：paramx1paramx2……paramx2callp,nn表示實參個數(shù)。returny中y為過程返回的一個值形如x=y[i]及x[i]=y的索引賦值。形如x=&y,x=*y和*x=y的地址和指針賦值。三地址語句的實現(xiàn)三地址語句是中間代碼的一種抽象形式。這些語句可以以帶有操作符和操作數(shù)域的記錄來實現(xiàn)。四元式、三元式及間接三元式是三種這樣的表示。四元式 一個四元式是帶有四個域的記錄結構，這四個域分別稱為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]間接三元式為了便于代碼優(yōu)化處理，有時不直接使用三元式表，而是另設一張指示器（稱為間接碼表），它將運算的先后順序列出有關三元式在三元表中的位置。即，用一張間接碼表輔以三元式表來表示中間代碼。這種表示方法稱為間接三元式。間接三元式舉例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)當在代碼優(yōu)化過程中需要調整運算順序時，只需重新安排間接碼表，無需改動三元式表對于間接三元式表示，語義規(guī)則中應增添產生間接碼表的動作，并且在向三元式表填進一個三元式之前，必須先查看一下此式是否已在其中，就無須填入。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語義動作用到的函數(shù)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臨時名字的重新使用大量臨時變量的使用對優(yōu)化有利大量臨時變量會增加符號表管理的負擔也會增加運行時臨時數(shù)據占的空間7.3

賦值語句7.3.3數(shù)組元素的地址計算一維數(shù)組A的第i個元素的地址計算

base+(i

low)

w7.3

賦值語句7.3.3數(shù)組元素的地址計算一維數(shù)組A的第i個元素的地址計算

base+(i

low)

w

重寫成

i

w+(base

low

w)可減少了運行時的計算量7.3

賦值語句二維數(shù)組列為主

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

賦值語句二維數(shù)組列為主

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

賦值語句二維數(shù)組列為主

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

賦值語句二維數(shù)組列為主

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

賦值語句多維數(shù)組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數(shù)組元素地址計算的翻譯方案下標變量訪問的產生式

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

布爾表達式和控制流語句分支數(shù)較少時 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: