編譯原理課件 第7章 語義分析和中間代碼產(chǎn)生

本章在編譯程序中的地位

表格管理詞法分析器語法分析器語義分析與中間代碼產(chǎn)生優(yōu)化器目標(biāo)代碼生成器源程序單詞符號(hào)語法單位中間代碼中間代碼目標(biāo)代碼出錯(cuò)處理語義分析和中間代碼的產(chǎn)生語義分析的概念:

源程序經(jīng)過詞法分析、語法分析后，表明該源程序書寫正確、符合程序語言所規(guī)定的語法，但語法分析并未對(duì)程序內(nèi)部的邏輯含義加以分析，因此編譯程序接著進(jìn)行語義分析，即審查每個(gè)語法成分的靜態(tài)語義。如果靜態(tài)語義正確，則生成與該語言成分等效的中間代碼，或直接生成目標(biāo)代碼。

直接生成機(jī)器語言或匯編語言形式的目標(biāo)代碼的優(yōu)點(diǎn)是編譯時(shí)間短且無需中間代碼到目標(biāo)代碼的翻譯，而生成中間代碼的優(yōu)點(diǎn)是使編譯結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，特別是使目標(biāo)代碼的優(yōu)化較易實(shí)現(xiàn)。語義分析進(jìn)行的語義檢查有兩類：動(dòng)態(tài)語義檢查和靜態(tài)語義檢查。動(dòng)態(tài)語義檢查需生成相應(yīng)的目標(biāo)代碼，在運(yùn)行時(shí)進(jìn)行；靜態(tài)語義檢查在編譯時(shí)進(jìn)行。語義分析和中間代碼的產(chǎn)生靜態(tài)語義檢查涉及以下幾個(gè)方面：(1)類型檢查，如運(yùn)算操作數(shù)的類型應(yīng)相容。(2)控制流檢查，用以保證控制語句有合法的轉(zhuǎn)向點(diǎn)。如C語言中不允許goto語句轉(zhuǎn)入case語句流；break語句需尋找包含它的最小switch、while或for語句方可找到轉(zhuǎn)向點(diǎn)。(3)一致性檢查，如在相同作用域中標(biāo)識(shí)符只能說明一次、case語句的標(biāo)號(hào)不能相同等。語義分析和中間代碼的產(chǎn)生語法分析器中間代碼產(chǎn)生器靜態(tài)檢查器中間代碼優(yōu)化器

語義分析階段只產(chǎn)生中間代碼而不生成目標(biāo)代碼的方法使編譯程序的開發(fā)變得較為容易，但由于語義是上下文有關(guān)的，因此語義的形式化描述非常困難，目前較常見的是用屬性文法作為描述語義的工具，并采用語法制導(dǎo)翻譯法完成對(duì)語法成分的翻譯。語義分析和中間代碼的產(chǎn)生語法制導(dǎo)翻譯：在語法分析的基礎(chǔ)上進(jìn)行邊分析邊翻譯。教學(xué)要求掌握：1.逆波蘭式,DAG圖,抽象語法樹,三地址代碼,三元式,四元式等中間代碼表示;2.簡(jiǎn)單賦值語句的翻譯,帶數(shù)組元素引用的賦值句的翻譯;3.布爾表達(dá)式的翻譯,控制語句中布爾表達(dá)式的翻譯;4.控制語句的翻譯。了解理解：說明語句的翻譯，過程調(diào)用和參數(shù)的處理。教學(xué)內(nèi)容7.1中間語言

后綴式，DAG，三地址碼(四元式，三元式，間接三元式)*7.2說明語句的翻譯7.3賦值語句的翻譯，數(shù)組元素引用的翻譯7.4布爾表達(dá)式的翻譯求布爾式值的翻譯，作為控制條件的翻譯7.5控制語句的翻譯if，while，goto，case7.6過程調(diào)用的處理,參數(shù)傳遞的處理*7.7類型檢查（不作要求，不講）7.1中間語言要掌握幾種中間語言的基本結(jié)構(gòu)：逆波蘭表示即后綴式抽象語法樹DAG圖三地址代碼(四元式、三元式、間接三元式)7.1.1后綴式波蘭邏輯學(xué)家盧卡西維奇（Lukasiewicz）發(fā)明的一種表示法，又稱逆波蘭式表示法。后綴式這種方法是，把運(yùn)算量(操作數(shù))寫在算符的前面，把算符寫在運(yùn)算量的后面(后綴)。后綴式的定義(P167.)一個(gè)表達(dá)式的后綴式可以如下定義：1.如果E是一個(gè)變量或常量，則E的后綴式是E自身。2.如果E是E1opE2形式的表達(dá)式，這里op是任何二元操作符，則E的后綴式為E1’E2’op,這里E1’和E2’分別為E1和E2的后綴式。3.如果E是(E1)形式的表達(dá)式，則E1的后綴式就是E的后綴式。要求會(huì)正確寫出表達(dá)式的后綴式。后綴式求值可以使用一個(gè)棧來求值求值過程：從左到右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧，每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，彈出這k項(xiàng)，并用運(yùn)算結(jié)果來代替這k個(gè)項(xiàng)后綴式：例寫表達(dá)式的后綴式要點(diǎn)：1.后綴式中運(yùn)算量的順序與中綴式的相同；2.算符出現(xiàn)的次序即表達(dá)式的運(yùn)算次序；3.不使用括號(hào)。例：a+bab+a*(b+c)abc+*(a+b)*(c+d)-a+b*cabc*+a/b*c-d*ex:=a-b/(c+d)用

表示取負(fù)算符(uminus):=表示賦值算符(assign)

