第四章 語(yǔ)義分析及中間代碼生成

第四章

語(yǔ)義分析和中間代碼的表示語(yǔ)義分析的概念語(yǔ)法制導(dǎo)翻譯方法屬性文法幾種常見的中間代碼表示簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯if語(yǔ)句的翻譯4.1概述4.1.1語(yǔ)義分析的概念語(yǔ)義分析：即審查每個(gè)語(yǔ)法成分的靜態(tài)語(yǔ)義。在早期的一些編譯程序中，是在語(yǔ)法分析的基礎(chǔ)上根據(jù)源程序中各語(yǔ)法成份的語(yǔ)義，直接產(chǎn)生機(jī)器語(yǔ)言或匯編語(yǔ)言形式的目標(biāo)代碼?，F(xiàn)在的編譯系統(tǒng)一般都將經(jīng)過語(yǔ)法分析的源程序先翻譯為某種形式的中間語(yǔ)言代碼，然后再將其翻譯為目標(biāo)代碼。優(yōu)點(diǎn)：使編譯程序各組成部分功能更單一;使得編譯程序的邏輯結(jié)構(gòu)更為清晰，從而使編譯程序更易于編寫與調(diào)整;同時(shí)為代碼優(yōu)化和程序的可移植性提供了條件。

回顧：語(yǔ)義處理在編譯程序中的邏輯位置詞法分析語(yǔ)法分析中間代碼生成中間代碼優(yōu)化（可選）目標(biāo)代碼優(yōu)化（可選）目標(biāo)代碼生成靜態(tài)語(yǔ)義分析語(yǔ)義處理

兩項(xiàng)工作：靜態(tài)語(yǔ)義分析，中間代碼生成

靜態(tài)語(yǔ)義分析：主要工作如類型檢查、名字的作用域分析、控制流檢查、一致性檢查等。中間代碼生成：從語(yǔ)法分析的結(jié)果生成中間代碼（個(gè)別編譯程序可能直接生成目標(biāo)代碼）。跨分析和綜合兩個(gè)階段分析階段：理解源程序，挖掘源程序的語(yǔ)義綜合階段：生成與源程序語(yǔ)義上等價(jià)的目標(biāo)程序跨編譯程序的前端和后端語(yǔ)法制導(dǎo)的語(yǔ)義處理

編譯程序的設(shè)計(jì)中，語(yǔ)義分析和中間（目標(biāo)）代碼生成的實(shí)現(xiàn)采用語(yǔ)法制導(dǎo)翻譯的方法。

程序設(shè)計(jì)語(yǔ)言的語(yǔ)義描述常采用屬性文法。語(yǔ)義處理涉及到的基本技術(shù)4.1.2語(yǔ)法制導(dǎo)翻譯方法對(duì)文法中的每個(gè)產(chǎn)生式都附加一個(gè)語(yǔ)義動(dòng)作或語(yǔ)義子程序,在語(yǔ)法分析過程中，每當(dāng)需要使用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約，語(yǔ)法分析程序除執(zhí)行相應(yīng)的語(yǔ)法分析動(dòng)作外，還要執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作或調(diào)用相應(yīng)的語(yǔ)義子程序。這種模式實(shí)際上是對(duì)上下文無關(guān)文法的一種擴(kuò)充。例如,文法G[E]:

產(chǎn)生式

語(yǔ)義動(dòng)作E→E(1)+T{E.Val=E(1).val+T.val;}E→T {E.Val=T.Val;}T→i {T.Val=i;}為了能在語(yǔ)法分析過程中平行地進(jìn)行語(yǔ)義處理，可在語(yǔ)法分析棧旁邊并行地設(shè)置一個(gè)語(yǔ)義信息棧。

語(yǔ)法分析棧語(yǔ)義分析棧TT.Val+‘+’E……#

產(chǎn)生式的語(yǔ)義是由組成該產(chǎn)生式的文法符號(hào)的語(yǔ)義所決定的。

可將文法符號(hào)的語(yǔ)義以“屬性”的形式附加到各個(gè)文法符號(hào)上，再根據(jù)產(chǎn)生式所蘊(yùn)含的語(yǔ)義，給出每個(gè)文法符號(hào)的屬性的求值規(guī)則，從而形成一種附帶有語(yǔ)義屬性的前后文無關(guān)文法，即屬性文法。4.2屬性文法

屬性文法=上下文無關(guān)文法+屬性+求值規(guī)則

