編譯原理第7章課件

第七章語(yǔ)義分析和中間代碼生成第七章語(yǔ)義分析和中間代碼生成緊接在詞法分析和語(yǔ)法分析之后，編譯程序要做的工作就是進(jìn)行靜態(tài)語(yǔ)義檢查和翻譯。靜態(tài)語(yǔ)義檢查(1)類型檢查。如果操作符作用于不相容的操作數(shù)，編譯程序必須報(bào)告出錯(cuò)信息。(2)控制流檢查?？刂屏髡Z(yǔ)句必須使控制轉(zhuǎn)移到合法的地方。

(3)一致性檢查。在很多場(chǎng)合要求對(duì)象只能被定義一次。

(4)相關(guān)名字檢查。其它如名字的作用域分析等。緊接在詞法分析和語(yǔ)法分析之后，編譯程序要做的工作就是進(jìn)行靜態(tài)使用中間語(yǔ)言的好處(1)便于進(jìn)行與機(jī)器無(wú)關(guān)的代碼優(yōu)化工作；(2)使編譯程序改變目標(biāo)機(jī)更容易；(3)使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確。以中間語(yǔ)言為界面，編譯前端和后端的接口更清晰。使用中間語(yǔ)言的好處編譯原理第7章課件本章內(nèi)容目錄中間語(yǔ)言后綴式圖表示法三地址代碼說(shuō)明語(yǔ)句過(guò)程中的說(shuō)明諳旬保留作用域信息記錄中的域名賦值語(yǔ)句的翻譯簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句數(shù)組元素的引用布爾表達(dá)式的翻譯數(shù)值表示法作為條件控制的布爾式翻譯控制語(yǔ)句的翻譯本章內(nèi)容目錄中間語(yǔ)言賦值語(yǔ)句的翻譯中間語(yǔ)言

幾種常見(jiàn)的中間語(yǔ)言形式

后綴式

三地址代碼（包括三元式、四元式、間接三元式）

DAG圖表示中間語(yǔ)言幾種常見(jiàn)的中間語(yǔ)言形式后綴式

后綴式表示法又稱逆波蘭表示法。這種表示法是把運(yùn)算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）。例如，把a(bǔ)十b寫成ab＋，把a(bǔ)*b寫成ab*。后綴式后綴式表示法又稱逆波蘭表示法。一個(gè)表達(dá)式E的后綴形式(1)如果E是一個(gè)變量或常量，則E的后綴式是E自身。(2)如果E是E1opE2形式的表達(dá)式，這里op是任何二元操作符，則E的后綴式為E1′E2′op，這里E1′和E2′分別為E1和E2的后綴式。(3)如果E是（E1）形式的表達(dá)式，則E1的后綴式就是E的后綴式。

后綴式表示法用不著使用括號(hào)。根據(jù)運(yùn)算量和算符出現(xiàn)的先后位置，以及每個(gè)算符的目數(shù)，就完全決定了一個(gè)表達(dá)式的分解。一個(gè)表達(dá)式E的后綴形式(1)如果E是一個(gè)變量或常量，則E的后只要知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都能對(duì)它正確進(jìn)行唯一分解。只要知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都圖表示法

包括DAG與抽象語(yǔ)法樹(shù)無(wú)循環(huán)有向圖（DirectedAcycliGraph簡(jiǎn)稱DAG）。 與抽象語(yǔ)法樹(shù)一樣，對(duì)表達(dá)式中的每個(gè)子表達(dá)式，DAG中都有一個(gè)結(jié)點(diǎn)。一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù)。 與抽象語(yǔ)法樹(shù)不同的是，在一個(gè)DAG中代公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)，而在一棵抽象語(yǔ)法樹(shù)中公共子表達(dá)式被表示為重復(fù)的子樹(shù)。圖表示法包括DAG與抽象語(yǔ)法樹(shù)例如，表達(dá)式a+a*(b-c)+(b-c)*d

例如，表達(dá)式a+a*(b-c)+(b-c)*d例如，表達(dá)式a+a*(b-c)+(b-c)*d

例如，表達(dá)式a+a*(b-c)+(b-c)*d編譯原理第7章課件編譯原理第7章課件后綴式即是對(duì)抽象語(yǔ)法樹(shù)的后續(xù)遍歷序列例：上圖中的抽象語(yǔ)法樹(shù)的后綴式是：abcuminus*bcuminu*+assign抽象語(yǔ)法樹(shù)的邊沒(méi)有顯式地出現(xiàn)在后綴式中，這些邊可以根據(jù)結(jié)點(diǎn)出現(xiàn)的次序及表示操作符的結(jié)點(diǎn)要求操作數(shù)的個(gè)數(shù)還原出來(lái)。后綴式即是對(duì)抽象語(yǔ)法樹(shù)的后續(xù)遍歷序列編譯原理第7章課件編譯原理第7章課件三地址代碼

三地址代碼是由下面一般形式的語(yǔ)句構(gòu)成的序列：x：=yopz其中,x,y,z為名字、常數(shù)或編譯時(shí)產(chǎn)生的臨時(shí)變量；op代表運(yùn)算符號(hào)如定點(diǎn)運(yùn)算符、浮點(diǎn)運(yùn)算符、邏輯運(yùn)算符等等。每個(gè)語(yǔ)句的右邊只能有一個(gè)運(yùn)算符。例如，源語(yǔ)言表達(dá)式x＋y*z可以被翻譯為如下語(yǔ)句序列：T1：＝y(tǒng)*zT2：＝x＋T1其中，Tl，T2為編譯時(shí)產(chǎn)生的臨時(shí)變量。三地址代碼三地址代碼是由下面一般形式的語(yǔ)句構(gòu)成的序列：三地址代碼可以看成是抽象語(yǔ)法樹(shù)或DAG的一種線性表示。

三地址代碼可以看成是抽象語(yǔ)法樹(shù)或DAG的一種線性表示。三地址語(yǔ)句類似于匯編語(yǔ)言代碼。語(yǔ)句可以帶有符號(hào)標(biāo)號(hào)，而且存在各種控制流語(yǔ)句。符號(hào)標(biāo)號(hào)代表存放中間代碼的數(shù)組中三地址代碼語(yǔ)句的下標(biāo)。下面列出所使用的三地址語(yǔ)句的種類。（1)形如x:＝y(tǒng)opz的賦值語(yǔ)句，其中op為二元算術(shù)算符或邏輯算符。(2)形如x:＝opy的贖值語(yǔ)句，其中op為一元算符，如一元減ununus,邏輯非not,移位算符及轉(zhuǎn)換算符（如將定點(diǎn)數(shù)轉(zhuǎn)換成浮點(diǎn)數(shù)）。(3)形如x:=y的復(fù)制語(yǔ)句，它將y的值賦給x。(4)形如gotoL的無(wú)條件轉(zhuǎn)移語(yǔ)句，即下一條將被執(zhí)行的語(yǔ)句是帶標(biāo)號(hào)L的三地址語(yǔ)句。三地址語(yǔ)句類似于匯編語(yǔ)言代碼。語(yǔ)句可以帶有符號(hào)標(biāo)號(hào)，而且存在