ab+cd+*ab/c*de*-xabcd+/-:=7.1.2抽象語法樹語法制導(dǎo)翻譯以語法樹作基礎(chǔ),實(shí)際上,語法樹可以作為一種合適的中間語言形式?，F(xiàn)在對(duì)語法樹進(jìn)行改造，去掉那些對(duì)翻譯不必要的信息，將語法樹進(jìn)行抽象---抽象語法樹。在表達(dá)式的抽象語法樹中，運(yùn)算符、關(guān)鍵字不作葉子結(jié)點(diǎn)而作為內(nèi)部結(jié)點(diǎn)，葉子結(jié)點(diǎn)只是運(yùn)算量。抽象語法樹也可以屬性化，給結(jié)點(diǎn)加上屬性變成帶附注的抽象語法樹。語法制導(dǎo)翻譯既可以基于語法分析樹也可以基于抽象語法樹進(jìn)行，采用的基本方法是一樣的。抽象語法樹：簡(jiǎn)例例，為下面文法的句子a-4+c

建立抽象語法樹。EE+T|E－T|TT(E)Tid|num為每個(gè)運(yùn)算量或運(yùn)算符號(hào)都建立一個(gè)結(jié)點(diǎn)?？梢愿鶕?jù)表達(dá)式的運(yùn)算順序自下而上的構(gòu)造---手工構(gòu)造。a－+c4抽象語法樹運(yùn)算符作內(nèi)部結(jié)點(diǎn)id(a)EE－TE+TTnum(4)id(c)語法樹7.1.3DAG圖表示法：無循環(huán)有向圖（DAG)與語法樹一樣，對(duì)于表達(dá)式中的每個(gè)子表達(dá)式，DAG圖中都有一個(gè)結(jié)點(diǎn)：一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù)；兩者不同的是在DAG圖中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)；在一棵抽象語法樹中公共子表達(dá)式被表示為重復(fù)的子樹；例如賦值語句的語法樹與DAG圖：a:=b*-c+b*-c抽象語法樹公共子表達(dá)式重復(fù)出現(xiàn)assigna+*bcuminus*uminuscb圖7.3抽象語法樹例：

a:=b*-c+b*-c

(b)DAG公共子表達(dá)式只出現(xiàn)一次，一個(gè)結(jié)點(diǎn)可以有多個(gè)父結(jié)點(diǎn)圖7.3DAG例：a:=b*-c+b*-c

assigna+bcuminus*

后綴式與抽象語法樹(DAG)的關(guān)系后綴式是抽象語法樹的線性表示形式。是樹的后序遍歷的一個(gè)序列。例如:抽象語法樹assigna+*bcuminus*uminuscb后綴式:abcuminus*bcuminus*+assign后序遍歷：

(1)遍歷左子樹；

(2)遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。

7.1.4三地址代碼三地址代碼是由下面一般形式的語句構(gòu)成的序列:x:=yopz其中，x、y、z為名字、常數(shù)或編譯時(shí)產(chǎn)生的臨時(shí)變量；op代表運(yùn)算符號(hào)。每個(gè)三地址語句的右邊只能有一個(gè)運(yùn)算符。例,表達(dá)式x+y*z翻譯為三地址代碼:T1:=y*zT2:=x+T1T1,T2是編譯時(shí)產(chǎn)生的臨時(shí)變量。三地址代碼：說明1.之所以稱為三地址代碼，是因?yàn)槿刂反a語句類似與匯編指令,涉及三個(gè)地址x、y和z，其中y、z表示操作數(shù)，x存放結(jié)果。地址常用屬性place表示。名字.place：指向符號(hào)表名字入口的指針臨時(shí)變量.place：臨時(shí)變量值存放的單元地址常數(shù).place：指向常數(shù)表中常數(shù)入口的指針2.三地址語句可以帶符號(hào)標(biāo)號(hào),標(biāo)號(hào)代表存放中間代碼的數(shù)組中三地址代碼語句的下標(biāo)。3.三地址代碼是抽象語法樹或DAG的線性化表示---每個(gè)內(nèi)部結(jié)點(diǎn)對(duì)應(yīng)一個(gè)三地址語句。例,P170.圖7.5，是相應(yīng)于P168.圖7.3的抽象語法樹和DAG的三地址代碼：

(a)對(duì)應(yīng)抽象語法樹的代碼(b)對(duì)應(yīng)DAG的代碼T1:＝-cT1:＝-cT2:＝b*T1T2:＝b*T1T3:＝-cT5:＝T2+T2T4:＝b*T3a:＝T5T5:＝T2+T4a:＝T5注：臨時(shí)變量的名字對(duì)應(yīng)抽象語法樹的內(nèi)部結(jié)點(diǎn)(算符結(jié)點(diǎn)),表達(dá)式中的每個(gè)運(yùn)算都要引入一個(gè)新的臨時(shí)變量存放計(jì)算結(jié)果,要多少引入多少。抽象語法樹與三地址代碼的關(guān)系(1)賦值語句x:＝y(tǒng)opz;

op是二元算術(shù)或邏輯運(yùn)算符(2)賦值語句x:＝opy;op是一元算符，如取負(fù)、邏輯非、移位及類型轉(zhuǎn)換(3)復(fù)制語句x:＝y(tǒng);(4)無條件轉(zhuǎn)移語句gotoL;

符號(hào)標(biāo)號(hào)L代表存放中間代碼的數(shù)組中三地址代碼語句的下標(biāo)(5)條件轉(zhuǎn)移語句ifxrelopygotoL;

ifagotoL;

relop是關(guān)系運(yùn)算符;a是布爾量*三地址代碼語句的種類(P170.)(6)過程調(diào)用語句paramx;x是實(shí)參數(shù)

callp,n;p過程名,n實(shí)參個(gè)數(shù)

過程返回語句returny;y返回值,可有可無(7)索引賦值x:=y[i];=[]變址取數(shù)

x[i]:=y;[]=變址存數(shù)(8)地址和指針賦值x:＝＆y;

x:＝*y;

