編譯原理課件：第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成

第8章語(yǔ)法制導(dǎo)翻譯和中間代碼生成§8.1概述語(yǔ)法分析后的源程序語(yǔ)義處理中間代碼或目標(biāo)代碼一、語(yǔ)義處理的任務(wù)：根據(jù)語(yǔ)義規(guī)則對(duì)識(shí)別出的各種語(yǔ)法成分析其含義，進(jìn)行初步翻譯，生成相應(yīng)的中間代碼或直接生成目標(biāo)代碼。第一靜態(tài)語(yǔ)義分析或靜態(tài)審查。第二動(dòng)態(tài)語(yǔ)義處理：

編譯中的語(yǔ)義處理是指兩個(gè)功能

①類型檢查。

②控制流檢查：確保控制語(yǔ)句有合法的轉(zhuǎn)向點(diǎn)。③一致性檢查。

④相關(guān)名字檢查。⑤名字的作用域分析第一:靜態(tài)語(yǔ)義分析通常包括：如果靜態(tài)語(yǔ)義正確，語(yǔ)義處理則要執(zhí)行真正的翻譯，即，或者將源程序翻譯成程序的一種中間表示形式（中間代碼），或者將源程序翻譯成目標(biāo)代碼。

第二動(dòng)態(tài)語(yǔ)義處理：實(shí)際應(yīng)用中比較流行的語(yǔ)義分析方法：基于屬性文法的語(yǔ)法制導(dǎo)翻譯方法

8.2屬性文法屬性文法：屬性：

所謂屬性，用以描述事物或人的特征、性質(zhì)，品質(zhì)等等。比如，談到一個(gè)物體，可以用“顏色”描述它，談起某人，可以使用“有幽默感“來(lái)形容他。對(duì)一個(gè)文法,文法中的每個(gè)符號(hào)都有屬性，可以用"類型"、"值"或"存儲(chǔ)位置"來(lái)描述它。附加了一組屬性和運(yùn)算（語(yǔ)義）規(guī)則的文法

屬性文法文法符號(hào)X的屬性t常用X.t來(lái)表示語(yǔ)義規(guī)則用花括號(hào)｛｝括起來(lái)，可被插入到產(chǎn)生式右部的任何合適的位置上。不同的產(chǎn)生式對(duì)應(yīng)不同的語(yǔ)義規(guī)則不同的分析目標(biāo)也對(duì)應(yīng)不同的語(yǔ)義規(guī)則

1.屬性的表示2.語(yǔ)義規(guī)則的表示語(yǔ)義信息語(yǔ)義之間的關(guān)系一個(gè)屬性文法是一個(gè)三元組：

A＝（G，V，F(xiàn)），

G:是一個(gè)上下文無(wú)關(guān)文法

V:有窮的屬性集,每個(gè)屬性與文法的一終結(jié)符或非終結(jié)符相連。

F:關(guān)于屬性的屬性斷言或謂詞集.每個(gè)斷言與一個(gè)產(chǎn)生式相聯(lián)。一個(gè)斷言就是一個(gè)語(yǔ)義規(guī)則，描述各屬性的關(guān)系。用法：針對(duì)語(yǔ)義：為每個(gè)符號(hào)設(shè)置一個(gè)屬性，終結(jié)符號(hào)用單詞屬性。為每個(gè)產(chǎn)生式設(shè)置語(yǔ)義規(guī)則——描述各屬性的關(guān)系。屬性文法的定義：屬性分為兩種

繼承屬性和綜合屬性綜合屬性：在語(yǔ)法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性由該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值確定。它的計(jì)算規(guī)則由底向上.

繼承屬性:在語(yǔ)法樹中，一個(gè)結(jié)點(diǎn)的繼承屬性由該結(jié)點(diǎn)的父結(jié)點(diǎn)/兄弟結(jié)點(diǎn)的屬性確定。

例綜合屬性

LEEE1+TETTT1*FTFF(E)Fiprint(E.val)E.val=E1.val+T.valE.val=T.valT.val=T1.valF.valT.val=F.valF.val=E.valF.val=i.lexval語(yǔ)義規(guī)則產(chǎn)生式計(jì)算3*5+4的值3*5+4的分析樹只使用綜合屬性.LEETTFTFFi5i4i3+*3*5+4的分析樹一個(gè)結(jié)點(diǎn)的綜合屬性值是其子結(jié)點(diǎn)的某些屬性來(lái)決定的通常使用自底向上的分析方法在每個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則來(lái)計(jì)算綜合屬性值當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語(yǔ)義子程序從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算

LEEE1+TETTT1*FTFF(E)Fiprint(E.val)E.val=E1.val+T.valE.val=T.valT.val=T1.valF.valT.val=F.valF.val=E.valF.val=i.lexval語(yǔ)義規(guī)則產(chǎn)生式繼承屬性一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性來(lái)決定的。例，添加標(biāo)識(shí)符類型的語(yǔ)義描述：繼承屬性

L1.in:=L.in產(chǎn)生式語(yǔ)義規(guī)則DTL

Tint

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

addtype(id.entry,L.in)

