編譯原理教程04語(yǔ)義分析及中間代碼生成

第4章語(yǔ)義分析和中間代碼生成4.1概述4.2屬性文法4.3幾種常見的中間語(yǔ)言4.4表達(dá)式及賦值語(yǔ)句的翻譯4.5控制語(yǔ)句的翻譯4.6數(shù)組元素的翻譯4.7過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯4.8說(shuō)明語(yǔ)句的翻譯4.9遞歸下降語(yǔ)法制導(dǎo)翻譯方法簡(jiǎn)介習(xí)題四4.1概述語(yǔ)義分析的概念語(yǔ)法制導(dǎo)翻譯方法

4.1.1語(yǔ)義分析的概念

一個(gè)源程序經(jīng)過(guò)詞法分析、語(yǔ)法分析之后，表明該源程序在書寫上是正確的，并且符合程序語(yǔ)言所規(guī)定的語(yǔ)法。

但是語(yǔ)法分析并未對(duì)程序內(nèi)部的邏輯含義加以分析，因此編譯程序接下來(lái)的工作是語(yǔ)義分析，即審查每個(gè)語(yǔ)法成分的靜態(tài)語(yǔ)義。

如果靜態(tài)語(yǔ)義正確，則生成與該語(yǔ)言成分等效的中間代碼，或者直接生成目標(biāo)代碼。

直接生成機(jī)器語(yǔ)言或匯編語(yǔ)言形式的目標(biāo)代碼的優(yōu)點(diǎn)是編譯時(shí)間短且無(wú)需中間代碼到目標(biāo)代碼的翻譯，

而中間代碼的優(yōu)點(diǎn)是使編譯結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，特別是使目標(biāo)代碼的優(yōu)化比較容易實(shí)現(xiàn)。靜態(tài)語(yǔ)義檢查是在編譯時(shí)完成的，它涉及以下幾個(gè)方面：

(1)類型檢查，如參與運(yùn)算的操作數(shù)其類型應(yīng)相容。

(2)控制流檢查，用以保證控制語(yǔ)句有合法的轉(zhuǎn)向點(diǎn)。如C語(yǔ)言中不允許goto語(yǔ)句轉(zhuǎn)入case語(yǔ)句流；break語(yǔ)句需尋找包含它的最小switch、while或for語(yǔ)句方可找到轉(zhuǎn)向點(diǎn)，否則出錯(cuò)。(3)一致性檢查，如在相同作用域中標(biāo)識(shí)符只能說(shuō)明一次，case語(yǔ)句的標(biāo)號(hào)不能相同等。

語(yǔ)義分析階段只產(chǎn)生中間代碼而不生成目標(biāo)代碼的方法使編譯程序的開發(fā)變得較為容易，

但語(yǔ)義分析不像詞法分析和語(yǔ)法分析那樣可以分別用正規(guī)文法和上下文無(wú)關(guān)文法描述。

由于語(yǔ)義是上下文有關(guān)的，因此語(yǔ)義的形式化描述是非常困難的，

目前較為常見的是用屬性文法作為描述程序語(yǔ)言語(yǔ)義的工具，并采用語(yǔ)法制導(dǎo)翻譯的方法完成對(duì)語(yǔ)法成分的翻譯工作。4.1.2語(yǔ)法制導(dǎo)翻譯方法語(yǔ)法制導(dǎo)翻譯的方法就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序(稱語(yǔ)義動(dòng)作或語(yǔ)義子程序)，并在語(yǔ)法分析的同時(shí)執(zhí)行這些子程序。在語(yǔ)法分析過(guò)程中，當(dāng)一個(gè)產(chǎn)生式獲得匹配(對(duì)于自上而下分析)或用于歸約(對(duì)于自下而上分析)時(shí)，此產(chǎn)生式相應(yīng)的語(yǔ)義子程序就進(jìn)入工作，完成既定的翻譯任務(wù)。語(yǔ)法制導(dǎo)翻譯分為自下而上語(yǔ)法制導(dǎo)翻譯和自上而下語(yǔ)法制導(dǎo)翻譯，我們重點(diǎn)介紹自下而上語(yǔ)法制導(dǎo)翻譯。假定有一個(gè)自下而上的LR分析器，我們可以把這個(gè)LR分析器的能力加以擴(kuò)大，使它能在用某個(gè)產(chǎn)生式進(jìn)行歸約的同時(shí)調(diào)用相應(yīng)的語(yǔ)義子程序進(jìn)行有關(guān)的翻譯工作。

每個(gè)產(chǎn)生式的語(yǔ)義子程序執(zhí)行之后，某些結(jié)果(語(yǔ)義信息)必須作為此產(chǎn)生式的左部符號(hào)的語(yǔ)義值暫時(shí)保存下來(lái)，以便以后語(yǔ)義子程序引用這些信息。此外，原LR分析器的分析棧也加以擴(kuò)充，以便能夠存放與文法符號(hào)相對(duì)應(yīng)的語(yǔ)義值。這樣，分析?？梢源娣湃愋畔ⅲ悍治鰻顟B(tài)、文法符號(hào)及文法符號(hào)對(duì)應(yīng)的語(yǔ)義值。擴(kuò)充后的分析棧如圖4–1所示。圖4–1擴(kuò)充后的LR分析棧

作為一個(gè)例子，我們考慮下面的文法及語(yǔ)義動(dòng)作所執(zhí)行的程序： 產(chǎn)生式 語(yǔ)義動(dòng)作

(0)S'→E printval[TOP]

(1)E→E(1)+E(2) val[TOP]=val[TOP]+val[TOP+2]

(2)E→E(1)*E(2) val[TOP]=val[TOP]*val[TOP+2]

(3)E→(E(1)) val[TOP]=val[TOP+1]

(4)E→i val[TOP]=lexval(注：lexval為i的整型內(nèi)部值)這個(gè)文法的LR分析表見表3.20。我們擴(kuò)充分析棧工作的總控程序功能，使其在完成語(yǔ)法分析的同時(shí)也能完成語(yǔ)義分析工作(這時(shí)的語(yǔ)法分析棧已成為語(yǔ)義分析棧)；即在用某一個(gè)規(guī)則進(jìn)行歸約之后，調(diào)用相應(yīng)的語(yǔ)義子程序完成與所用產(chǎn)生式相應(yīng)的語(yǔ)義動(dòng)作，并將每次工作后的語(yǔ)義值保存在擴(kuò)充后的“語(yǔ)義值”棧中。圖4–2表示算術(shù)表達(dá)式7＋9*5#的語(yǔ)法樹及各結(jié)點(diǎn)值，而表4.1則給出了根據(jù)表3.20用LR語(yǔ)法制導(dǎo)翻譯方法得到的該表達(dá)式的語(yǔ)義分析和計(jì)值過(guò)程。圖4–2語(yǔ)法制導(dǎo)翻譯計(jì)算表達(dá)式7＋9*5#的語(yǔ)法樹4.2屬性文法文法的屬性屬性文法4.2.1文法的屬性

屬性是指與文法符號(hào)的類型和值等有關(guān)的一些信息，在編譯中用屬性描述處理對(duì)象的特征。

隨著編譯的進(jìn)展，對(duì)語(yǔ)法分析產(chǎn)生的語(yǔ)法樹進(jìn)行語(yǔ)義分析，且分析的結(jié)果用中間代碼描述出來(lái)。

根據(jù)語(yǔ)義處理的需要，在用產(chǎn)生式A→αXβ進(jìn)行歸約或推導(dǎo)時(shí)，應(yīng)能準(zhǔn)確而恰當(dāng)?shù)乇磉_(dá)文法符號(hào)X在歸約或推導(dǎo)時(shí)的不同特征。

例如，判斷變量X的類型是否匹配，要用X的數(shù)據(jù)類型來(lái)描述；

判斷變量X是否存在，要用X的存儲(chǔ)位置來(lái)描述；

