語義分析和中間代碼生成

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

第4頁,共66頁，2024年2月25日，星期天7.1.1后綴式

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

和E2’分別為E1和E2的后綴式。（3）如果E是(E1)形式的表達式，則E1的后綴式就是E的后綴式。第5頁,共66頁，2024年2月25日，星期天后綴式的優(yōu)點

便于計算機處理，因為在后綴式中，表達式的求值順序與運算符出現(xiàn)的順序一致，這樣只要用一個棧就可以實現(xiàn)表達式的求值。實現(xiàn)過程：自左向右掃描后綴表達式；遇到運算對象入棧，遇到N元運算符，就從棧頂取出N個運算對象進行計算，再將結果入棧；當全部后綴表達式掃描結束，則棧頂?shù)闹导礊楸磉_式結果。第6頁,共66頁，2024年2月25日，星期天后綴式特點：無括號運算對象的順序與中綴式一致根據(jù)操作符（運算符）的優(yōu)先級和結合性進行相關的處理例：5+4*6546*+第7頁,共66頁，2024年2月25日，星期天7.1.2圖表示法圖表示法包括DAG與AST(抽象語法樹)。有向無環(huán)圖（DirectedAcyclicGraph,簡稱DAG).與抽象語法樹一樣，對于表達式中的每個子表達式，DAG圖中都有一個結點。一個內部結點代表一個操作符，它的孩子代表操作數(shù)。兩者不同的是，在DAG圖中代表公共子表達式的結點具有多個父結點，而在一棵抽象語法樹中公共子表達式被表示為重復的子樹。例：第8頁,共66頁，2024年2月25日，星期天5+4*6的DAG圖5+64*5+4*6+4*6的DAG圖5+64*+5+4*6+4*6的AST圖5+64*+64*第9頁,共66頁，2024年2月25日，星期天后綴式與抽象語法樹的關系后綴式是抽象語法樹的線性表示：每個結點都是在它的所有子節(jié)點之后立即出現(xiàn)的。通過對抽象語法樹的不同形式的遍歷可以形成不同形式的綴式表達式前序遍歷：前綴式中序遍歷：中綴式后序遍歷：后綴式5+64*+64*第10頁,共66頁，2024年2月25日，星期天產(chǎn)生賦值語句抽象語法樹的屬性文法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產(chǎn)生式語義規(guī)則第11頁,共66頁，2024年2月25日，星期天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+:=第12頁,共66頁，2024年2月25日，星期天抽象語法樹的存儲表示二叉樹的形式：算術運算通常都是二元運算樹中每個節(jié)點包含三個域：數(shù)組的形式表示：每一個數(shù)組元素形式如下：節(jié)點類型|操作數(shù)1|操作數(shù)2節(jié)點類型|操作數(shù)1|操作數(shù)2第13頁,共66頁，2024年2月25日，星期天*

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

...

第14頁,共66頁，2024年2月25日，星期天7.1.3三地址代碼三地址代碼是由下面一般形式的語句構成的序列:X:=yopz

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

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

a:=b*-c+b*-c第17頁,共66頁，2024年2月25日，星期天三地址代碼的具體表示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)第18頁,共66頁，2024年2月25日，星期天三地址代碼的具體表示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)第19頁,共66頁，2024年2月25日，星期天三地址代碼的具體表示3.間接三元式:間接碼表+三元式表目的：便于優(yōu)化處理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)第20頁,共66頁，2024年2月25日，星期天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)第21頁,共66頁，2024年2月25日，星期天語義分析中各種語句的處理說明語句的翻譯賦值語句的翻譯布爾表達式的翻譯控制語句的翻譯第22頁,共66頁，2024年2月25日，星期天7.2說明語句的翻譯說明語句的處理方式：不生成可執(zhí)行代碼，只涉及符號表的操作。說明語句的處理:對每個局部名字，在符號表中建立相應的表項，填寫有關的信息如類型、嵌套深度、相對地址等。相對地址：相對靜態(tài)數(shù)據(jù)區(qū)基址或活動記錄中局部數(shù)據(jù)區(qū)基址的一個偏移值。第23頁,共66頁，2024年2月25日，星期天因為每進入一次過程需分配一次內存，因此在處理過程內的說明語句時，要分配每個標識符的相對地址。設變量offset用來記錄相對地址，每次進入一個過程，先將offset置為0。每次遇到一個新名字，則把名字同offset的當前值一起錄入符號表，然后offset的值增加，其增加的值由該名字的數(shù)據(jù)類型所決定，稱為數(shù)據(jù)對象的寬度，用屬性width表示。假設integer型對象寬度為4，real型對象寬度為8，則下表為過程中說明語句的翻譯方案。第24頁,共66頁，2024年2月25日，星期天過程中的說明語句的翻譯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}第25頁,共66頁，2024年2月25日，星期天7.3賦值語句的翻譯在本節(jié)中賦值語句中的表達式的類型可以是整型、實型、數(shù)組和記錄。作為翻譯賦值語句為三地址代碼的一部分,我們將主要討論:

