第四章

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

回顧：語義處理在編譯程序中的邏輯位置詞法分析語法分析中間代碼生成中間代碼優化（可選）目標代碼優化（可選）目標代碼生成靜態語義分析語義處理

兩項工作：靜態語義分析，中間代碼生成

靜態語義分析：主要工作如類型檢查、名字的作用域分析、控制流檢查、一致性檢查等。中間代碼生成：從語法分析的結果生成中間代碼（個別編譯程序可能直接生成目標代碼）?？绶治龊途C合兩個階段分析階段：理解源程序，挖掘源程序的語義綜合階段：生成與源程序語義上等價的目標程序跨編譯程序的前端和后端語法制導的語義處理

編譯程序的設計中，語義分析和中間（目標）代碼生成的實現采用語法制導翻譯的方法。

程序設計語言的語義描述常采用屬性文法。語義處理涉及到的基本技術4.1.2語法制導翻譯方法對文法中的每個產生式都附加一個語義動作或語義子程序,在語法分析過程中，每當需要使用一個產生式進行推導或歸約，語法分析程序除執行相應的語法分析動作外，還要執行相應的語義動作或調用相應的語義子程序。這種模式實際上是對上下文無關文法的一種擴充。例如,文法G[E]:

產生式

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

語法分析棧語義分析棧TT.Val+‘+’E……#

產生式的語義是由組成該產生式的文法符號的語義所決定的。

可將文法符號的語義以“屬性”的形式附加到各個文法符號上，再根據產生式所蘊含的語義，給出每個文法符號的屬性的求值規則，從而形成一種附帶有語義屬性的前后文無關文法，即屬性文法。4.2屬性文法

屬性文法=上下文無關文法+屬性+求值規則

屬性用來描述文法符號的語義特征，如常量的“值”、變量的類型和存儲位置等。求值規則（屬性計算規則）與產生式相關聯的反映文法符號屬性之間關系的“規則”。求值規則還可進一步擴展為語義規則（語義動作）。1、定義【例】簡單表達式的屬性文法。語義規則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產生式詞法分析的結果若產生式AX1X2…Xn，與之相關的屬性計算規則 b=f(c1,c2,…)，其中f

是函數，b和c1,c2,…,ck

是該產生式文法符號的屬性，－如果屬性b是產生式左部符號A的屬性，c1,c2,…,ck

是產生式右部文法符號的屬性或A的其它屬性,則稱其為A的綜合屬性；－如果屬性b是產生式右部符號Xi的屬性，

c1,c2,…,ck

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

的屬性計算過程。

（綜合屬性的例子）語義規則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產生式

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

的分析樹進行自下而上（后序）遍歷，并執行相應的語義規則，得到該表達式的一種求值過程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【例】語句intx,y,z的語義分析。（繼承屬性）產生式

語

義

規

則

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)

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

樹遍歷方法

通過遍歷分析樹進行屬性計算

單遍的方法（On-the-fly方法）語法分析遍的同時進行屬性計算

基于樹遍歷方法的語義處理

步驟

構造輸入串的語法分析樹。

構造依賴圖（Dependencygraph）。

若該依賴圖是無圈的，則按造此無圈圖的一種拓撲排序（Topologicalsort）對分析樹進行遍歷，則可以計算所有的屬性。4.3幾種常見的中間語言

（中間代碼形式）抽象語法樹逆波蘭式三地址代碼（四元式、三元式、間接三元式）語法樹是分析樹的濃縮表示：算符和關鍵字作為內部結點。

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

中綴表示 后綴表示

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

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

op

arg2

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

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

arg1或op

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

除前面所述的抽象語法樹、逆波蘭式、四元式外，常見的中間語言還有接近PASCAL形式的P-代碼，接近C格式的C-代碼等等。4、其它表示法4.4簡單算術表達式和賦值語句的翻譯相關的語義處理說明對非終結符E定義語義變量E.place，即用E.place表示存放E值的變量名在符號表中的入口地址或臨時變量名的整數碼。定義語義函數newtemp()，即每次調用newtemp()時都回送一個代表新臨時變量的整數碼；臨時變量名按產生的順序可設為T1、T2…定義語義函數emit(op,arg1,arg2,result)，emit的功能是產生一個四元式。定義語義函數lookup()，其功能是查找是否出現在符號表中，是則返回在符號表中的入口指針，否則返回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);}寫出每個產生式對應的語義處理過程(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();}

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

∨E2如果E1為真，則立即可知E為真，即E1.tc與E.tc相同；如果E1為假，則必須計算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);}

寫出每個產生式對應的語義處理過程真出口，有待回填假出口，有待回填(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）先產生暫時沒有填寫目標標號的四元式。（2）對于每一條這樣的四元式作適當的記錄，即可用“拉鏈”的方法將這些四元式鏈接起來。

（實現見課本P104merge(p1,p2)函數）（3）一旦目標標號（即將要轉移的目標四元式的地址）被確定下來，再將它“回填”到相應的指令（四元式的第四個區段）中。

（實現見課本P104Backpatch(p,t)函數）4.5if語句的翻譯條件語句的模式

if(E)S1;elseS2條件語句的代碼結構

E的代碼

E.tc

S1的代碼

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

對應的語義規則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);}生成的四元式序列[例]將下面語句翻譯成四元式：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）控制流語句的自底向上翻譯_另一種實現方法SifEthenMS1 |ifEthenM1S1

NelseM2S2 |whileM1EdoM2S1 |S1;MS2

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

.chainthenM.qif-then-else語句

的自底向上翻譯SifEthenM1S1

NelseM2S2{backpatch