屬性用來描述文法符號(hào)的語(yǔ)義特征，如常量的“值”、變量的類型和存儲(chǔ)位置等。求值規(guī)則（屬性計(jì)算規(guī)則）與產(chǎn)生式相關(guān)聯(lián)的反映文法符號(hào)屬性之間關(guān)系的“規(guī)則”。求值規(guī)則還可進(jìn)一步擴(kuò)展為語(yǔ)義規(guī)則（語(yǔ)義動(dòng)作）。1、定義【例】簡(jiǎn)單表達(dá)式的屬性文法。語(yǔ)義規(guī)則S→EE→E（1）+TE→T

T→T（1）*FT→FF→(E)F→iprint(E.val)

E.val=E（1）.val+T.val

E.val=T.val

T.val=T（1）.valF.val

T.val=F.valF.val=E.valF.val=i.lexval產(chǎn)生式詞法分析的結(jié)果若產(chǎn)生式AX1X2…Xn，與之相關(guān)的屬性計(jì)算規(guī)則 b=f(c1,c2,…)，其中f

是函數(shù)，b和c1,c2,…,ck

是該產(chǎn)生式文法符號(hào)的屬性，－如果屬性b是產(chǎn)生式左部符號(hào)A的屬性，c1,c2,…,ck

是產(chǎn)生式右部文法符號(hào)的屬性或A的其它屬性,則稱其為A的綜合屬性；－如果屬性b是產(chǎn)生式右部符號(hào)Xi的屬性，

c1,c2,…,ck

是產(chǎn)生式右部文法符號(hào)的屬性或A的屬性則稱其為Xi的繼承屬性；－終結(jié)符僅有綜合屬性,如i.lex_val。通常由詞法程序提供。而開始符號(hào)沒有繼承屬性。2、屬性的分類繼承屬性用于“自上而下”傳遞信息。繼承屬性由相應(yīng)語(yǔ)法樹中結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)屬性計(jì)算得到，它反映了對(duì)上下文依賴的特性。繼承屬性可以很方便地用來表示程序設(shè)計(jì)語(yǔ)言上下文的結(jié)構(gòu)關(guān)系。幾點(diǎn)說明：幾點(diǎn)說明（續(xù)）：綜合屬性用于“自下而上”傳遞信息。綜合屬性由相應(yīng)語(yǔ)法樹中結(jié)點(diǎn)的分枝結(jié)點(diǎn)屬性計(jì)算得到，即沿語(yǔ)法樹向上傳遞，從分枝（子）結(jié)點(diǎn)到根結(jié)點(diǎn)。思考：簡(jiǎn)單表達(dá)式文法中的屬性各是什么類型的？A.bX1.c1X2.c2X…綜合屬性A.b的計(jì)算AX1.c1X2.c2…繼承屬性Xk.b的計(jì)算Xk.bX屬性的計(jì)算次序用圖表示如下：注釋分析樹在語(yǔ)法樹中,將每個(gè)結(jié)點(diǎn)均視為由若干個(gè)域組成的結(jié)構(gòu),則可將其中的一些域用來存放相應(yīng)文法符號(hào)諸屬性之值，并可用屬性來為這些域命名。通常我們將每個(gè)結(jié)點(diǎn)都標(biāo)注相應(yīng)屬性值的語(yǔ)法樹稱為注釋分析樹（DecoratedSyntaxTree）?！纠拷o出表達(dá)式3＊(5+4)

的屬性計(jì)算過程。

（綜合屬性的例子）語(yǔ)義規(guī)則S→EE→E（1）+TE→T

T→T（1）*FT→FF→(E)F→iprint(E.val)

E.val=E（1）.val+T.val

E.val=T.val

T.val=T（1）.valF.val

T.val=F.valF.val=E.valF.val=i.lexval產(chǎn)生式

綜合屬性代表自下而上傳遞的信息對(duì)表達(dá)式3＊(5+4)

的分析樹進(jìn)行自下而上（后序）遍歷，并執(zhí)行相應(yīng)的語(yǔ)義規(guī)則，得到該表達(dá)式的一種求值過程TETEFTi＋()iSEFFTiFi.lexval=5i.lexval=3i.lexval=4F.val=5F.val=3T.val=3T.val=5E.val=5F.val=4T.val=4E.val=9F.val=9T.val=27E.val=27print(27)S→EE→E（1）+TE→TT→T（1）*FT→FF→(E)F→i【例】語(yǔ)句intx,y,z的語(yǔ)義分析。（繼承屬性）產(chǎn)生式