(5)形如ifxrelopygotoL或ifagotoL的條件轉(zhuǎn)移語(yǔ)句。第一種形式語(yǔ)句施用關(guān)系運(yùn)算符號(hào)relop（如＜，＝，＞，=等等）于x和y,若x與y滿足關(guān)系relop,那么下面就執(zhí)行帶標(biāo)號(hào)L的語(yǔ)句，否則下面就繼續(xù)執(zhí)行if語(yǔ)句之后的語(yǔ)句。第二種形式的語(yǔ)句中，a為布爾變量或常量，若a為真，則執(zhí)行帶標(biāo)號(hào)L的語(yǔ)句，否則執(zhí)行后一條語(yǔ)句。(6)用于過(guò)程調(diào)用的語(yǔ)句paramx和callp,n,以及返回語(yǔ)句returny.源程序中的過(guò)程調(diào)用語(yǔ)句P(xl，x2，…，xn）通常產(chǎn)生如下的三地址代碼：paramx1paramx2……paramxncallp,n其中n表示實(shí)參個(gè)數(shù)。過(guò)程返回語(yǔ)句retumy中y為過(guò)程返回的一個(gè)值。(5)形如ifxrelopygotoL或(7)形如x:=y[i]及x[i]:=y的索引賦值。前者把相對(duì)于地址y的后面第i個(gè)單元里的值賦給x。后者把y的值賦給相對(duì)于地址x后面的第i個(gè)單元。（8）形如x:=&y,x:=*y和*x:=y的地址和指針賦值。其中第一個(gè)賦值語(yǔ)句把y的地址賦給x。假定y是個(gè)名字，或者是一個(gè)臨時(shí)變量，代表一個(gè)具有左值的表達(dá)式，例如A[i,j]；并且x是一個(gè)指針名字或臨時(shí)變量。也就是說(shuō),x的右值將被賦予對(duì)象y的左值。第二個(gè)賦值語(yǔ)句x:=*y，假定y是一個(gè)指針或者是一個(gè)其右值為地址的臨時(shí)變量。此語(yǔ)句執(zhí)行的結(jié)果是把y所指示的地址單元里存放的內(nèi)容賦給x.第三個(gè)賦值語(yǔ)句*x:=y,將把x所指向的對(duì)象的右值賦給y的右值。(7)形如x:=y[i]及x[i]:=y的在設(shè)計(jì)中間代碼形式時(shí)，運(yùn)算符的選擇是非常重要的。顯然，算符種類應(yīng)足以用來(lái)實(shí)現(xiàn)源語(yǔ)言中的運(yùn)算。一個(gè)小型算符集合較易于在新的目標(biāo)機(jī)器上實(shí)現(xiàn)。然而，用局限的指令集合會(huì)使某些源語(yǔ)言運(yùn)算表示成中間形式時(shí)代碼加長(zhǎng)，從而需要在目標(biāo)代碼生成時(shí)做較多的工作以獲得高效的代碼。在設(shè)計(jì)中間代碼形式時(shí)，運(yùn)算符的選擇是非常重要的。生成三地址代碼時(shí)，臨時(shí)變量的名字對(duì)應(yīng)抽象語(yǔ)法樹(shù)的內(nèi)部結(jié)點(diǎn)。對(duì)于產(chǎn)生式E→E1＋E2的左端的非終結(jié)符號(hào)E而言，它的經(jīng)過(guò)計(jì)算得出的值往往放到一個(gè)新的臨時(shí)變量T中。一般說(shuō)來(lái)，賦值語(yǔ)句id:=E的三地址代碼包括： 對(duì)表達(dá)式E求值并置于變量T中，然后進(jìn)行賦值id.place:=T. 如果一個(gè)表達(dá)式僅有一單個(gè)標(biāo)識(shí)符，例如Y,則由Y自身保留表達(dá)式的值。

生成三地址代碼時(shí)，臨時(shí)變量的名字對(duì)應(yīng)抽象語(yǔ)法樹(shù)的內(nèi)部結(jié)點(diǎn)。下表是為賦值語(yǔ)句生成三地址代碼的S-屬性文法定義。如給定輸入a:=b*-c+b*-c。非終結(jié)符號(hào)S有綜合屬性S.code,它代表賦值語(yǔ)句S的三地址代碼。非終結(jié)符號(hào)E有如下兩個(gè)屬性：（1)E.place表示存放E值的名字；(2)E.code表示對(duì)E求值的三地址語(yǔ)句序列。函數(shù)newtemp的功能是，每次調(diào)用它時(shí)，將返回一個(gè)不同臨時(shí)變量名字，如T1，T2，…。為了方便，我們?cè)诒硎褂胓en(x‘：＝’y‘+’z)表示生成三地址語(yǔ)句x:=y十z.代替x,y或z出現(xiàn)的表達(dá)式在傳遞給gen時(shí)求值，用單引號(hào)括起來(lái)的運(yùn)算符或操作數(shù)將保留引號(hào)里字面的符號(hào)。下表是為賦值語(yǔ)句生成三地址代碼的S-屬性文法定義。編譯原理第7章課件三地址語(yǔ)句可看成中間代碼的一種抽象形式。編譯程序中，三地址代碼語(yǔ)句的具體實(shí)現(xiàn)可以用記錄表示，記錄中包含表示運(yùn)算符和操作數(shù)的域。通常有三種表示方法：四元式、三元式、間接三元式。三地址語(yǔ)句可看成中間代碼的一種抽象形式。四元式一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為op、arg1,arg2及result.域op包含一個(gè)代表運(yùn)算符的內(nèi)部碼。三地址語(yǔ)句x:＝y(tǒng)opz可表示為：將y置于argl域，置于arg2域，x置于result域，：＝為算符。帶有一元運(yùn)算符的語(yǔ)句如：x:=-y或者x:=y的表示中不用arg2.而像param這樣的運(yùn)算符僅使用argl域。條件和無(wú)條件轉(zhuǎn)移語(yǔ)句將目標(biāo)標(biāo)號(hào)置于result域中。四元式一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為三元式

為了避免把臨時(shí)變量填入到符號(hào)表，可以通過(guò)計(jì)算這個(gè)臨時(shí)變量值的語(yǔ)句的位置來(lái)引用這個(gè)臨時(shí)變量。這樣表示三地址代碼的記錄只需三個(gè)域：op、argl和arg2

三元式為了避免把臨時(shí)變量填入到符號(hào)表，可以通過(guò)計(jì)算這個(gè)臨時(shí)編譯原理第7章課件間接三元式

為了便于代碼優(yōu)化處理，有時(shí)不直接使用三元式表，而是另設(shè)一張指示器（稱為間接碼表），它將按運(yùn)算的先后順序列出有關(guān)三元式在三元表中的位置。換句話說(shuō)就是，用一張間接碼表輔以三元式表的辦法來(lái)表示中間代碼。這種表示法稱為間接三元式。間接三元式為了便于代碼優(yōu)化處理，有時(shí)不直接使用三元式表，而例如，語(yǔ)句X:=（A＋B）*C；Y:=D↑（A＋B)的間接三元式表示如表所示。例如，語(yǔ)句四元式與三元式和間接三元式作一些比較