而對(duì)X的運(yùn)算，則要用X的值來(lái)描述。

因此，語(yǔ)義分析階段引入X的屬性，如X.type、X.place、X.val等來(lái)分別描述變量X的類型、存儲(chǔ)位置以及值等不同的特征。文法符號(hào)的屬性可分為繼承屬性與綜合屬性兩類。

繼承屬性用于“自上而下”傳遞信息。繼承屬性由相應(yīng)語(yǔ)法樹中結(jié)點(diǎn)的父結(jié)點(diǎn)屬性計(jì)算得到，即沿語(yǔ)法樹向下傳遞，由根結(jié)點(diǎn)到分枝(子)結(jié)點(diǎn)，它反映了對(duì)上下文依賴的特性。繼承屬性可以很方便地用來(lái)表示程序語(yǔ)言上下文的結(jié)構(gòu)關(guān)系。

綜合屬性用于“自下而上”傳遞信息。綜合屬性由相應(yīng)語(yǔ)法分析樹中結(jié)點(diǎn)的分枝結(jié)點(diǎn)(即子結(jié)點(diǎn))屬性計(jì)算得到，其傳遞方向與繼承屬性相反，即沿語(yǔ)法分析樹向上傳遞，從分枝結(jié)點(diǎn)到根結(jié)點(diǎn)。4.2.2屬性文法

屬性文法是一種適用于定義語(yǔ)義的特殊文法，即在語(yǔ)言的文法中增加了屬性的文法，它將文法符號(hào)的語(yǔ)義以“屬性”的形式附加到各個(gè)文法的符號(hào)上(如上述與變量X相關(guān)聯(lián)的屬性X.type、X.place和X.val等)，

再根據(jù)產(chǎn)生式所包含的含義，給出每個(gè)文法符號(hào)屬性的求值規(guī)則，從而形成一種帶有語(yǔ)義屬性的上下文無(wú)關(guān)文法，即屬性文法。屬性文法也是一種翻譯文法，屬性有助于更詳細(xì)地指定文法中的代碼生成動(dòng)作。例如，簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法如下： 產(chǎn)生式 語(yǔ)義規(guī)則

(1)?S→E print(E.val) (2)?E→E(1)+T

E.val=E(1).val+T.val (3)?E→T E.val=T.val (4)?T→T(1)*F T.val=T(1).val*F.val (5)?T→T(1) T.val=T(1).val (6)?F→(E) F.val=E.val (7)?F→i F.val=i.lexval上面的一組產(chǎn)生式中，每一個(gè)非終結(jié)符都有一個(gè)屬性val來(lái)表示整型值，如E.val表示E的整型值，而i.lexval則表示i的整型內(nèi)部值。

與產(chǎn)生式關(guān)聯(lián)的每一個(gè)語(yǔ)義規(guī)則的左部符號(hào)E、T、F等的屬性值的計(jì)算由其各自相應(yīng)的右部符號(hào)決定，這種屬性也稱為綜合屬性。

與產(chǎn)生式S→E關(guān)聯(lián)的語(yǔ)義規(guī)則是一個(gè)函數(shù)print(E.val)，其功能是打印E產(chǎn)生式的值。S在語(yǔ)義規(guī)則中沒(méi)有出現(xiàn)，可以理解為其屬性是一個(gè)虛屬性。4.3幾種常見的中間語(yǔ)言

抽象語(yǔ)法樹逆波蘭表示法三地址代碼4.3.3三地址代碼

1.三地址代碼的形式

2.三地址語(yǔ)句的種類

3.三地址代碼的具體實(shí)現(xiàn)1．三地址代碼的形式

三地址代碼語(yǔ)句的一般形式為x=yopz其中，x、y和z為名字、常量或編譯時(shí)產(chǎn)生的臨時(shí)變量；

op為運(yùn)算符，如定點(diǎn)運(yùn)算符、浮點(diǎn)運(yùn)算符和邏輯運(yùn)算符等。

三地址代碼的每條語(yǔ)句通常包含三個(gè)地址，兩個(gè)用來(lái)存放運(yùn)算對(duì)象，一個(gè)用來(lái)存放運(yùn)算結(jié)果。由于三地址語(yǔ)句只含有一個(gè)運(yùn)算符，因此多個(gè)運(yùn)算符組成的表達(dá)式必須用三地址語(yǔ)句序列來(lái)表示，如表達(dá)式x+y*z的三地址代碼為:t1=y*z;t2=x+t1

3．三地址代碼的具體實(shí)現(xiàn)三地址代碼是中間代碼的一種抽象形式。在編譯程序中，三地址代碼語(yǔ)言的具體實(shí)現(xiàn)通常有三種表示方法：

四元式、三元式和間接三元式。

1)四元式四元式是具有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域?yàn)?op，arg1，arg2，result)其中，op為運(yùn)算符；arg1、arg2及result為指針，它們可指向有關(guān)名字在符號(hào)表中的登記項(xiàng)或一臨時(shí)變量(也可空缺)。常用的三地址語(yǔ)句與相應(yīng)的四元式對(duì)應(yīng)如下：x=yopz 對(duì)應(yīng)(op,y,z,x)x=?y 對(duì)應(yīng)(uminus,y,_,x)x=y 對(duì)應(yīng)(=,y,_,x)parx1 對(duì)應(yīng)(par,x1,_,_)callP 對(duì)應(yīng)(call,_,_,P)gotoL 對(duì)應(yīng)(j,_,_,L)ifxropygotoL 對(duì)應(yīng)(jrop,x,y,L)例如，賦值語(yǔ)句a=b*(c+d)相應(yīng)的四元式代碼為①(+,c,d,t1)②(*,b,t1,t2)③(=,t2,_,a)

我們約定：凡只需一個(gè)運(yùn)算量的算符一律使用arg1。此外，注意這樣一個(gè)規(guī)則：如果op是一個(gè)算術(shù)或邏輯運(yùn)算符，則result總是一個(gè)新引進(jìn)的臨時(shí)變量，它用來(lái)存放運(yùn)算結(jié)果。由上例也可看出，四元式出現(xiàn)的順序與表達(dá)式計(jì)值的順序是一致的，四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的。

四元式由于其表示更接近程序設(shè)計(jì)的習(xí)慣而成為一種普遍采用的中間代碼形式。4.4表達(dá)式及賦值語(yǔ)句的翻譯簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯布爾表達(dá)式的翻譯4.4.1簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯簡(jiǎn)單算術(shù)表達(dá)式是一種僅含簡(jiǎn)單變量的算術(shù)表達(dá)式。簡(jiǎn)單變量是指普通變量和常數(shù)，但不含數(shù)組元素及結(jié)構(gòu)引用等復(fù)合型數(shù)據(jù)結(jié)構(gòu)。簡(jiǎn)單算術(shù)表達(dá)式的計(jì)值順序與四元式出現(xiàn)的順序相同，因此很容易將其翻譯成四元式形式?？紤]以下文法G[A]：A→i=E?? E→E+E∣E*E∣?E∣(E)∣i在此，非終結(jié)符A代表“賦值句”。文法G[A]雖然是一個(gè)二義文法，但通過(guò)確定運(yùn)算符的結(jié)合性及規(guī)定運(yùn)算符的優(yōu)先級(jí)就可避免二義性的發(fā)生。為了實(shí)現(xiàn)由表達(dá)式到四元式的翻譯，需要給文法加上語(yǔ)義子程序，以便在進(jìn)行歸約的同時(shí)執(zhí)行對(duì)應(yīng)的語(yǔ)義子程序。語(yǔ)義子程序所涉及的語(yǔ)義變量、語(yǔ)義過(guò)程及函數(shù)說(shuō)明如下：

(1)對(duì)非終結(jié)符E定義語(yǔ)義變量E.place，即用E.place表示存放E值的變量名在符號(hào)表中的入口地址或臨時(shí)變量名的整數(shù)碼。