語(yǔ)

義

規(guī)

則

D

TL

L.in=T.type

T

int

T.type=integer

T

float

T.type=float

L

L1,

id

L1.in=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

繼承屬性代表自上而下傳遞的信息對(duì)聲明語(yǔ)句intx,y,z的分析樹進(jìn)行遍歷，自下而上執(zhí)行綜合屬性相應(yīng)的語(yǔ)義規(guī)則，自上而下執(zhí)行繼承屬性相應(yīng)的語(yǔ)義規(guī)則，可以得到所有屬性值的一個(gè)求值過程T,LDLidintT.type=integerL.in=integer,idL.in=integeridLL.in=integeraddtype(id.entry,integer)addtype(id.entry,integer)addtype(id.entry,integer)思考：如何通過對(duì)注釋分析樹進(jìn)行樹遍歷的方法計(jì)算屬性值？最常用的方法是深度優(yōu)先、從左到右的遍歷。小結(jié)：基于屬性文法的語(yǔ)義處理基于屬性文法的語(yǔ)義處理即為語(yǔ)法制導(dǎo)翻譯（Syntax-DirectedTranslation）處理方法分兩類：

樹遍歷方法

通過遍歷分析樹進(jìn)行屬性計(jì)算

單遍的方法（On-the-fly方法）語(yǔ)法分析遍的同時(shí)進(jìn)行屬性計(jì)算

基于樹遍歷方法的語(yǔ)義處理

步驟

構(gòu)造輸入串的語(yǔ)法分析樹。

構(gòu)造依賴圖（Dependencygraph）。

若該依賴圖是無圈的，則按造此無圈圖的一種拓?fù)渑判颍═opologicalsort）對(duì)分析樹進(jìn)行遍歷，則可以計(jì)算所有的屬性。4.3幾種常見的中間語(yǔ)言

（中間代碼形式）抽象語(yǔ)法樹逆波蘭式三地址代碼（四元式、三元式、間接三元式）語(yǔ)法樹是分析樹的濃縮表示：算符和關(guān)鍵字作為內(nèi)部結(jié)點(diǎn)。

語(yǔ)法制導(dǎo)翻譯可以基于分析樹，也可以基于語(yǔ)法樹。在抽象語(yǔ)法樹表示中，每一個(gè)葉結(jié)點(diǎn)都表示諸如常量或變量這樣的運(yùn)算對(duì)象（本質(zhì)部分），而其他內(nèi)部結(jié)點(diǎn)則表示運(yùn)算符和關(guān)鍵字等（非本質(zhì)部分）。1、抽象語(yǔ)法樹語(yǔ)法樹的例子：if-then-elseES1S2+*2582、逆波蘭表示波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出的一種表示表達(dá)式的方法。按此方法，每一運(yùn)算符都置于其運(yùn)算對(duì)象之后，故稱為后綴表示。表達(dá)式E的后綴表示遞歸定義如下：（1）如果E是變量或常數(shù)，則E的后綴表示即E自身。（2）如果E為E1opE2形式，則它的后綴表示為E1’E2’op；其中E1’、E2’分別是E1和E2的后綴表示。若op是一元運(yùn)算符，則視E1和E1’為空。（3）如果E為(E1)形式，則E1的后綴表示即為E的后綴表示。特點(diǎn):操作數(shù)出現(xiàn)的順序與原來一致，而運(yùn)算符則按運(yùn)算先后的順序放到相應(yīng)的操作數(shù)之后，即運(yùn)算符先后的順序發(fā)生了變化，表達(dá)式中各個(gè)運(yùn)算是按運(yùn)算符出現(xiàn)的順序進(jìn)行的，故無須使用括號(hào)來指示運(yùn)算順序?！纠?/p>

中綴表示 后綴表示

A+B AB+ A+B*C ABC*+ (A+B)*(C+D) AB+CD+* x/y^z-d*e xyz^/de*-

程序語(yǔ)句的逆波蘭表示見課本P116。3、三地址代碼（四元式）四元式是一種更接近目標(biāo)代碼的中間代碼形式，由于這種形式的中間代碼便于優(yōu)化處理，因此，在目前的許多編譯程序中得到了廣泛的應(yīng)用。四元式是一種“三地址語(yǔ)句”（注：三地址語(yǔ)句的種類見課本P98）的等價(jià)表示。它的一般形式為：(op,arg1,arg2,result)其中，op為一個(gè)二元(也可是一元或零元)運(yùn)算符;arg1,arg2分別為它的兩個(gè)運(yùn)算對(duì)象，它們可以是變量、常數(shù)或系統(tǒng)定義的臨時(shí)變量名；運(yùn)算的結(jié)果將放入result中。四元式還可寫為類似于PASCAL語(yǔ)言的賦值語(yǔ)句的形式：result=arg1