簡單賦值語句的翻譯

第26頁,共66頁，2024年2月25日，星期天7.3.1簡單算術表達式及賦值語句的翻譯所討論的簡單賦值語句不包含對數(shù)組元素、記錄元素的引用，僅包含對簡單變量的算術表達式的引用。并且假定賦值語句中所有變量均為同一類型，不必考慮類型轉換的問題。簡單賦值語句的文法G[s]如下：S→id:=EE→E+T|TT→T*F|FF→(E)|id分析文法G[S]，可以看到文法中包含兩類不同語義操作的產(chǎn)生式，一類含有運算符操作，一類僅含有傳值操作。因此，要使語義分析后能產(chǎn)生三地址語句中間代碼，應該對這兩類不同的產(chǎn)生式進行不同的處理，含有運算符操作的產(chǎn)生式的語義動作應該產(chǎn)生相應的三地址語句，而僅含有傳值操作的產(chǎn)生式則只進行傳值的語義處理。根據(jù)這種思想，可以構造出各產(chǎn)生式的語義子程序如下表所示。第27頁,共66頁，2024年2月25日，星期天產(chǎn)生賦值語句三地址代碼的翻譯模式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值的變量名在符號表的位置或一整數(shù)碼(若此變量是一個臨時變量)；

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

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

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

(5)語義過程emit：表示產(chǎn)生三地址語句并輸出到文件上。第28頁,共66頁，2024年2月25日，星期天t1：＝-ct2：＝b*t1t3：＝-ct4：＝b*t3t5：＝t2+t4a：＝t5assigna+*bcuminus*uminuscba:=b*-c+b*-c產(chǎn)生賦值語句三地址代碼的翻譯模式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}第29頁,共66頁，2024年2月25日，星期天7.4布爾表達式的翻譯布爾表達式:

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

1.用作計算邏輯值

2.用作控制流語句如if-then，if-then-else和while-do等之中的條件表達式第30頁,共66頁，2024年2月25日，星期天◆一個布爾表達式的值的計算

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

方法二：優(yōu)化的方法。AorB解釋成ifAthentrueelseBAandB解釋成ifAthenBelsefalsenotA解釋成ifAthenfalseelsetrue第31頁,共66頁，2024年2月25日，星期天7.4.1數(shù)值表示法的翻譯（用作計算邏輯值）用1表示真，0表示假來實現(xiàn)布爾表達式的翻譯例如，布爾表達式：aorbandnotc

翻譯成三地址代碼序列：

100：t1:=notc101：t2:=bandt1102：t3:=aort1oraandbcnot第32頁,共66頁，2024年2月25日，星期天關系表達式：a<b等價于ifa<bthen1else0翻譯成三地址代碼序列：

100：ifa＜bgotol03

101：t：=0102：gotol04

103:t:=1104：

第33頁,共66頁，2024年2月25日，星期天關于布爾表達式的數(shù)值表示法的翻譯模式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)}第34頁,共66頁，2024年2月25日，星期天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：

第35頁,共66頁，2024年2月25日，星期天例：考慮如下語句：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第36頁,共66頁，2024年2月25日，星期天7.4.2作為條件控制語句的布爾表達式的翻譯(采用簡化的方法進行布爾表達式的計算)文法：ifEthenS1elseS2

