1、第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成,8.1 屬性文法 8.2 中間代碼的形式 8.3 語(yǔ)法制導(dǎo)翻譯概論 8.4 簡(jiǎn)單賦值語(yǔ)句的翻譯 8.5 布爾表達(dá)式的翻譯 8.6 控制語(yǔ)句的翻譯 8.7 說(shuō)明語(yǔ)句的翻譯 8.8 數(shù)組和結(jié)構(gòu)的翻譯,源程序經(jīng)詞法分析、語(yǔ)法分析后, 還需進(jìn)行語(yǔ)義分析, 即審查每個(gè)語(yǔ)法成分的靜態(tài)語(yǔ)義。如果靜態(tài)語(yǔ)義正確, 則生成與之等效的中間代碼或目標(biāo)代碼。,直接生成目標(biāo)代碼的優(yōu)點(diǎn)是編譯時(shí)間短且無(wú)需中間代碼到目標(biāo)代碼的翻譯; 生成中間代碼的優(yōu)點(diǎn)是使編譯結(jié)構(gòu)在邏輯上更簡(jiǎn)單明確、代碼優(yōu)化更易實(shí)現(xiàn)。,語(yǔ)義檢查: 靜態(tài)語(yǔ)義檢查和動(dòng)態(tài)語(yǔ)義檢查。前者在編譯階段進(jìn)行; 后者在運(yùn)行階段進(jìn)行。,靜態(tài)語(yǔ)

2、義檢查涉及以下幾個(gè)方面: (1)類(lèi)型檢查: 如操作數(shù)類(lèi)型是否相容 (2)控制流檢查: 用以保證控制語(yǔ)句有合法的轉(zhuǎn)向點(diǎn)。如C語(yǔ)言中不允許goto語(yǔ)句轉(zhuǎn)入case; break語(yǔ)句需尋找包含它的最小switch、while或for語(yǔ)句。 (3)一致性檢查: 如在相同作用域中標(biāo)識(shí)符只能說(shuō)明一次、case標(biāo)號(hào)不能相同等。,(4)相關(guān)名字檢查。有時(shí)同一名字必須出現(xiàn)多次。如Ada程序中, 循環(huán)或程序塊可以有一個(gè)名字, 出現(xiàn)在這些結(jié)構(gòu)的開(kāi)頭和結(jié)尾, 編譯程序必須檢查確認(rèn)這兩個(gè)地方用的名字是相同的。 (5)名字的作用域分析。,由于語(yǔ)義是上下文有關(guān)的, 故語(yǔ)義的形式化描述很困難。目前較常見(jiàn)的是利用屬性文法作為語(yǔ)

3、義描述工具, 并采用語(yǔ)法制導(dǎo)翻譯法對(duì)語(yǔ)法成分進(jìn)行翻譯。,語(yǔ)法制導(dǎo)翻譯法就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序(也稱(chēng)語(yǔ)義子程序或語(yǔ)義動(dòng)作), 并在語(yǔ)法分析的同時(shí)執(zhí)行這些子程序。 語(yǔ)義動(dòng)作規(guī)定生成中間代碼應(yīng)做哪些基本動(dòng)作。在語(yǔ)法分析過(guò)程中, 當(dāng)一個(gè)產(chǎn)生式用于歸約時(shí), 相應(yīng)的語(yǔ)義子程序被啟動(dòng), 完成既定翻譯任務(wù)。,語(yǔ)法制導(dǎo)翻譯分為自下而上和自上而下兩類(lèi), 下面介紹自下而上語(yǔ)法制導(dǎo)翻譯。,假定有一個(gè)自下而上的LR分析器, 把其能力擴(kuò)大, 使它在歸約的同時(shí)調(diào)用相應(yīng)的語(yǔ)義子程序進(jìn)行翻譯。 語(yǔ)義子程序執(zhí)行后, 有些結(jié)果需作為產(chǎn)生式左部符號(hào)的語(yǔ)義值暫存, 以后引用。 故分析棧需擴(kuò)充以存放三類(lèi)信息: 狀態(tài)、文法符號(hào)

4、及語(yǔ)義值。,棧頂,#,X1,Xk,s0,s1,sk,X1.val,Xk .val,擴(kuò)充后的分析棧如下圖所示:,擴(kuò)充總控程序, 使其在完成語(yǔ)法分析的同時(shí)也完成語(yǔ)義分析, 即進(jìn)行歸約時(shí)調(diào)用相應(yīng)的語(yǔ)義子程序。,算術(shù)表達(dá)式文法及語(yǔ)義動(dòng)作: (0) SE print valTOP EE(1)+E(2) valTOP = valTOP+valTOP+2 (2) EE(1)*E(2) valTOP=valTOP*valTOP+2 (3) E(E(1) valTOP= valTOP+1 (4) Ei valTOP=lexval (注: lexval為i的整型內(nèi)部值),例 給出算術(shù)表達(dá)式7+9*5#的語(yǔ)義分析過(guò)

5、程,表達(dá)式7+9*5#的語(yǔ)法樹(shù)及各結(jié)點(diǎn)值,表8.1 表達(dá)式7+9*5#的語(yǔ)義分析過(guò)程,狀態(tài)棧,符號(hào)棧,語(yǔ)義棧,輸入串,下一動(dòng)作,7+9*5#,+9*5#,+9*5#,01475,#E+E*,_7_9_,014753,#E+E*5,_7_9_ _,014758,#E+E*E,_7_9_5,# E+E,_7_45,8.1 屬 性 文 法,文法的屬性是指與文法符號(hào)的類(lèi)型和值等有關(guān)的一些信息。,例如, 判斷變量X的類(lèi)型是否匹配, 要用X的數(shù)據(jù)類(lèi)型描述; 判斷變量X是否存在, 要用X的存儲(chǔ)位置描述; 對(duì)X的運(yùn)算, 則要用X的值描述。 故語(yǔ)義分析需引入X的屬性, 如X.type、X.place、X.val