*x:＝y(tǒng);注：選擇適當(dāng)?shù)乃惴鲜侵虚g代碼設(shè)計(jì)的重要問題，應(yīng)該不大不小，足以實(shí)現(xiàn)源語言的操作運(yùn)算。*三地址代碼語句的種類(續(xù)P170.)四元式用了四個(gè)域（op,arg1,arg2,result）四元式需要利用較多的臨時(shí)單元，四元式之間的聯(lián)系通過臨時(shí)變量實(shí)現(xiàn)三地址語句：z:=xopy可表示為：(op，x，y，T1)(=，T1，，z)對(duì)于一元運(yùn)算可只使用arg1四元式中的arg1,arg2,result其實(shí)都是指針，它指向相關(guān)符號(hào)表中的名字的入口,臨時(shí)變量也要填入符號(hào)表。三地址代碼的實(shí)現(xiàn)算符操作數(shù)1(指針)操作數(shù)2(指針)結(jié)果(臨變)三地址代碼的具體實(shí)現(xiàn):用記錄結(jié)構(gòu),含四個(gè)域賦值語句a:=b*-c+b*-c

的三地址代碼實(shí)現(xiàn)(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcbT2T5arg1T1T3T4arg2resultT1T2T3T4T5aopP172.表7.4(a)三地址語句的四元式表示三地址代碼實(shí)現(xiàn)：四元式表示四元式之間的聯(lián)系通過臨時(shí)變量實(shí)現(xiàn)三元式

(op,arg1,arg2）因?yàn)橹挥腥齻€(gè)域，所以為三元式是為了避免把臨時(shí)變量填入符號(hào)表；而是通過計(jì)算整個(gè)這個(gè)臨時(shí)變量的值得語句的位置來引用該臨時(shí)變量；三地址代碼的實(shí)現(xiàn)(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcb(1)aarg1(0)(2)(3)(4)arg2opP172.表7.4(b)三地址語句的三元式表示三元式中使用了指向三元式語句的指針(序號(hào))，序號(hào)也表示該三元式計(jì)算的結(jié)果值,三元式之間的聯(lián)系通過指針實(shí)現(xiàn)。三地址代碼實(shí)現(xiàn)：三元式a:=b*-c+b*-c三地址代碼實(shí)現(xiàn)：(0)(1)(2)(3)uminus*+assigncb(1)aarg1(0)(1)(2)arg2op三元式表(0)(1)(0)(1)(2)(3)間接代碼三元式表中沒有了重復(fù)的三元式，語句的移動(dòng)僅改變左邊的間接碼表。另外的例見P173.表7.6。間接三元式（三元式的指針表）不直接使用三元式表，而是另外設(shè)一張指示器表(間接碼表)間接三元式a:=b*-c+b*-c寫中間語言：練習(xí)寫出表達(dá)式：A+B*(C-D)-E/(F-G)

的逆波蘭表示、三元式表示、四元式表示。解:四元式表示：①(-,C,D,T1)②(*,B,T1,T2)③(+,A,T2,T3)④(-,F,G,T4)⑤(/,E,T4,T5)⑥(-,T3,T5,T6)解:三元式表示：①(-,C,D)②(*,B,①)③(+,A,②)④(-,F,G)⑤(/,E,④)⑥(-,③,⑤)解：逆波蘭表示：ABCD-*+EFG-/-*7.2說明語句當(dāng)考察一個(gè)過程或分程序的一系列說明語句時(shí)，便可為局部于該過程的名字分配存儲(chǔ)空間。對(duì)每個(gè)局部名字，將在符號(hào)表中建立相應(yīng)的表項(xiàng)，并填入相應(yīng)的信息如類型、嵌套深度、相對(duì)地址等。說明語句的翻譯目的就是建立符號(hào)表。…局部變量……地址增加相對(duì)地址基地址→相對(duì)地址是指相對(duì)數(shù)據(jù)區(qū)基地址的一個(gè)偏移量。如圖所示：符號(hào)表的結(jié)構(gòu)和組織(參見CH.8)符號(hào)表結(jié)構(gòu)例,P235.FORTRAN語言的SD表結(jié)構(gòu)。名字屬性地址種屬維數(shù)/形參個(gè)數(shù)類型數(shù)據(jù)區(qū)號(hào)相對(duì)地址

a局部變量整型120

b數(shù)組2實(shí)型2100

p過程1符號(hào)表的組織:指各表項(xiàng)的安排線性表:順序填、查表二叉樹：按序填表，對(duì)折查找雜湊技術(shù)：根據(jù)HASH()函數(shù)值填、查表sortnilheaderaxreadarrayexchangequicksortheaderexchangeheaderkvpartitionquicksortheaderijpartitioniheaderreadarraytoreadarraytoexchangeP176.

嵌套過程的程序例子P176.圖7.7嵌套過程的符號(hào)表(5個(gè)過程,5張表,表之間的聯(lián)系)P177.圖7.8處理嵌套過程中的說明語句的翻譯模式說明語句翻譯的例子7.3賦值語句的翻譯本節(jié)討論的賦值語句，其表達(dá)式類型可以是整型、實(shí)型、數(shù)組和記錄。賦值語句的翻譯將討論如何在符號(hào)表中查找名字及如何存取數(shù)組和記錄的元素。本節(jié)只介紹7.3.1和7.3.2小節(jié)。7.3.1簡(jiǎn)單算術(shù)表達(dá)式及賦值語句的翻譯圖7.10的翻譯模式；賦值語句翻譯為三地址代碼7.3.2數(shù)組元素引用的翻譯一維、二維數(shù)組元素地址計(jì)算含有數(shù)組元素引用的賦值語句的翻譯含簡(jiǎn)單變量的賦值語句，如id:=E，其中，id為普通變量，而E是簡(jiǎn)單的算術(shù)表達(dá)式。7.3.1簡(jiǎn)單算術(shù)表達(dá)式及賦值語句文法定義如下：S→id:=EE→E1+E2E→E1*E2E→-E1E→(E1)E→id需要的語義過程

1.E的屬性定義：E.place:存放表達(dá)式E“值”2.newtemp：獲取臨時(shí)變量以存放中間結(jié)果3.emit－產(chǎn)生三地址碼的過程；4.lookup(name)－檢查name是否在符號(hào)表中有定義（條目）需要的語義變量E?PLACE：與非終結(jié)符E相聯(lián)系的語義變量值為某變量的符號(hào)表入口地址或臨時(shí)變量序號(hào)。它與文法的非終結(jié)符相聯(lián)，分析過程需要就建立，不需要就消亡。例.翻譯賦值語句x:=-a+b*c

為三地址代碼自下而上語法制導(dǎo)翻譯，結(jié)合圖7.10理解賦值語句和算術(shù)表達(dá)式翻譯：例三地址語句:

查表③①查表id(x):=E.placeSE.place+E.placeid(a)E.place*E.place－E.placeid(c)id(b)④查表②生成⑤生成⑥生成⑦查表,生成②T1:=uminusa

⑤T2:=b*c

⑥T3:=T1+T2

⑦x:=T3翻譯賦值語句x:=-a+b*(-c+d)/e為三地址代碼。掌握手工生成賦值句的三地址代碼的方法：按運(yùn)算順序?qū)懗鋈刂氛Z句。賦值語句和算術(shù)表達(dá)式翻譯：練習(xí)三地址語句序列:T1:=uminusa

T2:=uminuscT3:=T2+dT4:=b*T3

T5:=T3/eT6:=T1+T2x:=T67.3.2數(shù)組元素的引用一．?dāng)?shù)組及其下標(biāo)變量地址的計(jì)算1.數(shù)組分類：一維數(shù)組、二維數(shù)組、多維數(shù)組；2.多維數(shù)組的存放按行存放按列存放(FORTRAN)只要知道數(shù)組的首地址，及每個(gè)數(shù)組元素占多少內(nèi)存單元，就可計(jì)算出任一數(shù)組元素的地址；7.3.2數(shù)組元素的引用數(shù)組元素引用的關(guān)鍵問題:數(shù)組元素地址的計(jì)算，由數(shù)組的存放方式?jīng)Q定翻譯時(shí)要產(chǎn)生計(jì)算數(shù)組元素地址的中間代碼。以后都假定：數(shù)組的元素存放在一片連續(xù)存儲(chǔ)單元中，按行存放，數(shù)組的每個(gè)元素寬度為w。一維數(shù)組元素地址計(jì)算---牢記設(shè)一維數(shù)組：A[low

:high

]一維數(shù)組元素A[i]