四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的。這一點(diǎn)和三元式不同。要更動(dòng)一張三元表是很困難的，它意味著必須改變其中一系列指示器的值。但要更動(dòng)四元式表是很容易的，因?yàn)檎{(diào)整四元式之間的相對(duì)位置并不意味著必須改變其中一系列指示器的值。因此，當(dāng)需要對(duì)中間代碼進(jìn)行優(yōu)化處理時(shí)，四元式比三元式要方便得多。對(duì)優(yōu)化這一點(diǎn)而言，四元式和間接三元式同樣方便。四元式與三元式和間接三元式作一些比較四元式之間的聯(lián)系是通過(guò)說(shuō)明語(yǔ)句

當(dāng)考查一個(gè)過(guò)程或分程序的一系列說(shuō)明語(yǔ)句時(shí)，便可為局部于該過(guò)程的名字分配存儲(chǔ)空間。對(duì)每個(gè)局部名字，我們都將在符號(hào)表中建立相應(yīng)的表項(xiàng)，并填入有關(guān)的信息如類型、在存儲(chǔ)器中的相對(duì)地址等。相對(duì)地址是指對(duì)靜態(tài)數(shù)據(jù)區(qū)基址或活動(dòng)記錄中局部數(shù)據(jù)區(qū)基址的一個(gè)偏移量。說(shuō)明語(yǔ)句當(dāng)考查一個(gè)過(guò)程或分程序的一系列說(shuō)明語(yǔ)句時(shí)，便可為局當(dāng)產(chǎn)生中間代碼地址時(shí)，對(duì)目標(biāo)機(jī)一些情況做到心中有數(shù)是有好處的。例如，假定在一個(gè)以字節(jié)編址的目標(biāo)機(jī)上，整數(shù)必須存放在4的倍數(shù)的地址單元，那么，計(jì)算地址時(shí)就應(yīng)以4的倍數(shù)增加。當(dāng)產(chǎn)生中間代碼地址時(shí)，對(duì)目標(biāo)機(jī)一些情況做到心中有數(shù)是有好處的過(guò)程中的說(shuō)明語(yǔ)句

在C,Pascal及FORTRAN等語(yǔ)言的語(yǔ)法中，允許在一個(gè)過(guò)程中的所有說(shuō)明語(yǔ)句作為一個(gè)組來(lái)處理，把它們安排在一所數(shù)據(jù)區(qū)中。從而需要一個(gè)全程變量如offset來(lái)跟蹤下一個(gè)可用的相對(duì)地址的位置。過(guò)程中的說(shuō)明語(yǔ)句在C,Pascal及FORTRAN等語(yǔ)言在下圖關(guān)于說(shuō)明語(yǔ)句的翻譯模式中，非終結(jié)符號(hào)P產(chǎn)生一系列形如id：T的說(shuō)明語(yǔ)句。在處理第一條說(shuō)明語(yǔ)句之前，先置offset為0，以后每次遇到一個(gè)新的名字，便將該名字填入符號(hào)表中并置相對(duì)地址為當(dāng)前offset之值，然后使offset加上該名字所表示的數(shù)據(jù)對(duì)象的域?qū)?。在下圖關(guān)于說(shuō)明語(yǔ)句的翻譯模式中，非終結(jié)符號(hào)P產(chǎn)生一系列形如i編譯原理第7章課件過(guò)程enter(name,type,offset）用來(lái)把名字name填入到符號(hào)表中，并給出此名字的類型type及在過(guò)程數(shù)據(jù)區(qū)中的相對(duì)地址offset。非終結(jié)符號(hào)T有兩個(gè)綜合屬性T.type和T.width，分別表示名字的類型和名字的域?qū)挘丛擃愋兔炙加玫拇鎯?chǔ)單元個(gè)數(shù)）。在圖中,假定整數(shù)類型域?qū)挒?；實(shí)數(shù)域?qū)挒?;一個(gè)數(shù)組的域?qū)捒梢酝ㄟ^(guò)把數(shù)組元素?cái)?shù)目與一個(gè)元素的域?qū)捪喑双@得；每個(gè)指針類型的域?qū)捈俣?.過(guò)程enter(name,type,offset）用來(lái)把如果把圖中的第一條產(chǎn)生式及其語(yǔ)義動(dòng)作寫在一行，則對(duì)offset賦初值更明顯，如下式所示：

P→｛offset:=0｝D（7．1）前面曾談到產(chǎn)生ε的標(biāo)記非終結(jié)符號(hào)，可以用它來(lái)重新改寫上述產(chǎn)生式以便語(yǔ)義動(dòng)作均出現(xiàn)在整個(gè)產(chǎn)生式的右邊。我們可采用標(biāo)記非終結(jié)符號(hào)M來(lái)重寫式（7.1）：P→MDM→ε{offset:=0}如果把圖中的第一條產(chǎn)生式及其語(yǔ)義動(dòng)作寫在一行，則對(duì)offse保留作用域信息

允許嵌套過(guò)程的語(yǔ)言，對(duì)于每一個(gè)過(guò)程，其中局部名字的相對(duì)地址計(jì)算可以采用圖7.6的方法。而當(dāng)遇到一個(gè)嵌入的過(guò)程說(shuō)明時(shí)，則應(yīng)當(dāng)暫停包圍此過(guò)程的外圍過(guò)程說(shuō)明語(yǔ)句的處理。這種方法可以通過(guò)加入到如下的語(yǔ)言把有關(guān)語(yǔ)義動(dòng)作來(lái)說(shuō)明。P→DD→D;D|id：T|procid：D；S(7．2)由于我們當(dāng)前的目標(biāo)是考慮說(shuō)明語(yǔ)句，因而對(duì)其中產(chǎn)生語(yǔ)句的非終結(jié)符號(hào)S及產(chǎn)生類型的非終結(jié)符號(hào)T的產(chǎn)生式我們沒(méi)有給出。與圖7.6中相同．T有兩個(gè)綜合屬性type和width。保留作用域信息允許嵌套過(guò)程的語(yǔ)言，對(duì)于每一個(gè)過(guò)程，其中局部假定對(duì)于式(7．2)的語(yǔ)言的每一個(gè)過(guò)程都有一張獨(dú)立的符號(hào)表。這種符號(hào)表可用鏈表實(shí)現(xiàn)。當(dāng)碰到過(guò)程說(shuō)明D→procid；D,；S時(shí)，便創(chuàng)建一張新的符號(hào)表，并且把在D，中的所有說(shuō)明項(xiàng)都填入此符號(hào)表內(nèi)。新表有一個(gè)指針指向剛好包圍該嵌入過(guò)程的外圍過(guò)程的符號(hào)表，由id表示的過(guò)程名字作為該外圍過(guò)程的局部名字。對(duì)圖7.6處理變量說(shuō)明的唯一修改是，要告訴enter在哪個(gè)符號(hào)表填入一項(xiàng)。假定對(duì)于式(7．2)的語(yǔ)言的每一個(gè)過(guò)程都有一張獨(dú)立的符號(hào)表。在下面的語(yǔ)義規(guī)則中用到如下操作。(1)mktable(previous)創(chuàng)建一張新符號(hào)表，并返回指向新表的一個(gè)指針。參數(shù)previous指向一張先前創(chuàng)建的符號(hào)表，譬如剛好包圍嵌入過(guò)程的外圍過(guò)程符號(hào)表。指針previous之值放在新符號(hào)表表頭，表頭中還可存放一些其它信息如過(guò)程嵌套深度等等。我們也可以按過(guò)程被說(shuō)明的順序?qū)^(guò)程編號(hào)，并把這一編號(hào)填入表頭。(2)enter(table，name，type,offset）在指針table指示的符號(hào)表中為名字name建立一個(gè)新項(xiàng)，并把類型type、相對(duì)地址offset填入到該項(xiàng)中。(3)addwidth(table,width)在指針table指示的符號(hào)表表頭中記錄下該表中所有名字占用的總寬度。(4)enterpcoc(table，name，newtable）在指針table指示的符號(hào)表中為名字為name的過(guò)程建立一個(gè)新項(xiàng)。參數(shù)newtable指向過(guò)程name的符號(hào)表。在下面的語(yǔ)義規(guī)則中用到如下操作。在下圖中的翻譯模式給出了如何在一遍掃描中對(duì)數(shù)據(jù)進(jìn)行處理，它使用了一個(gè)棧tblptr保存各外層過(guò)程的符號(hào)表指針。當(dāng)處理過(guò)程partition中的說(shuō)明語(yǔ)句時(shí)，棧tblprt中將包括指向sort,quicksortRpartition的符號(hào)表的指針。指向當(dāng)前符號(hào)表的指針在棧頂。另一個(gè)棧offset存放各嵌套過(guò)程的當(dāng)前相對(duì)地址。offset的棧頂元素為當(dāng)前被處理過(guò)程的下一個(gè)局部名字的相對(duì)地址。在下圖中的翻譯模式給出了如何在一遍掃描中對(duì)數(shù)據(jù)進(jìn)行處理，它使編譯原理第7章課件編譯原理第7章課件編譯原理第7章課件記錄中的域名

除了基本類型、指針和數(shù)組外，下述產(chǎn)生式使非終結(jié)符號(hào)T產(chǎn)生記錄類型：T→recordDend當(dāng)遇到保留字record時(shí)，與標(biāo)記非終結(jié)符號(hào)L相應(yīng)的語(yǔ)義動(dòng)作為記錄中的各域名創(chuàng)建一張新的記錄符號(hào)表。把指向該表的指針壓人棧tblptr中，并把相對(duì)地址。壓入棧offset中。記錄中的域名除了基本類型、指針和數(shù)組外，下述產(chǎn)生式使非終結(jié)編譯原理第7章課件賦值語(yǔ)句的翻譯

賦值語(yǔ)句中的表達(dá)式的類型可以是整型、實(shí)型、數(shù)組和記錄。作為翻譯賦值語(yǔ)句為三地址代碼的一個(gè)部分，將討論如何在符號(hào)表中查找名字及如何存取數(shù)組和記錄的元素。賦值語(yǔ)句的翻譯賦值語(yǔ)句中的表達(dá)式的類型可以是整型、實(shí)型、數(shù)簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句

屬性表示id所代表的名字本身。過(guò)程lookup(id.nam）檢查是否在符號(hào)表中存在相應(yīng)此名字的入口。如果有，則返回一個(gè)指向該表項(xiàng)的指針，否則，返回nil表示沒(méi)有找到。在語(yǔ)義動(dòng)作中，調(diào)用過(guò)程emit將生成的三地址語(yǔ)句發(fā)送到輸出文件中．簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句屬性表示id所代表假定賦值語(yǔ)句出現(xiàn)在如下文法形成的上下文環(huán)境中：P→MDM→εD→D;D|id:T|procid;ND;SN→ε

如果把這些產(chǎn)生式加到下面文法中，非終結(jié)符P就變?yōu)殚_(kāi)始符號(hào)。假定賦值語(yǔ)句出現(xiàn)在如下文法形成的上下文環(huán)境中：編譯原理第7章課件數(shù)組元素的引用

現(xiàn)在討論包含數(shù)組元素的表達(dá)式和賦值句的翻譯問(wèn)題。數(shù)組在存儲(chǔ)器中的存放方式?jīng)Q定了數(shù)組元素的地址計(jì)算法，從而也決定了應(yīng)該產(chǎn)生什么樣的中間代碼。數(shù)組元素的引用現(xiàn)在討論包含數(shù)組元素的表達(dá)式和賦值句的翻譯問(wèn)若數(shù)組A的元素存放在一片連續(xù)單元里，則可以較容易地訪問(wèn)數(shù)組的每個(gè)元素。假設(shè)數(shù)組A每個(gè)元素寬度為w，則A[i]這個(gè)元素的起始地址為base+(i-low)*w其中:low為數(shù)組下標(biāo)的下界,base是分配給數(shù)組的相對(duì)地址，即base為A的第一個(gè)元素A[low]的相對(duì)地址。變形整理得：i*w＋（base一low*w)其中子表達(dá)式C=base-low*w可以在處理數(shù)組說(shuō)明時(shí)計(jì)算出來(lái)。我們假定C值存放在符號(hào)表中數(shù)組A的對(duì)應(yīng)項(xiàng)中，則A[i]相對(duì)地址可由i*w十C計(jì)算出來(lái).若數(shù)組A的元素存放在一片連續(xù)單元里，則可以較容易地訪問(wèn)數(shù)組的二維數(shù)組可以按行或按列存放。若二維數(shù)組A按行存放，則可用如下公式計(jì)算A[il，i2]的相對(duì)地址：base＋（（i1-low1）*n2＋i1-low2）*w可以重寫上述表達(dá)式為((i1*n2)＋i2)*w＋(base-((low1*n2)＋low2)*w)后一項(xiàng)子表達(dá)式(base-（(low1*n2)+low*w2)*w)的值是可以在編譯時(shí)確定的.二維數(shù)組可以按行或按列存放。如果在文法中id出現(xiàn)的地方允許下面產(chǎn)生式中L出現(xiàn)，則可把數(shù)組元素引用加入到賦值語(yǔ)句中。

L→id[Elist]|idElist→Elist,E|E改寫上述產(chǎn)生式為L(zhǎng)→Elist]|idElist→Elist，E|id［E如果在文法中id出現(xiàn)的地方允許下面產(chǎn)生式中L出現(xiàn)，則可把數(shù)組Elist.ndim記錄Elist中的下標(biāo)表達(dá)式的個(gè)數(shù)，即維數(shù)。函數(shù)limit(array,j)返回nj,即由array所指示的數(shù)組的第j維長(zhǎng)度。最后Elist.place表示臨時(shí)變量，用來(lái)臨時(shí)存放由Elist中的下標(biāo)表達(dá)式計(jì)算出來(lái)的值。一個(gè)Elist可以產(chǎn)生一個(gè)k-維數(shù)組引用A[i1,i2,…,ik]的前m維下標(biāo)，并將生成計(jì)算下面式子的三地址代碼：（…（(i1n2＋i2)n3＋i3)...）nm+im利用如下的遞歸公式進(jìn)行計(jì)算：e1=i1，em＝em-1*nm+im于是，當(dāng)m=k時(shí)將ek乘以元素域?qū)抴便可計(jì)算出式中的第一個(gè)子項(xiàng)。Elist.ndim記錄Elist中的下標(biāo)表達(dá)式的個(gè)數(shù)，即下面考慮在賦值語(yǔ)句中加入數(shù)組元素之后的翻譯模式，我們將把語(yǔ)義動(dòng)作加入到如下文法中：（1）S→L:=E(2）E→E＋E(3）E→（E)(4）E→L(5）L→Elist](6)L→id(7)Elist→Elist，E(8）Elist→id[E下面考慮在賦值語(yǔ)句中加入數(shù)組元素之后的翻譯模式，我們將把語(yǔ)義在語(yǔ)義動(dòng)作中由emit過(guò)程產(chǎn)生三地址代碼。若L是一個(gè)簡(jiǎn)單的名字，將生成一般的賦值；否則，若L為數(shù)組元素引用，則生成對(duì)L所指示地址的索引賦值。在語(yǔ)義動(dòng)作中由emit過(guò)程產(chǎn)生三地址代碼。例：設(shè)A為一個(gè)10*20的數(shù)組，即n1＝10，n2=20，并設(shè)w＝4。對(duì)賦值語(yǔ)句x：=A[y，z]的帶注釋的語(yǔ)法分析樹(shù)見(jiàn)圖7.12.該賦值語(yǔ)句被翻譯成如下三地址語(yǔ)句序列：T1:=y*20T1:=T1+zT2:=A-84T3:=4*T1T4:=T2[T3]X:=T4例：設(shè)A為一個(gè)10*20的數(shù)組，即n1＝10，n2=20，并編譯原理第7章課件布爾表達(dá)式的翻譯

在程序設(shè)計(jì)語(yǔ)言中，布爾表達(dá)式有兩個(gè)基本的作用：一個(gè)是用作計(jì)算邏輯值；另一個(gè)是用作控制流語(yǔ)句如if-then,if–then-else和while-do等之中的條件表達(dá)式。布爾表達(dá)式是用布爾運(yùn)算符號(hào)（and，or，not）作用到布爾變量或關(guān)系表達(dá)式上而組成的。關(guān)系表達(dá)式形如E1relopE2，其中E1和E2是算術(shù)表達(dá)式，relop為關(guān)系運(yùn)算符（＜，<=，=，，＞，>=）?？紤]由下列文法產(chǎn)生的布爾表達(dá)式：E→EorE|EandE|notE|（E)|idrelopid|id布爾表達(dá)式的翻譯在程序設(shè)計(jì)語(yǔ)言中，布爾表達(dá)式有兩個(gè)基本的作計(jì)算布爾表達(dá)式的值通常有兩種辦法。一是如同計(jì)算算術(shù)表達(dá)式一樣，一步不差地從表達(dá)式各部分的值計(jì)算出整個(gè)表達(dá)式的值。另一種計(jì)算法是采取某種優(yōu)化措施:把AorB解釋成ifAthentrueelseB把AandB解釋成ifAthenBelsefalse把notA解釋成ifAthenfalseelsetrue計(jì)算布爾表達(dá)式的值通常有兩種辦法。數(shù)值表示法

布爾表達(dá)式將從左到右按類似算術(shù)表達(dá)式的求值方法來(lái)計(jì)算。例如，對(duì)于布爾表達(dá)式：aorbandnotc將被翻譯成如下三地址序列：T1：＝notcT2：=bandT1T3：=aorT2數(shù)值表示法布爾表達(dá)式將從左到右按類似算術(shù)表達(dá)式的求值方法來(lái)一個(gè)形如a＜b的關(guān)系表達(dá)式可等價(jià)地寫成ifa＜bthen1else0，并可將它翻譯成如下三地址語(yǔ)句序列（我們假定語(yǔ)句序號(hào)從100開(kāi)始）：100:ifa＜bgoto103101：T:=0102:goto104103：T:＝1104:一個(gè)形如a＜b的關(guān)系表達(dá)式可等價(jià)地寫成編譯原理第7章課件編譯原理第7章課件作為條件控制的布爾式翻譯

出現(xiàn)在條件語(yǔ)句ifEthenS1elseSz2中的布爾表達(dá)式E，它的作用僅在于控制對(duì)S1和S2的選擇。只要能夠完成這一使命，E的值就無(wú)須最終保留在某個(gè)臨時(shí)單元之中。因此，作為轉(zhuǎn)移條件的布爾式E，我們可以賦予它兩種“出口”。一是“真”出口，出向S1；一是“假”出口，出向S2。

作為條件控制的布爾式翻譯出現(xiàn)在條件語(yǔ)句編譯原理第7章課件編譯原理第7章課件例7．3考慮如下表達(dá)式：a＜borc＜dande＜f假定整個(gè)表達(dá)式的真假出口已分別置為L(zhǎng)true和Lfalse，則按表7.7的定義將生成如下的代碼：ifa＜bgotoLtruegotoL1L1：ifc＜dgotoL2gotoLfalseL2：ife＜fgotoLtrungotoLfalse自然，這里的代碼是未優(yōu)化的，有冗余的指令。例7．3考慮如下表達(dá)式：下面討論如何通過(guò)一遍掃描來(lái)產(chǎn)生布爾表達(dá)式的代碼。為了便于討論，我們假設(shè)下面在實(shí)現(xiàn)三地址代碼時(shí)，采用四元式形式實(shí)現(xiàn)。把四元式存入一個(gè)數(shù)組中，數(shù)組下標(biāo)就代表四元式的標(biāo)號(hào)。四元式(jnz,a,-,p)表示ifagotop四元式(jmp,x,y,p)表示ifxropygotop四元式(j,-,-,p)表示gotop下面討論如何通過(guò)一遍掃描來(lái)產(chǎn)生布爾表達(dá)式的代碼。通過(guò)一遍掃描來(lái)產(chǎn)生布爾表達(dá)式和控制流語(yǔ)句的代碼的主要問(wèn)題在于，當(dāng)生成某些轉(zhuǎn)移語(yǔ)句時(shí)我們可能還不知道該語(yǔ)句將要轉(zhuǎn)移到的標(biāo)號(hào)究竟是什么。為了解決這個(gè)問(wèn)題，我們可以在生成形式分支的跳轉(zhuǎn)指令時(shí)暫時(shí)不確定跳轉(zhuǎn)目標(biāo)，而建立一個(gè)鏈表，把轉(zhuǎn)向這個(gè)目標(biāo)的跳轉(zhuǎn)指令的標(biāo)號(hào)鍵人這個(gè)鏈表。一旦目標(biāo)確定之后再把它填人有關(guān)的跳轉(zhuǎn)指令中。這種技術(shù)稱為回填。通過(guò)一遍掃描來(lái)產(chǎn)生布爾表達(dá)式和控制流語(yǔ)句的代碼的主要問(wèn)題在于為非終結(jié)符E賦予兩個(gè)綜合屬性E．truelist和E．falselist。它們分別記錄布爾表達(dá)式E所應(yīng)的四元式中需回填“真”、“假”出口的四元式的標(biāo)號(hào)所構(gòu)成的鏈表。具體實(shí)現(xiàn)時(shí)，我們可以借助于需要回填的跳轉(zhuǎn)四元式的第四區(qū)段來(lái)構(gòu)造這種鏈為非終結(jié)符E賦予兩個(gè)綜合屬性E．truelist和E．fal（1)變量nextquad,它指向下一條將要產(chǎn)生但尚未形式的四元式的地址（標(biāo)號(hào)）。nextquad的初值為1，每當(dāng)執(zhí)行一次emit之后，nextquad將自動(dòng)增1.(2)函數(shù)makelist(i)，它將創(chuàng)建一個(gè)僅含i的新鏈表，其中i是四元式數(shù)組的一個(gè)下標(biāo)（標(biāo)號(hào)）；函數(shù)返回指向這個(gè)鏈的指針。(3)函數(shù)merge(p1.p2),把以p1fnp2為鏈?zhǔn)椎膬蓷l鏈合并為一，作為函數(shù)值，回送合并后的鏈?zhǔn)住?4)過(guò)程backpatch(p,t)，其功能是完成“回填”，把p所鏈接的每個(gè)四元式的第四區(qū)段都填為t.（1)變量nextquad,它指向下一條將要產(chǎn)生但尚未形式的現(xiàn)在，我們來(lái)構(gòu)造一個(gè)翻譯模式，使之能在自底向上的分析過(guò)程中生成布爾表達(dá)式的四元式代碼。我們?cè)谖姆ㄖ胁迦肓藰?biāo)記非終結(jié)符M，以便在適當(dāng)?shù)臅r(shí)候執(zhí)行一個(gè)語(yǔ)義動(dòng)作，記下下一個(gè)將要產(chǎn)生的四元式標(biāo)號(hào)。我們使用的文法如下：（1）E→E1orME2(2）|E,1andME2(3)|notE1(4)|(E1）(5)|id1relopid2(6)|id(7)M→ε現(xiàn)在，我們來(lái)構(gòu)造一個(gè)翻譯模式，使之能在自底向上的分析過(guò)程中生例7.4重新考慮表達(dá)式a＜borc＜dande＜f.一棵作了注釋的分析樹(shù)如圖7．16所示。語(yǔ)義動(dòng)作是在對(duì)樹(shù)的深度優(yōu)先遍歷中完成的。由于所有的語(yǔ)義動(dòng)作均出現(xiàn)在產(chǎn)生式的右端的終點(diǎn)，因而它們可以在自下而上的語(yǔ)法分析中隨著對(duì)產(chǎn)生式的歸約來(lái)完成。按照上面所考慮的一些思想，構(gòu)造出布爾表達(dá)式的翻譯模式如下(如書(shū)P190)例7.4重新考慮表達(dá)式按照上面所考慮的一些思想，構(gòu)造出布編譯原理第7章課件100(j＜，a,b,0)101（j，-，-，0)102(j＜，c，d，104)103（j，-，-，0)104(j＜，e,f,0)105（i，-，-，0)100(j＜，a,b,0)101（j，-，-，102)102(j＜，c,d,104)103（i，-，-，0)104(i＜，e,f,0)105（i，-，-，0)100(j＜，a,b,0)100(j＜，a,b,控制語(yǔ)句的翻譯控制流語(yǔ)句if-then，if–then-else,while-do文法如下：S→ifEthenS1|ifEthenS1elseS2

|whileEdoS1其中E為布爾表達(dá)式?？刂普Z(yǔ)句的翻譯控制流語(yǔ)句編譯原理第7章課件編譯原理第7章課件例7.5考慮如下語(yǔ)句whilea<bdoifc<dthenx:=y+zelsex:=y-z根據(jù)上述屬性文法和賦值語(yǔ)句的翻譯模式，將生成下列代碼L1:ifa<bgotoL2gotoLnextL2:ifc<dgotoL3gotoL4L3:T1:=y+z;x:=T1gotoL1L4:T2:=y-zx:=T2gotoL1Lnext:例7.5考慮如下語(yǔ)句例7.6按照上述的語(yǔ)義動(dòng)作，加上前述關(guān)于賦值句和布爾表達(dá)式的翻譯法，語(yǔ)句while(a<b)doif(c<d)thenx:=y+z;將被翻譯成如下的一串四元式：100(j<,a,b,102)101(j,-,-,107)102(j<,c,d,104)103(j,-,-,100)104(+,y,z,T)105(:=,T,-,x)106(j,-,-,100)107例7.6按照上述的語(yǔ)義動(dòng)作，加上前述關(guān)于賦值句和布爾表達(dá)式第七章語(yǔ)義分析和中間代碼生成第七章語(yǔ)義分析和中間代碼生成緊接在詞法分析和語(yǔ)法分析之后，編譯程序要做的工作就是進(jìn)行靜態(tài)語(yǔ)義檢查和翻譯。靜態(tài)語(yǔ)義檢查(1)類型檢查。如果操作符作用于不相容的操作數(shù)，編譯程序必須報(bào)告出錯(cuò)信息。(2)控制流檢查?？刂屏髡Z(yǔ)句必須使控制轉(zhuǎn)移到合法的地方。

(3)一致性檢查。在很多場(chǎng)合要求對(duì)象只能被定義一次。

(4)相關(guān)名字檢查。其它如名字的作用域分析等。緊接在詞法分析和語(yǔ)法分析之后，編譯程序要做的工作就是進(jìn)行靜態(tài)使用中間語(yǔ)言的好處(1)便于進(jìn)行與機(jī)器無(wú)關(guān)的代碼優(yōu)化工作；(2)使編譯程序改變目標(biāo)機(jī)更容易；(3)使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確。以中間語(yǔ)言為界面，編譯前端和后端的接口更清晰。使用中間語(yǔ)言的好處編譯原理第7章課件本章內(nèi)容目錄中間語(yǔ)言后綴式圖表示法三地址代碼說(shuō)明語(yǔ)句過(guò)程中的說(shuō)明諳旬保留作用域信息記錄中的域名賦值語(yǔ)句的翻譯簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句數(shù)組元素的引用布爾表達(dá)式的翻譯數(shù)值表示法作為條件控制的布爾式翻譯控制語(yǔ)句的翻譯本章內(nèi)容目錄中間語(yǔ)言賦值語(yǔ)句的翻譯中間語(yǔ)言

幾種常見(jiàn)的中間語(yǔ)言形式

后綴式

三地址代碼（包括三元式、四元式、間接三元式）

DAG圖表示中間語(yǔ)言幾種常見(jiàn)的中間語(yǔ)言形式后綴式

后綴式表示法又稱逆波蘭表示法。這種表示法是把運(yùn)算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）。例如，把a(bǔ)十b寫成ab＋，把a(bǔ)*b寫成ab*。后綴式后綴式表示法又稱逆波蘭表示法。一個(gè)表達(dá)式E的后綴形式(1)如果E是一個(gè)變量或常量，則E的后綴式是E自身。(2)如果E是E1opE2形式的表達(dá)式，這里op是任何二元操作符，則E的后綴式為E1′E2′op，這里E1′和E2′分別為E1和E2的后綴式。(3)如果E是（E1）形式的表達(dá)式，則E1的后綴式就是E的后綴式。

后綴式表示法用不著使用括號(hào)。根據(jù)運(yùn)算量和算符出現(xiàn)的先后位置，以及每個(gè)算符的目數(shù)，就完全決定了一個(gè)表達(dá)式的分解。一個(gè)表達(dá)式E的后綴形式(1)如果E是一個(gè)變量或常量，則E的后只要知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都能對(duì)它正確進(jìn)行唯一分解。只要知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都圖表示法

包括DAG與抽象語(yǔ)法樹(shù)無(wú)循環(huán)有向圖（DirectedAcycliGraph簡(jiǎn)稱DAG）。 與抽象語(yǔ)法樹(shù)一樣，對(duì)表達(dá)式中的每個(gè)子表達(dá)式，DAG中都有一個(gè)結(jié)點(diǎn)。一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù)。 與抽象語(yǔ)法樹(shù)不同的是，在一個(gè)DAG中代公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)，而在一棵抽象語(yǔ)法樹(shù)中公共子表達(dá)式被表示為重復(fù)的子樹(shù)。圖表示法包括DAG與抽象語(yǔ)法樹(shù)例如，表達(dá)式a+a*(b-c)+(b-c)*d

例如，表達(dá)式a+a*(b-c)+(b-c)*d例如，表達(dá)式a+a*(b-c)+(b-c)*d

例如，表達(dá)式a+a*(b-c)+(b-c)*d編譯原理第7章課件編譯原理第7章課件后綴式即是對(duì)抽象語(yǔ)法樹(shù)的后續(xù)遍歷序列例：上圖中的抽象語(yǔ)法樹(shù)的后綴式是：abcuminus*bcuminu*+assign抽象語(yǔ)法樹(shù)的邊沒(méi)有顯式地出現(xiàn)在后綴式中，這些邊可以根據(jù)結(jié)點(diǎn)出現(xiàn)的次序及表示操作符的結(jié)點(diǎn)要求操作數(shù)的個(gè)數(shù)還原出來(lái)。后綴式即是對(duì)抽象語(yǔ)法樹(shù)的后續(xù)遍歷序列編譯原理第7章課件編譯原理第7章課件三地址代碼

三地址代碼是由下面一般形式的語(yǔ)句構(gòu)成的序列：x：=yopz其中,x,y,z為名字、常數(shù)或編譯時(shí)產(chǎn)生的臨時(shí)變量；op代表運(yùn)算符號(hào)如定點(diǎn)運(yùn)算符、浮點(diǎn)運(yùn)算符、邏輯運(yùn)算符等等。每個(gè)語(yǔ)句的右邊只能有一個(gè)運(yùn)算符。例如，源語(yǔ)言表達(dá)式x＋y*z可以被翻譯為如下語(yǔ)句序列：T1：＝y(tǒng)*zT2：＝x＋T1其中，Tl，T2為編譯時(shí)產(chǎn)生的臨時(shí)變量。三地址代碼三地址代碼是由下面一般形式的語(yǔ)句構(gòu)成的序列：三地址代碼可以看成是抽象語(yǔ)法樹(shù)或DAG的一種線性表示。