(2)定義語(yǔ)義函數(shù)newtemp(?)，即每次調(diào)用newtemp(?)時(shí)都將回送一個(gè)代表新臨時(shí)變量的整數(shù)碼；臨時(shí)變量名按產(chǎn)生的順序可設(shè)為T1、T2……

(3)定義語(yǔ)義過(guò)程emit(op,arg1,arg2,result),emit的功能是產(chǎn)生一個(gè)四元式并填入四元式表中。

(4)定義語(yǔ)義函數(shù)lookup()，其功能是審查是否出現(xiàn)在符號(hào)表中，是則返回在符號(hào)表的入口指針，否則返回NULL。使用上述語(yǔ)義變量、過(guò)程和函數(shù)，可寫出文法G[A]中的每一個(gè)產(chǎn)生式的語(yǔ)義子程序。

(1)?A→i=E {p=lookup(); if(p==NULL)error(?); elseemit(=,E.place,_,P);}

(2)?E→E(1)+E(2) {E.place=newtemp(?); emit(+,E(1).place,E(2).place,E.place);}

(3)?E→E(1)*E(2)? {E.place=newtemp(?); emit(*,E(1).place,E(2).place,E.place);}

(4)?E→?E(1) {E.place=newtemp(?); emit(uminus,E(1).place,_,E.place);}

(5)?E→(E(1))? {E.place=E(1).place;}

(6)?E→i

? {p=lookup();

if(p!=NULL)E.place=p;/*另一種表示為E.place=entry(i)*/ elseerror(?);}

例4.2

試分析賦值語(yǔ)句X=?B*(C+D)的語(yǔ)法制導(dǎo)翻譯過(guò)程。

[解答]賦值語(yǔ)句X=?B*(C+D)的語(yǔ)法制導(dǎo)翻譯過(guò)程如表4.2所示(加工分析過(guò)程參考表4.1)。4.4.2布爾表達(dá)式的翻譯在程序語(yǔ)言中，布爾表達(dá)式一般由運(yùn)算符與運(yùn)算對(duì)象組成。布爾表達(dá)式的運(yùn)算符為布爾運(yùn)算符，即┐、∧、∨，或?yàn)閚ot、and和or(注：C語(yǔ)言中為！、&&和|?|)，其運(yùn)算對(duì)象為布爾變量，也可為常量或關(guān)系表達(dá)式。關(guān)系表達(dá)式的運(yùn)算對(duì)象為算術(shù)表達(dá)式，其運(yùn)算符為關(guān)系運(yùn)算符<、<=、==、!=、>=、>等。關(guān)系運(yùn)算符的優(yōu)先級(jí)相同但不得結(jié)合，其運(yùn)算優(yōu)先級(jí)低于任何算術(shù)運(yùn)算符。布爾運(yùn)算符的運(yùn)算順序一般為┐、∧、∨，且∧和∨服從左結(jié)合。布爾算符的運(yùn)算優(yōu)先級(jí)低于任何關(guān)系運(yùn)算符。為簡(jiǎn)單起見，我們討論下述文法G[E]生成的布爾表達(dá)式：G[E]：E→E∧E∣E∨E∣┐E∣(E)∣i∣iropi

rop代表:<、<=、==、!=、>=、>注意：布爾表達(dá)式在程序語(yǔ)言中不僅用作計(jì)算布爾值，還作為控制語(yǔ)句(如if-else、while等)的條件表達(dá)式，用以確定程序的控制流向。

無(wú)論布爾表達(dá)式的作用如何，按照程序執(zhí)行的順序，都必須先計(jì)算出布爾表達(dá)式的值。布爾表達(dá)式的翻譯過(guò)程：1.畫表達(dá)式的翻譯圖；2.寫出每個(gè)布爾變量或關(guān)系表達(dá)式的2個(gè)四元式（四元式未完成，未填轉(zhuǎn)移目標(biāo)result）；3.待整個(gè)表達(dá)式的四元式寫完，回填轉(zhuǎn)移目標(biāo)。計(jì)算布爾表達(dá)式的值通常有兩種方法。

第一種方法是仿照計(jì)算算術(shù)表達(dá)式的方法，按布爾表達(dá)式的運(yùn)算順序一步步地計(jì)算出真假值來(lái)。假定邏輯值true用1表示、false用0表示，則布爾表達(dá)式1∨(┐0∧0)∨0值的計(jì)算過(guò)程為: 1∨(┐0∧0)∨0 =1∨(1∧0)∨0 =1∨0∨0 =1∨0 =1

另一種方法是根據(jù)布爾運(yùn)算的特點(diǎn)實(shí)施某種優(yōu)化，即不必一步一步地計(jì)算布爾表達(dá)式中所有運(yùn)算對(duì)象的值，而是省略不影響運(yùn)算結(jié)果的運(yùn)算。

例如，在計(jì)算A∨B時(shí)，

若計(jì)算出的A值為1，則B值就無(wú)需再計(jì)算了；因?yàn)椴还蹷的結(jié)果是什么，A∨B的值都為1。同理，在計(jì)算A∧B時(shí)若發(fā)現(xiàn)A值為0，則B值也無(wú)需計(jì)算，A∧B的值一定為0。如何確定一個(gè)表達(dá)式的真假出口呢？

考慮表達(dá)式E(1)∨E(2)，若E(1)為真，則立即知道E也為真，因此，E(1)的真出口也就是整個(gè)E的真出口；若E(1)為假，則E(2)必須被計(jì)值，此時(shí)E(2)的第一個(gè)四元式就是E(1)的假出口。當(dāng)然，E(2)的真假出口也就是整個(gè)E的真假出口。

類似的考慮適用于對(duì)E(1)∧E(2)的翻譯。我們將E(1)∨E(2)和E(1)∧E(2)的翻譯用圖4–5表示，而對(duì)形如┐E(1)的表達(dá)式則只需調(diào)換E(1)的真假出口就可得到該表達(dá)式E的真假出口。圖4–5E(1)∨E(2)和E(1)∧E(2)的翻譯圖(a)?E(1)∨E(2)；(b)?E(1)∧E(2)在自下而上的分析過(guò)程中，一個(gè)布爾式的真假出口往往不能在產(chǎn)生四元式的同時(shí)就填上，我們只好把這種未完成的四元式的地址(編號(hào))作為E的語(yǔ)義值暫存起來(lái)，待整個(gè)表達(dá)式的四元式產(chǎn)生完畢之后，再來(lái)填寫這個(gè)未填入的轉(zhuǎn)移目標(biāo)。

對(duì)于每個(gè)非終結(jié)符E，我們需要為它賦予兩個(gè)語(yǔ)義值E.tc和E.fc，以分別記錄E所對(duì)應(yīng)的四元式需要回填“真”、“假”出口的四元式地址所構(gòu)成的鏈。這是因?yàn)樵诜g過(guò)程中，常常會(huì)出現(xiàn)若干轉(zhuǎn)移四元式轉(zhuǎn)向同一個(gè)目標(biāo)但目標(biāo)位置又未確定的情況，此時(shí)可用“拉鏈”的方法將這些四元式鏈接起來(lái)，待獲得轉(zhuǎn)移目標(biāo)的四元式地址時(shí)再進(jìn)行返填。

例如，假定E的四元式需要回填“真”出口的有p、q、r這三個(gè)四元式，則它們可鏈接成如圖4–6所示的一條真值鏈(記作tc)。圖4–6拉鏈法鏈接四元式示意為了處理E.tc和E.fc這兩項(xiàng)語(yǔ)義值，我們需要引入如下的語(yǔ)義變量和函數(shù)：

(1)nxq：始終指向下一條將要產(chǎn)生的四元式的地址(序號(hào))，其初值為1。每執(zhí)行一次emit語(yǔ)句后，nxq自動(dòng)增1。

emit(op,arg1,arg2,result),emit的功能是產(chǎn)生一個(gè)四元式并填入四元式表中。