的相對(duì)地址為：

base+(i–low)*w(7.4)

其中：low為數(shù)組下標(biāo)的下界，high為數(shù)組下標(biāo)的上界，base是數(shù)組的起始地址，即base為A的第一個(gè)元素A[low]的相對(duì)地址。(7.4)式可以整理為：i*w+(base–low*w)其中：i*w

是隨數(shù)組下標(biāo)變量i而變化的部分；base–low*w是在數(shù)組元素地址計(jì)算公式中不變化的常數(shù),常記C=base–low*w。二維數(shù)組元素地址計(jì)算---牢記設(shè)二維數(shù)組：A[low1:high1][low2:high2]

每維

的長(zhǎng)度(n1、n2)

ni=highi－lowi+1P180.

二維數(shù)組元素A[i1][i2]

的相對(duì)地址計(jì)算公式：

base＋((

i1－low1)*n2＋(i2－low2))*w

可整理為：base－(low1*n2＋low2)*w＋(i1*n2＋i2)*w

(7.5)

(7.5)分出地址不變部分和地址變化部分。常記C=(low1*n2＋low2)*wC值在處理數(shù)組說明時(shí)即可以計(jì)算出來,與數(shù)組元素的下標(biāo)無關(guān),是一個(gè)定數(shù),C值可放在符號(hào)表數(shù)組A的表項(xiàng)中,或數(shù)組內(nèi)情向量中。k維數(shù)組元素地址計(jì)算一般,對(duì)于一個(gè)k維數(shù)組P180.

A[low1:high1,…,lowk:highk]若按行存放，數(shù)組的每個(gè)元素的寬度為w

各維的長(zhǎng)度ni=highi－lowi+1則數(shù)組元素A[i1,i2,…,ik]的相對(duì)地址計(jì)算：D=base–C+變化部分(7.6)

