編譯原理與技術(shù)中間代碼生成

2024/4/7《編譯原理與技術(shù)》講義1編譯原理與技術(shù)中間代碼生成2024/4/7《編譯原理與技術(shù)》講義2中間代碼生成

－中間代碼形式 －控制流語(yǔ)句翻譯2024/4/7《編譯原理與技術(shù)》講義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

－語(yǔ)法樹vs.分析樹

e.g.31）a:=b*-c+b*-c，其語(yǔ)法樹為

2024/4/7《編譯原理與技術(shù)》講義4

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

語(yǔ)法樹vs.分析樹

中間代碼的種類assigna+*b@c*b@cassignEEE+E*EbE@Ea賦值語(yǔ)句cE*EbE@c2024/4/7《編譯原理與技術(shù)》講義5

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

語(yǔ)法樹vs.DAG

中間代碼的種類assigna+*b@c*b@cassigna+*b@c2024/4/7《編譯原理與技術(shù)》講義6中間代碼的種類e.g.4構(gòu)造表達(dá)式的語(yǔ)法樹（DAG） 產(chǎn)生式 語(yǔ)義規(guī)則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《編譯原理與技術(shù)》講義7中間代碼的種類e.g.4構(gòu)造表達(dá)式的語(yǔ)法樹（DAG）

E.nptr

－E的語(yǔ)法樹（根結(jié)點(diǎn)指針）

mknode(op,left,right)－建立一個(gè)表達(dá)式語(yǔ)法樹結(jié)點(diǎn)，它的運(yùn)算符為op，左、右運(yùn)算對(duì)象是left和right所指的語(yǔ)法樹。

mkleaf(‘NUM’,number.lex_val)－

mkleaf(‘ID’,id.entry)－ 建立表達(dá)式語(yǔ)法樹的葉子結(jié)點(diǎn)。2024/4/7《編譯原理與技術(shù)》講義8e.g.4構(gòu)造表達(dá)式a+b*-4的語(yǔ)法樹（DAG）

中間代碼的種類+

IDa*

IDb@

NUM42024/4/7《編譯原理與技術(shù)》講義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《編譯原理與技術(shù)》講義10中間代碼的種類常用的三地址代碼 －x:=yopz二元運(yùn)算 －x:=opy單目運(yùn)算 －x:=y 值拷貝 －gotoL 無(wú)條件轉(zhuǎn)移到代碼標(biāo)號(hào)L處 －ifxRELOPygotoL條件轉(zhuǎn)移代碼：若x和y滿足RELOP關(guān)系，則轉(zhuǎn)移至代碼標(biāo)號(hào)L處 －paramX參數(shù)X

－CALLproc，N 調(diào)用過(guò)程proc，參數(shù)個(gè)數(shù)為N2024/4/7《編譯原理與技術(shù)》講義11中間代碼的種類常用的三地址代碼（續(xù)） －returny過(guò)程返回，返回值為y

－x:=y[i] x[i]:=y變址語(yǔ)句 －x:=&y*x:=yx:=*y指針操作語(yǔ)句三地址代碼實(shí)現(xiàn)形式 －四元式：（op,arg1,arg2,result） －三元式：（op,arg1,arg2

） －間接三元式（三元式的指針表）2024/4/7《編譯原理與技術(shù)》講義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《編譯原理與技術(shù)》講義13中間代碼的種類e.g.7a:=b*c+d/f的間接三元式間接三元式/調(diào)整次序 三元式⑴? ? ?（*,b,c）⑵? ? ?（/,d,f）⑶? ? ?（+,?,?）⑷

?

? ?

（:=,a,?）

2024/4/7《編譯原理與技術(shù)》講義14中間代碼的種類四元式按編號(hào)次序計(jì)算計(jì)算結(jié)果存于result方便移動(dòng)，計(jì)算次序容易調(diào)整大量引入臨時(shí)變量三元式按編號(hào)次序計(jì)算由編號(hào)代表不方便移動(dòng)在代碼生成時(shí)進(jìn)行臨時(shí)變量的分配間接三元式按編號(hào)次序計(jì)算方便移動(dòng)，計(jì)算次序容易調(diào)整在代碼生成時(shí)進(jìn)行臨時(shí)變量的分配2024/4/7《編譯原理與技術(shù)》講義15說(shuō)明語(yǔ)句的翻譯一般不產(chǎn)生代碼；僅將有關(guān)變量的屬性填入符號(hào)表（如類型、存儲(chǔ)偏移位置－offset）e.g.8一個(gè)說(shuō)明語(yǔ)句的翻譯方案 文法G1如下：

PD DD;D Did:T Tint|real|array[number]ofT1|T12024/4/7《編譯原理與技術(shù)》講義16e.g.8一個(gè)說(shuō)明語(yǔ)句的翻譯方案（續(xù)）－有關(guān)符號(hào)的屬性

T.type －變量所具有的類型，如 整型INT

實(shí)型 REAL

數(shù)組類型array（元素個(gè)數(shù)，元素類型） 指針類型pointer（所指對(duì)象類型）

T.width －該類型數(shù)據(jù)所占的字節(jié)數(shù)

offset－變量的存儲(chǔ)偏移地址2024/4/7《編譯原理與技術(shù)》講義17e.g.8一個(gè)說(shuō)明語(yǔ)句的翻譯方案（續(xù)）T.typeT.width整型INT4實(shí)型REAL4數(shù)組array（number,T1）number.val*T1.width指針pointer（T1）4enter(name,type,offset)－將類型type和偏移offset填入符號(hào)表中name所在的表項(xiàng)。2024/4/7《編譯原理與技術(shù)》講義18e.g.8一個(gè)說(shuō)明語(yǔ)句的翻譯方案（續(xù)）（1）P

MD（2）DD1;D2（3）Did:T {//填入變量的相關(guān)屬性

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

offset=offset+T.width }（4）M{offset:=0//偏移初始為0}2024/4/7《編譯原理與技術(shù)》講義19e.g.8一個(gè)說(shuō)明語(yǔ)句的翻譯方案（續(xù)）（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《編譯原理與技術(shù)》講義20e.g.9一個(gè)嵌套說(shuō)明語(yǔ)句的翻譯方案文法G2如下：

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

Sa2024/4/7《編譯原理與技術(shù)》講義21e.g.9一個(gè)嵌套說(shuō)明語(yǔ)句的翻譯方案產(chǎn)生式Dprocid;D1;S引入過(guò)程id的聲明；D1為其局部說(shuō)明語(yǔ)句，可以聲明變量或嵌套定義其它過(guò)程；約定每個(gè)過(guò)程有自己獨(dú)立的符號(hào)表且嵌套定義的過(guò)程符號(hào)表頭有指針指向外圍（父）過(guò)程的符號(hào)表；而父過(guò)程符號(hào)表中有該嵌套子過(guò)程的條目（涉及子過(guò)程名和子過(guò)程符號(hào)表的指針等屬性）。2024/4/7《編譯原理與技術(shù)》講義22相關(guān)定義：

/*在父過(guò)程符號(hào)表中建立子過(guò)程名的條目*/enter-proc（parent-table,sub-proc-name, sub-table）

/*將所聲明變量的類型、偏移填入當(dāng)前符號(hào)表*/enter（current-table,name,type,current-offset）/*建立新的符號(hào)表，其表頭指針指向父過(guò)程符號(hào)表*/mktable（parent-table）addwidth（table，offset）//記錄變量占用的總空間符號(hào)表?xiàng)blptr和偏移棧offset（棧頂值分別表示當(dāng)前分析的過(guò)程的符號(hào)表及可用變量偏移位置）2024/4/7《編譯原理與技術(shù)》講義23e.g.9一個(gè)嵌套說(shuō)明語(yǔ)句的翻譯方案 P

MD{addwidth(top(tblptr),top(offset)), pop(tblptr);pop(offset) }/*保留變量分配空間大小并清空符號(hào)表和偏移棧*/

M{t:=mktable(null); push(t,tblptr);push(0,offset) }/*建立主程序（最外圍）的符號(hào)表 偏移從0開始*/ DD1;D22024/4/7《編譯原理與技術(shù)》講義24Dprocid;ND1;S{t:=top(tblptr); addwidth(t,top(offset)); pop(tblptr);pop(offset); enter-proc(top(tblptr),,t)}/*保留當(dāng)前（子）過(guò)程聲明變量的總空間；彈出符號(hào)表和偏移棧頂（露出父過(guò)程的符號(hào)表和偏移）；在父過(guò)程符號(hào)表中填寫子過(guò)程名有關(guān)條目*/N{t:=mktable(top(tblptr)); push(t,tblptr);push(0,offset)

}/*建立子過(guò)程的符號(hào)表和偏移從0開始*/2024/4/7《編譯原理與技術(shù)》講義25Did:T{enter(top(tblptr),, T.type,top(offset)); top(offset):=top(offset)+T.width;}/*將變量name的有關(guān)屬性填入當(dāng)前符號(hào)表*//*以下產(chǎn)生式的翻譯方案略*/Tint|real|array[number]ofT1|T1Sa2024/4/7《編譯原理與技術(shù)》講義26i:int;j:int;PROCP1; k:int;f:real; PROCP2; l:int; a1; a2;PROCP3; temp:int;max:int; a3;

e.g.10過(guò)程嵌套聲明P0P1P3P2過(guò)程聲明層次圖2024/4/7《編譯原理與技術(shù)》講義27初始：M

e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧P00topnull總偏移：P02024/4/7《編譯原理與技術(shù)》講義28i:int;j:int;e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT42024/4/7《編譯原理與技術(shù)》講義29PROCP1;（N

）e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4P10總偏移：P12024/4/7《編譯原理與技術(shù)》講義30k:int;f:real;e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4P18總偏移：P1kINT0freal42024/4/7《編譯原理與技術(shù)》講義31PROCP2;（N

）e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4P18總偏移：P1kINT0freal4P20總偏移：P22024/4/7《編譯原理與技術(shù)》講義32l:int;e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4P18總偏移：P1kINT0freal4P24總偏移：P2lINT02024/4/7《編譯原理與技術(shù)》講義33a1;e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4P18總偏移：P1kINT0freal4總偏移：4P2lINT0P2proc

2024/4/7《編譯原理與技術(shù)》講義34a2;e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4總偏移：8P1kINT0freal4總偏移：4P2lINT0P2proc

P1proc

2024/4/7《編譯原理與技術(shù)》講義35PROCP3;（N

）e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4總偏移：8P1kINT0freal4總偏移：4P2lINT0P2proc

P1proc

P30總偏移：P32024/4/7《編譯原理與技術(shù)》講義36temp:int;max:int;e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4總偏移：8P1kINT0freal4總偏移：4P2lINT0P2proc

P1proc

P38總偏移：P3tempINT0maxINT42024/4/7《編譯原理與技術(shù)》講義37a3;e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧偏移棧topnull總偏移：P0iINT0jINT4總偏移：8P1kINT0freal4總偏移：4P2lINT0P2proc

P1proc

P08總偏移：8P3tempINT0maxINT4P3proc

2024/4/7《編譯原理與技術(shù)》講義38PMD

；e.g.10過(guò)程嵌套聲明（續(xù)）符號(hào)棧空偏移?？誸opnull總偏移：8P0iINT0jINT4總偏移：8P1kINT0freal4總偏移：4P2lINT0P2proc

P1proc

總偏移：8P3tempINT0maxINT4P3proc

2024/4/7《編譯原理與技術(shù)》講義39記錄的說(shuō)明記錄（record）語(yǔ)法如下：

TrecordDend

說(shuō)明D含義同前面。（一般不含有過(guò)程聲明，但C++可以）可以將記錄中的域變量聲明放在單獨(dú)的符號(hào)表中（參照嵌套過(guò)程聲明的做法，但外圍過(guò)程指針為空）。

2024/4/7《編譯原理與技術(shù)》講義40記錄說(shuō)明的翻譯TrecordLDend{ T.type:=record(top(tblptr));//記錄類型定義

T.width:=top(offset);//記錄的占用空間大小

pop(tblptr);pop(offset)}L{t:=mktable(null);//無(wú)外圍“過(guò)程”

push(t,tblptr); push(0,offset);//域變量偏移從0開始

}D的翻譯同前。2024/4/7《編譯原理與技術(shù)》講義41有2個(gè)C語(yǔ)言的結(jié)構(gòu)定義如下：structA{ structB{ charc1; charc1; charc2; longl; longl; charc2; doubled; doubled;}S1; }S2;e.g.11記錄域的偏移2024/4/7《編譯原理與技術(shù)》講義42e.g.11記錄域的偏移數(shù)據(jù)（類型）的對(duì)齊－alignment

在X86-Linux下：

char：對(duì)齊1，起始地址可分配在任意地址

int，long，double：對(duì)齊4，即從被4整除的地址開始分配注*：其它類型機(jī)器，double可能對(duì)齊到8，如sun－SPARC2024/4/7《編譯原理與技術(shù)》講義43e.g.11記錄域的偏移結(jié)構(gòu)A和B的大小分別為16和20字節(jié)(Linux)c1c2

l0l1l2l3d0d1d2d3d4d5d6d7

0481216結(jié)構(gòu)Ac1

l0l1l2l3c2

d0d1d2d3d4d5d6d70481216結(jié)構(gòu)B20襯墊padding2024/4/7《編譯原理與技術(shù)》講義442個(gè)結(jié)構(gòu)中域變量的偏移如下：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《編譯原理與技術(shù)》講義45含簡(jiǎn)單變量的賦值語(yǔ)句，如id:=E，其中，

id為普通變量，而E是簡(jiǎn)單的算術(shù)表達(dá)式。文法定義如下：

A

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

賦值語(yǔ)句的翻譯1)E的屬性定義：E.place:存放表達(dá)式E“值”的場(chǎng)所2)newtemp－獲取臨時(shí)變量以存放中間結(jié)果3)emit－產(chǎn)生三地址碼（TAC）的過(guò)程4)lookup(name)－檢查name是否在符號(hào)表中有定義（條目）2024/4/7《編譯原理與技術(shù)》講義46含簡(jiǎn)單變量的賦值語(yǔ)句的翻譯

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《編譯原理與技術(shù)》講義47e.g.12賦值語(yǔ)句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《編譯原理與技術(shù)》講義48e.g.13賦值語(yǔ)句后綴式代碼生成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《編譯原理與技術(shù)》講義49數(shù)組元素的翻譯數(shù)組類型的聲明

e.g.Pascal的數(shù)組聲明，

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

數(shù)組元素：A[i,j,k,…]或A[i][j][k]…

（下界）low1

i

high1（上界）,… e.g.C的數(shù)組聲明，

intA[100][100][100];

數(shù)組元素：A[i][30][40]0

i(100-1)2024/4/7《編譯原理與技術(shù)》講義50數(shù)組元素的翻譯數(shù)組元素的地址計(jì)算 僅討論按行優(yōu)先排列（即行主序）。約定數(shù)組名，如A，表示整個(gè)數(shù)組的起始地址（偏移）；w表示數(shù)組元素所占字節(jié)數(shù)。 一維：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《編譯原理與技術(shù)》講義51數(shù)組元素的地址計(jì)算（行主序） 多維（K維）：A[i1,i2,…,ik]的地址，

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

+

(A-((…((low1*n2+low2)*n3+low3)…)*nk+lowk)*w)數(shù)組元素的地址addr由可變部分－var-part和常量值－const-part相加而得，即addr=“可變部分”+“常量值” 兩部分可以由以下遞推式計(jì)算（nm＝highm-lowm+1）

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

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

mK

當(dāng)m＝K時(shí)，Vk*w即為可變部分；而A-Ck*w為常量值。 “常量值”可以在編譯時(shí)刻計(jì)算；而“可變部分”則必須生成代碼在運(yùn)行時(shí)刻加以計(jì)算（所有下標(biāo)是常量的數(shù)組元素可以除外。Why?）。2024/4/7《編譯原理與技術(shù)》講義52數(shù)組元素的翻譯含有數(shù)組元素的賦值語(yǔ)句文法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《編譯原理與技術(shù)》講義53輸入串A[x,y]:=z的分析樹SV:=EA[Elist]Elist,EEVxVyVz當(dāng)分析到下標(biāo)（表達(dá)式）x和y時(shí)，要計(jì)算地址中的“可變部分”。這時(shí)需要知曉數(shù)組A的有關(guān)的屬性，如nm，類型寬度w等，而這些信息存于在結(jié)點(diǎn)A處。若想使用必須定義有關(guān)繼承屬性來(lái)傳遞之。但在移進(jìn)－歸約分析不適合繼承屬性的計(jì)算！2024/4/7《編譯原理與技術(shù)》講義54改進(jìn)后的含有數(shù)組元素的賦值語(yǔ)句文法G3‘(1) SV:=E(2) VElist]

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

數(shù)組元素的翻譯修改文法，使數(shù)組名id成為Elist的子結(jié)點(diǎn)（類似于前面的類型聲明），從而避免繼承屬性的出現(xiàn)2024/4/7《編譯原理與技術(shù)》講義55數(shù)組元素的翻譯相關(guān)符號(hào)屬性定義：

V.place ，V.offset:

若V是簡(jiǎn)單變量，V.place為其“值”的存放場(chǎng)所，而V.offset為空（null）；當(dāng)V表示數(shù)組元素時(shí)，V.place是其地址的“常量值”部分；而此時(shí)V.offset為數(shù)組元素地址中可變部分的“值”存放場(chǎng)所，數(shù)組元素的表示為：V.place[V.offset] Elist.place:“可變部分”的值

Elist.array:數(shù)組的屬性

Elist.dim :當(dāng)前處理的維數(shù)2024/4/7《編譯原理與技術(shù)》講義56數(shù)組元素的翻譯翻譯方案如下：(1)SV:=E{ifV.offset==null//簡(jiǎn)單變量

emit(V.place“:=”E.place) elseemit(V.place‘[‘V.offset‘]’“:=”E.place) //取數(shù)組元素的左值

}(2)VElist]{/*獲取數(shù)組元素地址的常量值和可變部分*/ 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《編譯原理與技術(shù)》講義57數(shù)組元素的翻譯翻譯方案如下（續(xù)）：(3)Vid{p:=lookup(); if(p==null)error() elseV.place