(2)merge(p1,p2)：把以p1和p2為鏈?zhǔn)椎膬蓷l鏈合并為一條以p2為鏈?zhǔn)椎逆?即返回鏈?zhǔn)字祊2)。

(3)Backpatch(p,t)：把鏈?zhǔn)譸所鏈接的每個(gè)四元式的第四區(qū)段(即result)都改寫為地址t。merge(?)函數(shù)如下：merge(p1，p2){if(p2==0)return(p1);else{p=p2;while(四元式p的第四區(qū)段內(nèi)容不為0)p=四元式p的第四區(qū)段內(nèi)容；把p1填進(jìn)四元式p的第四區(qū)段；

return(p2);}}Backpatch(?)函數(shù)如下：Backpatch(p,t){Q=p;while(Q!=0){q=四元式Q的第四區(qū)段內(nèi)容；把t填進(jìn)四元式Q的第四區(qū)段；

Q=q;}}為了便于實(shí)現(xiàn)布爾表達(dá)式的語(yǔ)法制導(dǎo)翻譯，并在掃描到“∧”與“∨”時(shí)能及時(shí)回填一些已經(jīng)確定了的待填轉(zhuǎn)移目標(biāo)，我們將

文法G[E]改寫為下面的文法G‘[E]，以利于編制相應(yīng)的語(yǔ)義子程序：

G[E]：E→E∧E∣E∨E∣┐E∣(E)∣i∣iropi

G‘[E]：

E→EAE∣EBE∣┐E∣(E)∣i∣iropi EA→E∧ EB→E∨這時(shí)，文法G'[E]的每個(gè)產(chǎn)生式和相應(yīng)的語(yǔ)義子程序如下：

(1)E→i {E.tc=nxq;E.fc=nxq+1; emit(jnz,entry(i),_,0); emit(j,_,_,0);}

(2)E→i(1)ropi(2) {E.tc=nxq;E.fc=nxq+1; emit(jrop,entry(i(1)),entry(i(2)),0); emit(j,_,_,0);}

(3)E→(E(1)) {E.tc=E(1).tc;E.fc=E(1).fc;}

(4)E→┐E(1) {E.tc=E(1).fc;E.fc=E(1).tc;}

(5)EA→E(1)∧

{Backpatch(E(1).tc,nxq); EA.fc=E(1).fc;}

(6)E→EAE(2) {E.tc=E(2).tc; E.fc=merge(EA.fc，E(2).fc);}

(7)EB→E(1)∨

{Backpatch(E(1).fc，nxq); EB.tc=E(1).tc;}

(8)E→EBE(2) {E.fc=E(2).fc; E.tc=merge(EB.tc，E(2).tc);}注意：根據(jù)上述語(yǔ)義動(dòng)作，在整個(gè)布爾表達(dá)式所對(duì)應(yīng)的四元式全部產(chǎn)生之后，作為整個(gè)表達(dá)式的真假出口(轉(zhuǎn)移目標(biāo))仍尚待回填。此外，由產(chǎn)生式(2)也可看出關(guān)系表達(dá)式的優(yōu)先級(jí)要高于布爾表達(dá)式。例4.3

試給出布爾表達(dá)式a∧b∨c≥d作為控制條件的四元式中間代碼。

[解答]

設(shè)四元式序號(hào)從100開始，則布爾表達(dá)式a∧b∨c≥d的分析過(guò)程如圖4–7所示。這時(shí)，文法G'[E]的每個(gè)產(chǎn)生式和相應(yīng)的語(yǔ)義子程序如下：

(1)E→i {E.tc=nxq;E.fc=nxq+1;

emit(jnz,entry(i),_,0);

emit(j,_,_,0);}

(2)E→i(1)ropi(2) {E.tc=nxq;E.fc=nxq+1;

emit(jrop,entry(i(1)),entry(i(2)),0);

emit(j,_,_,0);}

(3)E→(E(1)) {E.tc=E(1).tc;E.fc=E(1).fc;}

(4)E→┐E(1) {E.tc=E(1).fc;E.fc=E(1).tc;}

(5)EA→E(1)∧

{Backpatch(E(1).tc,nxq); EA.fc=E(1).fc;}

(6)E→EAE(2) {E.tc=E(2).tc; E.fc=merge(EA.fc，E(2).fc);}

(7)EB→E(1)∨

{Backpatch(E(1).fc，nxq); EB.tc=E(1).tc;}

(8)E→EBE(2) {E.fc=E(2).fc; E.tc=merge(EB.tc，E(2).tc);}圖4–7表達(dá)式a∧b∨c≥d分析示意即：100(jnz，a，_，102)/*a為T*/101(j，_，_，104)/*a為F*/102(jnz，b，_，106)/*b為T*/103(j，_，_，104)/*b為F*/104(j≥，c，d，106)/*c≥d為T*/105(j，_，_，q)/*c≥d為F*/T:106/*“真”出口*/

F:q/*“假”出口*/當(dāng)然，我們也可以通過(guò)圖4–8的分析得到上述四元式序列。圖4–8a∧b∨c≥d的翻譯圖由例4.3可知，每一個(gè)布爾變量a都對(duì)應(yīng)一真一假兩個(gè)四元式，并且格式是固定的，即

(jnz，a，_，0) /*a為布爾變量*/(j，_，_，0)而每一個(gè)關(guān)系表達(dá)式同樣對(duì)應(yīng)一真一假兩個(gè)四元式，其格式也是固定的，即

(jrop，X，Y，0)/*X、Y為關(guān)系運(yùn)算符兩側(cè)的變量或值*/(j，_，_，0)例4.4

試給出布爾表達(dá)式a∨m≠n∨c∧x＞y的四元式代碼。

[解答]該布爾表達(dá)式的翻譯圖如圖4–9所示，所對(duì)應(yīng)的四元式代碼如下：

100(jnz，a，_，106)/*a為T*/101(j，_，_，102)/*a為F*/102(j≠，m，n，106)/*m≠n為T*/103(j，_，_，104)/*m≠n為F*/104(jnz，c，_，106)/*c為T*/105(j，_，_，q)/*c為F*/106(j＞，x，y，108)/*x>y為T*/107(j，_，_，q)/*x>y為F*/T:108/*“真”出口*/

F:q/*“假”出口*/圖4–9例4.4的翻譯圖4.5控制語(yǔ)句的翻譯條件語(yǔ)句if的翻譯條件循環(huán)語(yǔ)句While的翻譯三種基本控制結(jié)構(gòu)的翻譯多分支控制語(yǔ)句case的翻譯語(yǔ)句標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句的翻譯在源程序中，控制語(yǔ)句用于實(shí)現(xiàn)程序流程的控制。一般程序流程控制可分為下面三種基本結(jié)構(gòu)：

(1)順序結(jié)構(gòu)，一般用復(fù)合語(yǔ)句實(shí)現(xiàn)；

(2)選擇結(jié)構(gòu)，用if和case等語(yǔ)句實(shí)現(xiàn)；

(3)循環(huán)結(jié)構(gòu)，用for、while、do(即repeat)等語(yǔ)句實(shí)現(xiàn)。控制語(yǔ)句的翻譯過(guò)程：1.畫語(yǔ)句的代碼結(jié)構(gòu)圖；2.根據(jù)代碼結(jié)構(gòu)圖，寫四元式；（四元式未完成，未填轉(zhuǎn)移目標(biāo)result）3.翻譯過(guò)程（即掃描語(yǔ)句過(guò)程）中，伺機(jī)回填轉(zhuǎn)移目標(biāo)。4.5.1條件語(yǔ)句if的翻譯

1.條件語(yǔ)句if的代碼結(jié)構(gòu)

2.條件語(yǔ)句if的文法和語(yǔ)義子程序的設(shè)計(jì)1．條件語(yǔ)句if的代碼結(jié)構(gòu)我們按下面的條件語(yǔ)句if的模式進(jìn)行討論：