變化部分=((...((i1*n2+i2)*n3+i3)...)*nk+ik)*wC=((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w

(7.7)靜態(tài)數(shù)組,動(dòng)態(tài)數(shù)組靜態(tài)數(shù)組：數(shù)組說明中各維的上下界是確定的C值在編譯的時(shí)候就能計(jì)算出來動(dòng)態(tài)數(shù)組：數(shù)組說明中各維的上下界有不確定的C值在編譯的時(shí)候不能計(jì)算出來,運(yùn)行時(shí)才能計(jì)算計(jì)算動(dòng)態(tài)數(shù)組元素地址的公式與靜態(tài)數(shù)組是同樣的，只是上、下界在編譯時(shí)是未知的。數(shù)組元素引用的文法:P181.

L→id[Elist]|id

L表示簡(jiǎn)單變量或數(shù)組元素

Elist→Elist,E|E

Elist表示下標(biāo)列表Elist

+i1,i2,…,in數(shù)組元素地址變化部分:((i1*n2+i2)*n3+i3)*n4+……

nj

:=highj

–lowj

+1(7.8)

遞歸公式em

=em-1*nm+im

(7.9)為了從符號(hào)表獲得有關(guān)數(shù)組各維長(zhǎng)度nj

的信息，改寫文法為：

L→Elist]

|id

Elist→Elist,E|id[E

讓數(shù)組名與第一個(gè)下標(biāo)聯(lián)系設(shè)計(jì)數(shù)組元素引用的文法

P181.數(shù)組元素引用的文法:(1)S→L:＝ES賦值語句(2)E→E＋EE表達(dá)式,可含數(shù)組元素(3)E→(E)(4)E→L(5)L→Elist]L數(shù)組元素(6)L→idL簡(jiǎn)單變量(7)Elist→Elist,EElist

帶數(shù)組名的下標(biāo)表(8)Elist→id[E參見P181.~183.包含數(shù)組元素引用的賦值語句的翻譯模式。數(shù)組元素引用的文法及翻譯模式有關(guān)變量與函數(shù)的說明：Elist.ndim

綜合屬性：記錄Elist中的下標(biāo)表達(dá)式的個(gè)數(shù)，即維數(shù);函數(shù)limit(array,j)：返回nj，即由array所指示的數(shù)組的第j維長(zhǎng)度;Elist.place：臨時(shí)變量，用來臨時(shí)存放由Elist

中的下標(biāo)表達(dá)式計(jì)算出來的值:

em=em-1*nmElist.Array綜合屬性：數(shù)組名的符號(hào)表地址;過程emit()

產(chǎn)生一條三地址語句;數(shù)組元素引用的翻譯模式：說明(1)L.place,L.offset:描述L的左值的情況。若L為簡(jiǎn)單變量,則L.place為符號(hào)表指針,而L.offset為null;若L為數(shù)組,則L.place存放數(shù)組元素地址的不變部分的值,L.offset存放地址的變化部分的值,L表示的數(shù)組元素的地址為:L.place[L.offset]。

相應(yīng)語義動(dòng)作:若L是一個(gè)簡(jiǎn)單變量的名字，則生成一般的賦值;若L為數(shù)組元素引用，則生成對(duì)L所指示的數(shù)組元素地址的索引賦值。數(shù)組元素引用的翻譯模式：說明(2)手工生成數(shù)組元素引用的代碼1.先確定:數(shù)組維數(shù)k;寬度w;各維的下界Lowj,上界highj,計(jì)算各維長(zhǎng)度nj;數(shù)組首地址(不同的數(shù)組用不同的符號(hào),比如A數(shù)組用A表示);計(jì)算出常數(shù)C一維數(shù)組C=Low*w二維數(shù)組C=(low1*n2+low2)*w2.對(duì)一維數(shù)組元素A[i]產(chǎn)生2個(gè)地址計(jì)算的三地址語句:T1:=w*iT2:=A－C

地址表示T2[T1]3.對(duì)二維數(shù)組元素A[i,j]產(chǎn)生4個(gè)地址計(jì)算的三地址語句:T1:=i*n2T2:=A－C

T1:=T1+jT3:=w*T1

地址表示T2[T3]數(shù)組元素引用的代碼結(jié)構(gòu)例,

賦值語句x:=A[i1,i2]的三地址代碼結(jié)構(gòu)：

T1:=A[i1,i2]的地址變化部分的計(jì)算值

T2:=base-CA[i1,i2]地址的不變部分值T3:=T2[T1]x:=T3例,

賦值語句A[i1,i2]

:=E

的三地址代碼結(jié)構(gòu)：

T1:=A[i1,i2]的地址變化部分的計(jì)算值

T2:=base-CA[i1,i2]地址的不變部分值T3:=表達(dá)式E的值T2[T1]:=T3例7.1設(shè)A為一個(gè)10*20的二維數(shù)組P183.

即設(shè)A[1:10,1:20],

n1=10,n2=20;w＝4；

數(shù)組第一個(gè)元素為A[1,1]

則計(jì)算C值

=(low1*n2＋low2)*w=(1*20＋1)*4＝84使用P181~183.的翻譯模式,對(duì)賦值語句

x:=A[y,z]

進(jìn)行翻譯，帶注釋的分析樹如P183.圖7.12所示。考慮結(jié)合自下而上分析的一遍掃描語法制導(dǎo)翻譯。帶數(shù)組元素引用的賦值語句的翻譯例例7.1x:=A[y,z]的帶注釋的分析樹L.place=xL.offset=nullL.place=T2L.offset=T3E.place=T4Elist.place=T1Elist.ndim=2Elist.array=AS:=x]⑨4⑩1①6⑧5⑦7圖7.12結(jié)合翻譯模式理解第7步產(chǎn)生2條,第8步產(chǎn)生2條,第9步產(chǎn)生1條,10步產(chǎn)生1條Elist.place=yElist.ndim=1Elist.array=A,L.place=zL.offset=nullE.place=zA[zyL.place=yL.offset=nullE.place=yElist(place=T1,ndim=2,array=A)⑦7⑥4⑤6④8③4②6(續(xù)上頁）x:=A[y,z]在第7,8,9,10步歸約時(shí)產(chǎn)生計(jì)算數(shù)組元素地址的代碼數(shù)組元素的引用翻譯:例7.1賦值語句x:=A[y,z]

在自下而上的分析中被翻譯成如下三地址語句序列：P183.

T1:=y*20T1:=T1＋zT2:=A-84T3:=4*T1T4:=T2[T3]x:=T4

注意：20(第2維長(zhǎng)度)、84(C值)、4(寬度)都是編譯中引入的常量,用A代表數(shù)組的首地址。⑦7地址的變化部分計(jì)算:*,+⑧5地址的不變部分:base-C地址的變化部分(乘寬度w)⑨4從數(shù)組元素地址取數(shù)⑩1賦值手工生成數(shù)組元素引用的代碼：例翻譯A[i+2,j+1]:=M+B[k]

為三地址代碼設(shè)A數(shù)組A[1:10,1:20];w=4;數(shù)組首地址A;

CA=(1*20+1)*4=84設(shè)B數(shù)組B[1:10];w=4;數(shù)組首地址B;CB=1*4=4三地址語句:

T1:=i+2

T5:=4*kT2:=j+1T6:=B－4T1:=T1*20T7:=T6[T5]變址取數(shù)T1:=T1+T2T7:=M+T7T3:=A－84T3[T4]:=T7變址存數(shù)

T4:=4*T1計(jì)算下標(biāo)值一維B[k]二維A[i+2,j+1]數(shù)組元素引用翻譯:練習(xí)1設(shè)二維數(shù)組A[1:10,1:20]，則n1=10,n2=20；設(shè)W=2(1)賦值語句X:=A[I,J]的三地址代碼序列；(2)賦值語句A[I+2,J+1]:=M+N三地址代碼。

(1)解：C=42

T1:=I*20T1:=T1+JT2:=A-42T3:=T1*2T4:=T2[T3]X:=T4(2)解：C=42

T1:=I+2T2:=J+1T3:=T1*20T3:=T2+T3T4:=A-42T5:=T3*2T6:=M+NT4[T5]:=T6數(shù)組元素引用翻譯:練習(xí)2(3)賦值語句X:=A[I,J]的四元式序列；(4)賦值語句A[I+2,J+1]:=M+N四元式序列。(3)解：

C=42

(*，I,20,T1)(+,J,T1,T1)(-,A,42,T2)(*,T1,2,T3)(=[],T2[T3],_,T4)(:=,T4,_,X)(4)解：C=42(+,I,2,T1)(+,J,1,T2)(*,T1,20,T3)(+,T2,T3,T3)(-,A,42,T4)(*,T3,2,T5)(+,M,N,T6)([]=,T6,_,T4[T5])7.4布爾表達(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)算符:<,<=,>=,>,=,≠。程序設(shè)計(jì)語言中,布爾表達(dá)式有兩個(gè)基本作用：一個(gè)是用作計(jì)算邏輯值(真1,假0)另一個(gè)是用作控制流語句如if-then、if-then-else和while-do等中的條件表達(dá)式布爾表達(dá)式的文法本節(jié)中考慮由下列文法產(chǎn)生的布爾表達(dá)式：

E→EorE|EandE|notE|(E)|idrelopid|id使用relop的屬性relop.op來確定relop所指的6種關(guān)系運(yùn)算中的哪一個(gè)。假定按慣例確定and,、or、not的優(yōu)先級(jí)和結(jié)合性。注意:此id表示布爾量布爾表達(dá)式的語義布爾式的語義是指明計(jì)算一個(gè)邏輯值的規(guī)則,有兩種計(jì)算規(guī)則:

1.用數(shù)值(1/0)表示真和假,同計(jì)算算術(shù)表達(dá)式一樣,一步不差地按序計(jì)算出整個(gè)布爾式的值。例如:計(jì)算1or(not0and0)or0=12.優(yōu)化(短路)方法，不一定一步不差的計(jì)算，可以由某個(gè)子布爾式的值確定整個(gè)布爾式的值。布爾表達(dá)式的計(jì)值規(guī)則規(guī)則2用于翻譯控制流語句中的布爾表達(dá)式尤其方便①計(jì)算EE1

E2

or=真真真假假假②計(jì)算EE1

E2

and=真真真假假假解釋為:ifE1thentrueelseE2解釋為:ifE1thenE2elsefalse7.4.1數(shù)值表示法首先考慮用1表示真，用0表示假來實(shí)現(xiàn)布爾表達(dá)式的翻譯。1.類似算術(shù)表達(dá)式求值方法計(jì)算布爾式值例:aorbandnotc翻譯為:T1:=notc

T2:=bandT1T3:=aorT2注意:此布爾式中的a,b,c是邏輯量(值0/1)!數(shù)值表示法：第2種方法求布爾式值一個(gè)形如a<b的關(guān)系表達(dá)式可等價(jià)的寫成:

ifa<bthen1else0并將它翻譯成如下三地址語句序列：100ifa<bgoto103101T:=0102goto104103T:=1104邏輯量a也作同樣翻譯，只要將a<b換為a。P186.圖7.13布爾式的數(shù)值表示法的翻譯模式

P187.例7.2

翻譯布爾式

a<borc<dande<f100ifa<b

goto103108ife<f

goto111101T1:=0109T3:=0102goto104110goto112103T1:=1111T3:=1104ifc<d

goto107112T4:=T2andT3105T2:=0113T5:=T1orT4106goto108114107T2:=1注意:這兒,三地址代碼的序號(hào)作標(biāo)號(hào)!布爾表達(dá)式的數(shù)值表示法翻譯：圖7.147.4.2作為條件控制的布爾式翻譯出現(xiàn)在條件語句：作為控制語句中的布爾表達(dá)式E，其作用僅僅在控制選擇語句S1和S2無須保留E的值，而是賦與予E兩個(gè)出口“真出口”轉(zhuǎn)向S1“假出口”轉(zhuǎn)向S2語句(7.10)可翻譯成如P187.圖7.15所示的代碼結(jié)構(gòu)。ifEthenS1elseS2(7.10)假出口真出口無條件轉(zhuǎn)移If_then_else語句的代碼結(jié)構(gòu)E.code:綜合屬性布爾式E的三地址代碼S.code:綜合屬性語句S的三地址代碼E.true:繼承屬性,E為‘真’時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào);E.false:繼承屬性,E為‘假’時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào)；S.next:繼承屬性,標(biāo)號(hào),緊隨S代碼之后的地址。E.codeS1.codeGotoS.nextS2.code……E.ture:E.false:S.next:ToE.tureToE.false布爾表達(dá)式的翻譯－短路計(jì)算對(duì)于布而表達(dá)式E:aorb如果a為true，則E為true

如果a為false，則E的值取決于b，要對(duì)b求值如果b為true，則E為true;如果b為false，則E為false對(duì)于布而表達(dá)式E:aandb如果a為false，則E為false如果a為true，則E的值取決于b，要對(duì)b求值如果b為true，則E為true;如果b為false，則E為false產(chǎn)生布爾式三地址跳轉(zhuǎn)代碼：例7.3例7.3應(yīng)用P188.表7.7的屬性文法語法制導(dǎo)翻譯布爾表達(dá)式

E=a<borc<dande<f

為跳轉(zhuǎn)三地址代碼：P189.

ifa<bgoto

Ltrue---表達(dá)式的真出口

gotoL1

L1:ifc<dgotoL2

goto

Lfalse---表達(dá)式的假出口L2:ife<fgoto

Ltrue

goto

Lfalse設(shè)實(shí)現(xiàn)三地址代碼時(shí)采用四元式形式,并且假定：

(jnz,a,_,p)

表示ifagotop

(jrop,x,y,p)

表示ifxropygotop

(j,_,_,p)

表示gotop例7.3布爾式a<borc<dande<f

翻譯為跳轉(zhuǎn)四元式序列:P189.

100(j<,a,b,Ltrue)104(j<,e,f,Lture)

101(j,_,_,102)105(j,_,_,

Lfalse)

102(j<,c,d,104)106

103(j,_,_,Lfalse)布爾式翻譯為四元式注意:有向前轉(zhuǎn)移!!7.5控制語句的翻譯分三類進(jìn)行討論:7.5.1控制流語句

if–thenif–then–elsewhile-do*7.5.2標(biāo)號(hào)與goto語句*7.5.3CASE語句的翻譯7.5.1控制流語句控制流語句的文法：P192.

S→ifEthenS1S→ifEthenS1elseS2S→whileEdoS1

其中E是布爾表達(dá)式。與7.4節(jié)一樣，先討論對(duì)這些語句進(jìn)行翻譯的一般語義規(guī)則(P193.表7.8)。然后討論如何通過一遍掃描產(chǎn)生上述語句的四元式代碼，給出相應(yīng)的翻譯模式(P195.~196.)。控制流語句的代碼結(jié)構(gòu)及屬性文法三條控制流語句的代碼結(jié)構(gòu)見P193.圖7.17。P193.表7.8是這三條控制流語句的屬性文法。用代碼結(jié)構(gòu)圖去理解屬性文法(表7.8)中給出的語義規(guī)則。該屬性文法產(chǎn)生三地址指令。屬性文法中:繼承屬性E.true、E.false、S.next綜合屬性E.code、S.code、S.begin||連接符號(hào)過程newlabel產(chǎn)生新的標(biāo)號(hào),標(biāo)識(shí)即將產(chǎn)生的指令過程Gen()產(chǎn)生字面標(biāo)號(hào)和轉(zhuǎn)移指令圖7.17(a)條件句的代碼結(jié)構(gòu)S→ifEthenS1E.true:繼承屬性,真出口,E為真時(shí)轉(zhuǎn)移到的標(biāo)號(hào);E.false:繼承屬性,假出口,E為假時(shí)轉(zhuǎn)移到的標(biāo)號(hào);E.code:綜合屬性,E的代碼S1.code:綜合屬性,S1的代碼S1.next:E.codeS1.code……E.ture:E.false:S.next:ToE.tureToE.false三個(gè)標(biāo)號(hào)表示同一位置S.code..圖7.17(b)條件句的代碼結(jié)構(gòu)S→ifEthenS1elseS2S.next:繼承屬性,是繼S的代碼之后的位置S1.next:繼承屬性,是繼S1的代碼之后的位置S2.next:繼承屬性,是繼S2的代碼之后的位置E.codeS1.codeGotoS.nextS2.code……E.ture:E.false:S.next:ToE.tureToE.falseS2.next:S1.next:三個(gè)標(biāo)號(hào)表示同一位置..S.code圖7.17(c)循環(huán)句的代碼結(jié)構(gòu)S→whileEdoS1

S.begin:綜合屬性,標(biāo)識(shí)S代碼的第1條指令,循環(huán)的開始位置E.codeS1.codeGotoS.begin……E.ture:E.false:S.next:ToE.tureToE.falseS.begin:S1.next:兩個(gè)標(biāo)號(hào)表示同一位置兩個(gè)標(biāo)號(hào)表示同一位置...S.code控制流語句翻譯為三地址碼：例7.5例7.5

P194.

考慮如下語句：

whilea＜bdoifc＜dthenx：=y＋zelsex：＝y(tǒng)-z根據(jù)表7.8的屬性文法,和圖7.10賦值語句的翻譯模式，得到代碼。

L1：ifa＜bgotoL2gotoLnextL2：ifc＜dgotoL3gotoL4L3：T1：=y＋zx：＝T1gotoL1L4：T2:=y－zx：＝T2gotoL1Lnext：控制流語句的文法：P194.

（1）S→ifEthenS（2）S→ifEthenSelseS條件句（3）S→whileEdoS循環(huán)句（4）S→beginLend復(fù)合句（5）S→A賦值句（6）L→L；S語句表(序列)（7）L→S其中E

為一個(gè)布爾表達(dá)式。使用回填技術(shù)翻譯控制流語句1.用emit()過程產(chǎn)生不完全的轉(zhuǎn)移四元式,如:(jnz,a,_,0);(j,_,_,0);(jrop,a,b,0)2.用makelist(i)函數(shù)創(chuàng)建一個(gè)僅包含i的新鏈表，i是四元式數(shù)組的一個(gè)索引(下標(biāo))，或說i是四元式代碼序列的一個(gè)標(biāo)號(hào)。3.一旦轉(zhuǎn)移目標(biāo)確定后,用backpatch(p,t)函數(shù)回填,將t填入鏈表p的所有四元式中。4.用merge(p1,p2)函數(shù)并鏈,將兩條待填轉(zhuǎn)移目標(biāo)相同的鏈合并為一條。翻譯考慮：使用過程和函數(shù)照這個(gè)方法,需要設(shè)置綜合屬性:E.truelist:真鏈表,E的代碼中需回填真出口的四元式標(biāo)號(hào)。E.falselist:假鏈表,E的代碼中需回填假出口的四元式標(biāo)號(hào)。S.nextlist:S的代碼中需轉(zhuǎn)移到S之后的代碼處的四元式標(biāo)號(hào)。L.nextlist:L的代碼中需轉(zhuǎn)移到L之后的代碼處的四元式標(biāo)號(hào)。變量nextquad

指向下一條將要產(chǎn)生但尚為形成的四元式標(biāo)號(hào),初值1,每執(zhí)行一次emit()后值自動(dòng)加1。翻譯考慮：設(shè)置綜合屬性在文法產(chǎn)生式適當(dāng)?shù)牡胤揭霕?biāo)記非終結(jié)符M,以便在適當(dāng)?shù)臅r(shí)候執(zhí)行一個(gè)語義動(dòng)作,記下下一個(gè)將要產(chǎn)生的四元式標(biāo)號(hào),使用綜合屬性M.quad

來標(biāo)記。SifEthenMS1

SifEthenM1S1

NelseM2S2

SwhileM1EdoM2S1引入標(biāo)記非終結(jié)符N標(biāo)記產(chǎn)生式

SifEthenS1elseS2的S1和S2之間的跳轉(zhuǎn)四元式(開始也是不完全的)標(biāo)號(hào),使用綜合屬性N.nextlist

來標(biāo)記。翻譯考慮：引入標(biāo)記非終結(jié)符翻譯模式的說明(P195.)(1).SifEthenM1S1NelseM2S2用此產(chǎn)生式歸約時(shí)：M1處回填E.truelistM2處回填E.falselist三鏈S1,S2

和N的nextlist合并,用S.nextlist標(biāo)記,暫不回填E.codeS1.codeM1.quad:S2.codegotoS.next...toE.truetoE.falseM2.quad:N.nextlist:S.code翻譯模式的說明(P195.)(4).SifEthenMS1

用此產(chǎn)生式歸約時(shí)：M處回填E.truelist兩條鏈S1.

nextlist,和E.falselist合并,用S.nextlist標(biāo)記,暫不回填E.codeS1.codeM.quad:...toE.truetoE.falseS.code翻譯模式的說明(P195.)(5).SwhileM1EdoM2S1

用此產(chǎn)生式歸約時(shí)：M1處回填S1.nextlistM2處回填E.truelist傳鏈

S.nextlist:=E.falselist產(chǎn)生無條件轉(zhuǎn)移指令E.codeS1.codeM1.quad:gotoM1.quad...toE.truetoE.falseM2.quad:S.code(2).N{N.nextlist:=makelist(nextquad);emit(′j,_,_,0′)}產(chǎn)生不完全轉(zhuǎn)移四元式,用N.nextlist標(biāo)記(3).M{M.quad:=nextquad}用M.quad標(biāo)記即將產(chǎn)生的下一條四元式標(biāo)號(hào)控制流語句的翻譯模式P195.控制流語句的翻譯模式P196.(6).SbeginLend{S.nextlist:=L.nextlist}傳鏈

(7).SA{S.nextlist:=makelist()}初始化S.nextlist為空鏈(8).LL1;MS{backpatch(L1.nextlist,M.quad);

L.nextlist:=S.nextlist}回填,傳鏈(9).LS{L.nextlist:=S.nextlist}1.先記錄要回填的轉(zhuǎn)移指令地址(標(biāo)號(hào))，在適當(dāng)?shù)臅r(shí)候進(jìn)行回填，以便賦值和布爾表達(dá)式的求值得到合適的連接，以完成程序的控制流程。2.上述規(guī)則中只有(2)和(5)產(chǎn)生新的轉(zhuǎn)移四元式,(2)產(chǎn)生不完全的轉(zhuǎn)移四元式,(5)產(chǎn)生完全的轉(zhuǎn)移四元式,其他四元式將由賦值語句及算術(shù)表達(dá)式和布爾表達(dá)式產(chǎn)生。控制流語句的翻譯模式:說明結(jié)合自下而上語法分析,翻譯下面的句子生成四元式

