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

1、2022/7/12編譯原理與技術(shù)講義1編譯原理與技術(shù)中間代碼生成2022/7/12編譯原理與技術(shù)講義2中間代碼生成中間代碼形式控制流語句翻譯2022/7/12編譯原理與技術(shù)講義3中間代碼生成中間代碼的種類 后綴式（逆波蘭式）e.g.1 a + b * -c a b c * +e.g.2 1）a := b* -c + b * -c，其后綴式為 a b c * b c * + assign 2）if ab then c := c + 1 a b c c 1 + assign IF 語法樹 vs. 分析樹e.g.3 1）a := b* -c + b * -c，其語法樹為2022/7/12編譯原理與技

2、術(shù)講義4 e.g.3 1）a := b* -c + b * -c 語法樹 vs. 分析樹中間代碼的種類assigna+*bc*bcassignEEE+E*EbEEa賦值語句cE*EbEc2022/7/12編譯原理與技術(shù)講義5 e.g.3 2）a := b* -c + b * -c 語法樹 vs. DAG中間代碼的種類assigna+*bc*bcassigna+*bc2022/7/12編譯原理與技術(shù)講義6中間代碼的種類e.g.4 構(gòu)造表達(dá)式的語法樹（DAG）產(chǎn)生式 語義規(guī)則EE1 + E2 E.nptr := mknode(+,E1.nptr, E2.nptr)EE1 - E2 E.nptr :

3、= mknode(-,E1.nptr, E2.nptr)EE1 * E2 E.nptr := mknode(*,E1.nptr, E2.nptr)EE1 / E2 E.nptr := mknode(/,E1.nptr, E2.nptr)E( E1 ) E.nptr := E1.nptrE - E1 E.nptr := mknode(,E1.nptr, )Enumber E.nptr := mkleaf(NUM,number.lex_val)Eid E.nptr := mkleaf(ID,id.entry)2022/7/12編譯原理與技術(shù)講義7中間代碼的種類e.g.4 構(gòu)造表達(dá)式的語法樹（DAG

4、）E.nptr E的語法樹（根結(jié)點(diǎn)指針） mknode(op, left, right)建立一個(gè)表達(dá)式語法樹結(jié)點(diǎn)，它的運(yùn)算符為op，左、右運(yùn)算對(duì)象是left和right所指的語法樹。 mkleaf(NUM,number.lex_val) mkleaf(ID,id.entry)建立表達(dá)式語法樹的葉子結(jié)點(diǎn)。2022/7/12編譯原理與技術(shù)講義8e.g.4 構(gòu)造表達(dá)式a+b*-4的語法樹（DAG）中間代碼的種類+ ID a* ID b NUM42022/7/12編譯原理與技術(shù)講義9中間代碼的種類三地址代碼一般形式：x := y op z或 x := op ye.g.5 a := b* -c + b

5、* -c的三地址代碼 1）t1 := - c1） 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 := t52022/7/12編譯原理與技術(shù)講義10中間代碼的種類常用的三地址代碼 x := y op z 二元運(yùn)算 x := op y 單目運(yùn)算 x := y 值拷貝 goto L 無條件轉(zhuǎn)移到代碼標(biāo)號(hào)L處 if x RELOP y goto L 條件轉(zhuǎn)移代碼：若x和y滿足RELOP關(guān)系，則轉(zhuǎn)移至代碼標(biāo)號(hào)L處 par

6、am X 參數(shù)X CALL proc，N 調(diào)用過程proc，參數(shù)個(gè)數(shù)為N2022/7/12編譯原理與技術(shù)講義11中間代碼的種類常用的三地址代碼（續(xù)） return y 過程返回，返回值為y x := y i x i := y 變址語句 x := &y *x := y x := *y 指針操作語句 三地址代碼實(shí)現(xiàn)形式 四元式： （ op, arg1, arg2, result ） 三元式： （ op, arg1, arg2 ） 間接三元式（三元式的指針表）2022/7/12編譯原理與技術(shù)講義12中間代碼的種類e.g.6 a := b* -c + b * -c 的四元式和三元式 四元式 vs. 三

7、元式 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, ）2022/7/12編譯原理與技術(shù)講義13中間代碼的種類e.g.7 a := b * c + d / f 的間接三元式間接三元式 / 調(diào)整次序三元式 （ * , b , c ） （ / , d , f ） （ + , , ） （ := , a , ） 2022/7/12編

8、譯原理與技術(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í)變量的分配2022/7/12編譯原理與技術(shù)講義15說明語句的翻譯一般不產(chǎn)生代碼；僅將有關(guān)變量的屬性填入符號(hào)表（如類型、存儲(chǔ)偏移位置offset）e.g. 8 一個(gè)說明語句的翻譯方案文法G1如下：PDDD ; DDid : TTint | real | array number of T1 | T12022/7/12編譯原理與技術(shù)講義16e

9、.g. 8 一個(gè)說明語句的翻譯方案（續(xù)） 有關(guān)符號(hào)的屬性 T.type 變量所具有的類型，如整型 INT實(shí)型REAL數(shù)組類型 array（元素個(gè)數(shù)，元素類型）指針類型 pointer（所指對(duì)象類型） T.width 該類型數(shù)據(jù)所占的字節(jié)數(shù) offset 變量的存儲(chǔ)偏移地址2022/7/12編譯原理與技術(shù)講義17e.g. 8 一個(gè)說明語句的翻譯方案（續(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)

10、表中name所在的表項(xiàng)。2022/7/12編譯原理與技術(shù)講義18e.g. 8 一個(gè)說明語句的翻譯方案（續(xù)）（1）PM D（2）DD1 ; D2（3）Did : T / 填入變量的相關(guān)屬性 enter( , T.type, offset) / 計(jì)算下一可用偏移位置 offset = offset + T.width （4）M offset := 0 / 偏移初始為02022/7/12編譯原理與技術(shù)講義19e.g. 8 一個(gè)說明語句的翻譯方案（續(xù)）（5）Tint T.type := INT; T.width := 4 （6）Treal T.type := REAL; T.width

11、:= 4 （7）Tarray number of T1 T.type := array( number.val, T1.type); T.width := number.val * T1.width（8）Tpointer( T1 ) T.type := pointer( T1.type) ; T.width := 4 2022/7/12編譯原理與技術(shù)講義20e.g. 9 一個(gè)嵌套說明語句的翻譯方案文法G2如下：PDDD1 ; D2Did : T D proc id ; D1 ; S Tint | real | array number of T1 | T1Sa2022/7/12編譯原理與技術(shù)講

12、義21e.g. 9 一個(gè)嵌套說明語句的翻譯方案產(chǎn)生式 D proc id ; D1 ; S 引入過程id的聲明；D1為其局部說明語句，可以聲明變量或嵌套定義其它過程；約定每個(gè)過程有自己獨(dú)立的符號(hào)表且嵌套定義的過程符號(hào)表頭有指針指向外圍（父）過程的符號(hào)表；而父過程符號(hào)表中有該嵌套子過程的條目（涉及子過程名和子過程符號(hào)表的指針等屬性）。2022/7/12編譯原理與技術(shù)講義22相關(guān)定義：/* 在父過程符號(hào)表中建立子過程名的條目*/enter-proc（parent-table, sub-proc-name, sub-table）/* 將所聲明變量的類型、偏移填入當(dāng)前符號(hào)表*/enter（curren

13、t-table, name, type, current-offset）/* 建立新的符號(hào)表，其表頭指針指向父過程符號(hào)表*/mktable（parent-table）addwidth（table，offset ）/記錄變量占用的總空間符號(hào)表?xiàng)blptr和偏移棧offset（棧頂值分別表示當(dāng)前分析的過程的符號(hào)表及可用變量偏移位置）2022/7/12編譯原理與技術(shù)講義23e.g. 9 一個(gè)嵌套說明語句的翻譯方案PM D addwidth( top(tblptr), top(offset) ), pop( tblptr ) ; pop( offset ) /* 保留變量分配空間大小并清空符號(hào)表和偏

14、移棧 */M t := mktable(null); push(t,tblptr); push(0,offset) /* 建立主程序（最外圍）的符號(hào)表偏移從0開始 */DD1 ; D22022/7/12編譯原理與技術(shù)講義24D proc id ; N D1 ; S t := top( tblptr );addwidth( t, top( offset ) );pop( tblptr ); pop( offset );enter-proc( top( tblptr ), , t ) /* 保留當(dāng)前（子）過程聲明變量的總空間；彈出符號(hào)表和偏移棧頂（露出父過程的符號(hào)表和偏移）；在父過程

15、符號(hào)表中填寫子過程名有關(guān)條目 */N t := mktable( top( tblptr ) ); push( t, tblptr ) ; push( 0, offset ) /* 建立子過程的符號(hào)表和偏移從0開始 */2022/7/12編譯原理與技術(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 n

16、umber of T1 | T1Sa2022/7/12編譯原理與技術(shù)講義26i : int; j : int ;PROC P1 ; k : int; f : real ;PROC P2; l : int ;a1 ;a2;PROC P3;temp : int ; max : int ;a3;e.g.10 過程嵌套聲明P0P1P3P2過程聲明層次圖2022/7/12編譯原理與技術(shù)講義27初始：Me.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧P00topnull總偏移：P02022/7/12編譯原理與技術(shù)講義28i : int ; j : int ;e.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08t

17、opnull總偏移：P0iINT0jINT42022/7/12編譯原理與技術(shù)講義29PROC P1 ; （N）e.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4P10總偏移：P12022/7/12編譯原理與技術(shù)講義30k : int ; f : real ;e.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4P18總偏移：P1kINT0freal42022/7/12編譯原理與技術(shù)講義31PROC P2 ; （N）e.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT

18、4P18總偏移：P1kINT0freal4P20總偏移：P22022/7/12編譯原理與技術(shù)講義32l : int ;e.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4P18總偏移：P1kINT0freal4P24總偏移：P2lINT02022/7/12編譯原理與技術(shù)講義33a1 ;e.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4P18總偏移：P1kINT0freal4總偏移：4P2lINT0P2proc 2022/7/12編譯原理與技術(shù)講義34a2 ;e.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧P0

19、8topnull總偏移：P0iINT0jINT4總偏移：8P1kINT0freal4總偏移：4P2lINT0P2proc P1proc 2022/7/12編譯原理與技術(shù)講義35PROC P3 ; （N）e.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4總偏移：8P1kINT0freal4總偏移：4P2lINT0P2proc P1proc P30總偏移：P32022/7/12編譯原理與技術(shù)講義36temp : int; max : int;e.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧P08topnull總偏移：P0iINT0jINT4總偏移：8P1k

20、INT0freal4總偏移：4P2lINT0P2proc P1proc P38總偏移：P3tempINT0maxINT42022/7/12編譯原理與技術(shù)講義37a3;e.g.10 過程嵌套聲明（續(xù)）符號(hào)棧偏移棧topnull總偏移：P0iINT0jINT4總偏移：8P1kINT0freal4總偏移：4P2lINT0P2proc P1proc P08總偏移：8P3tempINT0maxINT4P3proc 2022/7/12編譯原理與技術(shù)講義38P M D ；e.g.10 過程嵌套聲明（續(xù)）符號(hào)?？掌茥？誸opnull總偏移：8P0iINT0jINT4總偏移：8P1kINT0freal4總偏移

21、：4P2lINT0P2proc P1proc 總偏移：8P3tempINT0maxINT4P3proc 2022/7/12編譯原理與技術(shù)講義39記錄的說明記錄（record ）語法如下：T record D end說明D含義同前面。（一般不含有過程聲明，但C+可以）可以將記錄中的域變量聲明放在單獨(dú)的符號(hào)表中（參照嵌套過程聲明的做法，但外圍過程指針為空）。 2022/7/12編譯原理與技術(shù)講義40記錄說明的翻譯T record L D end T.type := record( top( tblptr ) ); /記錄類型定義 T.width := top( offset ); / 記錄的占用空

22、間大小 pop( tblptr ); pop( offset ) L t := mktable( null ); / 無外圍“過程” push(t, tblptr ); push( 0, offset ); / 域變量偏移從0開始D的翻譯同前。2022/7/12編譯原理與技術(shù)講義41有2個(gè)C語言的結(jié)構(gòu)定義如下：struct A struct B char c1; char c1;char c2; long l; long l; char c2;double d; double d; S1; S2;e.g.11 記錄域的偏移2022/7/12編譯原理與技術(shù)講義42e.g.11 記錄域的偏移數(shù)據(jù)（

23、類型）的對(duì)齊alignment在 X86-Linux下：char ：對(duì)齊1，起始地址可分配在任意地址int，long，double ：對(duì)齊4，即從被4整除的地址開始分配注* ：其它類型機(jī)器，double可能對(duì)齊到8，如sunSPARC2022/7/12編譯原理與技術(shù)講義43e.g.11 記錄域的偏移結(jié)構(gòu)A 和 B的大小分別為16和20字節(jié)(Linux)c1 c2l0l1l2l3d0d1d2d3d4d5d6d7 0481216結(jié)構(gòu) Ac1 l0l1l2l3c2d0d1d2d3d4d5d6d70481216結(jié)構(gòu) B20襯墊padding2022/7/12編譯原理與技術(shù)講義442個(gè)結(jié)構(gòu)中域變量的偏移

24、如下：struct A struct B char c1; 0char c1; 0char c2; 1long l; 4long l; 4 char c2; 8double d; 8double d; 12 S1; S2;e.g.11 記錄域的偏移2022/7/12編譯原理與技術(shù)講義45含簡(jiǎn)單變量的賦值語句，如id := E，其中，id為普通變量，而E是簡(jiǎn)單的算術(shù)表達(dá)式。文法定義如下：A id := EE E1 + E2E E1 * E2E - E1E ( E1 )E id 賦值語句的翻譯1) E的屬性定義：E.place : 存放表達(dá)式E“值”的場(chǎng)所2) newtemp 獲取臨時(shí)變量以存放中

