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

第七章中間代碼生成本章內(nèi)容介紹幾種常用的中間表示：后綴表示、圖形表示和三地址代碼用語法制導(dǎo)定義和翻譯方案的方法來說明程序設(shè)計(jì)語言的結(jié)構(gòu)怎樣被翻譯成中間形式分析器靜態(tài)檢查器中間代碼生成器中間代碼記號(hào)流代碼生成器抽象語法樹后綴式DAG圖表示三地址代碼（包括三元式、四元式、間接三元式）7.1中間語言后綴式后綴式表示又稱逆波蘭表示法。這種表示法是：把運(yùn)算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）。一個(gè)表達(dá)式的后綴形式可以如下定義：如果E是一個(gè)變量或常量，則E的后綴式是E自身如果E是E1opE2形式的表達(dá)式，這里op是任何二元操作符，則E的后綴式為E1’E2’op。這里E1’和E2’分別是E1和E2的后綴式。如果E是(E1)形式的表達(dá)式，則E1的后綴式就是E的后綴式只要知道每個(gè)算符的目數(shù)，對(duì)于后綴式，無論從那一端進(jìn)行掃描，都能對(duì)它正確的進(jìn)行唯一分解后綴式表達(dá)式翻譯為后綴式的語義規(guī)則描述：其中E.code表示E的后綴式，op表示任何二元操作符，“||”表示后綴形式的連接產(chǎn)生式語義規(guī)則E→E1opE2E.code=E1.code||E2.code||opE→(E1)E.code=E1.codeE→idE.code=id圖表示法圖表示法主要包括DAG(DirectedAcyclicGraph)與抽象語法樹語法樹描述了源程序的自然層次結(jié)構(gòu)。DAG以更緊湊的形式給出了相同的信息。兩者不同的是：在一個(gè)DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)在一顆抽象語法樹中公共子表達(dá)式被表示為重復(fù)的子樹。assign+a**uminusbcuminusbca=b*-c+b*-cassign+a*uminusbcabcuminus*bcnuminus*+assign抽象語法樹構(gòu)造賦值語句語法樹的語法制導(dǎo)定義：如果函數(shù)mknode(op,child)和mknode(op,left,right)盡可能返回一個(gè)指向已經(jīng)存在結(jié)點(diǎn)的指針以代替建立新的結(jié)點(diǎn)，那么就會(huì)生成DAG圖。產(chǎn)生式語義規(guī)則S→id=ES.nptr=mknode(‘a(chǎn)ssign’,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是名字，常量或編譯器生成的臨時(shí)變量op代表任何操作符（定點(diǎn)運(yùn)算符、浮點(diǎn)運(yùn)算符、邏輯運(yùn)算符等）像x+y*z這樣的表達(dá)式要翻譯為:T1=y*zT2=x+T1其中T1

，T2為編譯時(shí)產(chǎn)生的臨時(shí)變量。三地址語句的類型三地址語句類似于匯編語言代碼。語句可以有符號(hào)標(biāo)號(hào)，而且存在各種控制流語句。本書中使用的三地址語句：形如x=yopz的賦值語句，其中op為二元算術(shù)算符或邏輯算符形如x=opy的賦值語句，其中op為一元算符。形如x=y的賦值語句，將y的值賦給x形如gotoL的無條件跳轉(zhuǎn)語句，即下一條將被執(zhí)行的語句是帶有標(biāo)號(hào)L的三地址語句三地址語句的類型形如ifxrelopygotoL或ifagotoL的條件跳轉(zhuǎn)語句。第一種形式使用關(guān)系運(yùn)算符號(hào)relop（<，>等）第二種a為布爾變量或常量用于過程調(diào)用的語句paramx和callp,n，以及返回語句returny。源程序中的過程調(diào)用p(x1,x2,…,xn)：paramx1paramx2……paramx2callp,nn表示實(shí)參個(gè)數(shù)。returny中y為過程返回的一個(gè)值形如x=y[i]及x[i]=y的索引賦值。形如x=&y,x=*y和*x=y的地址和指針賦值。三地址語句的實(shí)現(xiàn)三地址語句是中間代碼的一種抽象形式。這些語句可以以帶有操作符和操作數(shù)域的記錄來實(shí)現(xiàn)。四元式、三元式及間接三元式是三種這樣的表示。四元式 一個(gè)四元式是帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為op,arg1,arg2及result。域op包含一個(gè)代表運(yùn)算符的內(nèi)部碼三地址語句x=yopz通過將y放入arg1，z放入arg2，并且將x放入result，=為算符。像x=y或x=-y這樣的一元操作符語句不使用arg2像param這樣的運(yùn)算符僅使用arg1域。條件和無條件語句將目標(biāo)標(biāo)號(hào)存入result域。臨時(shí)變量也要填入符號(hào)表中。三元式為了避免把臨時(shí)變量填入符號(hào)表，可以通過計(jì)算臨時(shí)值語句的位置來引用該臨時(shí)變量。這樣三地址代碼的記錄只需要三個(gè)域op,arg1和arg。對(duì)于單目運(yùn)算符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)化處理，有時(shí)不直接使用三元式表，而是另設(shè)一張指示器（稱為間接碼表），它將運(yùn)算的先后順序列出有關(guān)三元式在三元表中的位置。即，用一張間接碼表輔以三元式表來表示中間代碼。這種表示方法稱為間接三元式。間接三元式舉例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)當(dāng)在代碼優(yōu)化過程中需要調(diào)整運(yùn)算順序時(shí)，只需重新安排間接碼表，無需改動(dòng)三元式表對(duì)于間接三元式表示，語義規(guī)則中應(yīng)增添產(chǎn)生間接碼表的動(dòng)作，并且在向三元式表填進(jìn)一個(gè)三元式之前，必須先查看一下此式是否已在其中，就無須填入。7.2