while(a<b)do

if(c＜d)thenx:=y+zP196.例7.6控制流語句的翻譯解:先根據(jù)控制語句的代碼結(jié)構(gòu)按序?qū)懗龈鞑糠值拇a,適當(dāng)?shù)胤郊尤霟o條件轉(zhuǎn)移代碼;然后分析句子的控制情況,決定轉(zhuǎn)移目標(biāo),回填,拉鏈。四元式序列如下:100(j<,a,b,0)104(+,y,z,T)101

(j,_,_,0)105(:=,T,_,x)102

(j<,c,d,0)106(j,_,_,100)103(j,_,_,0)107102)107)104)100)結(jié)合自下而上語法分析,翻譯以下句子生成四元式ifa>borc＜dande=fthenwhilex＜ydoz:=y*z

控制流語句的翻譯:舉例解:四元式序列如下:100(j>,a,b,0)106(j<,x,y,0)101

(j,_,_,102)107(j,_,_,0)102

(j<,c,d,0)108

(*,y,z,T)103(j,_,_,0)109(:=,T,_,z)104

(j=,e,f,0)

110(j,_,_,106)

105(j,_,_,0)111106)104)111)106)111)108)111)考慮如下語句的翻譯：

whilea＜bdoifc＜dtheny:=a*belsez:=c/d

100(j<,a,b,0)101(j,_,_,0)102