if(E)S1;elseS2條件語(yǔ)句if(E)S1;elseS2中布爾表達(dá)式E的作用僅在于控制對(duì)S1和S2的選擇，因此可將作為轉(zhuǎn)移條件的布爾式E賦予兩種“出口”：一是“真”出口，出向S1；一是“假”出口，出向S2。于是，條件語(yǔ)句可以翻譯成如圖4–10所示的代碼結(jié)構(gòu)。圖4–10條件語(yǔ)句if(E)S1;elseS2的代碼結(jié)構(gòu)我們知道，非終結(jié)符E具有兩項(xiàng)語(yǔ)義值E.tc和E.fc，它們分別指出了尚待回填真假出口的四元式串。E的“真”出口只有在掃描完布爾表達(dá)式E后的“)”時(shí)才能知道，而它的“假”出口則需要處理過(guò)S1之后并且到else時(shí)才能明確。這就是說(shuō)，必須把E.fc的值傳下去，以便到達(dá)相應(yīng)的else時(shí)才進(jìn)行回填。S1語(yǔ)句執(zhí)行完就意味著整個(gè)if-else語(yǔ)句已執(zhí)行完畢，因此，在S1的編碼之后應(yīng)產(chǎn)生一條無(wú)條件轉(zhuǎn)移指令，這條轉(zhuǎn)移指令將導(dǎo)致程序控制離開整個(gè)if-else語(yǔ)句。但是，在完成S2的翻譯之前，這條無(wú)條件轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)是不知道的，甚至在翻譯完S2之后仍無(wú)法確定，這種情形是由語(yǔ)句的嵌套性所引起的。例如下面的語(yǔ)句：

if(E1)if(E2)S1;elseS2;elseS3在S1代碼之后的那條無(wú)條件轉(zhuǎn)移指令不僅應(yīng)跨越S2，而且應(yīng)跨越S3。這也就是說(shuō)，轉(zhuǎn)移目標(biāo)的確定和語(yǔ)句所處的環(huán)境密切相關(guān)。

2．條件語(yǔ)句if的文法和語(yǔ)義子程序的設(shè)計(jì)條件語(yǔ)句if的文法G[S]如下：

G[S]：S→if(E)S(1) S→if(E)S(1);elseS(2)為了在掃描條件語(yǔ)句過(guò)程中不失時(shí)機(jī)地處理和回填有關(guān)信息，可將G[S]改寫為如下的G'[S]：

G'[S]：(1)?S→CS(1)

(2)?C→if(E)

(3)?S→TpS(2)

(4)?TP→CS(1);else根據(jù)程序語(yǔ)言的處理順序，首先用產(chǎn)生式(2)C→if(E)進(jìn)行歸約，這時(shí)E的真出口即為E所生成四元式序列后的下一個(gè)地址。因此，將“)”后的第一個(gè)四元式地址回填至E的真出口，E的假出口地址則作為待填信息放在C的語(yǔ)義變量C.chain中，即

C→if(E) {Backpatch(E.tc,nxq); C.chain=E.fc;}接下來(lái)用產(chǎn)生式(1)S→CS(1)繼續(xù)向上歸約。這時(shí)已經(jīng)處理到S→if(E)S(1)，由于歸約時(shí)E的真出口已經(jīng)處理，而E的假出口(即語(yǔ)句S的出口)同時(shí)是語(yǔ)句S(1)的出口，但此時(shí)語(yǔ)句S的出口地址未定，故將C.chain和S(1).chain一起作為S的待填信息鏈用函數(shù)merge鏈在一起保留在S的語(yǔ)義值S.chain中，即有

S→CS(1){S.chain=merge(C.chain,S(1).chain)}如果此時(shí)條件語(yǔ)句為不含else的條件句，則在產(chǎn)生式(1)、(2)歸約為S后即可以用下一個(gè)將要產(chǎn)生的四元式地址(即S的出口地址)來(lái)回填S的出口地址鏈(即S.chain)；如果此時(shí)條件語(yǔ)句為if-else形式，則繼續(xù)用產(chǎn)生式(4)TP→CS(1);else歸約。用Tp→CS(1);else歸約時(shí)首先產(chǎn)生S(1)語(yǔ)句序列之后的一個(gè)無(wú)條件轉(zhuǎn)移四元式(以便跳過(guò)S(2)，見圖4–10的結(jié)構(gòu)框圖)，該四元式的地址(即標(biāo)號(hào))保留在q中，以便待獲知要轉(zhuǎn)移的地址后再進(jìn)行回填，也即(i)(S(1)的第一個(gè)四元式) /*E的真出口*/

(q?1)(S(1)的最后一個(gè)四元式)(q)(j,_,_,0)/*無(wú)條件跳過(guò)S(2)，其轉(zhuǎn)移地址有待回填*/(q+1)(S(2)的第一個(gè)四元式) /*E的假出口*/此時(shí)q的出口也就是整個(gè)條件語(yǔ)句的出口，因此應(yīng)將其與S.chain鏈接后掛入鏈頭為Tp.chain的鏈中。此外，emit產(chǎn)生四元式q后nxq自動(dòng)加1(即為q+1)，其地址即為else后(也即S(2))的第一個(gè)四元式地址，它也是E的假出口地址，因此應(yīng)將此地址回填到E.fc即C.chain中，即有

Tp→CS(1);else{q=nxq;? emit(j,_,_,0);? Backpatch(C.chain,nxq);? Tp.chain=merge(S.chain,q);}最后用產(chǎn)生式(3)S→TpS(2)歸約。S(2)語(yǔ)句序列處理完后繼續(xù)翻譯if語(yǔ)句之后的后繼語(yǔ)句，這時(shí)就有了后繼語(yǔ)句的四元式地址，該地址也是整個(gè)if語(yǔ)句的出口地址，它與S(2)語(yǔ)句序列的出口一致。由于S(2)的出口待填信息在S(2).chain中，故將Tp.chain與S(2).chain鏈接后掛入鏈頭為S.chain的鏈中，即

S→TpS(2){S.chain=merge(Tp.chain,S(2).chain);}4.5.2條件循環(huán)語(yǔ)句while的翻譯

1.條件循環(huán)語(yǔ)句while的代碼結(jié)構(gòu)

2.條件循環(huán)語(yǔ)句while的文法和語(yǔ)義子程序設(shè)計(jì)1．條件循環(huán)語(yǔ)句while的代碼結(jié)構(gòu)條件循環(huán)語(yǔ)句while(E)S(1)通常被翻譯成如圖4–11所示的代碼結(jié)構(gòu)。布爾表達(dá)式E的“真”出口出向S(1)代碼段的第一個(gè)四元式，緊接S(1)代碼段之后應(yīng)產(chǎn)生一條轉(zhuǎn)向測(cè)試E的無(wú)條件轉(zhuǎn)移指令；而E的“假”出口將導(dǎo)致程序控制離開整個(gè)while語(yǔ)句而去執(zhí)行while語(yǔ)句之后的后繼語(yǔ)句。圖4–11條件循環(huán)語(yǔ)句while的代碼結(jié)構(gòu)注意：E(1)的“假”出口目標(biāo)即使在整個(gè)while語(yǔ)句翻譯完之后也未必明確。例如：

if(E1)while(E2)S1;elseS2

這種情況仍是由于語(yǔ)句的嵌套性引起的，所以只好把E的假出口作為條件循環(huán)語(yǔ)句的語(yǔ)義值S.chain保留下來(lái)，以便在處理外層語(yǔ)句時(shí)再伺機(jī)回填。

2．條件循環(huán)語(yǔ)句while的文法和語(yǔ)義子程序設(shè)計(jì)同樣，我們給出易于及時(shí)處理和回填的條件循環(huán)語(yǔ)句while的文法G[S]如下：

G[S]：(1)?S→WdS(1)

(2)?Wd→W(E)