聲明語句為局部名字建立符號(hào)表?xiàng)l目為它分配存儲(chǔ)單元符號(hào)表中包含名字的類型和分配給它的存儲(chǔ)單元的相對(duì)地址等信息7.2

聲明語句7.2.1

過程中的聲明計(jì)算被聲明名字的類型和相對(duì)地址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語義動(dòng)作用到的函數(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符號(hào)表中的名字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臨時(shí)名字的重新使用大量臨時(shí)變量的使用對(duì)優(yōu)化有利大量臨時(shí)變量會(huì)增加符號(hào)表管理的負(fù)擔(dān)也會(huì)增加運(yùn)行時(shí)臨時(shí)數(shù)據(jù)占的空間7.3

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

base+(i

low)

w7.3

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

base+(i

low)

w

重寫成

i

w+(base

low

w)可減少了運(yùn)行時(shí)的計(jì)算量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

]的地址表達(dá)式((…((i1

n2+i2

)

n3

+i3)…)

nk

+ik)

w

+base

((…((low1

n2+low2)

n3

+low3)…)

nk

+lowk)

w7.3

賦值語句7.3.4數(shù)組元素地址計(jì)算的翻譯方案下標(biāo)變量訪問的產(chǎn)生式

Lid[Elist]|id Elist

Elist,E|E改成

L

Elist]|id Elist

Elist,E|id[E7.3

賦值語句所有產(chǎn)生式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

布爾表達(dá)式和控制流語句布爾表達(dá)式有兩個(gè)基本目的計(jì)算邏輯值在控制流語句中用作條件表達(dá)式7.4

布爾表達(dá)式和控制流語句布爾表達(dá)式有兩個(gè)基本目的計(jì)算邏輯值在控制流語句中用作條件表達(dá)式布爾表達(dá)式的完全計(jì)算布爾表達(dá)式的“短路”計(jì)算B1orB2定義成ifB1thentrueelseB2B1andB2定義成

ifB1thenB2elsefalse7.4

布爾表達(dá)式和控制流語句7.4.1布爾表達(dá)式的翻譯B

B

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

布爾表達(dá)式和控制流語句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

布爾表達(dá)式和控制流語句7.4.2控制流語句的翻譯SifBthenS1 |ifBthenS1

elseS2 |whileBdoS1 |S1;S2

7.4

布爾表達(dá)式和控制流語句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

布爾表達(dá)式和控制流語句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

布爾表達(dá)式和控制流語句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

布爾表達(dá)式和控制流語句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

布爾表達(dá)式和控制流語句S

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

布爾表達(dá)式和控制流語句7.4.3布爾表達(dá)式的控制流翻譯如果B是a<b的形式，那么代碼是：ifa<bgotoB.true gotoB.false7.4

布爾表達(dá)式和控制流語句表達(dá)式

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

布爾表達(dá)式和控制流語句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

布爾表達(dá)式和控制流語句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

布爾表達(dá)式和控制流語句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

布爾表達(dá)式和控制流語句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

布爾表達(dá)式和控制流語句Bid1relopid2{B.code=gen(‘if’,id1.place,relop.op,id2.place, ‘goto’,B.true)||

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

布爾表達(dá)式和控制流語句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)}布爾表達(dá)式的語法制導(dǎo)定義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)控制流語句的語法制導(dǎo)定義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

布爾表達(dá)式和控制流語句7.4.4開關(guān)語句的翻譯switchE begin caseV1:S1 caseV2:S2 ... caseVn-1:Sn–1 default:Sn end7.4

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

布爾表達(dá)式和控制流語句分支較多時(shí)，將分支測(cè)試代碼集中在一起，便于生成較好的分支測(cè)試代碼 t=E的代碼 |Ln: Sn的代碼 gototest

| gotonext

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

gotonext | ift==V2gotoL2

L2: