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

本章在編譯程序中的地位

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

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

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

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

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

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

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

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

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

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

assigna+bcuminus*

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

(1)遍歷左子樹；

(2)遍歷右子樹；

(3)訪問根結(jié)點。

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

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

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

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

ifagotoL;

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

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

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

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

x:＝*y;

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

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

(op,arg1,arg2）因為只有三個域，所以為三元式是為了避免把臨時變量填入符號表；而是通過計算整個這個臨時變量的值得語句的位置來引用該臨時變量；三地址代碼的實現(xiàn)(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcb(1)aarg1(0)(2)(3)(4)arg2opP172.表7.4(b)三地址語句的三元式表示三元式中使用了指向三元式語句的指針(序號)，序號也表示該三元式計算的結(jié)果值,三元式之間的聯(lián)系通過指針實現(xiàn)。三地址代碼實現(xiàn)：三元式a:=b*-c+b*-c三地址代碼實現(xiàn)：(0)(1)(2)(3)uminus*+assigncb(1)aarg1(0)(1)(2)arg2op三元式表(0)(1)(0)(1)(2)(3)間接代碼三元式表中沒有了重復(fù)的三元式，語句的移動僅改變左邊的間接碼表。另外的例見P173.表7.6。間接三元式（三元式的指針表）不直接使用三元式表，而是另外設(shè)一張指示器表(間接碼表)間接三元式a:=b*-c+b*-c寫中間語言：練習寫出表達式：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說明語句當考察一個過程或分程序的一系列說明語句時，便可為局部于該過程的名字分配存儲空間。對每個局部名字，將在符號表中建立相應(yīng)的表項，并填入相應(yīng)的信息如類型、嵌套深度、相對地址等。說明語句的翻譯目的就是建立符號表?！植孔兞俊刂吩黾酉鄬Φ刂坊刂贰鄬Φ刂肥侵赶鄬?shù)據(jù)區(qū)基地址的一個偏移量。如圖所示：符號表的結(jié)構(gòu)和組織(參見CH.8)符號表結(jié)構(gòu)例,P235.FORTRAN語言的SD表結(jié)構(gòu)。名字屬性地址種屬維數(shù)/形參個數(shù)類型數(shù)據(jù)區(qū)號相對地址

a局部變量整型120

b數(shù)組2實型2100

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

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

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

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

查表③①查表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為三地址代碼。掌握手工生成賦值句的三地址代碼的方法：按運算順序?qū)懗鋈刂氛Z句。賦值語句和算術(shù)表達式翻譯：練習三地址語句序列:T1:=uminusa

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

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

:high

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

的相對地址為：

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

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

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

每維

的長度(n1、n2)

ni=highi－lowi+1P180.

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

的相對地址計算公式：

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ù)組元素的下標無關(guān),是一個定數(shù),C值可放在符號表數(shù)組A的表項中,或數(shù)組內(nèi)情向量中。k維數(shù)組元素地址計算一般,對于一個k維數(shù)組P180.

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

各維的長度ni=highi－lowi+1則數(shù)組元素A[i1,i2,…,ik]的相對地址計算：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ù)組,動態(tài)數(shù)組靜態(tài)數(shù)組：數(shù)組說明中各維的上下界是確定的C值在編譯的時候就能計算出來動態(tài)數(shù)組：數(shù)組說明中各維的上下界有不確定的C值在編譯的時候不能計算出來,運行時才能計算計算動態(tài)數(shù)組元素地址的公式與靜態(tài)數(shù)組是同樣的，只是上、下界在編譯時是未知的。數(shù)組元素引用的文法:P181.

L→id[Elist]|id

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

Elist→Elist,E|E

Elist表示下標列表Elist

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

nj

:=highj

–lowj

+1(7.8)

遞歸公式em

=em-1*nm+im

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

的信息，改寫文法為：

L→Elist]

|id

Elist→Elist,E|id[E

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

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

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

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

中的下標表達式計算出來的值:

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

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

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

地址表示T2[T1]3.對二維數(shù)組元素A[i,j]產(chǎn)生4個地址計算的三地址語句: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]的地址變化部分的計算值

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

賦值語句A[i1,i2]

:=E

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

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

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

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

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

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

則計算C值

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

x:=A[y,z]

進行翻譯，帶注釋的分析樹如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步歸約時產(chǎn)生計算數(shù)組元素地址的代碼數(shù)組元素的引用翻譯:例7.1賦值語句x:=A[y,z]

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

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