(3)?W→while根據(jù)while語(yǔ)句的掃描加工順序，首先用產(chǎn)生式(3)W→while進(jìn)行歸約，這時(shí)nxq即為E的第一個(gè)四元式地址，我們將其保留在W.quad中。然后繼續(xù)掃描并用Wd→W(E)歸約，即掃描完“)”后可以用Backpatch(E.tc,nxq)回填E.tc值；而E.fc則要等到S(1)語(yǔ)句序列全部產(chǎn)生后才能回填，因此E.fc作為待填信息用Wd.chain=E.fc傳下去。當(dāng)用產(chǎn)生式(1)S→WdS(1)歸約時(shí)，S(1)語(yǔ)句序列的全部四元式已經(jīng)產(chǎn)生。根據(jù)圖4–11while語(yǔ)句代碼結(jié)構(gòu)的特點(diǎn)，此時(shí)應(yīng)無(wú)條件返回到E的第一個(gè)四元式繼續(xù)對(duì)條件E進(jìn)行測(cè)試，即形成四元式(j,_,_,Wd.quad)，同時(shí)用Backpatch(S(1).chain,Wd.quad)回填E的入口地址到S(1)語(yǔ)句序列中所有需要該信息的四元式中。在無(wú)條件轉(zhuǎn)移語(yǔ)句(j,_,_,Wd.quad)之后即為while語(yǔ)句的后繼語(yǔ)句，而這個(gè)后繼語(yǔ)句中的第一個(gè)四元式地址即為while語(yǔ)句E的假出口，保存在Wd.chain中?？紤]到嵌套情況，將Wd.chain信息作為整個(gè)while語(yǔ)句的出口保留在S.chain中，以便適當(dāng)時(shí)機(jī)回填。因此，文法G[S]對(duì)應(yīng)的語(yǔ)義加工子程序如下：

(1)?W→while {W.quad=nxq;}

(2)?Wd→W(E)? {Backpatch(E.tc,nxq); Wd.chain=E.fc; Wd.quad=W.quad;}