25、間結(jié)果3) emit 產(chǎn)生三地址碼（TAC）的過程4) lookup( name ) 檢查name是否在符號(hào)表中有定義（條目）2022/7/12編譯原理與技術(shù)講義46含簡(jiǎn)單變量的賦值語句的翻譯A id := E p = lookup ()； if ( p != null ) emit( p := E.place) else error E E1 + E2 t := newtemp; E.place := t ;emit( t := E1.place + E2.place ) E E1 * E2 t := newtemp; E.place := t; emit( t := E1.p

26、lace * E2.place ) E - E1 t := newtemp; ;E.place := t; emit( t := - E1.place ) E ( E1 ) E.place := E1.place E id p = lookup ()； if ( p != null ) E.place := p else error 2022/7/12編譯原理與技術(shù)講義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

27、.place=dE.place=t33) t3 := t2 + d A4) a := t32022/7/12編譯原理與技術(shù)講義48e.g.13 賦值語句后綴式代碼生成 A L := E print ( := ) E E1 + E2 print ( + ) E E1 * E2 print ( * ) E - E1 print ( ) E ( E1 ) E id p = lookup (name)； if ( p != null ) print( p ) else error Lid p = lookup (name)； if ( p != null ) print( p ) else error

28、 2022/7/12編譯原理與技術(shù)講義49數(shù)組元素的翻譯數(shù)組類型的聲明e.g. Pascal的數(shù)組聲明，A : array low1.high1,lown.highn of integer ;數(shù)組元素：A i , j, k, 或 Aijk （下界）low1 i high1（上界） , e.g. C的數(shù)組聲明，int A 100100100; 數(shù)組元素：A i 3040 0 i (100-1)2022/7/12編譯原理與技術(shù)講義50數(shù)組元素的翻譯數(shù)組元素的地址計(jì)算僅討論按行優(yōu)先排列（即行主序）。約定數(shù)組名，如A，表示整個(gè)數(shù)組的起始地址（偏移）；w 表示數(shù)組元素所占字節(jié)數(shù)。一維：A i 的地址ad

29、dr為，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)2022/7/12編譯原理與技術(shù)講義51數(shù)組元素的地址計(jì)算（行主序）多維（K維）：A i1 , i2,ik 的地址，addr = ( ( ( ( i1 * n2 + i2 ) * n3 + i3)*nk+ik)

30、 * w + (A - ( ( ( ( low1 * n2 + low2 ) * n3 + low3)*nk+lowk) * w)數(shù)組元素的地址addr由可變部分var-part和常量值const-part相加而得，即 addr = “可變部分” + “常量值”兩部分可以由以下遞推式計(jì)算（nmhighm-lowm+1）V1 = i1Vm = Vm-1 * nm + im 1 m KC1 = low1Cm = Cm-1 * nm + lowm 1 m K當(dāng)mK時(shí)，Vk * w 即為可變部分；而A-Ck*w為常量值?！俺Ａ恐怠笨梢栽诰幾g時(shí)刻計(jì)算；而“可變部分”則必須生成代碼在運(yùn)行時(shí)刻加以計(jì)算（所有

31、下標(biāo)是常量的數(shù)組元素可以除外。Why?）。2022/7/12編譯原理與技術(shù)講義52數(shù)組元素的翻譯含有數(shù)組元素的賦值語句文法G3(1)SV := E(2)V id Elist (3)V id (4)ElistElist1 , E(5)ElistE(6) E V (7) EE1 + E2 | E1 * E2 | (E1) | - E1 2022/7/12編譯原理與技術(shù)講義53輸入串 A x,y := z的分析樹 SV:=EAElistElist,EEVxVyVz當(dāng)分析到下標(biāo)（表達(dá)式）x和y時(shí)，要計(jì)算地址中的“可變部分”。這時(shí)需要知曉數(shù)組A的有關(guān)的屬性，如nm，類型寬度w等，而這些信息存于在結(jié)點(diǎn)A處

32、。若想使用必須定義有關(guān)繼承屬性來傳遞之。但在移進(jìn)歸約分析不適合繼承屬性的計(jì)算！2022/7/12編譯原理與技術(shù)講義54改進(jìn)后的含有數(shù)組元素的賦值語句文法G3(1)SV := E(2)V Elist (3)V id (4)Elistid E(5)ElistElist1 , E(6) E V(7)EE1 + E2 | E1 * E2 | (E1) | - E1 數(shù)組元素的翻譯修改文法，使數(shù)組名id成為Elist的子結(jié)點(diǎn)（類似于前面的類型聲明），從而避免繼承屬性的出現(xiàn)2022/7/12編譯原理與技術(shù)講義55數(shù)組元素的翻譯相關(guān)符號(hào)屬性定義：V.place，V.offset :若V是簡(jiǎn)單變量，V.pla

33、ce為其“值”的存放場(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ù)2022/7/12編譯原理與技術(shù)講義56數(shù)組元素的翻譯翻譯方案如下：(1) SV := E if V.offset = null / 簡(jiǎn)單變量 emit( V.place “:=” E.place )else emit( V.place V

34、.offset “:=” E.place) /取數(shù)組元素的左值 (2) V Elist /* 獲取數(shù)組元素地址的常量值和可變部分 */t := newtemp;emit( t “:=” Elist.array - get-CONST(Elist.array) )V.place := t ;t := newtemp ;emit( t “:=” Elist.place * w )V.offset := t 2022/7/12編譯原理與技術(shù)講義57數(shù)組元素的翻譯翻譯方案如下（續(xù)）：(3) V id p := lookup( ); if (p = null) error() else V.place := p (4) El