語義分析和中間代碼生成第一頁，共六十六頁，編輯于2023年，星期一翻譯為中間語言的好處（1）便于進行與機器無關的代碼優化；（2）使編譯程序改變目標機更容易；易于編譯器的移植（3）使編譯程序的結構在邏輯上更為簡單明確，以中間語言為界面，編譯前端和后端的接口更清晰。第二頁，共六十六頁，編輯于2023年，星期一主要內容中間語言的形式后綴式，圖表方法，三元式編譯過程中不同語言的翻譯或處理方法說明語句的翻譯賦值語句的翻譯布爾表達式的翻譯控制語句的翻譯第三頁，共六十六頁，編輯于2023年，星期一7.1中間語言中間語言的形式：逆波蘭表示：后綴式圖表示法：DAG和AST三地址代碼:四元式、三元式、間接三元式

第四頁，共六十六頁，編輯于2023年，星期一7.1.1后綴式

后綴式表示法又稱逆波蘭表示法。這種方法是，把運算量（操作數）寫在前面，把算符寫在后面（后綴）。一個表達式的后綴式可以如下定義：（1）如果E是一個變量或常量，則E的后綴式是E自身。（2）如果E是E1opE2形式的表達式，這里op是任何二元操作符，則E的后綴式為E1’E2’op,這里E1’

和E2’分別為E1和E2的后綴式。（3）如果E是(E1)形式的表達式，則E1的后綴式就是E的后綴式。第五頁，共六十六頁，編輯于2023年，星期一后綴式的優點

便于計算機處理，因為在后綴式中，表達式的求值順序與運算符出現的順序一致，這樣只要用一個棧就可以實現表達式的求值。實現過程：自左向右掃描后綴表達式；遇到運算對象入棧，遇到N元運算符，就從棧頂取出N個運算對象進行計算，再將結果入棧；當全部后綴表達式掃描結束，則棧頂的值即為表達式結果。第六頁，共六十六頁，編輯于2023年，星期一后綴式特點：無括號運算對象的順序與中綴式一致根據操作符（運算符）的優先級和結合性進行相關的處理例：5+4*6546*+第七頁，共六十六頁，編輯于2023年，星期一7.1.2圖表示法圖表示法包括DAG與AST(抽象語法樹)。有向無環圖（DirectedAcyclicGraph,簡稱DAG).與抽象語法樹一樣，對于表達式中的每個子表達式，DAG圖中都有一個結點。一個內部結點代表一個操作符，它的孩子代表操作數。兩者不同的是，在DAG圖中代表公共子表達式的結點具有多個父結點，而在一棵抽象語法樹中公共子表達式被表示為重復的子樹。例：第八頁，共六十六頁，編輯于2023年，星期一5+4*6的DAG圖5+64*5+4*6+4*6的DAG圖5+64*+5+4*6+4*6的AST圖5+64*+64*第九頁，共六十六頁，編輯于2023年，星期一后綴式與抽象語法樹的關系后綴式是抽象語法樹的線性表示：每個結點都是在它的所有子節點之后立即出現的。通過對抽象語法樹的不同形式的遍歷可以形成不同形式的綴式表達式前序遍歷：前綴式中序遍歷：中綴式后序遍歷：后綴式5+64*+64*第十頁，共六十六頁，編輯于2023年，星期一產生賦值語句抽象語法樹的屬性文法S.nptr:=mknode('assign',mkleaf(id,id.place),E.nptr)

E.nptr:=mknode('+',E1.nptr,E2.nptr)E.nptr:=mknode('*',E1.nptr,E2.nptr)mkleaf(id,id.place)S→id:=EE→E1+E2E→E1*E2

E->id產生式語義規則第十一頁，共六十六頁，編輯于2023年，星期一S.nptr:=mknode('assign',mkleaf(id,id.place),E.nptr)

E.nptr:=mknode('+',E1.nptr,E2.nptr)E.nptr:=mknode('*',E1.nptr,E2.nptr)E.nptr:=mkleaf(id,id.place)mkleaf(id,id.place)S→id:=EE→E1+E2E→E1*E2E->id

a:=b+cabc+:=第十二頁，共六十六頁，編輯于2023年，星期一抽象語法樹的存儲表示二叉樹的形式：算術運算通常都是二元運算樹中每個節點包含三個域：數組的形式表示：每一個數組元素形式如下：節點類型|操作數1|操作數2節點類型|操作數1|操作數2第十三頁，共六十六頁，編輯于2023年，星期一*

uminus

id

c

id

b

賦值語句：a:=b*-c+b*-c后綴式：abcuminus*bcuminus*+assignassign

+

*

uminus

id

a

id

c

id

b

idb

idcunimus1*02

idb

idc

unimus5

*46

+37

ida

assign98

...

第十四頁，共六十六頁，編輯于2023年，星期一7.1.3三地址代碼三地址代碼是由下面一般形式的語句構成的序列:X:=yopz

其中，x、y、z為名字、常數或編譯時產生的臨時變量（存放中間結果，對應于語法樹的內部節點）；

op代表運算符號如定點運算符、浮點運算符、邏輯運算符等。每個語句的右邊只能有一個運算符。每條語句通常包含三個地址：兩個操作數地址，一個操作結果地址第十五頁，共六十六頁，編輯于2023年，星期一三地址碼示例t1：＝-ct2：＝b*t1t3：＝-ct4：＝b*t3t5：＝t2+t4a：＝t5assigna+*bcuminus*uminuscba:=b*-c+b*-c第十六頁，共六十六頁，編輯于2023年，星期一三地址碼示例（2）assigna+*bcuminust1：＝-ct2：＝b*t1t5：＝t2+t2a：=t5

a:=b*-c+b*-c第十七頁，共六十六頁，編輯于2023年，星期一三地址代碼的具體表示1．四元式：op,arg1,arg2,result(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcbt2t5arg1t1t3t4arg2resultt1t2t3t4t5aop

t1：＝-ct2：＝b*t1t3：＝-ct4：＝b*t3t5：＝t2+t4a：＝t5a:=b*(-c)+b*(-c)第十八頁，共六十六頁，編輯于2023年，星期一三地址代碼的具體表示2.三元式:op,arg1,arg2(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcb（1）aarg1(0)(2)(3)(4)arg2op

t1：＝-ct2：＝b*t1t3：＝-ct4：＝b*t3t5：＝t2+t4a：＝t5a:=b*(-c)+b*(-c)第十九頁，共六十六頁，編輯于2023年，星期一三地址代碼的具體表示3.間接三元式:間接碼表+三元式表目的：便于優化處理t1：＝-ct2：＝b*t1t3：＝-ct4：＝b*t3t5：＝t2+t4a：＝t5(1)(2)(3)(4)uminus*+assigncb（2）aarg1(1)(2)(3)arg2op間接代碼表(1)(2)(1)(2)(3)(4)a:=b*(-c)+b*(-c)第二十頁，共六十六頁，編輯于2023年，星期一t1：＝a+bt2：＝t1*cX：＝t2t3：＝a+bt4：＝d^t3Y：＝t4(1)(2)(3)(4)(5)+*:=^:=a(1)xdYarg1bc(2)(1)(4)arg2op間接代碼表(1)(2)(3)(1)(4)(5)X：=(a+b)*cY:=d^(a+b)第二十一頁，共六十六頁，編輯于2023年，星期一語義分析中各種語句的處理說明語句的翻譯賦值語句的翻譯布爾表達式的翻譯控制語句的翻譯第二十二頁，共六十六頁，編輯于2023年，星期一7.2說明語句的翻譯說明語句的處理方式：不生成可執行代碼，只涉及符號表的操作。說明語句的處理:對每個局部名字，在符號表中建立相應的表項，填寫有關的信息如類型、嵌套深度、相對地址等。相對地址：相對靜態數據區基址或活動記錄中局部數據區基址的一個偏移值。第二十三頁，共六十六頁，編輯于2023年，星期一因為每進入一次過程需分配一次內存，因此在處理過程內的說明語句時，要分配每個標識符的相對地址。設變量offset用來記錄相對地址，每次進入一個過程，先將offset置為0。每次遇到一個新名字，則把名字同offset的當前值一起錄入符號表，然后offset的值增加，其增加的值由該名字的數據類型所決定，稱為數據對象的寬度，用屬性width表示。假設integer型對象寬度為4，real型對象寬度為8，則下表為過程中說明語句的翻譯方案。第二十四頁，共六十六頁，編輯于2023年，星期一過程中的說明語句的翻譯P→D ｛offset：＝0}

D→D;DD→id：T ｛enter（，T.type，offset）； offset:=offset＋T.width｝T→integer ｛T.type：=integer;T.width：=4｝T→real ｛T.type：＝real;T.width：＝8}T→array[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}第二十五頁，共六十六頁，編輯于2023年，星期一7.3賦值語句的翻譯在本節中賦值語句中的表達式的類型可以是整型、實型、數組和記錄。作為翻譯賦值語句為三地址代碼的一部分,我們將主要討論:

簡單賦值語句的翻譯

第二十六頁，共六十六頁，編輯于2023年，星期一7.3.1簡單算術表達式及賦值語句的翻譯所討論的簡單賦值語句不包含對數組元素、記錄元素的引用，僅包含對簡單變量的算術表達式的引用。并且假定賦值語句中所有變量均為同一類型，不必考慮類型轉換的問題。簡單賦值語句的文法G[s]如下：S→id:=EE→E+T|TT→T*F|FF→(E)|id分析文法G[S]，可以看到文法中包含兩類不同語義操作的產生式，一類含有運算符操作，一類僅含有傳值操作。因此，要使語義分析后能產生三地址語句中間代碼，應該對這兩類不同的產生式進行不同的處理，含有運算符操作的產生式的語義動作應該產生相應的三地址語句，而僅含有傳值操作的產生式則只進行傳值的語義處理。根據這種思想，可以構造出各產生式的語義子程序如下表所示。第二十七頁，共六十六頁，編輯于2023年，星期一產生賦值語句三地址代碼的翻譯模式S→id:=E {p:=lookup(); ifp<>nilthenemit(p':='E.place)elseerror}E→E1+E2 {E.place=newtemp;

emit(E.place':='E1.place'+'E2.place')}E→E1*E2 {E.place=newtemp;

emit(E.place':='E1.place'*'E2.place')}E→-E {E.place:=newtemp; emit(E.place′:=′′uminus′E1.place}E→(E1) {E.place:=E1.place}E→id {p:=lookup(); ifp<>nilthenE.place:=pelseerror}有關說明：(1)語義變量E．place：表示存放E值的變量名在符號表的位置或一整數碼(若此變量是一個臨時變量)；

(2)語義變量id．name：表示單詞id的名字；

(3)語義過程newtemp:表示生成一個臨時變量,每調用一次,生成一新的臨時變量；

(4)語義過程lookup：表示檢查id．name是否出現在符號表中，若在則返回一指向該登記項的指針，否則返回nil：

(5)語義過程emit：表示產生三地址語句并輸出到文件上。第二十八頁，共六十六頁，編輯于2023年，星期一t1：＝-ct2：＝b*t1t3：＝-ct4：＝b*t3t5：＝t2+t4a：＝t5assigna+*bcuminus*uminuscba:=b*-c+b*-c產生賦值語句三地址代碼的翻譯模式S→id:=E{p:=lookup(); ifp<>nilthenemit(p':='E.place)elseerror}E→E1+E2{E.place=newtemp;

emit(E.place':='E1.place'+'E2.place')}E→E1*E2{E.place=newtemp;

emit(E.place':='E1.place'*'E2.place')}E→-E {E.place:=newtemp; emit(E.place′:=′′uminus′E1.place}E→(E1){E.place:=E1.place}E→id {p:=lookup(); ifp<>nilthenE.place:=pelseerror}第二十九頁，共六十六頁，編輯于2023年，星期一7.4布爾表達式的翻譯布爾表達式:

用布爾運算符號（and，or，not）作用到布爾變量或關系表達式上而組成。布爾表達式的作用：

1.用作計算邏輯值

2.用作控制流語句如if-then，if-then-else和while-do等之中的條件表達式第三十頁，共六十六頁，編輯于2023年，星期一◆一個布爾表達式的值的計算

方法一：用數值表示真和假，從而對布爾表達式的求值，可以象對算術表達式的求值那樣一步一步地來計算

方法二：優化的方法。AorB解釋成ifAthentrueelseBAandB解釋成ifAthenBelsefalsenotA解釋成ifAthenfalseelsetrue第三十一頁，共六十六頁，編輯于2023年，星期一7.4.1數值表示法的翻譯（用作計算邏輯值）用1表示真，0表示假來實現布爾表達式的翻譯例如，布爾表達式：aorbandnotc

翻譯成三地址代碼序列：

100：t1:=notc101：t2:=bandt1102：t3:=aort1oraandbcnot第三十二頁，共六十六頁，編輯于2023年，星期一關系表達式：a<b等價于ifa<bthen1else0翻譯成三地址代碼序列：

100：ifa＜bgotol03

101：t：=0102：gotol04

103:t:=1104：

第三十三頁，共六十六頁，編輯于2023年，星期一關于布爾表達式的數值表示法的翻譯模式E→E1orE2 ｛E.place:=newtemp; emit(E.place‘:=‘E1.place‘or’E2.place)}E→E1andE2 ｛E.place:=newtemp; emit(E.place':='E1.place'and’E2.place)}E→notE1 ｛E.place:=newtemp;emit(E.place':=''not'E1.place)}第三十四頁，共六十六頁，編輯于2023年，星期一E→id1relopid2注：relop是關系運算符

{E.place:=newtemp;emit('if'id1.placerelop.opid2.place'goto'nextstat+3);emit(E.place':=0');emit('goto'nextstat+2);emit(E.place':=‘'1')}E→ture ｛E.place:=newtemp;emit(E.place':=''1')}

E→false ｛E.place:=newtemp;emit(E.place':=''0')}

a<b的翻譯：

100：ifa＜bgotol03

101：t：=0102：gotol04

103:t:=1104：

第三十五頁，共六十六頁，編輯于2023年，星期一例：考慮如下語句：X=a<bandc<dore<fa<bEandC<dEor

e<fEEE100:ifa＜bgoto103101:t1=0102:goto104103:t1=1104:ifc＜dgoto107105:t2=0106:goto108107:t2=1109:ife＜fgoto112110:t4=0111:goto113112:t4=1X=S108：T3=t1andt2113：T5=t3ort4114：x:=t5第三十六頁，共六十六頁，編輯于2023年，星期一7.4.2作為條件控制語句的布爾表達式的翻譯(采用簡化的方法進行布爾表達式的計算)文法：ifEthenS1elseS2

E.codeS1.codeE.true:Gotos.nextE.false:toE.truetoE.false生成的代碼結構：S2.code……S.next:第三十七頁，共六十六頁，編輯于2023年，星期一控制語句中的條件表達式翻譯的基本思想給控制語句中的條件表達式設兩個屬性：E.true,和E.false，記錄控制語句所轉向的兩個語句的標號。對條件表達式的翻譯如下：E:a<b,生成如下的代碼Ifa<bgotoE.trueGotoE.falseE.codeS1.codeE.true:Gotos.nextE.false:toE.truetoE.falseS2.code……s.next:第三十八頁，共六十六頁，編輯于2023年，星期一控制語句中的條件表達式翻譯的基本思想假定E形如E1orE2。若E1為真，則立即可知E為真，于是E1.true與E.true是相同的。若El為false則必須對E2求值，因此我們置E1.false：為E2的代碼的第一條指令的標號。而E2的真、假出口可以分別與E的真、假出口相同。類似可考慮形如E1andE2的E的翻譯。至于形如notE1的布爾表達式E不必生成新的代碼，只要把E1的假、真出口作為E的真、假出口即可。按此方式可以寫出布爾表達式譯成三地址代碼的語義規則。注意E的true和false屬性均為繼承屬性。E:E1orE2E1.true=E.true,E1.false=E2的第一條代碼E2.true=E.true,E2.false=E.false第三十九頁，共六十六頁，編輯于2023年，星期一控制語句中的條件表達式翻譯的基本思想E:E1orE2E1.true=E.trueE1.false=E2的第一條代碼E2.true=E.trueE2.false=E.falseE1.codeS1.codeE.true:Gotos.nextE.false:toE.truetoE.falseS2.code……s.next:E2.codetoE.truetoE.false第四十頁，共六十六頁，編輯于2023年，星期一控制語句中的條件表達式翻譯的基本思想E:E1andE2E1.true=E2的第一條語句;E1.false=E.falseE2.true=E.true；E2.false=E.falseE1.codeS1.codeE.true:Gotos.nextE.false:toE.truetoE.falseS2.code……s.next:E2.codetoE.truetoE.false第四十一頁，共六十六頁，編輯于2023年，星期一產生式語義規則E→E1orE2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.falseE.code:=E1.code||gen(E1.false’:’)||E2.code第四十二頁，共六十六頁，編輯于2023年，星期一產生式語義規則E→E1andE2E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code‖gen(E1.true’:’)‖E2.codeE→notE1E1.true:=E.false;E1.false:=E.true;E.code:=E1.code第四十三頁，共六十六頁，編輯于2023年，星期一產生式語義規則E→id1relopid2E.code:=gen(‘if’id1.placerelop.opid2.place‘goto’E.true)||gen(‘goto’E.false)E→trueE.code:=gen(‘goto’E.true)E→falseE.code:=gen(‘goto’E.false)E的true和false屬性都是繼承屬性，E.code是綜合屬性。因此該語義規則的不能通過一遍掃描完成。E→(E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.code第四十四頁，共六十六頁，編輯于2023年，星期一例：考慮如下語句：

a<borc<dande<f假定整個表達式的真假出口分別置為Ltrue和Lfalse

a<bEorC<dEande<fEEEifa＜bgotoE.truegotoE.falseifc＜dgotoE.truegotoE.falseife<fgotoE.truegotoE.falseifc＜dgotoE.truegotoE.falseL2:ife<fgotoE.truegotoE.falseifa＜bgotoE.truegotoE.falseL1:ifc＜dgotoE.truegotoE.falseL2:ife<fgotoE.truegotoE.false第四十五頁，共六十六頁，編輯于2023年，星期一例：考慮如下語句：

a<borc<dande<f假定整個表達式的真假出口分別置為Ltrue和Lfalsea<bEorC<dEande<fEEEifc＜dgotoL2gotoLfalseL2:ife<fgotoLtruegotoLfalseifa＜bgotoLtruegotoL1L1:ifc＜dgotoL2gotoLfalseL2:ife<fgotoLtruegotoLfalseL1:L2:ifa＜bgotoE.truegotoE.falseifc＜dgotoE.truegotoE.falseife<fgotoE.truegotoE.false第四十六頁，共六十六頁，編輯于2023年，星期一例：考慮如下語句：a<bandc<dore<fa<bEandC<dEore<fEEEifa＜bgotoE.truegotoE.falseifc＜dgotoE.truegotoE.falseife<fgotoE.truegotoE.falseifa＜bgotoE.truegotoE.falseL1:ifc<dgotoE.truegotoE.falseifa＜bgotoE.truegotoE.falsel1:ifc＜dgotoE.truegotoE.falsel2:ife<fgotoE.truegotoE.falseL1:L2:第四十七頁，共六十六頁，編輯于2023年，星期一例：考慮如下語句：a<bandc<dore<fa<bEandC<dEore<fEEEifa＜bgotoE.truegotoE.falseL1:ifc＜dgotoE.truegotoE.falseL2:ife<fgotoE.truegotoE.falseL1:L2:ifa＜bgotoL1gotoE.falseL1:ifc＜dgotoE.truegotoL2L2:ife<fgotoE.truegotoE.false第四十八頁，共六十六頁，編輯于2023年，星期一

我們假設實現三地址代碼時采用四元式形式實現，并且假定：（jnz,a,-,p)表示ifagotop(jrop,x,y,p)表示ifxropygotop(j,-,-，p)表示gotop第四十九頁，共六十六頁，編輯于2023年，星期一控制語句中布爾表達式的翻譯模式一遍掃描的表達式翻譯中存在的問題：生成某些轉移語句時，轉移到的目標的標號是未知的解決方案：當目標語句的標號確定后，進行回填第五十頁，共六十六頁，編輯于2023年，星期一用四元式表示1:(j<,a,b,3)2:(j,-,-,6)3:(+,a,1,t1)4:(:=,t1,-,a)5:(j,-,-,8)6:(+,b,1,t2)7:(:=,t2,-,b)8：……例：ifa＜bthena:=a+1elseb:=b+1第五十一頁，共六十六頁，編輯于2023年，星期一7.5控制語句的翻譯任何程序都可有順序結構、選擇結構和while循環結構表示，這三類結構可用如下的文法描述：（1）S→ifEthenS

（2）|ifEthenSelseS

（3）|whileEdoS

（4）|beginLend

（5）|A

（6）L→L；S

（7）|SS表示語句 E為一個布爾表達式L表示語句塊A為賦值語句 第五十二頁，共六十六頁，編輯于2023年，星期一控制流語句的翻譯模式：SifEthenS1

的四元式序列

1.(j,E,-,3)2.(j,-,-,q)3.……q.……S1的四元式序列第五十三頁，共六十六頁，編輯于2023年，星期一2.SifEthen

S1elseS2的四元式序列

1.(j,E,-,3)2.(j,-,-,p+1)3.……p.(j,-,-,q)p+1.……q.……

S1的四元式序列S2的四元式序列第五十四頁，共六十六頁，編輯于2023年，星期一3.SwhileEdoS1的四元式序列

1.(j,E,-,3)2.(j,-,-,p+1)3.……p.(j,-,-,1)p+1.……

S1的四元式序列第五十五頁，共六十六頁，編輯于2023年，星期一（4）SbeginLend

（5）SA

（6）L→L；S

（7）SS1語句塊L的四元式序列賦值語句A的四元式序列語句塊L的四元式序列語句S的四元式序列語句S1的四元式序列第五十六頁，共六十六頁，編輯于2023年，星期一翻譯為四元式例：將語句ifa＜borc＜dande＜fthens1elses21(j<,a,b,?)2(j,-,-,?)3(j<,c,d,?)4(j,-,-

?)5(j<,e,f,?)6(j,-,-,?)7S1的四元式序列

……p(j,-,-,?)p+1S2的四元式序列

……q……1(j<,a,b,7)2(j,-,-,3)3(j<,c,d,5)4(j,-,-

p+1)5(j<,e,f,7)6(j,-,-,p+1)7S1的四元式序列

……p(j,-,-,q)第五十七頁，共六十六頁，編輯于2023年，星期一例：考慮如下語句：

whilea＜bdoifc＜dthenx：=y＋z100(j<,a,b,?)101(j<,--,--,?)106(j,--,--,100)104(+,y,z,T)105(:=,T,--,x)102(j<,c,d,?)103(j<,--,--,?)102(j<,c,d,104)103(j<,--,--,?