addtype(id.entry,L.in)與L產(chǎn)生式相聯(lián)的語(yǔ)義規(guī)則中有一個(gè)過(guò)程調(diào)用addtype，過(guò)程addtype的功能是把每個(gè)標(biāo)識(shí)符的類型信息登錄在符號(hào)表的相關(guān)項(xiàng)中。句子intid1,id2的語(yǔ)法樹，使用

表示屬性的傳遞情況。

L1.in:=L.in產(chǎn)生式語(yǔ)義規(guī)則DTL

Tint

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

addtype(id.entry,L.in)

addtype(id.entry,L.in)DTLLid1id2，int1、文法非終結(jié)符既可有綜合屬性，也可有繼承屬性；2、開始符號(hào)沒(méi)有繼承屬性；3、終結(jié)符只有綜合屬性，由詞法分析器提供。幾點(diǎn)說(shuō)明：語(yǔ)法制導(dǎo)翻譯：將語(yǔ)義規(guī)則與語(yǔ)法規(guī)則相結(jié)合，在語(yǔ)法分析的過(guò)程中通過(guò)執(zhí)行語(yǔ)義動(dòng)作，計(jì)算語(yǔ)義屬性值，從而完成預(yù)定的翻譯工作。8.3語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯分為兩種處理方法：（1）自底向上的翻譯：（只有綜合屬性）對(duì)每個(gè)產(chǎn)生式編制一個(gè)語(yǔ)義子程序，在進(jìn)行語(yǔ)法分析的過(guò)程中，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語(yǔ)義子程序?qū)崿F(xiàn)語(yǔ)義檢查與翻譯。這種實(shí)現(xiàn)方案隱藏了其中語(yǔ)義規(guī)則的計(jì)算次序等實(shí)現(xiàn)細(xì)節(jié)。（2）自頂向下翻譯（含有繼承屬性）：在產(chǎn)生式右部的適當(dāng)位置，插入相應(yīng)的語(yǔ)義動(dòng)作，即語(yǔ)義規(guī)則或語(yǔ)義動(dòng)作用花括號(hào)｛｝括起來(lái)，可被插入到產(chǎn)生式右部的任何合適的位置上。按照分析的進(jìn)程，執(zhí)行遇到的語(yǔ)義動(dòng)作。這是一種動(dòng)作與分析交錯(cuò)的實(shí)現(xiàn)方案。綜合屬性繼承屬性自底向上傳遞信息自頂向下（自左向右）傳遞信息僅包含綜合屬性的語(yǔ)法制導(dǎo)定義如：算術(shù)表達(dá)式求值的屬性文法S-屬性文法和自下而上的翻譯一個(gè)結(jié)點(diǎn)的綜合屬性值是其子結(jié)點(diǎn)的某些屬性來(lái)決定的２+3*4的注釋分析樹通常使用自底向上的分析方法在每個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則來(lái)計(jì)算綜合屬性值當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語(yǔ)義子程序從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算只含有綜合屬性的語(yǔ)法制導(dǎo)定義稱為S屬性定義L-屬性文法在自上而下分析中的實(shí)現(xiàn)既包括綜合屬性，又包括繼承屬性，即對(duì)于所有Ａ→Ｘ1

Ｘ2

…

Ｘn，每一個(gè)屬性或者都是綜合屬性，或者Ｘi屬性計(jì)算僅使用ＡＸ1

Ｘ2

…

Ｘi-1

的屬性,這種叫L-屬性的文法法制導(dǎo)定義其屬性可用深度優(yōu)先的順序從左至右計(jì)算非L-屬性的文法制導(dǎo)定義產(chǎn)生式語(yǔ)義規(guī)則ALMAQRL.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s)R.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)表中的語(yǔ)法制導(dǎo)定義不是L-屬性定義文法符號(hào)Q的繼承屬性依賴于它右邊文法符號(hào)R的屬性

L1.in:=L.in產(chǎn)生式語(yǔ)義規(guī)則DTL

Tint

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

addtype(id.entry,L.in)

addtype(id.entry,L.in)L-屬性文法的例子DTLLid1id2，int例一個(gè)簡(jiǎn)單的翻譯模式

E→TRR→addopT{print(addop.lexeme)}R1|εT→num{print(num.val)}輸入9-5+2,其分析樹如下頁(yè)圖，當(dāng)按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問(wèn)的語(yǔ)義動(dòng)作，將輸出結(jié)果是什么？它輸出結(jié)果是：95-2+它是輸出表達(dá)式9-5+2的后綴式。ET9TPt(′9′)RPt(′-′)Pt(′+′)R-5Pt(′5′)+T2Pt(′2′)R9-5+2的帶語(yǔ)義動(dòng)作的分析樹E→TRR→addopT{print(addop.lexeme)}R1|εT→num{print(num.val)}輸出：

95-2+設(shè)計(jì)翻譯模式分兩種情況:1、只需要綜合屬性的情況2.既有綜合屬性又有繼承屬性為每一個(gè)語(yǔ)義規(guī)則建立一個(gè)包含賦值的動(dòng)作，并把這個(gè)動(dòng)作放在相應(yīng)的產(chǎn)生式右邊的末尾。例如：TT1*F{Tval:=T1val*Fval}TT1*F{Tval:=T1val*Fval}1.只需要綜合屬性的情況：產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來(lái)。一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊符號(hào)的屬性。產(chǎn)生式左邊非終結(jié)符號(hào)的綜合屬性只有在它所引用的所有屬性都計(jì)算出來(lái)以后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通?？煞旁诋a(chǎn)生式右端的未尾。2.既有綜合屬性又有繼承屬性下面的翻譯模式不滿足要求,不滿足第1)個(gè)條件：

SA1A2{A1in:=1;A2in:=2}Aa{print(Ain)}可以看出,按深度優(yōu)先遍歷輸入串a(chǎn)a的語(yǔ)法樹，當(dāng)要打印屬性A.in時(shí)，該屬性還沒(méi)有定義。也就是說(shuō)，從S開始按深度優(yōu)先遍歷A1和A2子樹之前，A1.in和A2.in的值還未賦值。SA1A2aaA1.in:=1;A2.in:=2Print(A.in)Print(A.in)如果計(jì)算A1.in和A2.in的值的動(dòng)作分別被嵌入在產(chǎn)生式SA1A2的右部A1和A2之前，而不是后面，那么A.in在執(zhí)行Print（A.in）時(shí)已有定義。S{A1in:=1}A1{A2in:=2}

A2Aa{print(Ain)}SA1A2aaA1.in:=1;Print(A.in)Print(A.in)A2.in:=2;常見的中間代碼形式：后綴式三地址代碼（四元式、三元式和間接三元式）圖形（抽象語(yǔ)法樹等）

中間代碼：一種介于源語(yǔ)言和目標(biāo)語(yǔ)言之間的中間語(yǔ)言形式中間代碼逆波蘭記號(hào)

逆波蘭記號(hào)是最簡(jiǎn)單的一種中間代碼表示形式。這種表示法將運(yùn)算對(duì)象寫在前面，把運(yùn)算符號(hào)寫在后面，比如把a(bǔ)+b寫成ab+，把a(bǔ)*b寫成ab*，用這種表示法表示的表達(dá)式也稱做后綴式。中綴表示后綴表示

a+bab+

a+b*cabc*+

(a+b)*cab+c*a:=b*c+b*dabc*bd*+:=特點(diǎn)1、運(yùn)算對(duì)象出現(xiàn)的順序和原有順序（從左到右）相同2、運(yùn)算符按實(shí)際計(jì)算順序（從左到右）出現(xiàn)3、運(yùn)算符緊跟在運(yùn)算對(duì)象的后面出現(xiàn)，且沒(méi)有括號(hào)優(yōu)點(diǎn)：簡(jiǎn)明、便于計(jì)值后綴表示法表示表達(dá)式，其最大的優(yōu)點(diǎn)是易于計(jì)算機(jī)處理表達(dá)式。常用的算法是使用一個(gè)棧，自左至右掃描算術(shù)表達(dá)式（后綴表示），每掃描到運(yùn)算對(duì)象，就把它推進(jìn)棧；掃描到運(yùn)算符，若該運(yùn)算符是二目的，則對(duì)棧頂部的兩個(gè)運(yùn)算對(duì)象實(shí)施該運(yùn)算，并將運(yùn)算結(jié)果代替這兩個(gè)運(yùn)算對(duì)象而進(jìn)棧；若是一目運(yùn)算符，則對(duì)棧頂元素執(zhí)行該運(yùn)算，并以運(yùn)算結(jié)果代替該元素進(jìn)棧，最后的結(jié)果留在棧頂。

例如B@CD*+（它的中綴表示為－B+C*D，使用@表示一目減）的計(jì)值過(guò)程為：B進(jìn)棧；對(duì)棧頂元素施行一目減運(yùn)算，并將結(jié)果代替棧頂，即－B置于棧頂；C進(jìn)棧；

D進(jìn)棧；棧頂兩元素相乘，兩元素退棧，相乘結(jié)果置棧頂；棧頂兩元素相加，兩元素退棧，相加結(jié)果進(jìn)棧，現(xiàn)在棧頂存放的是整個(gè)表達(dá)式的值。

逆波蘭表示很容易擴(kuò)充到表達(dá)式以外的范圍。只要遵守運(yùn)算對(duì)象后直接緊跟它們的運(yùn)算符的規(guī)則即可。比如把轉(zhuǎn)語(yǔ)句GOTOL寫為“Ljump"，

運(yùn)算對(duì)象L為語(yǔ)句標(biāo)號(hào)，運(yùn)算符jump表示轉(zhuǎn)到某個(gè)標(biāo)號(hào)L。再比如條件語(yǔ)句ifEthenS1elseS2

可表示為：ES1S2￥，把ifthenelse看成三目運(yùn)算符，用￥來(lái)表示。例:給出下列表達(dá)式的逆波蘭式:(1)a*(-b+c)(2)a+b*(c+d/e)解(1)ab@c+*(2)abcde/+*+練習(xí):P2021

另一類中間代碼形式是三元式。把表達(dá)式及各種語(yǔ)句表示成一組三元式(op,ARG1,ARG2)。分別是算符op，第一運(yùn)算對(duì)象ARG1和第二運(yùn)算對(duì)象ARG2。運(yùn)算對(duì)象可能是源程序中的變量，也可能是某個(gè)三元式的結(jié)果，用三元式的編號(hào)表示。例如a:=b*c+b*d的表示為：

（1）（*，b，c）

（2）（*，b，d）

（3）（+（1），（2））

（4）（∶＝（3），a）三元式和樹形表示例：A=B+C*D/EF=C*D三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)*,C,D(6)=,F,(1)

不便于代碼優(yōu)化：刪除某些三元式后可能需作一系列的修改

三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)=,F,(1)間接三元式執(zhí)行順序（間接碼表）(1)(2)(3)(4)(1)(5)三元式的執(zhí)行次序用另一張表表示,優(yōu)化時(shí)三元式可以不變，僅僅改變其執(zhí)行順序表例:A+B*(C-D)+E/(C-D)^N三元式：

（1）（－C

D）

（2）（*B（1））

（3）（+

A（2））

（4）（－C

D）

（5）（^（4）N）

（6）（/

E（5））

（7）（+（3）（6））

間接三元式：

（1）(－C

D)

（2）(*

B

(1))

（3）(+

A(2))

（4）(^(1)

N）

（5）(/

E

(4))（6）(+

(3)

(5))

間接碼表

（1）

（2）

（3）

（1）

（4）

（5）

（6）每生成一條指令，先檢查已生成的間接三元式序列，若已有,不再生成,只把序號(hào)列入間接碼表。間接碼表明了間接三元式執(zhí)行的順序樹形表示是三元式表示的翻版。例:a∶=b*c+b*d可表示成下面的樹表示：

例表達(dá)式(A-12)*B+6的語(yǔ)法結(jié)構(gòu)樹將賦值語(yǔ)句變換為語(yǔ)法結(jié)構(gòu)樹基本函數(shù)——結(jié)點(diǎn)構(gòu)造Mknode(op,left,right)建標(biāo)記為op的算符結(jié)點(diǎn),結(jié)點(diǎn)有兩個(gè)域，分別為left和right.Mkleaf(id,entry)建標(biāo)記為id的葉結(jié)點(diǎn)，有一個(gè)entry域，它是指向符號(hào)表的入口。Mkleaf(num,val)建標(biāo)記為id的葉結(jié)點(diǎn),有一個(gè)val域，是表示該數(shù)的值。構(gòu)造a-4+c的語(yǔ)法樹：

＋－id指向c的入口id指向a的入口num4(1)p1:=mkleaf(id,entrya);(2)p2:=mkleaf(num,4);(3)p3:=mknode(‘-’，p1,p2)(4)p4:=mkleaf(id,entryc)(5)p5:=mknode(‘+’,p3,p4)語(yǔ)法制導(dǎo)定義(屬性文法)E.p是語(yǔ)法結(jié)構(gòu)樹指針?biāo)脑胶腿降闹饕煌谟冢脑綄?duì)中間結(jié)果的引用必須通過(guò)給定的名字，而三元式是通過(guò)產(chǎn)生中間結(jié)果的三元式編號(hào)。也就是說(shuō)，四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的。(OP,ARG1,ARG2,T)有時(shí)，為了更直觀，也把四元式的形式寫成簡(jiǎn)單賦值形式或更易理解的形式。比如把a(bǔ)∶=b*c+b*d四元式序列寫成：

（1）t1∶=b*c

（2）t2∶=b*d

（3）t3∶=t1+t2

（4）a∶=t3

把（jump，－，－，L）寫成gotoL

把（jrop，B，C，L）寫成ifBropCgotoL2．具體實(shí)現(xiàn)四元式操作符操作數(shù)1操作數(shù)2結(jié)果結(jié)果：通常是由編譯引進(jìn)的臨時(shí)變量例:X=(A+B)*(C+D)-E+,A,B,T1+,C,D,T2*,T1,T2,T3-,T3,E,T4=,T4,一,XT1,T2,T3,T4為臨時(shí)變量，由四元式優(yōu)化比較方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T4請(qǐng)將表達(dá)式-(a+b)*(c+d)-(a+b)分別表示成三元式、間接三元式和四元式序列。

三元式

(1)(+a,b)

(2)(+c,d)

(3)(*(1),(2))

(4)(-(3),/)

(5)(+a,b)

(6)(-(4),(5))

間接三元式

間接三元式序列間接碼表

(1)(+a,b)

(1)

(2)(+c,d)

(2)

(3)(*(1),(2))

(3)

(4)(-(3),/)

(4)

(5)(-(4),(1))

(1)

(5)四元式

(1)(+,a,b,t1)

(2)(+,c,d,t2)

(3)(*,t1,t2,t3)

(4)(-,t3,/,t4)

(5)(+,a,b,t5)

(6)(-,t4,t5,t6)簡(jiǎn)單的賦值語(yǔ)句的（四元式）翻譯四元式形式：t:=arg1oparg2語(yǔ)義屬性：,E.place

函數(shù)：lookup()

過(guò)程：emit(t:=arg1oparg2)（生成一條指令）

newtemp;(分配一個(gè)臨時(shí)工作單元）(1)S→id∶=E{p∶=lookup（id．name）；

ifp≠nil

then

Emit（p‘∶=’E．place）

else

error}

(2)E→E1+E2{E．place∶=newtemp；

Emit（E.place‘∶=’E1.place‘+’E2．place）}

(3)E→E1*E2{E.placeE∶=newtemp；

Emit（E.place‘∶=’E1.place‘*’E2.place）}

(4)E→－E1{E.Place‘∶=’newtemp；

Emit（E．Place‘:=’‘uminus’E1．place）}

(5)E→（E1）{E．Place’∶=’E1．place}

(6)E→id{p:=lookup（id．name）}；

if

p≠nilthen

E．placeE’∶=’p

else

error}賦值語(yǔ)句的四元式翻譯實(shí)際上，在一個(gè)表達(dá)式中可能出現(xiàn)各種不同類型的變量，而不象前面假定為同一類型。因此，上例應(yīng)改為P181圖8.13的形式。8.3布爾表達(dá)式的翻譯程序設(shè)計(jì)語(yǔ)言中的布爾表達(dá)式有兩個(gè)作用。一是計(jì)算邏輯值更多的情況是二:用做改變控制流語(yǔ)句中的條件表達(dá)式，如在if-then，if-then-else，或是while-do語(yǔ)句中那樣。布爾表達(dá)式是由布爾算符and，or和not或表示為（∧，∨和┓）施于布爾變量或關(guān)系表達(dá)式而成。約定優(yōu)先順序?yàn)椹?∧,∨,遵循左結(jié)合。布爾表達(dá)式有兩個(gè)作用：是計(jì)算邏輯值用來(lái)改變控制流語(yǔ)句中的條件表達(dá)式。布爾表達(dá)式的翻譯方法通常，計(jì)算布爾表達(dá)式的值有兩種辦法:第一種辦法，如同計(jì)算算術(shù)表達(dá)式一樣，步步計(jì)算出各部分的真假值，最后計(jì)算出整個(gè)表達(dá)式的值。那么布爾表達(dá)式1or（not0and0）or0的計(jì)算過(guò)程是：

1or（not0and0）or0

＝1or（1and0）or0

＝1or0or0

＝1or0

＝1

用數(shù)值1表示true，用0表示false。另一種計(jì)算方法是采取某種優(yōu)化措施，只計(jì)算部分表達(dá)式.例如要計(jì)算AorB，若計(jì)算出A的值為1，那么B的值就無(wú)需再計(jì)算了，因?yàn)椴还蹷的值為何結(jié)果，AorB的值都為1。如計(jì)算AandB若A為假值0，則無(wú)需計(jì)算B，結(jié)果為0。這種計(jì)算方法，意味著可以用if–then-else來(lái)解釋∧，∨和┓即：把A∨B解釋成：ifAthentrueelseB把A∧B解釋成：ifAthenBelsefals.把┓A解釋成：ifAthenfalseelsetrue控制語(yǔ)句中布爾表達(dá)式的翻譯

現(xiàn)在討論出現(xiàn)在ifthen；ifthenelse和whiledo等語(yǔ)句中的布爾表達(dá)式E的翻譯。

這三種語(yǔ)句的語(yǔ)法為：

S→ifEthenS1|ifEthenS1elseS2|whileEdoS1

控制語(yǔ)句的代碼結(jié)構(gòu)

(a)ifEthenS1E的代碼.

。S1的代碼JumpoutS2的代碼out(b)|ifEthenS1elseS2E的代碼.

。

S1的代碼真假beginE的代碼.

。S1的代碼Jumpbegin(c)whileEdoS1對(duì)于E為E1orE2的形式：1、E1為真，則E為真，即E的真出口為E1的真出口。2、E1為假，計(jì)算E2，即E1的假出口應(yīng)為E2的第一個(gè)四元式標(biāo)號(hào)，E2的真、假出口與E的真、假出口一樣。翻譯的基本思路：對(duì)于E為aropb,形成代碼為：IfaropbgotoE.truegotoE.false把條件轉(zhuǎn)移的布爾表達(dá)式E翻譯成僅含條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移的四元式E：aropbifaropbgotoE.truegotoE.false如：a<borc<dande<f可以翻成如下四元式：（1)ifa<bgoto(2)goto

（3）ifc<dgoto(4)goto(5)ife<fgoto(6)gotoE.tue(3)(5)E.falseE.trueE.false我們使用E．true和E．false分別表示整個(gè)表達(dá)式a＜borc＜dande<f的真、假出口，而E．true和E．false的值并不能在產(chǎn)生四元式的同時(shí)就知道。為了看清這一點(diǎn)，我們把該表達(dá)式放在條件語(yǔ)句中考慮，如語(yǔ)句If(a＜borc＜dande<f)thenS1elseS2的四元式序列見下頁(yè)：（1）if

a＜b

goto

（2）goto

（3）if

c＜d

goto

（4）goto

（5）if

e<f

goto

（6）goto

（7）（關(guān)于S1的四元式）

…

（p）goto

（p+1）（關(guān)于S2的四元式）

…

（q）If(a＜borc＜dande<f)thenS1elseS2的四元式序列為（7）（3）（5）(p+1)（q）（7）（p+1）使用拉鏈回填翻譯控制語(yǔ)句中的布爾表達(dá)式拉鏈：

……….L1:gotoL;

……….L2:gotoL;

……….L3:gotoL;

……….L:……….

L2L10語(yǔ)義描述使用的量：E.true“真”鏈，E.false“假”鏈E.codebeginE的第一個(gè)四元式

nextstat下一四元式地址

過(guò)程：

emit()

輸出一條四元式

merge(p1,p2)

例：

merge(p1,p2)(p100)goto0

……

p1鏈(p10)gotop100……`(p1)gotop10(p200)goto0……

p2鏈(p20)gotop200……(p2)gotop20

backpatch(p,t)

把p所鏈接的每個(gè)四元式的第四區(qū)段都填為t。如：E1orE2E1有一個(gè)真出口，E2也有一個(gè)真出口，將兩個(gè)鏈合并為一條鏈。p1（7）E→true{E.true:=nextstat;E.codebegin:=nextstat;emit(‘goto’__)}(8)E→false{E.false:=nextstat;E.codebegin:=nextstat;emit(‘goto’__)}以表達(dá)式a<borc<dande>f為例，它的四元式序列：100：ifa<bgoto

101:goto

102：ifc<dgoto

103：goto104:ife>fgoto105:goto將分析產(chǎn)生語(yǔ)法樹時(shí)的語(yǔ)義動(dòng)作結(jié)果“真”“假”鏈情況注釋在相應(yīng)結(jié)點(diǎn)處，見P185圖8.17E.true102104E.falseE.trueE.false控制語(yǔ)句的翻譯條件轉(zhuǎn)移

考慮ifthen，ifthenelse和whiledo語(yǔ)句，在圖8.12中已給出了它們的代碼結(jié)構(gòu)。這里我們使用下面文法G[S]定義這些語(yǔ)句：

G[S]

（1）S→ifEthenS

（2）|

ifEthenSelseS

（3）|

whileEdoS

（4）|

beginLend

（5）|

A

（6）L→L；S

（7）|S

其中各非終結(jié)符號(hào)的意義是：

S--語(yǔ)句

L--語(yǔ)句串

A--賦值句

E--布爾表達(dá)式為了能使語(yǔ)義在程序置于每個(gè)產(chǎn)生式的最后，需對(duì)原文法的產(chǎn)生式拆分，對(duì)G(S)進(jìn)行拆分修改為G(S’):(1)S→CS1(8)C→ifEthen(2)S→TpS2(9)Tp→CSelse(3)S→WdS3(10)Wd→WEdo(4)S→beginLend(11)W→while(5)

S→A(6)S→LsS1(12)Ls→L;(7)L→S(1)S→CS1{S.Chain:=merge(C.Chain,S1.Chain)(8)C→ifEthen{backpatch(E.true,nextstat)C.chain:=E.false}(9)Tp→CS1else{q:=nextstatemit(‘goto’___)backpatch(C.Chain,nextstat)Tp.Chain:=merge(S1.chain,q)}(2)S→TpS2{S.chain:=merge(Tp.Chain,S2.Chain)}(11)W→while{W.codebegin:=nextstat}(10)Wd→WEdo{backpatch(E.true,nextstat)Wd.chain:=E.false

Wd.codebegin:=W.codebegin}S→WdS3{backpatch(S3.chain,Wd.codebegin)emit(‘goto’Wd.codebegin)S.chain:=Wd.chain}(4)S→beginLend{S.chain:=L.chain}(5)

S→A{S.chain:=0/*空鏈*/}L→S{L.chain:=S.chain}(12)Ls→L;{backpatch(L.chain,nextstat)}(6)L→LsS1{L.chain:=S1.chain}按照上述文法產(chǎn)生式相應(yīng)的語(yǔ)義動(dòng)作，加上前述關(guān)于賦值句和布爾表達(dá)式的翻譯法，語(yǔ)句

while（A＜B）doif（C＜D）thenX∶=Y+Z

將被翻譯成如下的一串四元式：

100

ifA<B

goto

101

goto

102

if

C＜Dgoto

103

goto100

104

T∶=Y+Z

105

X∶=T

106

goto100

107while（A＜B）doif（C＜D）thenX∶=Y+Z102107104for循環(huán)語(yǔ)句fori∶=E1stepE2untilE3doS1

為了簡(jiǎn)單起見，假定E2總是正的。在這種假定下，上述循環(huán)句的意義等價(jià)于：

i∶=E1；

gotoOVER；

AGAIN：i∶=i+E2；

OVER：ifi≤E3then

beginS1；gotoAGAINend；

翻譯見P191-P192開關(guān)語(yǔ)句開關(guān)語(yǔ)句（case語(yǔ)句或switch語(yǔ)句）switchEof

caseV1：S1

caseV2：S2

…

caseVn-1：Sn-1

default：Sn

end如果分叉不太多，case語(yǔ)句翻譯成如下的一連串條件轉(zhuǎn)移語(yǔ)句。

t∶=E；

L1：ift≠V1gotoL2；

S1；

gotonext；

L2：ift≠V2gotoL3；

S2

gotonext；

…

Ln-1：ift≠Vn-1gotoLn；

Sn-1；

gotonext；

Ln：Sn；

next：另一種方法:P190圖8.18

計(jì)算E值，并把結(jié)果放到臨時(shí)變量t中

gototestL1:S1的中間代碼

gotonextL2:S2的中間代碼

gotonext

……Ln:Sn的中間代碼

gotonexttest:ift=v1gotoL1;ift=v2gotoL2;

…….ift=vn-1gotoLn-1;gotoLnnext:goto語(yǔ)句多數(shù)程序語(yǔ)言中的轉(zhuǎn)移是通過(guò)標(biāo)號(hào)和goto語(yǔ)句實(shí)現(xiàn)的。帶標(biāo)號(hào)語(yǔ)句的形式是L∶S；goto語(yǔ)句的形式是gotoL。

當(dāng)L∶S；語(yǔ)句被處理之后，標(biāo)號(hào)L是"定義了"的。即在符號(hào)表中，將登記L的項(xiàng)的"地址"欄中登上語(yǔ)句S的第一個(gè)四元式的地址。如果gotoL是一個(gè)向上轉(zhuǎn)移的語(yǔ)句，那么，當(dāng)編譯程序碰到這個(gè)語(yǔ)句時(shí)，L必是已定義了的。通過(guò)對(duì)L查找符號(hào)表獲得它的定義地址p，編譯程序可立即產(chǎn)生出相應(yīng)于這個(gè)gotoL的四元式如（j，－，－，p）。

如果gotoL是一個(gè)向下轉(zhuǎn)移的語(yǔ)句，也就是說(shuō)，標(biāo)號(hào)L尚未定義，那么，若L是第一次出現(xiàn)，則把它填進(jìn)符號(hào)表中并標(biāo)志上“未定義”。由于L尚未定義，對(duì)gotoL只能產(chǎn)生一個(gè)不完全的四元式（goto－），它的轉(zhuǎn)移目標(biāo)須待L定義時(shí)再回填進(jìn)去。

在這種情況下，必須把所有那些以L為轉(zhuǎn)移目標(biāo)的四元式的地址全都記錄下來(lái)，以便一旦L定義時(shí)就可對(duì)這些四元式進(jìn)行回填。我們將采用如圖8.20所示的拉鏈辦法，把所有以L為轉(zhuǎn)移目標(biāo)的四元式串在一起。鏈的首地址放在符號(hào)表中L的"地址"欄中建鏈的方法是：若gotoL中的標(biāo)號(hào)L尚未在符號(hào)表中出現(xiàn)，則把L填入表中，置L的“定義否”標(biāo)志為“未”，把nextstat填進(jìn)L的地址欄中作為新鏈?zhǔn)?，然后，產(chǎn)生四元式(p)（goto0），其中0為鏈尾標(biāo)志。若L已在符號(hào)表中出現(xiàn)（但“定義否”標(biāo)志為“未”），則把它的地址欄中的編號(hào)（記為p）取出，把nextstat填進(jìn)該欄作新鏈?zhǔn)?，然后，產(chǎn)生四元式(q)（gotop）。一旦標(biāo)號(hào)L定義時(shí)，我們將根據(jù)這條鏈回填那些待填轉(zhuǎn)移目標(biāo)的四元式。一般而言，假定用下面的產(chǎn)生式來(lái)定義標(biāo)號(hào)語(yǔ)句S→labelS

label→i：1.若i所指的標(biāo)識(shí)符（假定為L(zhǎng)）不在符號(hào)表中，則把它填入，置“類型”為“標(biāo)號(hào)”，“定義否”為“已”，“地址”為nextstat。

2.若L已在符號(hào)表中但“類型”不為“標(biāo)號(hào)”或“定義否”為“已”，則報(bào)告出錯(cuò)。

3.若L已在符號(hào)表中，則把標(biāo)志“未”改為“已”，然后，把地址欄中的鏈?zhǔn)祝ㄓ洖閝）取出，同時(shí)把nextstat填在其中，最后，執(zhí)行backpatch(q,nextstat)。過(guò)程調(diào)用的四元式產(chǎn)生過(guò)程調(diào)用的實(shí)質(zhì)是把程序控制轉(zhuǎn)移到子程序,在轉(zhuǎn)子之前,必須用某種辦法把實(shí)參的信息傳給調(diào)用的子程序。傳遞實(shí)參信息方面有種種不同的方法,我們這里只討論一種,即傳實(shí)參地址的方式。若實(shí)參是一個(gè)變量或數(shù)組，則直接傳遞地址。若實(shí)參是表達(dá)式，如：A+B或2，則把它們的值計(jì)算出來(lái)，并存放在一個(gè)臨時(shí)變量T中，然后傳遞T的地址。傳遞實(shí)參地址的一個(gè)簡(jiǎn)單辦法是：把實(shí)參地址逐一放在轉(zhuǎn)指令的前面；例：過(guò)程調(diào)用：CallS(A+B,Z)譯為：計(jì)算A＋B的值置于T中/*T:=A+B*/ParT/*第一個(gè)實(shí)參的地址*/ParZ/*第二個(gè)實(shí)參的地址*/CallS/*轉(zhuǎn)指令*/為了處理在實(shí)參時(shí)記住每個(gè)實(shí)參的地址，以便最后把它們排在Call指令之前，我們需要把這些地址存放起來(lái)，我們可用隊(duì)列來(lái)存放。例：一個(gè)描述過(guò)程調(diào)用語(yǔ)句的文法如下：

(1)S→calli(<arglist>)(2)<arglist>→<arglist>1,E(3)<arglist>→E它的語(yǔ)法制導(dǎo)翻譯見P196例：寫一個(gè)翻譯過(guò)程調(diào)用語(yǔ)句的語(yǔ)義子程序。要求生成的四元式序列在轉(zhuǎn)指令之前的參數(shù)四元式par按反序出現(xiàn)（與實(shí)在參數(shù)的順序相反）。過(guò)程調(diào)用語(yǔ)句的文法如下：

(1)S→calli(<arglist>)(2)<arglist>→<arglist>1,E(3)<arglist>→E(1)<arglist>→E{建一個(gè)arglist.Stack棧，它僅包含一項(xiàng)E.Place}(2)<arglist>→<arglist>1,E{將E.Palce壓入<arglist>1.Stack棧，

arglist.Stack:=arglist1.Stack}(3)S→calli(<arglist>){Whilearglist.Stack≠nulldobegin

將arglist.Stack棧頂彈出生成

Gen(par,_,_,p)end;Gen(call,_,_,Entry(i))}簡(jiǎn)單說(shuō)明語(yǔ)句的翻譯程序設(shè)計(jì)語(yǔ)言中的說(shuō)明語(yǔ)句旨在定義各種形式的有名實(shí)體，如常量、變量、數(shù)組、記錄(結(jié)構(gòu))、過(guò)程、子程序等等，說(shuō)明語(yǔ)句的種類也多，對(duì)象說(shuō)明、變量說(shuō)明、類型說(shuō)明、過(guò)程說(shuō)明等等。編譯程序把說(shuō)明語(yǔ)句中定義的名字和性質(zhì)登記在符號(hào)表中，用以檢查名字的引用和說(shuō)明是否一致。簡(jiǎn)單說(shuō)明句的翻譯

程序設(shè)計(jì)語(yǔ)言中最簡(jiǎn)單的說(shuō)明句的語(yǔ)法描述為：

D→integer〈namelist〉|real〈namelist〉

〈namelise〉→〈namelist〉，id|id

即使用關(guān)鍵字integer和real定義一串名字的性質(zhì)。對(duì)這種說(shuō)明句的翻譯是指在符號(hào)表中登錄該名和性質(zhì)。

用上述文法來(lái)制導(dǎo)翻譯(自下而上)存在著這樣一個(gè)問(wèn)題，我們只能在把所有的名字都?xì)w約成namelist后才能把它們的性質(zhì)登記進(jìn)符號(hào)表我們可以把上述的文法改寫成：

D→D1,id

|integerid

|realid

這樣,就能把所說(shuō)明的性質(zhì)及時(shí)地告訴每個(gè)名字id，或者說(shuō)，每當(dāng)讀進(jìn)一個(gè)標(biāo)識(shí)符時(shí)，就可以把它的性質(zhì)登記在符號(hào)表中，不用把它們集中起來(lái)最后再成批登記了。

現(xiàn)在來(lái)定義這些產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義動(dòng)作，給非終結(jié)符D一個(gè)語(yǔ)義變量D.ATT，用以記錄說(shuō)明句所引入的名字的性質(zhì)(int還是real)，使用過(guò)程enter(id,A)把名字id和性質(zhì)A登錄在名表中。

(1)D→integerid{enter(id,int);

D.ATT∶=int}

(2)D→realid{enter(id,real);

D.ATT∶=real}

(3)D→D1,id{enter(id,D1.ATT);

D.ATT∶=D1.ATT}過(guò)程中的說(shuō)明現(xiàn)在主要討論過(guò)程中的局部變量的說(shuō)明。我們要為過(guò)程的局部名字安排存儲(chǔ)，對(duì)這些名字建符號(hào)表時(shí)，要記錄名字，類型和相對(duì)地址。為了記錄相對(duì)地址，可以使用一個(gè)變量offset。記錄當(dāng)前可用的空間的開始地址，每次分配一個(gè)變量，將offset增加相應(yīng)的值，offset增加的值由名字的類型決定，即由數(shù)據(jù)對(duì)象的寬度決定，寬度用Width來(lái)表示。例：產(chǎn)生式語(yǔ)義動(dòng)作

D→realid{enter(id,real,offset);D.ATT:=real;D.Width:=8;offset:=offset+D.Width;}

數(shù)組的翻譯：一般編譯程序?qū)?shù)組的處理是把數(shù)組的相關(guān)信息匯集在一個(gè)叫做“內(nèi)情向量”的表格中，“內(nèi)情向量”，包括數(shù)組的類型，維數(shù)，各維的上、下界，每維的長(zhǎng)度以及數(shù)組的首地址。

A[l1:u1,l2:u2,,ln

:un]

l1

u1

l2

u2::type

a（首地址）

nCd1d2其中：li表示每維的下界，ui表示每維的上界,di為每維的長(zhǎng)度,di=ui-li+1C為Conspart=a-C的第二項(xiàng),a為數(shù)組的首地址，n為數(shù)組的維數(shù),type為數(shù)組的類型X:=a[i,j]翻譯成四元式的結(jié)構(gòu)：

T1:=VARPART;T2: