編譯原理第7章課件

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

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

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

幾種常見的中間語言形式

后綴式

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

DAG圖表示中間語言幾種常見的中間語言形式后綴式

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

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

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

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

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

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

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

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

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

為了避免把臨時變量填入到符號表，可以通過計算這個臨時變量值的語句的位置來引用這個臨時變量。這樣表示三地址代碼的記錄只需三個域：op、argl和arg2

三元式為了避免把臨時變量填入到符號表，可以通過計算這個臨時編譯原理第7章課件間接三元式

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

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

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

在C,Pascal及FORTRAN等語言的語法中，允許在一個過程中的所有說明語句作為一個組來處理，把它們安排在一所數(shù)據(jù)區(qū)中。從而需要一個全程變量如offset來跟蹤下一個可用的相對地址的位置。過程中的說明語句在C,Pascal及FORTRAN等語言在下圖關于說明語句的翻譯模式中，非終結符號P產(chǎn)生一系列形如id：T的說明語句。在處理第一條說明語句之前，先置offset為0，以后每次遇到一個新的名字，便將該名字填入符號表中并置相對地址為當前offset之值，然后使offset加上該名字所表示的數(shù)據(jù)對象的域寬。在下圖關于說明語句的翻譯模式中，非終結符號P產(chǎn)生一系列形如i編譯原理第7章課件過程enter(name,type,offset）用來把名字name填入到符號表中，并給出此名字的類型type及在過程數(shù)據(jù)區(qū)中的相對地址offset。非終結符號T有兩個綜合屬性T.type和T.width，分別表示名字的類型和名字的域寬（即該類型名字所占用的存儲單元個數(shù)）。在圖中,假定整數(shù)類型域寬為4；實數(shù)域寬為8;一個數(shù)組的域寬可以通過把數(shù)組元素數(shù)目與一個元素的域寬相乘獲得；每個指針類型的域寬假定為4.過程enter(name,type,offset）用來把如果把圖中的第一條產(chǎn)生式及其語義動作寫在一行，則對offset賦初值更明顯，如下式所示：

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

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

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

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

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

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

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

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

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

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

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

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

|whileEdoS1其中E為布爾表達式。控制語句的翻譯控制流語句編譯原理第7章課件編譯原理第7章課件例7.5考慮如下語句whilea<bdoifc<dthenx:=y+zelsex:=y-z根據(jù)上述屬性文法和賦值語句的翻譯模式，將生成下列代碼L1:ifa<bgotoL2gotoLnextL2:ifc<dgotoL3gotoL4L3:T1:=y+z;x:=T1gotoL1L4:T2:=y-zx:=T2gotoL1Lnext:例7.5考慮如下語句例7.6按照上述的語義動作，加上前述關于賦值句和布爾表達式的翻譯法，語句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按照上述的語義動作，加上前述關于賦值句和布爾表達式第七章語義分析和中間代碼生成第七章語義分析和中間代碼生成緊接在詞法分析和語法分析之后，編譯程序要做的工作就是進行靜態(tài)語義檢查和翻譯。靜態(tài)語義檢查(1)類型檢查。如果操作符作用于不相容的操作數(shù)，編譯程序必須報告出錯信息。(2)控制流檢查。控制流語句必須使控制轉移到合法的地方。

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

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

幾種常見的中間語言形式

后綴式

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

DAG圖表示中間語言幾種常見的中間語言形式后綴式

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

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

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

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

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

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

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

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

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

為了避免把臨時變量填入到符號表，可以通過計算這個臨時變量值的語句的位置來引用這個臨時變量。這樣表示三地址代碼的記錄只需三個域：op、argl和arg2

三元式為了避免把臨時變量填入到符號表，可以通過計算這個臨時編譯原理第7章課件間接三元式

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

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

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

在C,Pascal及FORTRAN等語言的語法中，允許在一個過程中的所有說明語句作為一個組來處理，把它們安排在一所數(shù)據(jù)區(qū)中。從而需要一個全程變量如offset來跟蹤下一個可用的相對地址的位置。過程中的說明語句在C,Pascal及FORTRAN等語言在下圖關于說明語句的翻譯模式中，非終結符號P產(chǎn)生一系列形如id：T的說明語句。在處理第一條說明語句之前，先置offset為0，以后每次遇到一個新的名字，便將該名字填入符號表中并置相對地址為當前offset之值，然后使offset加上該名字所表示的數(shù)據(jù)對象的域寬。在下圖關于說明語句的翻譯模式中，非終結符號P產(chǎn)生一系列形如i編譯原理第7章課件過程enter(name,type,offset）用來把名字name填入到符號表中，并給出此名字的類型type及在過程數(shù)據(jù)區(qū)中的相對地址offset。非終結符號T有兩個綜合屬性T.type和T.width，分別表示名字的類型和名字的域寬（即該類型名字所占用的存儲單元個數(shù)）。在圖中,假定整數(shù)類型域寬為4；實數(shù)域寬為8;一個數(shù)組的域寬可以通過把數(shù)組元素數(shù)目與一個元素的域寬相乘獲得；每個指針類型的域寬假定為4.過程enter(name,type,offset）用來把如果把圖中的第一條產(chǎn)生式及其語義動作寫在一行，則對offset賦初值更明顯，如下式所示：

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

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

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

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

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

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

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

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

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

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

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

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