E.codeS1.codeE.true:Gotos.nextE.false:toE.truetoE.false生成的代碼結構：S2.code……S.next:第37頁,共66頁，2024年2月25日，星期天控制語句中的條件表達式翻譯的基本思想給控制語句中的條件表達式設兩個屬性：E.true,和E.false，記錄控制語句所轉向的兩個語句的標號。對條件表達式的翻譯如下：E:a<b,生成如下的代碼Ifa<bgotoE.trueGotoE.falseE.codeS1.codeE.true:Gotos.nextE.false:toE.truetoE.falseS2.code……s.next:第38頁,共66頁，2024年2月25日，星期天控制語句中的條件表達式翻譯的基本思想假定E形如E1orE2。若E1為真，則立即可知E為真，于是E1.true與E.true是相同的。若El為false則必須對E2求值，因此我們置E1.false：為E2的代碼的第一條指令的標號。而E2的真、假出口可以分別與E的真、假出口相同。類似可考慮形如E1andE2的E的翻譯。至于形如notE1的布爾表達式E不必生成新的代碼，只要把E1的假、真出口作為E的真、假出口即可。按此方式可以寫出布爾表達式譯成三地址代碼的語義規(guī)則。注意E的true和false屬性均為繼承屬性。E:E1orE2E1.true=E.true,E1.false=E2的第一條代碼E2.true=E.true,E2.false=E.false第39頁,共66頁，2024年2月25日，星期天控制語句中的條件表達式翻譯的基本思想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第40頁,共66頁，2024年2月25日，星期天控制語句中的條件表達式翻譯的基本思想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第41頁,共66頁，2024年2月25日，星期天產(chǎn)生式語義規(guī)則E→E1orE2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.falseE.code:=E1.code||gen(E1.false’:’)||E2.code第42頁,共66頁，2024年2月25日，星期天產(chǎn)生式語義規(guī)則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第43頁,共66頁，2024年2月25日，星期天產(chǎn)生式語義規(guī)則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是綜合屬性。因此該語義規(guī)則的不能通過一遍掃描完成。E→(E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.code第44頁,共66頁，2024年2月25日，星期天例：考慮如下語句：

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第45頁,共66頁，2024年2月25日，星期天例：考慮如下語句：

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第46頁,共66頁，2024年2月25日，星期天例：考慮如下語句：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:第47頁,共66頁，2024年2月25日，星期天例：考慮如下語句：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第48頁,共66頁，2024年2月25日，星期天

我們假設實現(xiàn)三地址代碼時采用四元式形式實現(xiàn)，并且假定：（jnz,a,-,p)表示ifagotop(jrop,x,y,p)表示ifxropygotop(j,-,-，p)表示gotop第49頁,共66頁，2024年2月25日，星期天控制語句中布爾表達式的翻譯模式一遍掃描的表達式翻譯中存在的問題：生成某些轉移語句時，轉移到的目標的標號是未知的解決方案：當目標語句的標號確定后，進行回填第50頁,共66頁，2024年2月25日，星期天用四元式表示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第51頁,共66頁，2024年2月25日，星期天7.5控制語句的翻譯任何程序都可有順序結構、選擇結構和while循環(huán)結構表示，這三類結構可用如下的文法描述：（1）S→ifEthenS

（2）|ifEthenSelseS

（3）|whileEdoS

（4）|beginLend

（5）|A

（6）L→L；S

（7）|SS表示語句 E為一個布爾表達式L表示語句塊A為賦值語句 第52頁,共66頁，2024年2月25日，星期天控制流語句的翻譯模式：SifEthenS1

的四元式序列

1.(j,E,-,3)2.(j,-,-,q)3.

……q.……S1的四元式序列第53頁,共66頁，2024年2月25日，星期天2.SifEthen

S1elseS2的四元式序列

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

S1的四元式序列S2的四元式序列第54頁,共66頁，2024年2月25日，星期天3.S

whileEdoS1的四元式序列

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

S1的四元式序列第55頁,共66頁，2024年2月25日，星期天（4）S

beginLend

（5）S

A

（6）L→L；S

（7）S

S1語句塊L的四元式序列賦值語句A的四元式序列語句塊L的四元式序列語句S的四元式序列語句S1的四元式序列第56頁,共66頁，2024年2月25日，星期天翻譯為四元式例：將語句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)第57頁,共66頁，2024年2月25日，星期天例：考慮如下語句：

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<,--,--,?)102(j<,c,d,104)103(j<,--,