op

arg2

種類：x=yopz雙目運(yùn)算(op,y,z,x)x=opy 單目運(yùn)算(op,y,_,x)x=y 賦值語(yǔ)句(=,y,_,x)x=-y(uminus,y,_,x)ifxrelopygotol條件轉(zhuǎn)移語(yǔ)句 (jrop,x,y,l)

gotol無條件轉(zhuǎn)移(j,_,_,l)每個(gè)四元式只能有一個(gè)運(yùn)算符，所以，一個(gè)復(fù)雜的表達(dá)式只能由多個(gè)四元式構(gòu)成的序列表示。例如，表達(dá)式a+b*c可寫為序列 （*,b,c,t1） （+,a,t1,t2）當(dāng)op為一元、零元運(yùn)算（如無條件轉(zhuǎn)移）時(shí)，arg2甚至arg1應(yīng)缺省，即result=op

arg1或op

result；對(duì)應(yīng)的一般形式為： (op,arg1,-,result)或 (op,-,-,result)。說明：【例】賦值語(yǔ)句a=b*(c+d)相應(yīng)的四元式代碼為：(1)(+,c,d,t1)(2)(*,b,t1,t2)(3)(=,t2,_,a)

除前面所述的抽象語(yǔ)法樹、逆波蘭式、四元式外，常見的中間語(yǔ)言還有接近PASCAL形式的P-代碼，接近C格式的C-代碼等等。4、其它表示法4.4簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯相關(guān)的語(yǔ)義處理說明對(duì)非終結(jié)符E定義語(yǔ)義變量E.place，即用E.place表示存放E值的變量名在符號(hào)表中的入口地址或臨時(shí)變量名的整數(shù)碼。定義語(yǔ)義函數(shù)newtemp()，即每次調(diào)用newtemp()時(shí)都回送一個(gè)代表新臨時(shí)變量的整數(shù)碼；臨時(shí)變量名按產(chǎn)生的順序可設(shè)為T1、T2…定義語(yǔ)義函數(shù)emit(op,arg1,arg2,result)，emit的功能是產(chǎn)生一個(gè)四元式。定義語(yǔ)義函數(shù)lookup()，其功能是查找是否出現(xiàn)在符號(hào)表中，是則返回在符號(hào)表中的入口指針，否則返回null。(1)S→i=E {p=lookup(); if(p==null)thenerror();elseemit(=,E.place,_,p);}

(2)E→E1+E2{E.place=newtemp(); emit(+,E1.place,E2.place,E.place);}

(3)E→E1*E2{E.place=newtemp(); emit(*,E1.place,E2.place,E.place);}寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義處理過程(4)E→-E1{E.place=newtemp();emit(uminus,E1.place,_,E.place);}(5)E→(E1){E.place=E1.place;}

(6)E→i{p=lookup(); if(p!=null)thenE.place=p; elseerror();}

表達(dá)式翻譯中的其它問題臨時(shí)變量空間的統(tǒng)計(jì)了解需求、及時(shí)釋放運(yùn)算合法性檢查利用符號(hào)表保存的名字類型類型自動(dòng)轉(zhuǎn)換添加專用指令兩種方法：1）類似于算術(shù)表達(dá)式計(jì)算布爾表達(dá)式的值，用“1”表示“真”，用“0”表示“假”。2）“短路”計(jì)算的方法，用表達(dá)式的真、假出口表示運(yùn)算后轉(zhuǎn)移的地址。真假出口表示法給出兩個(gè)表示語(yǔ)義的屬性：E.tc，E為真時(shí)控制到達(dá)的位置；E.fc，E為假時(shí)控制到達(dá)的位置。思考：布爾表達(dá)式如何翻譯？則有示例如下：a<bifa<bgotoE.tc（j<,a,b,E.tc）gotoE.fc（j,_,_,E.fc）E→E1

∨E2如果E1為真，則立即可知E為真，即E1.tc與E.tc相同；如果E1為假，則必須計(jì)算E2的值，令E1.false為E2的開始位置；E2的真假出口分別與E的真假出口相同(1)E→i {E.tc=nxq;E.fc=nxq+1; emit(jnz,entry(i),_,0);emit(j,_,_,0);}(2)E→i1ropi2{E.tc=nxq;E.fc=nxq+1; emit(jrop,entry(i1),entry(i2),0);emit(j,_,_,0);}

寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義處理過程真出口，有待回填假出口，有待回填(3)E→(E1){E.tc=E1.tc;E.fc=E1.fc;}(4)E→┐E1{E.tc=E1.fc;E.fc=E1.tc;}(5)EA→E1{Backpatch(E1.tc,nxq);EA.fc=E1.fc}(6)E→EAE2{E.tc=E2.tc;E.fc=merge(EA.fc,E2.fc);}(7)EB→E1{Backpatch(E1.fc,nxq);EB.tc=E1.tc}(8)E→EBE2{E.fc=E2.fc;E.tc=merge(EB.tc,E2.tc);}什么是“回填”？（1）先產(chǎn)生暫時(shí)沒有填寫目標(biāo)標(biāo)號(hào)的四元式。（2）對(duì)于每一條這樣的四元式作適當(dāng)?shù)挠涗?，即可用“拉鏈”的方法將這些四元式鏈接起來。

（實(shí)現(xiàn)見課本P104merge(p1,p2)函數(shù)）（3）一旦目標(biāo)標(biāo)號(hào)（即將要轉(zhuǎn)移的目標(biāo)四元式的地址）被確定下來，再將它“回填”到相應(yīng)的指令（四元式的第四個(gè)區(qū)段）中。

（實(shí)現(xiàn)見課本P104Backpatch(p,t)函數(shù)）4.5if語(yǔ)句的翻譯條件語(yǔ)句的模式

if(E)S1;elseS2條件語(yǔ)句的代碼結(jié)構(gòu)

E的代碼

E.tc

S1的代碼

gotooutS2的代碼out:E.fcE.tcE.fc相關(guān)語(yǔ)義處理說明對(duì)非終結(jié)符E定義語(yǔ)義變量E.tc和E.fc，分別表示“真”、“假”兩個(gè)出口。定義語(yǔ)義變量nxq，始終指向下一條將要產(chǎn)生的四元式的地址（此處用序號(hào)表示），其初值為1。每執(zhí)行一次emit語(yǔ)句后，nxq自動(dòng)加1。所有的出口地址采用“拉鏈”、“回填”的方式確定。相應(yīng)的定義如下兩個(gè)語(yǔ)義函數(shù):merge(p1,p2):把以p1和p2為鏈?zhǔn)椎膬蓷l鏈合并為一條以p2為鏈?zhǔn)椎逆?。Backpatch(p,t):把鏈?zhǔn)譸所鏈接的每個(gè)四元式的第四個(gè)區(qū)段都改寫為地址t。（具體實(shí)現(xiàn)見課本P104）一種翻譯方法：為了及時(shí)回填地址，將條件語(yǔ)句的文法修改為如下形式:G′[S]:(1)S→CS1(2)C→if(E)(3)S→TPS2(4)TP→CS1;else

對(duì)應(yīng)的語(yǔ)義規(guī)則C→if(E){Backpatch(E.tc,nxq);C.chain=E.fc;}S→CS1{S.chain=merge(C.chain,S1.chain);}Tp→CS1;

else{q=nxq;emit(j,_,_,0);Backpatch(C.chain,nxq);Tp.chain=merge(S1.chain,q);}S→TpS2{S.chain=merge(Tp.chain,S2.chain);}生成的四元式序列[例]將下面語(yǔ)句翻譯成四元式：ifc<5z=x+1

elsex=y102105107100：（j<,c,5,?）101：（j,-,-,?）102：（+,x,1,t1）103：（=,t1,-,z）104：（j,-,-,?）105：（=,y,-,t2）107:106：（=,t2,-,z）控制流語(yǔ)句的自底向上翻譯_另一種實(shí)現(xiàn)方法SifEthenMS1 |ifEthenM1S1

NelseM2S2 |whileM1EdoM2S1 |S1;MS2

Mε{M.q=nxq}Nε{N.chain=makechain(nxq);emit(j,_,_,0)}if-then語(yǔ)句的自底向上翻譯SifEthenMS1{backpatch(E.tc,M.q)S.chain=merge(E.fc,S(1).chain)}E的代碼S⑴的代碼ifE.tcE.fcS.chainS⑴

.chainthenM.qif-then-else語(yǔ)句

的自底向上翻譯SifEthenM1S1

NelseM2S2{backpatch