(3)?S→WdS(1){Backpatch(S(1).chain,Wd.quad);

emit((j,_,_,Wd.quad);

S.chain=Wd.chain;}當(dāng)然，我們還可按同樣方法得到doS(1)while(E)條件語(yǔ)句的文法及語(yǔ)義加工子程序。4.5.3三種基本控制結(jié)構(gòu)的翻譯

1.三種基本控制結(jié)構(gòu)的文法

2.翻譯示例1．三種基本控制結(jié)構(gòu)的文法我們給出三種基本控制結(jié)構(gòu)的文法G[S]如下：

G[S]： (1)?S→CS (2)?∣TPS (3)?∣WdS (4)?∣{L} (5)?∣A/*A代表賦值語(yǔ)句*/

(6)?L→LSS (7)?∣S (8)?C→if(E) (9)?TP→CS;else (10)?W→while (11)?Wd→W(E) (12)?LS→L;

G[S]中各產(chǎn)生式對(duì)應(yīng)的語(yǔ)義子程序如下：

(1)?S→CS(1){S.chain=merge(C.chain,S(1).chain);}

(2)?S→TPS(2)?{S.chain=merge(TP.chain,S(2).chain);}

(3)?S→WdS(1){Backpatch(S(1).chain,Wd.quad);

emit(j,_,_,Wd.quad);

S.chain=Wd.chain;}

(4)?S→{L}?{S.chain=L.chain;}

(5)?S→A?{S.chain=0;/*空鏈*/}

(6)?L→LSS(1){L.chain=S(1).chain;}

(7)?L→S

{L.chain=S.chain;}

(8)?C→if(E){Backpatch(E.tc,nxq);

C.chain=E.fc;}(9)?TP→CS(1);else?{q=nxq; emit(j,_,_,0); Backpatch(C.chain,nxq); TP.chain=merge(S(1).chain,q);}

(10)?W→while {W.quad=nxq;}

(11)?Wd→W(E) {Backpatch(E.tc,nxq); Wd.chain=E.fc; Wd.quad=W.quad;}

(12)?LS→L; {Backpatch(L.chain,nxq);}

2．翻譯示例例4.5

將下面的語(yǔ)句翻譯成四元式：

if(x＞y)if(a∧b)m=m+1；elsem=m-1；elsex=y；

[解答]該語(yǔ)句對(duì)應(yīng)的代碼結(jié)構(gòu)圖如圖4–12所示，它所對(duì)應(yīng)的四元式序列如下：100(j＞，x，y，102)/*x>y為T*/101(j，_，_，110)/*x>y為F*/102(jnz，a，_，104)/*a為T*/103(j，_，_，108)/*a為F*/104(jnz，b，_，106)/*b為T*/105(j，_，_，108)/*b為F*/106(+，m，1，m)/*m=m+1*/107(j，_，_，109)/*內(nèi)層else之前的跳轉(zhuǎn)*/108(_，m，1，m)/*m=m-1*/109(j，_，_，111)/*外層else之前的跳轉(zhuǎn)*/110(=，y，_，x)/*x=y*/111/*出口*/圖4–12例4.5的代碼結(jié)構(gòu)圖

如果按圖4–13所示的翻譯圖進(jìn)行翻譯，則第107句四元式為(j，_，_，111)，雖然與上面的107句不同，但仔細(xì)分析就會(huì)發(fā)現(xiàn)：翻譯圖與代碼結(jié)構(gòu)圖兩者所翻譯的結(jié)果在功能上是完全相同的。圖4–13例4.5的翻譯圖

例4.6

將下面的語(yǔ)句翻譯成四元式：while(A<B) if(C<D)X=Y+Z

[解答]我們首先畫出該語(yǔ)句對(duì)應(yīng)的代碼結(jié)構(gòu)圖如圖4–14所示。

圖4–14例4.3的代碼結(jié)構(gòu)圖按照文法及加工子程序(包括前述賦值句和布爾表達(dá)式的翻譯法)得到該語(yǔ)句對(duì)應(yīng)的四元式序列如下：100(j<，A，B，102) /*E1為T*/101(j，_，_，107) /*E1為F*/

102(j<，C，D，104) /*E2為T*/103(j，_，_，106) /*E2為F*/104(+，Y，Z，T)/*T為臨時(shí)變量，保存Y+Z*/105(=，T，_，X)/*X=T*/106(j，_，_，100)/*循環(huán)回跳*/

107/*出口*/例4.7

將下面的語(yǔ)句翻譯成四元式：if(a∧b)

while(x<y)

if(m≠n)

m=n;elsem=m+1;else

while(m>n)x=x+y；

[解答]我們首先畫出該語(yǔ)句對(duì)應(yīng)的代碼結(jié)構(gòu)圖如圖4–15所示。圖4–15例4.4的代碼結(jié)構(gòu)圖雖然根據(jù)文法及加工子程序可以得到該語(yǔ)句對(duì)應(yīng)的四元式序列，但我們知道每個(gè)布爾變量及每個(gè)關(guān)系表達(dá)式都對(duì)應(yīng)一真一假固定格式的兩個(gè)四元式，且if語(yǔ)句在else之前應(yīng)有一無(wú)條件轉(zhuǎn)移語(yǔ)句跳過(guò)else后的語(yǔ)句，而while語(yǔ)句則在結(jié)束時(shí)有一個(gè)向回跳的無(wú)條件轉(zhuǎn)移語(yǔ)句。由本題可知，共有兩個(gè)布爾變量a、b和三個(gè)關(guān)系表達(dá)式，共需10條四元式，而兩個(gè)if語(yǔ)句和兩個(gè)while語(yǔ)句共需4條無(wú)條件轉(zhuǎn)移四元式，再加上3條賦值四元式，總計(jì)為17條四元式。再依據(jù)代碼結(jié)構(gòu)圖來(lái)確定各個(gè)條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移四元式的轉(zhuǎn)移地址，就很容易得到該語(yǔ)句的四元式序列如下：100(jnz，a，_，102)/*a為T*/101(j，_，_，113)/*a為F*/102(jnz，b，_，104)/*b為T*/103(j，_，_，113)/*b為T*/104(j<，x，y，106)/*x<y為T*/105(j，_，_，112)/*x<y為F*/106(j≠，m，n，108)/*m≠n為T*/107(j，_，_，110)/*m≠n為F*/108(=，n，_，m)/*m=n*/109(j，_，_，111)/*內(nèi)層else之前跳轉(zhuǎn)*/110(+，m，1，m)/*m=m+1*/111(j，_，_，104)/*循環(huán)回跳*/112(j，_，_，117)/*外層else之前跳轉(zhuǎn)*/113(j>，m，n，115)/*m>n為T*/114(j，_，_，117)/*m>n為F*/115(+，x，y，x)/*x=x+y*/116(j，_，_，113)/*循環(huán)回跳*/117/*出口*/例4.8

按已學(xué)過(guò)的文法及語(yǔ)義加工子程序分析下述語(yǔ)句語(yǔ)義加工的全過(guò)程：

while(x<y)x=x+1

[解答]語(yǔ)句while(x<y)x=x+1的語(yǔ)義加工過(guò)程見表4.3。4.5.4多分支控制語(yǔ)句case的翻譯多分支控制語(yǔ)句具有如下形式的語(yǔ)法結(jié)構(gòu)：switch(E){ casec1:S1;casec2:S2;caseci:Si;casecn:Sn;default:Sn+1}其中n≥1。switch語(yǔ)句的語(yǔ)義是：先計(jì)算整型表達(dá)式E的值，然后將表達(dá)式的值依次和case后的常數(shù)ci比較，當(dāng)與某常數(shù)ci相等時(shí)就執(zhí)行語(yǔ)句Si，并結(jié)束多分支控制語(yǔ)句；若與諸常數(shù)均不相等，則執(zhí)行語(yǔ)句Sn+1。多分支控制語(yǔ)句switch常見的中間代碼形式如下：

E計(jì)值后存放在臨時(shí)單元T的中間代碼；

gototest；

P1: S1的中間代碼；

gotonext；

P2: S2的中間代碼；

gotonext；

Pn: Sn的中間代碼；

gotonext；

Pn+1: Sn+1的中間代碼；

gotonext；

test: if(T==c1)gotoP1；

if(T==c2)gotoP2；

if(T==cn)gotoPn；

if(T=='default')gotoPn+1；

next:進(jìn)行語(yǔ)義加工處理時(shí)應(yīng)先設(shè)置一空隊(duì)列queue，當(dāng)遇到ci時(shí)，將這個(gè)ci連同nxq(指向標(biāo)號(hào)ci后語(yǔ)句Si的入口)送入隊(duì)列queue，然后按通常的辦法產(chǎn)生語(yǔ)句Si的四元式。需要注意的是，在Si的四元式之后要有一個(gè)gotonext的四元式。當(dāng)處理完default:Sn+1之后，應(yīng)產(chǎn)生以test為標(biāo)號(hào)的n個(gè)條件轉(zhuǎn)移語(yǔ)句的四元式。這時(shí)，逐項(xiàng)讀出queue的內(nèi)容即可形成如下的四元式序列：

(case,c1,P1,_?) (case,c2,P2,_?) (case,cn,Pn,_?) (case,T.place,default,_?)其中，T.place是存放E值的臨時(shí)變量名，每個(gè)四元式(case,ci,Pi,_?)實(shí)際上代表一個(gè)如下的條件語(yǔ)句：

if(T==ci)gotoPi為了便于語(yǔ)法制導(dǎo)翻譯，我們給出了switch語(yǔ)句的文法和相應(yīng)的語(yǔ)義加工子程序如下：

(1)?A→switch(E)?{T.place=E.place；

F1.quad=nxq；

emit(j,_,_,0)； /*轉(zhuǎn)向test*/}

(2)?B→A{casec?{P=1；

queue[P].label=c；

queue[P].quad=nxq；}

(3)?D→B:S{生成S的四元式序列；

Backpatch(S.chain,nxq)；

B.quad=nxq；

emit(j,_,_,0)； /*轉(zhuǎn)向next*/}

(4)?D→F:S{生成S的四元式序列；

Backpatch(S.chain,nxq)；

B.quad=nxq；

emit(j,_,_,0)； /*轉(zhuǎn)向next*/ F.quad=merge(B.quad,F.quad)；

/*轉(zhuǎn)向next的語(yǔ)句拉成鏈*/}

(5)?F→D;casec?{P=P+1；

queue[P].label=c；

queue[P].quad=nxq；}

(6)?S→D;default:S} {生成S的四元式序列；

Backpatch(S.chain,nxq)；

B.quad=nxq；

emit(j,_,_,0)；

F.quad=merge(B.quad,F.quad);

/*形成轉(zhuǎn)向next的鏈?zhǔn)?/} P=P+1；

queue[P].label='default'；

queue[P].quad=nxq；

F3.quad=nxq；/*指向標(biāo)號(hào)test*/ m=1； do { ci=queue[m].label；

Pi=queue[m].quad；

m=m+1；

if(ci!='default')emit(case,ci,Pi,_) elseemit(case,T.place,default,_) }while(m<=P+1)；

Backpatch(F1.quad,F3.quad)；

Backpatch(F.quad,nxq)；

/*填寫所有轉(zhuǎn)向next語(yǔ)句的轉(zhuǎn)移地址*/}4.5.5語(yǔ)句標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句的翻譯程序語(yǔ)言中直接改變控制流程的語(yǔ)句是gotoL語(yǔ)句，其中L是源程序中的語(yǔ)句標(biāo)號(hào)。標(biāo)號(hào)L在源程序中可以以兩種方式出現(xiàn)：

(1)定義性出現(xiàn)。定義性出現(xiàn)的語(yǔ)句形式為

L：S此時(shí)，帶標(biāo)號(hào)的語(yǔ)句S所生成的第一個(gè)四元式地址即為標(biāo)號(hào)L的值。

(2)引用性出現(xiàn)。引用性出現(xiàn)的語(yǔ)句形式為

gotoL它引用L的值作為四元式(j,_,_,L)中轉(zhuǎn)向的目標(biāo)地址。對(duì)標(biāo)號(hào)L的處理方法是：當(dāng)標(biāo)號(hào)L定義性出現(xiàn)時(shí)，應(yīng)將標(biāo)號(hào)此時(shí)對(duì)應(yīng)的四元式地址(即標(biāo)號(hào)L的值)登錄到符號(hào)表中L所對(duì)應(yīng)的項(xiàng)；當(dāng)標(biāo)號(hào)L引用性出現(xiàn)時(shí)，則引用符號(hào)表中該標(biāo)號(hào)L的值。顯然，在源程序中，如果標(biāo)號(hào)的定義性出現(xiàn)在前而引用性出現(xiàn)在后，即先定值后引用(稱為向后引用)，則填、查符號(hào)表及將轉(zhuǎn)移語(yǔ)句翻譯成四元式很容易。但是，如果標(biāo)號(hào)引用性出現(xiàn)在前而定義性出現(xiàn)在后(稱為向前引用)，則引用時(shí)不可能從符號(hào)表中獲得標(biāo)號(hào)L的值，此時(shí)只能生成有待回填的四元式(j,_,_,0)，等到向前翻譯到標(biāo)號(hào)L定義性出現(xiàn)時(shí)，再將標(biāo)號(hào)L的值回填到待填的四元式中。翻譯gotoL語(yǔ)句時(shí)需要查符號(hào)表，看L是否定值，有以下幾種情況：

(1)?L已經(jīng)定值，即L.value為符號(hào)表中所記錄的L值，這時(shí)生成(j,_,_,L.value)語(yǔ)句。

(2)在符號(hào)表中未出現(xiàn)標(biāo)號(hào)L項(xiàng)，則gotoL中的L是首次出現(xiàn)，故生成(j,_,_,0)形式的語(yǔ)句并在符號(hào)表中登錄L項(xiàng)，給L項(xiàng)標(biāo)記為“未定值”并將四元式(j,_,_,0)的地址作為L(zhǎng)的值記入符號(hào)表(作為L(zhǎng)引用鏈的鏈頭)，以待L定值后回填。

(3)在符號(hào)表中已有標(biāo)號(hào)L項(xiàng)但未定值，此時(shí)的gotoL語(yǔ)句并非首次出現(xiàn)，故生成四元式(j,_,_,0)并將其地址掛入到L的引用鏈中，待L定值后再進(jìn)行回填。翻譯語(yǔ)句L：S時(shí)，在識(shí)別L后也要查符號(hào)表。如L為首次出現(xiàn)，則在符號(hào)表中建立L項(xiàng)，將此時(shí)的nxq值作為L(zhǎng)的值登入符號(hào)表并置“已定值”標(biāo)記；如果符號(hào)表中已有L項(xiàng)且標(biāo)記為“未定值”，這意味著是向前引用情況，應(yīng)將此時(shí)的nxq值作為L(zhǎng)的值登入符號(hào)表并置“已定值”，同時(shí)以此值回填L的引用鏈；若查找符號(hào)表發(fā)現(xiàn)L已定值，則表示L出現(xiàn)了重復(fù)定義的錯(cuò)誤。4.6數(shù)組元素的翻譯數(shù)組元素的地址計(jì)算及中間代碼形式賦值語(yǔ)句中數(shù)組元素的翻譯數(shù)組元素翻譯示例4.6.1數(shù)組元素的地址計(jì)算及中間代碼形式在表達(dá)式或賦值語(yǔ)句中若出現(xiàn)數(shù)組元素，則翻譯時(shí)將牽涉到數(shù)組元素的地址計(jì)算。數(shù)組在存儲(chǔ)器中的存放方式?jīng)Q定了數(shù)組元素的地址計(jì)算法，從而也決定了應(yīng)該產(chǎn)生什么樣的中間代碼。數(shù)組在存儲(chǔ)器中的存放方式通常有按行存放和按列存放兩種。在此，我們討論以行為主序存放方式的數(shù)組元素地址計(jì)算方法。數(shù)組的一般定義為A[l1:u1,l2:u2,…,lk:uk,…,ln:un]其中，A是數(shù)組名，lk是數(shù)組A第k維的下界，uk是第k維的上界。為簡(jiǎn)單起見，假定數(shù)組A中每個(gè)元素的存儲(chǔ)長(zhǎng)度為1，a是數(shù)組A的首地址，則數(shù)組元素A[i1,i2,…in]的地址D的計(jì)算公式如下：D=a+(i1?l1)d2d3…dn+(i2?l2)d3d4…dn+…+(in-1?ln?1)dn+(in?ln)其中，di=ui?li+1(i=1,2,…,n?1)。整理后得到D=CONSPART+VARPART其中，CONSPART=a?(…((l1d2+l2)d3+l3)d4+…+ln-1)dn+ln VARPART=(…((i1d2+i2)d3+i3)d4+…+in?1dn)+in