6、。,文法符號(hào)的屬性可分為兩類(lèi): 繼承屬性: 由父結(jié)點(diǎn)的屬性計(jì)算得到, 即沿語(yǔ)法樹(shù)自上向下傳遞信息。 綜合屬性: 由子結(jié)點(diǎn)的屬性計(jì)算得到, 即沿語(yǔ)法樹(shù)自下向上傳遞信息。,屬性文法是指在文法中增加了屬性, 它包含一個(gè)CFG文法和一系列語(yǔ)義規(guī)則, 這些語(yǔ)義規(guī)則附在文法的每個(gè)產(chǎn)生式上。 語(yǔ)法制導(dǎo)翻譯是指在語(yǔ)法分析過(guò)程中, 完成附加在產(chǎn)生式上的語(yǔ)義規(guī)則描述的動(dòng)作。,例 簡(jiǎn)單算術(shù)表達(dá)式求值的語(yǔ)義描述: 產(chǎn)生式 語(yǔ)義規(guī)則 (0) SE print (E.val) (1) EE(1)+T E.val = E(1).val+T.val (2) ET E.val = T.val (3) TT(1)*F T.val

7、 = T(1).val*F.val (4) TF(1) T.val = T(1).val (5) F(E) F.val = E.val (6) Fi F.val = i.lexval,每個(gè)非終結(jié)符都有一個(gè)屬性val, 它由其右部符號(hào)的val值計(jì)算, 為綜合屬性。 與SE關(guān)聯(lián)的是函數(shù)print(E.val), S在語(yǔ)義規(guī)則中沒(méi)有出現(xiàn), 理解為S的屬性是空的或虛的。,例 說(shuō)明語(yǔ)句中各變量類(lèi)型信息的語(yǔ)義規(guī)則。 說(shuō)明語(yǔ)句文法: GD: D int L | float L L L, id | id,產(chǎn)生式 語(yǔ)義規(guī)則 (1) DTL L.in = T.type (2) Tint T.type = int

8、(3) Tfloat T.type = float (4) LL(1), id L(1).in = L.in; addtype(id.entry,L.in) (5) Lid addtype(id.entry, L.in),T有一個(gè)綜合屬性T.type, 值為int或float; L有一個(gè)繼承屬性L(fǎng).in, 值由T.type決定; 屬性L(fǎng).in被確定后將隨語(yǔ)法樹(shù)的逐步生成而傳遞到下邊有關(guān)結(jié)點(diǎn)。,例如, 輸入串int a, b的屬性傳遞情況:,8.2.1 抽象語(yǔ)法樹(shù) 抽象語(yǔ)法樹(shù)是一種較流行的中間語(yǔ)言表示形式。在抽象語(yǔ)法樹(shù)中, 每個(gè)葉結(jié)點(diǎn)表示常量或變量這樣的運(yùn)算對(duì)象, 而內(nèi)部結(jié)點(diǎn)表示運(yùn)算符。 抽象語(yǔ)

9、法樹(shù)不同于語(yǔ)法樹(shù), 它展示了一個(gè)操作過(guò)程并同時(shí)描述了源程序的層次結(jié)構(gòu)。,8.2 中間代碼的形式,例如, 賦值語(yǔ)句x=a+b的抽象語(yǔ)法樹(shù)如圖(a), 其普通語(yǔ)法樹(shù)如圖(b)所示:,assign,x,+,a,b,(a) 抽象語(yǔ)法樹(shù),說(shuō)明: 語(yǔ)法規(guī)則中包含的某些符號(hào)可能起標(biāo)點(diǎn)符號(hào)作用, 也可能起解釋作用。 例如, 賦值語(yǔ)句SV=E中, 賦值號(hào)僅起標(biāo)點(diǎn)符號(hào)作用, 其目的是把V與E分開(kāi)。,再如, 條件語(yǔ)句Sif(e)S1;else S2中, if和else起注釋作用, 說(shuō)明當(dāng)e為真時(shí)執(zhí)行S1, 否則執(zhí)行S2; 而“;”僅起標(biāo)點(diǎn)符號(hào)作用。,當(dāng)把語(yǔ)法規(guī)則的本質(zhì)部分抽象出來(lái)、把非本質(zhì)部分去掉后, 便得抽象語(yǔ)法

10、規(guī)則。 賦值語(yǔ)句和條件語(yǔ)句的抽象語(yǔ)法規(guī)則為: (1) 賦值語(yǔ)句: 左部 表達(dá)式 (2) 條件語(yǔ)句: 表達(dá)式 語(yǔ)句1 語(yǔ)句2 這種去掉不必要信息的做法可以獲得高效的中間表示。,(a) 抽象語(yǔ)法樹(shù),(b) 普通語(yǔ)法樹(shù),例如, 賦值語(yǔ)句x=a+b*c的抽象語(yǔ)法樹(shù)如圖(a)所示, 其普通語(yǔ)法樹(shù)如圖(b)所示:,上述普通語(yǔ)法樹(shù)的結(jié)點(diǎn)為14個(gè), 而抽象語(yǔ)法樹(shù)的結(jié)點(diǎn)為7個(gè)且每個(gè)內(nèi)部結(jié)點(diǎn)最多只有兩個(gè)分支。 因此, 賦值語(yǔ)句或表達(dá)式可表示為一棵二叉樹(shù)。對(duì)于含多元運(yùn)算的語(yǔ)法成分, 其抽象語(yǔ)法樹(shù)為一棵多叉樹(shù), 但可轉(zhuǎn)為二叉樹(shù)。,抽象語(yǔ)法樹(shù)的優(yōu)點(diǎn): 結(jié)構(gòu)緊湊、容易構(gòu)造、結(jié)點(diǎn)數(shù)較少。,逆波蘭表示法是由波蘭科學(xué)家提出的一

11、種表達(dá)式表示方法, 這種方法把運(yùn)算量寫(xiě)在前、把運(yùn)算符寫(xiě)在后, 又稱(chēng)后綴表示法。,8.2.2逆波蘭表示法,1. 表達(dá)式E的逆波蘭表示 (1)若E是變量或常數(shù), 則E的后綴表示為E; (2)若E為E1opE2, 則后綴表示為E1E2op, 其中E1,E2分別為E1,E2的后綴表示。 若op為一元運(yùn)算, 則視E1和E1為空。 (3)若E為(E1)形式, 則后綴表示即為E1, 其中E1為E1的后綴表示。,在逆波蘭表示中, 操作數(shù)的出現(xiàn)順序與原來(lái)一致, 而把運(yùn)算符按運(yùn)算先后順序放在相應(yīng)操作數(shù)后。,逆波蘭表示不需要用括號(hào)規(guī)定運(yùn)算順序, 便于用棧實(shí)現(xiàn)計(jì)值。 計(jì)值過(guò)程: 自左至右掃描后綴表達(dá)式, 遇到運(yùn)算量就

12、把它入棧, 遇到K目運(yùn)算符就把它作用于棧頂?shù)腒個(gè)運(yùn)算量, 并用運(yùn)算結(jié)果取代棧頂?shù)腒個(gè)運(yùn)算量。,2. 程序語(yǔ)句的逆波蘭表示 為了用逆波蘭式表示一些控制語(yǔ)句, 定義轉(zhuǎn)移操作如下: (1) BL: 轉(zhuǎn)向某標(biāo)號(hào) (2) BT: 條件為真時(shí)轉(zhuǎn)移 (3) BF: 條件為假時(shí)轉(zhuǎn)移 (4) BR: 無(wú)條件轉(zhuǎn)移,部分程序語(yǔ)句的逆波蘭表示如下: 賦值語(yǔ)句 =的逆波蘭表示為 = 例如, x=a+b*c的逆波蘭式為 xabc*+=,(2) GOTO語(yǔ)句 GOTO的逆波蘭表示為 BL 其中, BL為單目后綴運(yùn)算符。,(3) 條件語(yǔ)句 BR表示無(wú)條件轉(zhuǎn)移的單目后綴運(yùn)算符。 例如, BR 其中, 表示逆波蘭式中單詞符號(hào)的順

13、序號(hào)(即第幾個(gè)單詞)。,BT和BF表示條件轉(zhuǎn)移雙目后綴運(yùn)算符。 例如, 當(dāng)布爾式e為真時(shí)轉(zhuǎn)移 表示為: BT 當(dāng)布爾式e為假時(shí)轉(zhuǎn)移 表示為: BF,若用BF和BR, 則if(e)S1;else S2的逆波蘭式: BF /順序號(hào)1為S2第1單詞 /e為真時(shí)執(zhí)行S1 BR /S2后第1個(gè)單詞 ,例如, if (mn) k=i+1; else k=i1的逆波蘭式表示為: (1) mn (4) 13BF (6) ki1+= (11) 18BR (13) ki1= (18) 把逆波蘭式寫(xiě)在一行上: mn13BFki1+=18BRki1 =,(4) 循環(huán)語(yǔ)句 循環(huán)語(yǔ)句不能直接用逆波蘭表示, 需展開(kāi)為等價(jià)的

14、條件語(yǔ)句再用逆波蘭表示。 例如, for (i=m; i=n; i+) S 轉(zhuǎn)換為: i=m; 10: if(i=n) S; i=i+1; goto l0 ,1. 三地址代碼的一般形式 x = y op z 其中x,y,z為操作數(shù), op為操作符。,8.2.3 三地址代碼,由于三地址語(yǔ)句只含一個(gè)運(yùn)算符, 故由多個(gè)運(yùn)算符組成的表達(dá)式需要用三地址語(yǔ)句序列表示。 例如, 表達(dá)式x+y*z的三地址代碼: t1= y*z; t2= x+t1,2. 三地址語(yǔ)句的種類(lèi) 常用的三地址語(yǔ)句有8種: (1) x=y op z, 其中op為二元運(yùn)算符; (2) x=op y, 其中op為一元運(yùn)算符; (3) x=y

15、, 將y的值賦給x; (4) 無(wú)條件轉(zhuǎn)移語(yǔ)句goto L; (5) 條件轉(zhuǎn)移語(yǔ)句if x rop y goto L; (6) 變址賦值語(yǔ)句 x=yi表示把從地址y開(kāi)始的第i個(gè)單元中的值賦給x; xi=y表示把y的值賦給從地址x開(kāi)始的第i個(gè)地址單元。,(7) 過(guò)程調(diào)用語(yǔ)句par X和call P,n。 過(guò)程調(diào)用語(yǔ)句P(X1, X2, Xn) 可用下述三地址代碼表示: par X1 par Xn call P,n 過(guò)程返回語(yǔ)句為return y 其中y為返回值。,(8) 地址和指針賦值語(yǔ)句 x= *x=y 表示將x所指對(duì)象的值 置為y的值。,3. 三地址代碼的具體實(shí)現(xiàn) 三地址代碼的實(shí)現(xiàn)通常有三種方

16、法: 四元式、三元式和間接三元式。 (1) 四元式 四元式是具有四個(gè)域的記錄結(jié)構(gòu): (op, arg1, arg2, result) 其中op為操作符, arg1, arg2, result為指針, 指向相關(guān)名字在符號(hào)表中的登記項(xiàng)或臨時(shí)變量(可為空)。,常用三地址語(yǔ)句對(duì)應(yīng)的四元式: x = y op z (op, y, z, x) x = y (minus, y, _, x) x = y (=, y, _, x) par x1 (par, x1, _, _) call P, n (call, _, _, P) goto L (j, _, _, L) if x rop y goto L (jro

17、p, x, y, L),例如, 賦值語(yǔ)句a=b*(c+d)的四元式: (+, c, d, t1) (*, b, t1, t2) (=, t2, _, a) 約定: 一元運(yùn)算符使用arg1; 若op為算術(shù)或邏輯運(yùn)算符, 則result為一個(gè)新引進(jìn)的臨時(shí)變量, 用于存放運(yùn)算結(jié)果?？梢?jiàn), 四元式之間的聯(lián)系通過(guò)臨時(shí)變量實(shí)現(xiàn)。,(2) 三元式 三元式是具有三個(gè)域的記錄結(jié)構(gòu): (op, arg1, arg2) 其中op為操作符, arg1和arg2既可指向有關(guān)名字在符號(hào)表中的登記項(xiàng)或臨時(shí)變量, 也可指向三元式表中的某個(gè)三元式。,例如, 賦值語(yǔ)句a=(b+c)*(b+c)的三元式: (+, b, c) (+

18、, b, c) (*, , ) (=, a, ),三元式表示中, 每個(gè)語(yǔ)句的位置有兩作用: (1)作為三元式的結(jié)果被其它三元式引用; (2)三元式的位置順序即為運(yùn)算順序。,若采用三元式表示, 則代碼優(yōu)化階段需調(diào)整三元式的運(yùn)算順序時(shí)會(huì)遇到困難。 這是因?yàn)槿街械腶rg1,arg2可以是指向三元式位置的指針, 當(dāng)這些三元式的位置順序發(fā)生變化時(shí), 含有指向這些三元式位置指針的三元式也需隨之改變指針值。因此, 變動(dòng)一張三元式表很困難。,(3) 間接三元式 在三元式表的基礎(chǔ)上另設(shè)一張表, 該表按運(yùn)算次序列出相應(yīng)三元式在三元式表中的位置, 這張表稱(chēng)為間接碼表。 三元式表只記錄不同的三元式語(yǔ)句, 間接碼表

19、表示由這些語(yǔ)句組成的運(yùn)算次序。,例 a=(b+c)*(b+c)的三元式表與間接碼表: 三元式表: (+, b, c) (*, , ) (=, a, ) 間接碼表: ,對(duì)于四元式, 引用一個(gè)語(yǔ)句的結(jié)果可通過(guò)引用該語(yǔ)句的result來(lái)實(shí)現(xiàn), 而間接三元式則通過(guò)間接碼表描述語(yǔ)句的運(yùn)算次序。 這兩種方法都不存在語(yǔ)句位置同時(shí)具有兩種功能的現(xiàn)象, 代碼調(diào)整時(shí)所做改動(dòng)是局部的, 故需要對(duì)中間代碼進(jìn)行優(yōu)化時(shí), 四元式和間接三元式比三元式方便。,8.3 語(yǔ)法制導(dǎo)翻譯概論,屬性計(jì)算有兩類(lèi)方法： (1) 通過(guò)遍歷分析樹(shù)進(jìn)行屬性計(jì)算(樹(shù)遍歷方法)；(2) 語(yǔ)法分析的同時(shí)進(jìn)行屬性計(jì)算(一遍掃描方法) 樹(shù)遍歷方法步驟：

20、(1) 構(gòu)造輸入串的語(yǔ)法分析樹(shù)； (2) 構(gòu)造依賴(lài)圖； (3) 若依賴(lài)圖無(wú)圈, 則按依賴(lài)圖的一種拓?fù)渑判驅(qū)Ψ治鰳?shù)進(jìn)行遍歷, 計(jì)算所有屬性。 依賴(lài)圖的構(gòu)造方法見(jiàn)P172。,S-屬性文法：只包含綜合屬性。 S-屬性文法的翻譯通常采用自下而上方式進(jìn)行。采用LR分析技術(shù)時(shí), 可利用語(yǔ)義棧存放綜合屬性的值, 計(jì)算產(chǎn)生式左部文法符號(hào)的綜合屬性值剛好發(fā)生在歸約前的時(shí)刻。 例如, 假設(shè)產(chǎn)生式AXYZ的語(yǔ)義規(guī)則為 A.a := f(X.x, Y.y, Z.z) 在XYZ歸約到A之前, X.x, Y.y, Z.z正好存放于語(yǔ)義棧棧頂, 故A.a可以順利求出。歸約后, X.x, Y.y, Z.z被彈出, 而棧頂to

21、p的位置上存放A.a。 例 考慮輸入串2+3*5 (有優(yōu)先級(jí); 二義文法),L-屬性文法： 除了綜合屬性, 還可以有繼承屬性, 但產(chǎn)生式右端文法符號(hào)的繼承屬性只取決于該符號(hào)左邊文法符號(hào)(包括產(chǎn)生式左邊文法符號(hào))的屬性。 S-屬性文法是L-屬性文法的一個(gè)特例。,L-屬性文法的翻譯可采用深度優(yōu)先后序遍歷: procedure dfvisit (n: node); for n的每一孩子m, 從左到右 do 計(jì)算m的繼承屬性值; dfvisit(m) ; 計(jì)算n的綜合屬性值; ,簡(jiǎn)單算術(shù)表達(dá)式指僅含普通變量和常數(shù)等簡(jiǎn)單變量、不含數(shù)組元素及結(jié)構(gòu)引用等復(fù)合型數(shù)據(jù)結(jié)構(gòu)的算術(shù)表達(dá)式。,8.4 簡(jiǎn)單賦值語(yǔ)句的翻

22、譯,簡(jiǎn)單算術(shù)表達(dá)式的計(jì)值順序與四元式出現(xiàn)順序相同, 故很易翻譯為四元式。,考慮賦值語(yǔ)句文法GA: Ai=E EE+E | E*E | E | (E) | i 為了實(shí)現(xiàn)翻譯, 需給文法加上語(yǔ)義子程序。,語(yǔ)義子程序所涉及的語(yǔ)義變量、語(yǔ)義過(guò)程、函數(shù)說(shuō)明如下:,(1)對(duì)非終結(jié)符E定義語(yǔ)義變量E.place, 用于表示存放E值的變量名在符號(hào)表中的入口地址或臨時(shí)變量名的整數(shù)碼;,(2)定義語(yǔ)義函數(shù)newtemp(), 每次調(diào)用回送一個(gè)代表新臨時(shí)變量的整數(shù)碼;,定義語(yǔ)義過(guò)程emit(op,arg1,arg2,result), 功能是產(chǎn)生一個(gè)四元式并填入四元式表; 定義語(yǔ)義函數(shù)lookup(),

23、功能是檢查是否出現(xiàn)在符號(hào)表, 若是則返回在符號(hào)表入口指針, 否則返回Null.,文法GA的語(yǔ)義子程序: (1)Ai=E p = lookup(); if(p= =Null) error(); else emit(=,E.place,_,p); (2)EE(1)+E(2) E.place=newtemp( ); emit(+,E(1).place,E(2).place,E.place); (3)EE(1)*E(2) E.place = newtemp(); emit(*,E(1).place,E(2).place,E.place); (4)EE(1) E.pl

24、ace = newtemp(); emit(minus,E(1) .place,_,E.place); (5)E(E(1) E.place = E(1) .place ; (6)Ei p=lookup(); if(p!=Null) E.place=p; else error(),例 給出x=-b*(c+d)的語(yǔ)法制導(dǎo)翻譯過(guò)程. 解: x=-b*(c+d)的語(yǔ)法制導(dǎo)翻譯過(guò)程:,關(guān)系運(yùn)算的優(yōu)先級(jí)低于算術(shù)運(yùn)算; 布爾運(yùn)算的優(yōu)先級(jí)低于關(guān)系運(yùn)算。 考慮文法GE生成的布爾表達(dá)式: GE: EEE|EE|E|(E)|i | i rop i,8.5 布爾表達(dá)式的翻譯,計(jì)算布爾表達(dá)式值的方法有兩種:

25、 (1)仿照算術(shù)表達(dá)式的計(jì)算方法 例如, 1(00)0 =1(10)0=100=10=1,(2)根據(jù)布爾運(yùn)算特點(diǎn)實(shí)施某種優(yōu)化 例如, 計(jì)算AB時(shí), 若計(jì)算出A的值為1, 則B值無(wú)需再計(jì)算。同理, 計(jì)算AB時(shí), 若計(jì)算出A的值為0, 則B值無(wú)需計(jì)算。,注意: 上述優(yōu)化措施當(dāng)布爾式中含有布爾函數(shù)調(diào)用且函數(shù)調(diào)用引起副作用(指對(duì)全局變量賦值)時(shí)會(huì)出現(xiàn)問(wèn)題。 例如, 下面兩個(gè)C語(yǔ)言程序因布爾式書(shū)寫(xiě)順序不同而得到不同的結(jié)果。,(1) #include “stdio.h” int p; int f( ) p=0; return(0); main( ) p=1; if p|f( ) printf(“True!

26、n”); else printf(“False!n”); ,(2) #include “stdio.h” int p; int f( ) p=0; return(0); main( ) p=1; if f( )|p printf(“True!n”); else printf(“False!n”); ,后面的翻譯均假定函數(shù)/過(guò)程不出現(xiàn)副作用。,如何確定一個(gè)表達(dá)式的真假出口?,考慮布爾式E(1)E(2): 若E(1)為真, 則E為真, 故E(1)的真出口為整個(gè)E的真出口; 若E(1)為假, 則E(2)必須被計(jì)值, 故E(1)的假出口為E(2)的第一個(gè)四元式。 E(2)的真出口為整個(gè)E的真出口; E

27、(2)的假出口為整個(gè)E的假出口。,E(1)的真假出口,在自下而上分析過(guò)程中, 布爾式的真假出口往往不能在生成四元式的同時(shí)填上。這就需要把未完成的四元式的地址作為E的語(yǔ)義值暫存起來(lái), 待相應(yīng)的四元式生成時(shí)再回填。 翻譯過(guò)程中常出現(xiàn)若干個(gè)四元式轉(zhuǎn)向同一個(gè)目標(biāo)而目標(biāo)位置又未確定的情況, 此時(shí)可把這些四元式鏈接起來(lái), 待獲得轉(zhuǎn)移目標(biāo)的四元式地址時(shí)再回填。,為了便于回填, 賦予每個(gè)非終結(jié)符E兩個(gè)語(yǔ)義值E.tc和E.fc。 E.tc用于記錄E對(duì)應(yīng)的需回填真出口的四元式地址鏈。 E.fc用于記錄E對(duì)應(yīng)的需回填假出口的四元式地址鏈。,假定E的四元式中需回填真出口的有p,q,r, 則它們可鏈成一條下圖所示的鏈表

28、(記為tc):,為了易于處理E.tc和E.fc, 引入如下語(yǔ)義變量和函數(shù): (1)nxq: 始終指向下一條將要產(chǎn)生的四元式的地址, 初值為1。 每執(zhí)行一次emit語(yǔ)句, nxq自動(dòng)增1。 (2)merge(p1,p2): 把以p1和p2為鏈?zhǔn)椎膬涉満蠟橐粭l以p2為鏈?zhǔn)椎逆湣?(3)backpatch(p,t): 把鏈?zhǔn)譸所鏈接的每個(gè)四元式的第四區(qū)段都回填t。,merge()函數(shù)如下: merge(p1, p2) if (p2= =0) return(p1); else p = p2; while (p的第四區(qū)段內(nèi)容不為0) p = p的第四區(qū)段內(nèi)容; 把p1填進(jìn)p的第四區(qū)段; return(p

29、2); ,backpatch()函數(shù)如下: backpatch(p,t) r = p; while (r!= 0) q = r的第四區(qū)段內(nèi)容; 把t填入r的第四區(qū)段; r = q; ,在實(shí)現(xiàn)布爾式的翻譯時(shí), 為了在掃描到與時(shí)能及時(shí)回填, 把布爾表達(dá)式文法GE改寫(xiě)為GE: GE: EEE | EE |E | (E) | i | i rop i GE: EEAE | EBE |E | (E) | i | i rop i EAE EBE,文法GE的語(yǔ)義子程序: (1) Ei E.tc=nxq; E.fc=nxq+1; emit(jnz,entry(i),_,0); emit(j,_,_,0); (2

30、) Ei(1) rop i(2) E.tc=nxq; E.fc=nxq+1; emit(jrop, entry(i(1), entry(i(2),0); emit(j,_,_,0); (3) E(E(1) ) E.tc=E(1).tc; E.fc=E(1).fc; (4) EE(1) E.tc=E(1).fc; E.fc=E(1).tc;,(5) EAE(1) backpatch(E(1).tc, nxq); EA.fc=E(1).fc; (6) EEAE(2) E.tc=E(2).tc; E.fc=merge(EA.fc, E(2).fc); (7) EBE(1) backpatch(E(1

31、).fc, nxq); EB.tc=E(1).tc; (8) EEBE(2) E.fc=E(2).fc; E.tc=merge(EB.tc, E(2).tc);,例 試給出布爾式ab cd 作為控制 條件的四元式中間代碼。 解: 布爾式ab cd 的分析過(guò)程如下:,布爾式ab cd 對(duì)應(yīng)的四元式: 100 (jnz, a, _, 102) 101 (j, _, _, 104) 102 (jnz, b, _,106) 103 (j, _, _, 104) 104 (j, c, d, 106) 105 (j, _, _, q) T: 106 F: q,小結(jié): 每個(gè)布爾變量a對(duì)應(yīng)兩個(gè)四元式: (jn

32、z, a, _, 0) (j, _, _, 0) 每個(gè)關(guān)系表達(dá)式對(duì)應(yīng)兩個(gè)四元式: (jrop, x, y, 0) ( j, _, _, 0),例 試給出布爾式af作為控制條件的四元式中間代碼。,例 試給出布爾式a or cd and e作為控制條件的四元式中間代碼。,源程序中, 控制語(yǔ)句用于實(shí)現(xiàn)程序流程的控制。程序流程控制一般可分為三種基本結(jié)構(gòu): (1)順序結(jié)構(gòu): 用復(fù)合語(yǔ)句實(shí)現(xiàn) (2)選擇結(jié)構(gòu): 用if和case等語(yǔ)句實(shí)現(xiàn) (3)循環(huán)結(jié)構(gòu): 用for, while, do等實(shí)現(xiàn),8.6 控制語(yǔ)句的翻譯,1. 條件語(yǔ)句 if 的代碼結(jié)構(gòu) 考慮條件語(yǔ)句: if (E) S1; else S2 布

33、爾式E的作用僅在于控制對(duì)S1和S2的選擇, 故為E賦予了兩種出口: 真出口指向S1; 假出口指向S2。 條件語(yǔ)句可翻譯成下述代碼結(jié)構(gòu):,8.6.1 條件語(yǔ)句 if 的翻譯,T,E的代碼,S1的代碼,S2的代碼,F,if (E) S1;else S2的代碼結(jié)構(gòu),T,E1的代碼,E2的代碼,S1的代碼,F,T,S2的代碼,S3的代碼,F,if 語(yǔ)句的嵌套: if (E1) if (E2) S1; else S2; else S3 S1代碼之后的無(wú)條件轉(zhuǎn)移指令不僅應(yīng)跨越S2, 還應(yīng)跨越S3。,T,E1的代碼,E2的代碼,S1的代碼,F,T,S2的代碼,S3的代碼,F,2. if 語(yǔ)句的文法和語(yǔ)義子程

34、序 if 語(yǔ)句的文法: GS: Sif (E) S(1) Sif (E) S(1); else S(2) 為了及時(shí)回填, 把GS改寫(xiě)為GS: GS: (1) SCS(1) (2) Cif (E) (3) STpS(2) (4) TPCS(1);else (2) Cif (E),if 語(yǔ)句的語(yǔ)義子程序: Cif (E) backpatch(E.tc, nxq); C.chain=E.fc; SCS(1) S.chain=merge(C.chain, S(1).chain); TpCS(1); else q=nxq; emit(j,_,_,0); backpatch(C.chain, nxq);

35、Tp.chain=merge(S(1).chain, q); STpS(2) S.chain=merge(Tp.chain, S(2).chain);,1. while語(yǔ)句的代碼結(jié)構(gòu) while語(yǔ)句文法: while (E) S(1) 其中E.tc指向S(1)的第一個(gè)四元式, E.fc指向while語(yǔ)句的后繼語(yǔ)句; S(1)之后應(yīng)產(chǎn)生一條無(wú)條件轉(zhuǎn)向E的轉(zhuǎn)移指令。,8.6.2 while語(yǔ)句的翻譯,while語(yǔ)句的代碼結(jié)構(gòu),T,E的代碼,S(1)的代碼,F,2. while語(yǔ)句的文法和語(yǔ)義子程序 while語(yǔ)句文法: while (E) S(1) 為了及時(shí)回填, while語(yǔ)句文法改為: GS:

36、 (1) SWdS(1) (2) WdW(E) (3) Wwhile 根據(jù)while語(yǔ)句的掃描順序, 先用產(chǎn)生式(3)進(jìn)行歸約, 這時(shí)nxq為E的第一個(gè)四元式地址, 保留于W.quad。,用WdW(E)歸約時(shí), 用nxq回填E.tc, 待填信息E.fc用Wd.chain=E.fc傳下去。 用SWdS(1)歸約時(shí), 應(yīng)轉(zhuǎn)到E的第一個(gè)四元式,即(j, , ,Wd.quad), 并用backpatch (S(1).chain, Wd.quad)回填E的入口地址。 無(wú)條件轉(zhuǎn)移(j, , ,Wd.quad)之后為while語(yǔ)句的后繼語(yǔ)句, 該后繼語(yǔ)句的第一個(gè)四元式為E的假出口, 保存于Wd.chain。

37、,考慮到嵌套情況, 把Wd.chain作為整個(gè)while語(yǔ)句的出口保存于S.chain, 以便回填。,while語(yǔ)句文法的語(yǔ)義子程序: (1) Wwhile W.quad=nxq; (2) WdW(E) backpatch(E.tc, nxq); Wd.chain=E.fc; Wd.quad=W.quad; (3) SWd S(1) backpatch(S(1).chain, Wd.quad); emit(j,_,_, Wd.quad); S.chain=Wd.chain; 同理可寫(xiě)出do S(1) while (E)語(yǔ)句的文法及語(yǔ)義子程序。,1. 三種基本控制結(jié)構(gòu)的文法 GS: (1) SC

38、S (2) STP S (3) SWd S (4) SL (5) SA /*賦值*/ (6) LLS S (7) LS (8) Cif(E) (9) TPCS; else (10) WdW(E) (11) Wwhile (12) LSL;,8.6.3 三種基本控制結(jié)構(gòu)的翻譯,GS中各產(chǎn)生式的語(yǔ)義子程序: (1) W while W.quad=nxq; (2) WdW(E) backpatch(E.tc, nxq); Wd.chain=E.fc; Wd.quad=W.quad; (3) LSL; backpatch(L.chain, nxq);,(4) Cif(E) backpatch(E.tc

39、, nxq); C.chain=E.fc; (5) TPCS(1);else q=nxq; emit(j,_,_,0); backpatch(C.chain, nxq); TP.chain=merge(S(1).chain, q); (6) LLS S(1) L.chain=S(1).chain (7) LS L.chain=S.chain,(8) SCS(1) S.chain=merge(C.chain,S(1).chain); (9) STPS(2) S.chain=merge(TP.chain,S(2).chain); (10) SWd S(1) backpatch(S(1).chain

40、, Wd.quad); emit(j,_,_,Wd.quad); S.chain=Wd.chain; (11) SL S.chain=L.chain; (12) SA S.chain=0; /*空鏈*/,2. 翻譯示例 例1 將下述語(yǔ)句翻譯成四元式: while (ad) x=y+2;,E1: ab,E2: cd,x=y+2,F,T,F,T,解: 所得四元式如下: 100 (j, c, d, 104) 103 (j, _, _, 106) 104 (+, y, 2, t1) 105 (=, t1, _, x) 106 (j, _, _, 100) 107,while (ad) x=y+2;,例

41、3 將下述語(yǔ)句翻譯成四元式: if (xy) while (ab) m=m+1; else x=y;,例2 將下述語(yǔ)句翻譯成四元式: while (ad) x=y+2; else m=n*3;,例4 按已學(xué)文法及語(yǔ)義加工子程序分析下述語(yǔ)句的語(yǔ)義加工全過(guò)程: while (xy) x=x+1 解: (略),多分支控制語(yǔ)句具有如下形式: switch (E) case c1: S1; case c2: S2; case ci: Si; case cn: Sn; default: Sn+1 ,8.6.4 多分支控制語(yǔ)句case的翻譯,switch語(yǔ)句的語(yǔ)義: 先計(jì)算整型式E的值。若E值與某常數(shù)ci相

42、等,則執(zhí)行Si; 若E值與諸常數(shù)均不等,則執(zhí)行Sn+1。,switch語(yǔ)句的中間代碼形式: E計(jì)值后存于臨時(shí)單元T的中間代碼; goto test; P1: S1的中間代碼; goto next; P2: S2的中間代碼; goto next; Pn: Sn的中間代碼; goto next; Pn+1:Sn+1的中間代碼; goto next; test: if (T= =c1) goto P1; if (T= =c2) goto P2; if (T= =cn) goto Pn; if (T= =T) goto Pn+1; next:,goto L中, 標(biāo)號(hào)L以?xún)煞N方式出現(xiàn): (1)定義性出現(xiàn)

43、: L: S 此時(shí)S的第1個(gè)四元式地址即為L(zhǎng)的值,8.6.5 語(yǔ)句標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句的翻譯,(2)引用性出現(xiàn): goto L L的值為四元式(j,_,_,L)的目標(biāo)地址 對(duì)標(biāo)號(hào)L的處理方法: 當(dāng)L為定義性出現(xiàn)時(shí), 把其對(duì)應(yīng)的四元式地址登錄到符號(hào)表; 當(dāng)L為引用性出現(xiàn)時(shí), 引用符號(hào)表中L的值。,若標(biāo)號(hào)的定義性出現(xiàn)在前而引用性出現(xiàn)在后, 即先定值后引用, 則填表、查表及把轉(zhuǎn)移語(yǔ)句翻譯成四元式都容易。 若標(biāo)號(hào)的引用性出現(xiàn)在前而定義性出現(xiàn)在后(向前引用), 則引用時(shí)不能從符號(hào)表中獲得L的值, 只能生成待回填的四元式(j,_,_,0), 等翻譯到L的定義性出現(xiàn)時(shí), 再回填L的值。,L已經(jīng)定值: L.valu

44、e為符號(hào)表中L的值, 生成(j, _, _, L.value); 符號(hào)表中未出現(xiàn)標(biāo)號(hào)L: goto L中L是首次出現(xiàn), 則生成(j,_,_,0); 在符號(hào)表中登錄L項(xiàng), 并標(biāo)記為“未定值”;待L定值后再回填四元式(j,_,_,0)。,翻譯goto L語(yǔ)句時(shí)需查符號(hào)表, 確定L是否定值, 有以下幾種情況:,符號(hào)表中已有標(biāo)號(hào)L項(xiàng)但未定值: 此時(shí)goto L并非首次出現(xiàn), 故生成四元式(j,_,_,0), 并把其地址掛入L的引用鏈, 待L定值后再回填。,8.6.1 數(shù)組元素地址計(jì)算及中間代碼形式 表達(dá)式或賦值語(yǔ)句中若出現(xiàn)數(shù)組元素, 則翻譯時(shí)將牽涉到數(shù)組元素的地址計(jì)算。 數(shù)組在存儲(chǔ)器中的存放方式?jīng)Q定了

45、數(shù)組元素的地址計(jì)算方法, 從而決定了中間代碼的形式。,8.6 數(shù)組元素的翻譯,數(shù)組的存放方式通常有按行存放和按列存放兩種。下面討論按行存放的數(shù)組元素地址計(jì)算方法。 數(shù)組的一般定義為: Al1:u1, l2:u2, , lk:uk, , ln:un 其中A是數(shù)組名, lk是第k維的下界, uk是第k維的上界。,假定數(shù)組A中元素存儲(chǔ)長(zhǎng)度為1, 首地址為a, 則數(shù)組元素Ai1,i2, in的地址D的計(jì)算公式: D = a + (i1-l1)d2d3dn + (i2-l2)d3d4dn + + (in-1-ln1)dn + (in-ln) 其中, di = ui-li +1 (i =1,2,n),整理

46、得 D = CPART + VPART, 其中 CPART= a-C = a-(l1d2+l2)d3+l3)dn+ln) VPART= (i1d2+i2)d3+i3)dn+in CPART中各項(xiàng)在處理說(shuō)明語(yǔ)句時(shí)得到, 故CPART中的C值在編譯時(shí)計(jì)算并保存在數(shù)組A的符號(hào)表相關(guān)項(xiàng)里。此后, 計(jì)算數(shù)組A的元素地址時(shí)僅需計(jì)算VPART的值, 而直接引用a和C值。,實(shí)現(xiàn)數(shù)組元素的地址計(jì)算時(shí), 產(chǎn)生兩組四元式序列: 一組計(jì)算VPART, 值存在臨時(shí)變量T1中; 另一組計(jì)算CPART, 值存在臨時(shí)變量T2中; 用T2T1表示數(shù)組元素的地址。,數(shù)組元素的引用和賦值有兩種四元式: (1)變址取數(shù): X=TT1

47、, 用(=,T2T1,_,X)表示 (2)變址存數(shù): TT1=X, 用(=,X,_,T2T1)表示,8.6.2 賦值語(yǔ)句中數(shù)組元素的翻譯 為了便于語(yǔ)法制導(dǎo)翻譯, 定義一個(gè)含數(shù)組元素的賦值語(yǔ)句文法如下: GA: (1) AV=E (2) Vielist | i (3) elistelist, E | E (4) EE+E | (E) | V,為了在用產(chǎn)生式(2),(3)歸約時(shí), 能及時(shí)計(jì)算VPART, 把文法改寫(xiě)為: GA: (1) AV=E (2) Velist | i (3) elistelist, E | iE (4) EE+E | (E) | V,(1) AV=E (2) Vielist

48、 | i (3) elistelist, E | E (4) EE+E | (E) | V,(1) elist.ARRAY: 表示數(shù)組名在符號(hào)表的入口; (2) elist.DIM: 表示數(shù)組的維數(shù); (3) elist.place: 表示VPART中間結(jié)果的存放位置; (4) limit(ARRAY, k): 表示數(shù)組ARRAY的第k維長(zhǎng)度dk.,為了產(chǎn)生計(jì)算VPART的四元式序列, 需設(shè)置如下語(yǔ)義變量和函數(shù):,每個(gè)變量V有兩項(xiàng)語(yǔ)義值: V.place和V.offset。 若V是簡(jiǎn)單變量名i, 則V.place為該變量名在符號(hào)表中的入口, V.offset為null; 若V是下標(biāo)變量名, 則

49、V.place為保存CPART的臨時(shí)變量名的整數(shù)碼,V.offset為保存VPART的臨時(shí)變量名的整數(shù)碼。,(1) AV=E if (V.offset = = null) emit(=, E.place, _, V.place); else emit( =, E.place, _, V.placeV.offset);,(1) AV=E (2) Velist | i (3) elistelist, E | iE (4) EE+E | (E) | V,含數(shù)組元素的賦值語(yǔ)句文法GA的語(yǔ)義子程序:,(2) EE(1) +E(2) T = newtemp; emit(+, E(1).place, E(2

50、).place, T); E.place = T; (3) E(E(1) ) E.place = E(1).place;,(4) Vi V.place = entry(i); V.offset = null; ,(1) AV=E (2) Velist | i (3) elistelist, E | iE (4) EE+E | (E) | V,(5) Velist T = newtemp; emit(, elist.ARRAY, C, T); V.place = T; V.offset = elist.place; ,(6) EV if (V.offset = = null) E.place =

51、 V.place; else T = newtemp; emit(= , V.placeV.offset,_,T); E.place = T; ,(1) AV=E (2) Velist | i (3) elistelist, E | iE (4) EE+E | (E) | V,(7) elistiE elist.place=E.place; elist.DIM=1; elist.ARRAY = entry(i); ,(8) elistelist(1), E k = elist(1).DIM + 1; dk=limit(elist(1).ARRAY, k); T = newtemp; emit(

52、*, elist(1).place, dk, T); emit(+, T; E.place, T); elist.ARRAY=elist(1).ARRAY; elist.place = T; elist.DIM = k; ,(5) Velist T = newtemp; emit(, elist.ARRAY, C, T); V.place = T; V.offset = elist.place; ,8.6.3 數(shù)組元素翻譯示例 例 已知A是一個(gè)1020的數(shù)組(每維下界均為1)且按行存放, 求下式的四元式序列: (1) x=ai, j; (2) x=ai+1, j-2; (3) ai+3, j+

53、4=m+n 解: 由于a是1020的數(shù)組, 故d1=10, d2=20, C=l1d2+12=21 (1) x=ai,j的翻譯過(guò)程如下:,x=ai,j,V.place=entry(x); V.offset=null,V=ai,j,(6),(4),(6),V=aV1,j,V1.place=entry(i); V1.offset=null,V=aE1,j,E1.place=V1.place,V=elist,j,elist.place=E1.place; elist.DIM=1; elist.ARRAY=a,(6),V=elist,V2,V2.place=entry(j); V2.offset=nu

54、ll,(4),E2.place=V2.place,V=elist,E2,最后得到x=ai,j的四元式序列: 100 (*, i, 20, T1) 101 (+, T1, j, T1) 102 (, a, 21, T2) 103 (=, T2T1, _, T3) 104 (=, T3, _, X),(2) x=ai+1, j-2; (略) (3) ai+3,j+4=m+n;的四元式序列為: 100 (+, i, 3, T1) 101 (+, j, 4, T2) 102 (*, T1, 20, T3) 103 (+, T3, T2, T3) 104 (, a, 21, T4) 105 (+, m,

55、 n, T5) 106 (=, T5, _, T4T3),例 給出下列語(yǔ)句的四元式序列: if (p1= =0p210) x2,3=4; else y=x7,6; 其中x是1020數(shù)組(每維下界為1)且按行存放, 每個(gè)數(shù)組元素占2字節(jié)。 解: C=l1d2*2+l2*2=42 四元式序列如下: 100 (j=, p1, 0, 102) 101 (j, _, _, 110) 102 (j, p2, 10, 104) 103 (j, _, _, 110),104 (*, 2, 40, T1) / x2,3=4 105 (*, 3, 2, T2) 106 (+, T1, T2, T3) 107 (,

56、 x, 42, T4) 108 (=, 4, _, T4T3) 109 (j, _, _, 116) 110 (*, 7, 40, T5) / y=x7,6 111 (*, 6, 2, T6) 112 (+, T5, T6, T7) 113 (, x, 42, T8) 114 (= , T8T7, _,T9) 115 (=, T9, _, y) 116,8.7.1 過(guò)程調(diào)用的方法 過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯產(chǎn)生一個(gè)調(diào)用序列和返回序列。 若過(guò)程P中有過(guò)程調(diào)用call Q, 則執(zhí)行到call Q時(shí)所做的過(guò)程調(diào)用工作如下:,8.7 過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯,執(zhí)行call Q時(shí)所做的過(guò)程調(diào)用工作: (1) 為Q分配活動(dòng)記錄的存儲(chǔ)空間; (2) 將實(shí)參傳遞給Q的形式單元; (3) 建立過(guò)程Q的外圍嵌套過(guò)程的層次顯示表; (4) 保留調(diào)用時(shí)的環(huán)境狀態(tài), 以便返回時(shí)恢復(fù); (5) 保存返回地址; (6) 生成一條轉(zhuǎn)子指令轉(zhuǎn)移到被調(diào)用過(guò)程的代碼段開(kāi)始位置。,過(guò)程返回時(shí): (1) 若是函數(shù)調(diào)用, 則返回前將返回值存放到指定位置;