三地址代碼可以看成是抽象語(yǔ)法樹(shù)或DAG的一種線性表示。三地址語(yǔ)句類似于匯編語(yǔ)言代碼。語(yǔ)句可以帶有符號(hào)標(biāo)號(hào)，而且存在各種控制流語(yǔ)句。符號(hào)標(biāo)號(hào)代表存放中間代碼的數(shù)組中三地址代碼語(yǔ)句的下標(biāo)。下面列出所使用的三地址語(yǔ)句的種類。（1)形如x:＝y(tǒng)opz的賦值語(yǔ)句，其中op為二元算術(shù)算符或邏輯算符。(2)形如x:＝opy的贖值語(yǔ)句，其中op為一元算符，如一元減ununus,邏輯非not,移位算符及轉(zhuǎn)換算符（如將定點(diǎn)數(shù)轉(zhuǎn)換成浮點(diǎn)數(shù)）。(3)形如x:=y的復(fù)制語(yǔ)句，它將y的值賦給x。(4)形如gotoL的無(wú)條件轉(zhuǎn)移語(yǔ)句，即下一條將被執(zhí)行的語(yǔ)句是帶標(biāo)號(hào)L的三地址語(yǔ)句。三地址語(yǔ)句類似于匯編語(yǔ)言代碼。語(yǔ)句可以帶有符號(hào)標(biāo)號(hào)，而且存在

(5)形如ifxrelopygotoL或ifagotoL的條件轉(zhuǎn)移語(yǔ)句。第一種形式語(yǔ)句施用關(guān)系運(yùn)算符號(hào)relop（如＜，＝，＞，=等等）于x和y,若x與y滿足關(guān)系relop,那么下面就執(zhí)行帶標(biāo)號(hào)L的語(yǔ)句，否則下面就繼續(xù)執(zhí)行if語(yǔ)句之后的語(yǔ)句。第二種形式的語(yǔ)句中，a為布爾變量或常量，若a為真，則執(zhí)行帶標(biāo)號(hào)L的語(yǔ)句，否則執(zhí)行后一條語(yǔ)句。(6)用于過(guò)程調(diào)用的語(yǔ)句paramx和callp,n,以及返回語(yǔ)句returny.源程序中的過(guò)程調(diào)用語(yǔ)句P(xl，x2，…，xn）通常產(chǎn)生如下的三地址代碼：paramx1paramx2……paramxncallp,n其中n表示實(shí)參個(gè)數(shù)。過(guò)程返回語(yǔ)句retumy中y為過(guò)程返回的一個(gè)值。(5)形如ifxrelopygotoL或(7)形如x:=y[i]及x[i]:=y的索引賦值。前者把相對(duì)于地址y的后面第i個(gè)單元里的值賦給x。后者把y的值賦給相對(duì)于地址x后面的第i個(gè)單元。（8）形如x:=&y,x:=*y和*x:=y的地址和指針賦值。其中第一個(gè)賦值語(yǔ)句把y的地址賦給x。假定y是個(gè)名字，或者是一個(gè)臨時(shí)變量，代表一個(gè)具有左值的表達(dá)式，例如A[i,j]；并且x是一個(gè)指針名字或臨時(shí)變量。也就是說(shuō),x的右值將被賦予對(duì)象y的左值。第二個(gè)賦值語(yǔ)句x:=*y，假定y是一個(gè)指針或者是一個(gè)其右值為地址的臨時(shí)變量。此語(yǔ)句執(zhí)行的結(jié)果是把y所指示的地址單元里存放的內(nèi)容賦給x.第三個(gè)賦值語(yǔ)句*x:=y,將把x所指向的對(duì)象的右值賦給y的右值。(7)形如x:=y[i]及x[i]:=y的在設(shè)計(jì)中間代碼形式時(shí)，運(yùn)算符的選擇是非常重要的。顯然，算符種類應(yīng)足以用來(lái)實(shí)現(xiàn)源語(yǔ)言中的運(yùn)算。一個(gè)小型算符集合較易于在新的目標(biāo)機(jī)器上實(shí)現(xiàn)。然而，用局限的指令集合會(huì)使某些源語(yǔ)言運(yùn)算表示成中間形式時(shí)代碼加長(zhǎng)，從而需要在目標(biāo)代碼生成時(shí)做較多的工作以獲得高效的代碼。在設(shè)計(jì)中間代碼形式時(shí)，運(yùn)算符的選擇是非常重要的。生成三地址代碼時(shí)，臨時(shí)變量的名字對(duì)應(yīng)抽象語(yǔ)法樹(shù)的內(nèi)部結(jié)點(diǎn)。對(duì)于產(chǎn)生式E→E1＋E2的左端的非終結(jié)符號(hào)E而言，它的經(jīng)過(guò)計(jì)算得出的值往往放到一個(gè)新的臨時(shí)變量T中。一般說(shuō)來(lái)，賦值語(yǔ)句id:=E的三地址代碼包括： 對(duì)表達(dá)式E求值并置于變量T中，然后進(jìn)行賦值id.place:=T. 如果一個(gè)表達(dá)式僅有一單個(gè)標(biāo)識(shí)符，例如Y,則由Y自身保留表達(dá)式的值。

生成三地址代碼時(shí)，臨時(shí)變量的名字對(duì)應(yīng)抽象語(yǔ)法樹(shù)的內(nèi)部結(jié)點(diǎn)。下表是為賦值語(yǔ)句生成三地址代碼的S-屬性文法定義。如給定輸入a:=b*-c+b*-c。非終結(jié)符號(hào)S有綜合屬性S.code,它代表賦值語(yǔ)句S的三地址代碼。非終結(jié)符號(hào)E有如下兩個(gè)屬性：（1)E.place表示存放E值的名字；(2)E.code表示對(duì)E求值的三地址語(yǔ)句序列。函數(shù)newtemp的功能是，每次調(diào)用它時(shí)，將返回一個(gè)不同臨時(shí)變量名字，如T1，T2，…。為了方便，我們?cè)诒硎褂胓en(x‘：＝’y‘+’z)表示生成三地址語(yǔ)句x:=y十z.代替x,y或z出現(xiàn)的表達(dá)式在傳遞給gen時(shí)求值，用單引號(hào)括起來(lái)的運(yùn)算符或操作數(shù)將保留引號(hào)里字面的符號(hào)。下表是為賦值語(yǔ)句生成三地址代碼的S-屬性文法定義。編譯原理第7章課件三地址語(yǔ)句可看成中間代碼的一種抽象形式。編譯程序中，三地址代碼語(yǔ)句的具體實(shí)現(xiàn)可以用記錄表示，記錄中包含表示運(yùn)算符和操作數(shù)的域。通常有三種表示方法：四元式、三元式、間接三元式。三地址語(yǔ)句可看成中間代碼的一種抽象形式。四元式一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為op、arg1,arg2及result.域op包含一個(gè)代表運(yùn)算符的內(nèi)部碼。三地址語(yǔ)句x:＝y(tǒng)opz可表示為：將y置于argl域，置于arg2域，x置于result域，：＝為算符。帶有一元運(yùn)算符的語(yǔ)句如：x:=-y或者x:=y的表示中不用arg2.而像param這樣的運(yùn)算符僅使用argl域。條件和無(wú)條件轉(zhuǎn)移語(yǔ)句將目標(biāo)標(biāo)號(hào)置于result域中。四元式一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為三元式

為了避免把臨時(shí)變量填入到符號(hào)表，可以通過(guò)計(jì)算這個(gè)臨時(shí)變量值的語(yǔ)句的位置來(lái)引用這個(gè)臨時(shí)變量。這樣表示三地址代碼的記錄只需三個(gè)域：op、argl和arg2

三元式為了避免把臨時(shí)變量填入到符號(hào)表，可以通過(guò)計(jì)算這個(gè)臨時(shí)編譯原理第7章課件間接三元式

為了便于代碼優(yōu)化處理，有時(shí)不直接使用三元式表，而是另設(shè)一張指示器（稱為間接碼表），它將按運(yùn)算的先后順序列出有關(guān)三元式在三元表中的位置。換句話說(shuō)就是，用一張間接碼表輔以三元式表的辦法來(lái)表示中間代碼。這種表示法稱為間接三元式。間接三元式為了便于代碼優(yōu)化處理，有時(shí)不直接使用三元式表，而例如，語(yǔ)句X:=（A＋B）*C；Y:=D↑（A＋B)的間接三元式表示如表所示。例如，語(yǔ)句四元式與三元式和間接三元式作一些比較

四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的。這一點(diǎn)和三元式不同。要更動(dòng)一張三元表是很困難的，它意味著必須改變其中一系列指示器的值。但要更動(dòng)四元式表是很容易的，因?yàn)檎{(diào)整四元式之間的相對(duì)位置并不意味著必須改變其中一系列指示器的值。因此，當(dāng)需要對(duì)中間代碼進(jìn)行優(yōu)化處理時(shí)，四元式比三元式要方便得多。對(duì)優(yōu)化這一點(diǎn)而言，四元式和間接三元式同樣方便。四元式與三元式和間接三元式作一些比較四元式之間的聯(lián)系是通過(guò)說(shuō)明語(yǔ)句

當(dāng)考查一個(gè)過(guò)程或分程序的一系列說(shuō)明語(yǔ)句時(shí)，便可為局部于該過(guò)程的名字分配存儲(chǔ)空間。對(duì)每個(gè)局部名字，我們都將在符號(hào)表中建立相應(yīng)的表項(xiàng)，并填入有關(guān)的信息如類型、在存儲(chǔ)器中的相對(duì)地址等。相對(duì)地址是指對(duì)靜態(tài)數(shù)據(jù)區(qū)基址或活動(dòng)記錄中局部數(shù)據(jù)區(qū)基址的一個(gè)偏移量。說(shuō)明語(yǔ)句當(dāng)考查一個(gè)過(guò)程或分程序的一系列說(shuō)明語(yǔ)句時(shí)，便可為局當(dāng)產(chǎn)生中間代碼地址時(shí)，對(duì)目標(biāo)機(jī)一些情況做到心中有數(shù)是有好處的。例如，假定在一個(gè)以字節(jié)編址的目標(biāo)機(jī)上，整數(shù)必須存放在4的倍數(shù)的地址單元，那么，計(jì)算地址時(shí)就應(yīng)以4的倍數(shù)增加。當(dāng)產(chǎn)生中間代碼地址時(shí)，對(duì)目標(biāo)機(jī)一些情況做到心中有數(shù)是有好處的過(guò)程中的說(shuō)明語(yǔ)句

在C,Pascal及FORTRAN等語(yǔ)言的語(yǔ)法中，允許在一個(gè)過(guò)程中的所有說(shuō)明語(yǔ)句作為一個(gè)組來(lái)處理，把它們安排在一所數(shù)據(jù)區(qū)中。從而需要一個(gè)全程變量如offset來(lái)跟蹤下一個(gè)可用的相對(duì)地址的位置。過(guò)程中的說(shuō)明語(yǔ)句在C,Pascal及FORTRAN等語(yǔ)言在下圖關(guān)于說(shuō)明語(yǔ)句的翻譯模式中，非終結(jié)符號(hào)P產(chǎn)生一系列形如id：T的說(shuō)明語(yǔ)句。在處理第一條說(shuō)明語(yǔ)句之前，先置offset為0，以后每次遇到一個(gè)新的名字，便將該名字填入符號(hào)表中并置相對(duì)地址為當(dāng)前offset之值，然后使offset加上該名字所表示的數(shù)據(jù)對(duì)象的域?qū)?。在下圖關(guān)于說(shuō)明語(yǔ)句的翻譯模式中，非終結(jié)符號(hào)P產(chǎn)生一系列形如i編譯原理第7章課件過(guò)程enter(name,type,offset）用來(lái)把名字name填入到符號(hào)表中，并給出此名字的類型type及在過(guò)程數(shù)據(jù)區(qū)中的相對(duì)地址offset。非終結(jié)符號(hào)T有兩個(gè)綜合屬性T.type和T.width，分別表示名字的類型和名字的域?qū)挘丛擃愋兔炙加玫拇鎯?chǔ)單元個(gè)數(shù)）。在圖中,假定整數(shù)類型域?qū)挒?；實(shí)數(shù)域?qū)挒?;一個(gè)數(shù)組的域?qū)捒梢酝ㄟ^(guò)把數(shù)組元素?cái)?shù)目與一個(gè)元素的域?qū)捪喑双@得；每個(gè)指針類型的域?qū)捈俣?.過(guò)程enter(name,type,offset）用來(lái)把如果把圖中的第一條產(chǎn)生式及其語(yǔ)義動(dòng)作寫在一行，則對(duì)offset賦初值更明顯，如下式所示：

P→｛offset:=0｝D（7．1）前面曾談到產(chǎn)生ε的標(biāo)記非終結(jié)符號(hào)，可以用它來(lái)重新改寫上述產(chǎn)生式以便語(yǔ)義動(dòng)作均出現(xiàn)在整個(gè)產(chǎn)生式的右邊。我們可采用標(biāo)記非終結(jié)符號(hào)M來(lái)重寫式（7.1）：P→MDM→ε{offset:=0}如果把圖中的第一條產(chǎn)生式及其語(yǔ)義動(dòng)作寫在一行，則對(duì)offse保留作用域信息

允許嵌套過(guò)程的語(yǔ)言，對(duì)于每一個(gè)過(guò)程，其中局部名字的相對(duì)地址計(jì)算可以采用圖7.6的方法。而當(dāng)遇到一個(gè)嵌入的過(guò)程說(shuō)明時(shí)，則應(yīng)當(dāng)暫停包圍此過(guò)程的外圍過(guò)程說(shuō)明語(yǔ)句的處理。這種方法可以通過(guò)加入到如下的語(yǔ)言把有關(guān)語(yǔ)義動(dòng)作來(lái)說(shuō)明。P→DD→D;D|id：T|procid：D；S(7．2)由于我們當(dāng)前的目標(biāo)是考慮說(shuō)明語(yǔ)句，因而對(duì)其中產(chǎn)生語(yǔ)句的非終結(jié)符號(hào)S及產(chǎn)生類型的非終結(jié)符號(hào)T的產(chǎn)生式我們沒(méi)有給出。與圖7.6中相同．T有兩個(gè)綜合屬性type和width。保留作用域信息允許嵌套過(guò)程的語(yǔ)言，對(duì)于每一個(gè)過(guò)程，其中局部假定對(duì)于式(7．2)的語(yǔ)言的每一個(gè)過(guò)程都有一張獨(dú)立的符號(hào)表。這種符號(hào)表可用鏈表實(shí)現(xiàn)。當(dāng)碰到過(guò)程說(shuō)明D→procid；D,；S時(shí)，便創(chuàng)建一張新的符號(hào)表，并且把在D，中的所有說(shuō)明項(xiàng)都填入此符號(hào)表內(nèi)。新表有一個(gè)指針指向剛好包圍該嵌入過(guò)程的外圍過(guò)程的符號(hào)表，由id表示的過(guò)程名字作為該外圍過(guò)程的局部名字。對(duì)圖7.6處理變量說(shuō)明的唯一修改是，要告訴enter在哪個(gè)符號(hào)表填入一項(xiàng)。假定對(duì)于式(7．2)的語(yǔ)言的每一個(gè)過(guò)程都有一張獨(dú)立的符號(hào)表。在下面的語(yǔ)義規(guī)則中用到如下操作。(1)mktable(previous)創(chuàng)建一張新符號(hào)表，并返回指向新表的一個(gè)指針。參數(shù)previous指向一張先前創(chuàng)建的符號(hào)表，譬如剛好包圍嵌入過(guò)程的外圍過(guò)程符號(hào)表。指針previous之值放在新符號(hào)表表頭，表頭中還可存放一些其它信息如過(guò)程嵌套深度等等。我們也可以按過(guò)程被說(shuō)明的順序?qū)^(guò)程編號(hào)，并把這一編號(hào)填入表頭。(2)enter(table，name，type,offset）在指針table指示的符號(hào)表中為名字name建立一個(gè)新項(xiàng)，并把類型type、相對(duì)地址offset填入到該項(xiàng)中。(3)addwidth(table,width)在指針table指示的符號(hào)表表頭中記錄下該表中所有名字占用的總寬度。(4)enterpcoc(table，name，newtable）在指針table指示的符號(hào)表中為名字為name的過(guò)程建立一個(gè)新項(xiàng)。參數(shù)newtable指向過(guò)程name的符號(hào)表。在下面的語(yǔ)義規(guī)則中用到如下操作。在下圖中的翻譯模式給出了如何在一遍掃描中對(duì)數(shù)據(jù)進(jìn)行處理，它使用了一個(gè)棧tblptr保存各外層過(guò)程的符號(hào)表指針。當(dāng)處理過(guò)程partition中的說(shuō)明語(yǔ)句時(shí)，棧tblprt中將包括指向sort,quicksortRpartition的符號(hào)表的指針。指向當(dāng)前符號(hào)表的指針在棧頂。另一個(gè)棧offset存放各嵌套過(guò)程的當(dāng)前相對(duì)地址。offset的棧頂元素為當(dāng)前被處理過(guò)程的下一個(gè)局部名字的相對(duì)地址。在下圖中的翻譯模式給出了如何在一遍掃描中對(duì)數(shù)據(jù)進(jìn)行處理，它使編譯原理第7章課件編譯原理第7章課件編譯原理第7章課件記錄中的域名

除了基本類型、指針和數(shù)組外，下述產(chǎn)生式使非終結(jié)符號(hào)T產(chǎn)生記錄類型：T→recordDend當(dāng)遇到保留字record時(shí)，與標(biāo)記非終結(jié)符號(hào)L相應(yīng)的語(yǔ)義動(dòng)作為記錄中的各域名創(chuàng)建一張新的記錄符號(hào)表。把指向該表的指針壓人棧tblptr中，并把相對(duì)地址。壓入棧offset中。記錄中的域名除了基本類型、指針和數(shù)組外，下述產(chǎn)生式使非終結(jié)編譯原理第7章課件賦值語(yǔ)句的翻譯

賦值語(yǔ)句中的表達(dá)式的類型可以是整型、實(shí)型、數(shù)組和記錄。作為翻譯賦值語(yǔ)句為三地址代碼的一個(gè)部分，將討論如何在符號(hào)表中查找名字及如何存取數(shù)組和記錄的元素。賦值語(yǔ)句的翻譯賦值語(yǔ)句中的表達(dá)式的類型可以是整型、實(shí)型、數(shù)簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句

屬性表示id所代表的名字本身。過(guò)程lookup(id.nam）檢查是否在符號(hào)表中存在相應(yīng)此名字的入口。如果有，則返回一個(gè)指向該表項(xiàng)的指針，否則，返回nil表示沒(méi)有找到。在語(yǔ)義動(dòng)作中，調(diào)用過(guò)程emit將生成的三地址語(yǔ)句發(fā)送到輸出文件中．簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句屬性表示id所代表假定賦值語(yǔ)句出現(xiàn)在如下文法形成的上下文環(huán)境中：P→MDM→εD→D;D|id:T|procid;ND;SN→ε

如果把這些產(chǎn)生式加到下面文法中，非終結(jié)符P就變?yōu)殚_(kāi)始符號(hào)。假定賦值語(yǔ)句出現(xiàn)在如下文法形成的上下文環(huán)境中：編譯原理第7章課件數(shù)組元素的引用

現(xiàn)在討論包含數(shù)組元素的表達(dá)式和賦值句的翻譯問(wèn)題。數(shù)組在存儲(chǔ)器中的存放方式?jīng)Q定了數(shù)組元素的地址計(jì)算法，從而也決定了應(yīng)該產(chǎn)生什么樣的中間代碼。數(shù)組元素的引用現(xiàn)在討論包含數(shù)組元素的表達(dá)式和賦值句的翻譯問(wèn)若數(shù)組A的元素存放在一片連續(xù)單元里，則可以較容易地訪問(wèn)數(shù)組的每個(gè)元素。假設(shè)數(shù)組A每個(gè)元素寬度為w，則A[i]這個(gè)元素的起始地址為base+(i-low)*w其中:low為數(shù)組下標(biāo)的下界,base是分配給數(shù)組的相對(duì)地址，即base為A的第一個(gè)元素A[low]的相對(duì)地址。變形整理得：i*w＋（base一low*w)其中子表達(dá)式C=base-low*w可以在處理數(shù)組說(shuō)明時(shí)計(jì)算出來(lái)。我們假定C值存放在符號(hào)表中數(shù)組A的對(duì)應(yīng)項(xiàng)中，則A[i]相對(duì)地址可由i*w十C計(jì)算出來(lái).若數(shù)組A的元素存放在一片連續(xù)單元里，則可以較容易地訪問(wèn)數(shù)組的二維數(shù)組可以按行或按列存放。若二維數(shù)組A按行存放，則可用如下公式計(jì)算A[il，i2]的相對(duì)地址：base＋（（i1-low1）*n2＋i1-low2）*w可以重寫上述表達(dá)式為((i1*n2)＋i2)*w＋(base-((low1*n2)＋low2)*w)后一項(xiàng)子表達(dá)式(base-（(low1*n2)+low*w2)*w)的值是可以在編譯時(shí)確定的.二維數(shù)組可以按行或按列存放。如果在文法中id出現(xiàn)的地方允許下面產(chǎn)生式中L出現(xiàn)，則可把數(shù)組元素引用加入到賦值語(yǔ)句中。