CONSPART中的各項(xiàng)(如li、di(i=1,2,…,n))在處理說(shuō)明語(yǔ)句時(shí)就可以得到，因此CONSPART值可在編譯時(shí)計(jì)算出來(lái)后保存在數(shù)組A的相關(guān)符號(hào)表項(xiàng)里。此后，在計(jì)算數(shù)組A的元素地址時(shí)僅需計(jì)算VARPART值，而直接引用CONSPART值。實(shí)現(xiàn)數(shù)組元素的地址計(jì)算時(shí)，將產(chǎn)生兩組四元式序列：一組計(jì)算CONSPART，其值存放在臨時(shí)變量T中；另一組計(jì)算VARPART，其值存放在臨時(shí)變量T1中，即用T1[T]表示數(shù)組元素的地址。這樣，對(duì)數(shù)組元素的引用和賦值就有如下兩種不同的四元式：

(1)變址存數(shù)：若有T1[T]=X，則可以用四元式([?]=，X，_，T1[T])表示。

(2)變址取數(shù)：若有X=T1[T]，則可用四元式(=[?]，T1[T]，_，X)表示。4.6.2賦值語(yǔ)句中數(shù)組元素的翻譯為了便于語(yǔ)法制導(dǎo)翻譯，我們定義一個(gè)含有數(shù)組元素的賦值語(yǔ)句文法G[A]如下：

G[A]：(1)?A→V=E (2)?V→i[elist]∣i (3)?elist→elist,E∣E (4)?E→E+E∣(E)∣V其中，A代表賦值語(yǔ)句；V代表變量名；E代表算術(shù)表達(dá)式；elist代表由逗號(hào)分隔的表達(dá)式，它表示數(shù)組的一維下標(biāo)；i代表簡(jiǎn)單變量名或數(shù)組名。在用產(chǎn)生式(2)、(3)進(jìn)行歸約時(shí)，為了能夠及時(shí)計(jì)算數(shù)組元素的VARPART，我們將產(chǎn)生式(2)、(3)改寫為

(2')?V→elist]∣i (3')?elist→elist,E∣i[E把數(shù)組名i和最左的下標(biāo)式寫在一起的目的是在整個(gè)下標(biāo)串elist的翻譯過(guò)程中隨時(shí)都能知道數(shù)組名i的符號(hào)表入口，從而隨時(shí)能夠了解登記在符號(hào)表中有關(guān)數(shù)組i的全部信息。為產(chǎn)生計(jì)算VARPART的四元式序列，還需要設(shè)置如下的語(yǔ)義變量和函數(shù)：

(1)?elist.ARRAY：表示數(shù)組名在符號(hào)表的入口。

(2)?elist.DIM：計(jì)數(shù)器，用來(lái)計(jì)算數(shù)組的維數(shù)。

(3)?elist.place：登錄已生成VARPART中間結(jié)果的單元名字在符號(hào)表中的存放位置，或是一個(gè)臨時(shí)變量的整數(shù)碼。

(4)?limit(ARRAY,k)：參數(shù)ARRAY表示數(shù)組名在符號(hào)表的入口，k表示數(shù)組當(dāng)前計(jì)算的維數(shù)；函數(shù)limit(?)計(jì)算數(shù)組ARRAY的第k維長(zhǎng)度dk。在逐次對(duì)elist歸約的過(guò)程中，將逐步產(chǎn)生計(jì)算VARPART的四元式。此外，每個(gè)變量V有兩項(xiàng)語(yǔ)義值：V.place和V.offset。?若V是一個(gè)簡(jiǎn)單變量名i，則V.place就是該變量名在符號(hào)表中的入口，而V.offset此時(shí)為null；若V是一個(gè)下標(biāo)變量名，則V.place是保存CONSPART的臨時(shí)變量名的整數(shù)碼，而V.offset則是保存VARPART的臨時(shí)變量名的整數(shù)碼。含有數(shù)組元素的賦值語(yǔ)句對(duì)應(yīng)的文法G[A]及相應(yīng)的語(yǔ)義子程序如下(省略語(yǔ)義檢查，僅給出主要語(yǔ)義動(dòng)作)：

(1)?A→V=E{if(V.offset==null)? emit(=,E.place,_,V.place);/*V是簡(jiǎn)單變量*/ elseemit([]=,E.place,_,V.place[V.offset]);

/*V是下標(biāo)變量*/}

(2)?E→E(1)+E(2)?{T=newtemp;emit(+,E(1).place,E(2).place,T);E.place=T;}

(3)?E→(E(1)){E.place=E(1).place;}

(4)?E→V{if(V.offset==null)? E.place=V.place; /*V是簡(jiǎn)單變量*/ else{T=newtemp;/*V是下標(biāo)變量*/? emit(=[],V.place[V.offset],_,T);