注意：20(第2維長度)、84(C值)、4(寬度)都是編譯中引入的常量,用A代表數(shù)組的首地址。⑦7地址的變化部分計算:*,+⑧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計算下標值一維B[k]二維A[i+2,j+1]數(shù)組元素引用翻譯:練習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ù)組元素引用翻譯:練習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布爾表達式的翻譯布爾表達式是用布爾運算符號and、or、not

作用到布爾變量或關(guān)系表達式上而組成的。關(guān)系表達式形式如E1relopE2,其中E1和E2是算術(shù)表達式，relop為關(guān)系運算符:<,<=,>=,>,=,≠。程序設(shè)計語言中,布爾表達式有兩個基本作用：一個是用作計算邏輯值(真1,假0)另一個是用作控制流語句如if-then、if-then-else和while-do等中的條件表達式布爾表達式的文法本節(jié)中考慮由下列文法產(chǎn)生的布爾表達式：

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

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

E2

or=真真真假假假②計算EE1

E2

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

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

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注意:這兒,三地址代碼的序號作標號!布爾表達式的數(shù)值表示法翻譯：圖7.147.4.2作為條件控制的布爾式翻譯出現(xiàn)在條件語句：作為控制語句中的布爾表達式E，其作用僅僅在控制選擇語句S1和S2無須保留E的值，而是賦與予E兩個出口“真出口”轉(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為‘真’時控制流轉(zhuǎn)向的標號;E.false:繼承屬性,E為‘假’時控制流轉(zhuǎn)向的標號；S.next:繼承屬性,標號,緊隨S代碼之后的地址。E.codeS1.codeGotoS.nextS2.code……E.ture:E.false:S.next:ToE.tureToE.false布爾表達式的翻譯－短路計算對于布而表達式E:aorb如果a為true，則E為true

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

E=a<borc<dande<f

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

ifa<bgoto

Ltrue---表達式的真出口

gotoL1

L1:ifc<dgotoL2

goto

Lfalse---表達式的假出口L2:ife<fgoto

Ltrue

goto

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

(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控制語句的翻譯分三類進行討論:7.5.1控制流語句

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

S→ifEthenS1S→ifEthenS1elseS2S→whileEdoS1

其中E是布爾表達式。與7.4節(jié)一樣，先討論對這些語句進行翻譯的一般語義規(guī)則(P193.表7.8)。然后討論如何通過一遍掃描產(chǎn)生上述語句的四元式代碼，給出相應(yīng)的翻譯模式(P195.~196.)?？刂屏髡Z句的代碼結(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||連接符號過程newlabel產(chǎn)生新的標號,標識即將產(chǎn)生的指令過程Gen()產(chǎn)生字面標號和轉(zhuǎn)移指令圖7.17(a)條件句的代碼結(jié)構(gòu)S→ifEthenS1E.true:繼承屬性,真出口,E為真時轉(zhuǎn)移到的標號;E.false:繼承屬性,假出口,E為假時轉(zhuǎn)移到的標號;E.code:綜合屬性,E的代碼S1.code:綜合屬性,S1的代碼S1.next:E.codeS1.code……E.ture:E.false:S.next:ToE.tureToE.false三個標號表示同一位置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:三個標號表示同一位置..S.code圖7.17(c)循環(huán)句的代碼結(jié)構(gòu)S→whileEdoS1

S.begin:綜合屬性,標識S代碼的第1條指令,循環(huán)的開始位置E.codeS1.codeGotoS.begin……E.ture:E.false:S.next:ToE.tureToE.falseS.begin:S1.next:兩個標號表示同一位置兩個標號表示同一位置...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

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

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

來標記。SifEthenMS1

SifEthenM1S1

NelseM2S2

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

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

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

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

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

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

用此產(chǎn)生式歸約時：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標記(3).M{M.quad:=nextquad}用M.quad標記即將產(chǎn)生的下一條四元式標號控制流語句的翻譯模式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)移指令地址(標號)，在適當?shù)臅r候進行回填，以便賦值和布爾表達式的求值得到合適的連接，以完成程序的控制流程。2.上述規(guī)則中只有(2)和(5)產(chǎn)生新的轉(zhuǎn)移四元式,(2)產(chǎn)生不完全的轉(zhuǎn)移四元式,(5)產(chǎn)生完全的轉(zhuǎn)移四元式,其他四元式將由賦值語句及算術(shù)表達式和布爾表達式產(chǎn)生?？刂屏髡Z句的翻譯模式:說明結(jié)合自下而上語法分析,翻譯下面的句子生成四元式

while(a<b)do

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