L→id[Elist]|idElist→Elist,E|E改寫上述產(chǎn)生式為L(zhǎng)→Elist]|idElist→Elist，E|id［E如果在文法中id出現(xiàn)的地方允許下面產(chǎn)生式中L出現(xiàn)，則可把數(shù)組Elist.ndim記錄Elist中的下標(biāo)表達(dá)式的個(gè)數(shù)，即維數(shù)。函數(shù)limit(array,j)返回nj,即由array所指示的數(shù)組的第j維長(zhǎng)度。最后Elist.place表示臨時(shí)變量，用來(lái)臨時(shí)存放由Elist中的下標(biāo)表達(dá)式計(jì)算出來(lái)的值。一個(gè)Elist可以產(chǎn)生一個(gè)k-維數(shù)組引用A[i1,i2,…,ik]的前m維下標(biāo)，并將生成計(jì)算下面式子的三地址代碼：（…（(i1n2＋i2)n3＋i3)...）nm+im利用如下的遞歸公式進(jìn)行計(jì)算：e1=i1，em＝em-1*nm+im于是，當(dāng)m=k時(shí)將ek乘以元素域?qū)抴便可計(jì)算出式中的第一個(gè)子項(xiàng)。Elist.ndim記錄Elist中的下標(biāo)表達(dá)式的個(gè)數(shù)，即下面考慮在賦值語(yǔ)句中加入數(shù)組元素之后的翻譯模式，我們將把語(yǔ)義動(dòng)作加入到如下文法中：（1）S→L:=E(2）E→E＋E(3）E→（E)(4）E→L(5）L→Elist](6)L→id(7)Elist→Elist，E(8）Elist→id[E下面考慮在賦值語(yǔ)句中加入數(shù)組元素之后的翻譯模式，我們將把語(yǔ)義在語(yǔ)義動(dòng)作中由emit過(guò)程產(chǎn)生三地址代碼。若L是一個(gè)簡(jiǎn)單的名字，將生成一般的賦值；否則，若L為數(shù)組元素引用，則生成對(duì)L所指示地址的索引賦值。在語(yǔ)義動(dòng)作中由emit過(guò)程產(chǎn)生三地址代碼。例：設(shè)A為一個(gè)10*20的數(shù)組，即n1＝10，n2=20，并設(shè)w＝4。對(duì)賦值語(yǔ)句x：=A[y，z]的帶注釋的語(yǔ)法分析樹(shù)見(jiàn)圖7.12.該賦值語(yǔ)句被翻譯成如下三地址語(yǔ)句序列：T1:=y*20T1:=T1+zT2:=A-84T3:=4*T1T4:=T2[T3]X:=T4例：設(shè)A為一個(gè)10*20的數(shù)組，即n1＝10，n2=20，并編譯原理第7章課件布爾表達(dá)式的翻譯

在程序設(shè)計(jì)語(yǔ)言中，布爾表達(dá)式有兩個(gè)基本的作用：一個(gè)是用作計(jì)算邏輯值；另一個(gè)是用作控制流語(yǔ)句如if-then,if–then-else和while-do等之中的條件表達(dá)式。布爾表達(dá)式是用布爾運(yùn)算符號(hào)（and，or，not）作用到布爾變量或關(guān)系表達(dá)式上而組成的。關(guān)系表達(dá)式形如E1relopE2，其中E1和E2是算術(shù)表達(dá)式，relop為關(guān)系運(yùn)算符（＜，<=，=，，＞，>=）?？紤]由下列文法產(chǎn)生的布爾表達(dá)式：E→EorE|EandE|notE|（E)|idrelopid|id布爾表達(dá)式的翻譯在程序設(shè)計(jì)語(yǔ)言中，布爾表達(dá)式有兩個(gè)基本的作計(jì)算布爾表達(dá)式的值通常有兩種辦法。一是如同計(jì)算算術(shù)表達(dá)式一樣，一步不差地從表達(dá)式各部分的值計(jì)算出整個(gè)表達(dá)式的值。另一種計(jì)算法是采取某種優(yōu)化措施:把AorB解釋成ifAthentrueelseB把AandB解釋成ifAthenBelsefalse把notA解釋成ifAthenfalseelsetrue計(jì)算布爾表達(dá)式的值通常有兩種辦法。數(shù)值表示法

布爾表達(dá)式將從左到右按類似算術(shù)表達(dá)式的求值方法來(lái)計(jì)算。例如，對(duì)于布爾表達(dá)式：aorbandnotc將被翻譯成如下三地址序列：T1：＝notcT2：=bandT1T3：=aorT2數(shù)值表示法布爾表達(dá)式將從左到右按類似算術(shù)表達(dá)式的求值方法來(lái)一個(gè)形如a＜b的關(guān)系表達(dá)式可等價(jià)地寫成ifa＜bthen1else0，并可將它翻譯成如下三地址語(yǔ)句序列（我們假定語(yǔ)句序號(hào)從100開(kāi)始）：100:ifa＜bgoto103101：T:=0102:goto104103：T:＝1104:一個(gè)形如a＜b的關(guān)系表達(dá)式可等價(jià)地寫成編譯原理第7章課件編譯原理第7章課件作為條件控制的布爾式翻譯

出現(xiàn)在條件語(yǔ)句ifEthenS1elseSz2中的布爾表達(dá)式E，它的作用僅在于控制對(duì)S1和S2的選擇。只要能夠完成這一使命，E的值就無(wú)須最終保留在某個(gè)臨時(shí)單元之中。因此，作為轉(zhuǎn)移條件的布爾式E，我們可以賦予它兩種“出口”。一是“真”出口，出向S1；一是“假”出口，出向S2。

作為條件控制的布爾式翻譯出現(xiàn)在條件語(yǔ)句編譯原理第7章課件編譯原理第7章課件例7．3考慮如下表達(dá)式：a＜b