語法制導(dǎo)翻譯和中間代碼第一頁，共七十二頁，2022年，8月28日本章內(nèi)容8.1屬性文法8.2語法制導(dǎo)翻譯概論8.3中間代碼的形式8.4簡單賦值語句的翻譯8.5布爾表達(dá)式的翻譯8.6控制結(jié)構(gòu)的翻譯8.7說明語句的翻譯8.8數(shù)組和結(jié)構(gòu)的翻譯符號表第二頁，共七十二頁，2022年，8月28日編譯程序的任務(wù)是將匯編語言或高級語言書寫成的源程序轉(zhuǎn)換成等價的目標(biāo)代碼程序。其中要求目標(biāo)代碼程序和源程序的語義(Semantics）必須相同。

什么是語義？程序的語義就是它的“意思”。語義分析的任務(wù)包括兩方面:一個是靜態(tài)語義檢查;一個是動態(tài)語義的解釋執(zhí)行（通俗地說就是計算并生成中間代碼。8.1屬性文法第三頁，共七十二頁，2022年，8月28日一、靜態(tài)語義分析或靜態(tài)語義審查語義分析的工作:包括：（1）類型檢查。根據(jù)類型相容性要求，驗證程序中執(zhí)行的每個操作是否遵守語言的類型系統(tǒng)的過程，編譯程序必須報告不符合類型系統(tǒng)的信息。

（2）控制流檢查?？刂屏髡Z句必須使控制轉(zhuǎn)移到合法的地方。例如，在C語言中break語句使控制跳離包括該語句的最小while、for或switch語句。如果不存在包括它的這樣的語句，則報錯。（3）一致性檢查。

（4）上下文相關(guān)性檢查。比如，變量名字必須先聲明后引用；

(5)名字的作用域分析例例第四頁，共七十二頁，2022年，8月28日1、各種條件表達(dá)式的類型是不是boolean型？2、運(yùn)算符的分量的類型是否相容？3、賦值語句的左右部的類型是否相容？4、形參和實(shí)參的類型是否相容？5、下標(biāo)表達(dá)式的類型是否為所允許的類型？6、函數(shù)說明中的函數(shù)類型和返回值的類型是否一致？第五頁，共七十二頁，2022年，8月28日1、每個使用的標(biāo)識符是否都有聲明？在同層內(nèi)有無標(biāo)識符被聲明多次？

【例如】Pascal語言規(guī)定同一標(biāo)識符在一個分程序中只能被說明一次，同一case語句的標(biāo)號不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等等。2、標(biāo)號是否有聲明？有無重復(fù)聲明和重復(fù)定位錯誤？有無非法轉(zhuǎn)入錯誤？

3、子界類型中的下界和上界類型是否相容？下界是否小于等于上界？第六頁，共七十二頁，2022年，8月28日二、動態(tài)語義處理

如果靜態(tài)語義正確，語義處理則執(zhí)行真正的翻譯（動態(tài)語義）即：生成程序的一種中間表示形式或生成實(shí)際的目標(biāo)代碼。中間代碼(中間語言)是介于源語言和機(jī)器語言的一種表示形式。通常語義分析生成中間代碼的原因：便于移植：中間代碼相對獨(dú)立于目標(biāo)機(jī)，在編譯程序移植時編譯前端保持不變。利于優(yōu)化：將優(yōu)化分為與目標(biāo)機(jī)無關(guān)的中間代碼優(yōu)化，以及與目標(biāo)機(jī)相關(guān)的目標(biāo)代碼的優(yōu)化，使優(yōu)化更加細(xì)致有效。第七頁，共七十二頁，2022年，8月28日

語義分析的整個過程和詞法及語法分析相類似。例如,在語法分析中，使用BackusNaus范式(BNF)中的上下文無關(guān)文法描述語法結(jié)構(gòu)，并用各種自頂向下和自底向上的分析算法實(shí)現(xiàn)語法結(jié)構(gòu)。由于沒有標(biāo)準(zhǔn)的方法(如BNF)來說明語言的靜態(tài)語義，因此語義分析就沒有這么簡單。常采用屬性文法(attributegrammar)來描述語義。語義的形式化描述第八頁，共七十二頁，2022年，8月28日8.1屬性文法一、屬性（Attribute

）屬性翻譯文法是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號（終結(jié)符或非終結(jié)符）配備若干相關(guān)的“值”（稱為屬性）。屬性代表與文法符號相關(guān)信息，例如它的類型、值、代碼序列、符號表內(nèi)容等等。屬性與變量一樣，可以進(jìn)行計算和傳遞。屬性加工的過程即是語義處理的過程。對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。

第九頁，共七十二頁，2022年，8月28日二、屬性文法（AttributeGrammar）的定義一個屬性文法是一個三元組A＝(G,V,F)，其中：G為一上下文無關(guān)文法。V為屬性的有窮集。F是關(guān)于屬性的斷言或一組屬性的計算規(guī)則(稱為語義規(guī)則)。第十頁，共七十二頁，2022年，8月28日屬性文法的表示分兩部分：首先在上下文無關(guān)文法中，對于每個文法符號引進(jìn)相關(guān)的屬性符號；其次對于每個產(chǎn)生式寫出計算屬性值的計算規(guī)則（即語義規(guī)則）,來描述各屬性間的關(guān)系。形式為：

文法規(guī)則語義規(guī)則

規(guī)則1相關(guān)的屬性等式

..

..

規(guī)則n相關(guān)的屬性等式第十一頁，共七十二頁，2022年，8月28日【例】用屬性文法表示簡單的無符號整數(shù)文法：

number→numberdigit|digit

digit→0|1|2|3|4|5|6|7|8|9【分析】一個數(shù)最重要的屬性是它的值，將其命名為val。每個數(shù)字都有一個值，可以用它表示的實(shí)際數(shù)直接計算。1、文法規(guī)則：digit→0

語義規(guī)則：digit.val=0

2、文法規(guī)則：number→digit

語義規(guī)則：number.val=digit.val。3、文法規(guī)則number→numberdigit,必須表示出這個文法規(guī)則左邊符號的值和右邊符號的值之間的關(guān)系。通過使用下標(biāo)進(jìn)行區(qū)分，將文法寫成如下形式：

number1→number2digit語義規(guī)則：number1.val:=number2.val*10+digit.val第十二頁，共七十二頁，2022年，8月28日三、屬性的分類（1）綜合屬性：用于“自下而上”傳遞信息分析樹中，如果一個結(jié)點(diǎn)的屬性值是通過子結(jié)點(diǎn)的屬性值計算得到則稱綜合屬性。（2）繼承屬性：用于“自上而下”傳遞信息分析樹中，如果一個結(jié)點(diǎn)的屬性值由該結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)定義的則稱繼承屬性。第十三頁，共七十二頁，2022年，8月28日四、語義規(guī)則在一個屬性文法中，對應(yīng)于每個產(chǎn)生式A→都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為：b:=f(c1,c2,…,ck)

這里，f是一個函數(shù)，而且或者1）b是A的一個綜合屬性并且c1,c2,…,ck是產(chǎn)生式右邊文法符號的屬性，或者2）b是產(chǎn)生式右邊某個文法符號的一個繼承屬性并且c1,c2,…,ck

是A或產(chǎn)生式右邊任何文法符號的屬性。 屬性b依賴于屬性c1,c2,…,ck。第十四頁，共七十二頁，2022年，8月28日說明：終結(jié)符只有綜合屬性，由詞法分析器提供非終結(jié)符既可有綜合屬性也可有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值對出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提供一個計算規(guī)則。屬性計算規(guī)則中只能使用相應(yīng)產(chǎn)生式中的文法符號的屬性出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給的產(chǎn)生式的屬性計算規(guī)則進(jìn)行計算，它們由其它產(chǎn)生式的屬性規(guī)則計算或者由屬性計算器的參數(shù)提供第十五頁，共七十二頁，2022年，8月28日【例8.1】算術(shù)表達(dá)式求值的語義描述:

產(chǎn)生式語義規(guī)則L→Eprint(E.val)E→E1+T

E.val:=E1.val+T.valE→TE.val:=T.valT→T1*FT.val:=T1.val×F.val

T→FT.val:=F.val

F→(E)F.val:=E.val

F→digit

F.val=digit.lexval語義過程L的屬性為空E、T、F的val為綜合屬性digit僅有綜合屬性由詞法分析程序提供第十六頁，共七十二頁，2022年，8月28日【例8.2】

帶有繼承屬性L.in的語義規(guī)則

產(chǎn)生式語義規(guī)則

DTLLin:=TtypeTintTtype:=intTrealTtype:=realLL1,idL1in:=Linaddtype(identry,Lin)Lidaddtype(identry,Lin)第十七頁，共七十二頁，2022年，8月28日8.2語法制導(dǎo)翻譯概論語法制導(dǎo)翻譯法在語法分析的基礎(chǔ)上進(jìn)行邊分析邊翻譯。注：1）語法制導(dǎo)翻譯時會根據(jù)文法產(chǎn)生式右部符號串的含義，進(jìn)行翻譯，翻譯的結(jié)果是生成相應(yīng)中間代碼。

2）語法制導(dǎo)翻譯的依據(jù)是語義子程序。

3）具體做法：為每個產(chǎn)生式配置一個語義子程序，當(dāng)語法分析進(jìn)行歸約或推導(dǎo)時，調(diào)用語義子程序，完成一部分翻譯任務(wù)。

4）語法分析完成，翻譯工作也結(jié)束。第十八頁，共七十二頁，2022年，8月28日語法制導(dǎo)翻譯過程通常是這樣的：1)對單詞符號串進(jìn)行語法分析，構(gòu)造語法分析樹;2)從語法分析樹得到描述節(jié)點(diǎn)屬性間依賴關(guān)系的依賴圖;3)由此依賴圖得到語義規(guī)則的計算次序;進(jìn)行語義規(guī)則計算，得到翻譯結(jié)果可表示為：輸入串語法樹依賴圖語義規(guī)則計算次序

第十九頁，共七十二頁，2022年，8月28日

在一棵語法樹中結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以用稱作依賴圖的一個有向圖來描述。在為一棵語法樹構(gòu)造依賴圖以前，為每一個包含過程調(diào)用的語義規(guī)則引入一個虛綜合屬性b，這樣把每一個語義規(guī)則都寫成如下形式：

b:=f(c1,c2,…ck)依賴圖中為每一個屬性設(shè)置一個結(jié)點(diǎn)，如果屬性b依賴屬性c，則從屬性c的結(jié)點(diǎn)有一條有向邊連到屬性b的結(jié)點(diǎn)。依賴圖第二十頁，共七十二頁，2022年，8月28日

for分析樹中每一個結(jié)點(diǎn)ndo

for

結(jié)點(diǎn)的文法符號的每一個屬性ado

為a在依賴圖中建立一個結(jié)點(diǎn)；

for

分析樹中每一個結(jié)點(diǎn)ndo

for結(jié)點(diǎn)n所用產(chǎn)生式對應(yīng)的每一個語義規(guī)則

b:=f(c1,c2,…ck)do

fori:=1tokdo

從ci結(jié)點(diǎn)到b結(jié)點(diǎn)構(gòu)造一條有向邊

對于給定的一棵語法分析樹、依賴圖是按下面步驟構(gòu)造出來的：第二十一頁，共七十二頁，2022年，8月28日【例如】屬性A.a:=f(X.x,Y.y)

對應(yīng)于產(chǎn)生式AXY的語義規(guī)則,這條語義規(guī)則確定了依賴于屬性X.x和Y.y的綜合屬性A.a。如果在語法樹中應(yīng)用這個產(chǎn)生式，那么在依賴圖中會有三個結(jié)點(diǎn)A.a,X.x,和Y.y。由于A.a依賴X.x，所以有一條有向邊從X.x到A.a.由于A.a也依賴于Y.y，所以還有一條有向邊從Y.y連到A.a.

如果與產(chǎn)生式AXY對應(yīng)的語義規(guī)則還有：

X.i:=g(A.a,Y.y)

那么，圖中還應(yīng)有兩條有向邊，一條從A.a連到X.i，另一條從Y.y連到X.i,因為X.i依賴于A.a和Y.y.A.aX.xY.yX.i第二十二頁，共七十二頁，2022年，8月28日如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么該文法為良定義的。為了設(shè)計編譯程序，我們只處理良定義的屬性文法。第二十三頁，共七十二頁，2022年，8月28日8.2.2S-屬性文法的自下而上計算1、S-屬性文法僅僅使用綜合屬性的屬性文法稱S－屬性文法綜合屬性可以在分析輸入符號串的同時由自下而上的分析器來計算。分析器可以保存與棧中文法符號有關(guān)的綜合屬性值，每當(dāng)進(jìn)行歸約時，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號的屬性值來計算。第二十四頁，共七十二頁，2022年，8月28日2、S-屬性文法的翻譯器

S-屬性文法的翻譯器通常可借助LR分析器來實(shí)現(xiàn)在分析棧中使用一個附加的域來存放綜合屬性值假設(shè)語義規(guī)則A.a:=f(X.x,Y.y,Z.z)是對應(yīng)于產(chǎn)生式A→XYZ的第二十五頁，共七十二頁，2022年，8月28日 產(chǎn)生式 代碼段

L→En print(val[top]) E→E1+T val[ntop]:=val[top-2]+val[top] E→T T→T1*F val[ntop]:=val[top-2]*val[top] T→F F→(E) val[ntop]:=val[top-1] F→digit

產(chǎn)生式語義規(guī)則

L→Enprint(E.val)E→E1+TE.val:=E1.val+T.valE→TE.val:=T.valT→T1*FT.val:=T1.val*F.valT→F T.val:=F.valF→(E)F.val:=E.valF→digitF.val:=digit.lexval第二十六頁，共七十二頁，2022年，8月28日輸入 state sym val 用到的產(chǎn)生式

3*5+4n0 # - *5+4n05 #3 -3 *5+4n03 #F -3 F→digit*5+4n02 #T -3 T→F5+4n027 #T* -3- +4n0275 #T*5 -3-5 產(chǎn)生式 代碼段

L→En print(val[top]) E→E1+T val[ntop]:=val[top-2]+val[top] E→T T→T1*F val[ntop]:=val[top-2]*val[top] T→F F→(E) val[ntop]:=val[top-1] F→digit 第二十七頁，共七十二頁，2022年，8月28日輸入 state sym val 用到的產(chǎn)生式

+4n0275 #T*5 -3-5 +4n02710 #T*F -3-5 F→digit+4n02 #T -15 T→T*F+4n01 #E -15 E→T4n016 #E+ -15- n0165 #E+4 -15-4 產(chǎn)生式 代碼段

L→En print(val[top]) E→E1+T val[ntop]:=val[top-2]+val[top] E→T T→T1*F val[ntop]:=val[top-2]*val[top] T→F F→(E) val[ntop]:=val[top-1] F→digit 第二十八頁，共七十二頁，2022年，8月28日輸入 state symval 用到的產(chǎn)生式

n0165 #E+4 -15-4 n0163#E+F -15-4 F→digitn0169#E+T -15-4 T→Fn01 #E-19 E→E+T #En -19- #L -19 L→En 產(chǎn)生式 代碼段

L→En print(val[top]) E→E1+T val[ntop]:=val[top-2]+val[top] E→T T→T1*F val[ntop]:=val[top-2]*val[top] T→F F→(E) val[ntop]:=val[top-1] F→digit 第二十九頁，共七十二頁，2022年，8月28日8.2.3L-屬性文法和自頂向下翻譯

通過深度優(yōu)先的方法對語法樹進(jìn)行遍歷，計算屬性文法的所有屬性值LL(1)：自上而下分析方法，深度優(yōu)先建立語法樹第三十頁，共七十二頁，2022年，8月28日一個屬性文法稱為L-屬性文法，如果對于每個產(chǎn)生式A→X1X2…Xn，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj(1jn)的一個繼承屬性且這個繼承屬性僅依賴于：(1)產(chǎn)生式Xj的左邊符號X1，X2，…，Xj-1的屬性；(2)A的繼承屬性。S-屬性文法一定是L-屬性文法第三十一頁，共七十二頁，2022年，8月28日【思考】非L-屬性的語法制導(dǎo)定義【分析】該語法制導(dǎo)定義不是L-屬性定義，文法符號Q的繼承屬性依賴于它右邊文法符號R的屬性。產(chǎn)生式語義規(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)第三十二頁，共七十二頁，2022年，8月28日8.3中間代碼的形式中間代碼是源程序的一種內(nèi)部表示復(fù)雜性介于源語言和目標(biāo)機(jī)語言之間中間代碼的作用使編譯程序的邏輯結(jié)構(gòu)更加簡單明確利于進(jìn)行與目標(biāo)機(jī)無關(guān)的優(yōu)化利于在不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語言中間代碼的形式逆波蘭式、四元式、三元式、樹第三十三頁，共七十二頁，2022年，8月28日1、后綴表示式Lukasiewicz發(fā)明的一種表示表達(dá)式的方法，又稱逆波蘭表示法。一個表達(dá)式E的后綴形式可以如下定義：1）如果E是一個變量或常量，則E的后綴式是E自身。2）如果E是E1opE2形式的表達(dá)式，其中op是任何二元運(yùn)算符，則E的后綴式為E1E2op，其中E1和E2分別為E1

和E2的后綴式。3）如果E是(E1)形式的表達(dá)式，則E1

的后綴式就是E的后綴式。第三十四頁，共七十二頁，2022年，8月28日1、后綴表示式逆波蘭表示法不用括號。只要知道每個算符的目數(shù)，對于后綴式，不論從哪一端進(jìn)行掃描，都能對它進(jìn)行唯一分解。

例如：（a+b）*c表示成ab+c*后綴式的計算用一個棧實(shí)現(xiàn)。一般的計算過程是：自左至右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個項，并用運(yùn)算結(jié)果代替這k個項。第三十五頁，共七十二頁，2022年，8月28日1、后綴表示式把表達(dá)式翻譯成后綴式的語義規(guī)則描述產(chǎn)生式E→E(1)opE(2)E→(E(1))E→id 語義動作E.code:=E(1).code||E(2).code||opE.code:=E(1).codeE.code:=idE.code表示E后綴形式op表示任意二元運(yùn)算符“||”表示后綴形式的連接。第三十六頁，共七十二頁，2022年，8月28日數(shù)組POST存放后綴式：k為下標(biāo)，初值為1上述語義動作可實(shí)現(xiàn)為： 產(chǎn)生式 程序段 E→E(1)opE(2) {POST[k]:=op;k:=k+1} E→(E(1)) {} E→i {POST[k]:=i;k:=k+1}例：輸入串a(chǎn)+b+c的分析和翻譯 POST：12345E→E(1)opE(2) E.code:=E(1).code||E(2).code||opE→(E(1)) E.code:=E(1).codeE→id E.code:=idab+c+…第三十七頁，共七十二頁，2022年，8月28日2、圖表示法DAG（無循環(huán)有向圖）抽象語法樹（1）無循環(huán)有向圖(DirectedAcyclicGraph，簡稱DAG)對表達(dá)式中的每個子表達(dá)式，DAG中都有一個結(jié)點(diǎn)一個內(nèi)部結(jié)點(diǎn)代表一個操作符，它的孩子代表操作數(shù)在一個DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個父結(jié)點(diǎn)第三十八頁，共七十二頁，2022年，8月28日

a:=b*(-c)+b*(-c)的圖表示法

assigna+*buminuscDAGassigna+*buminusc抽象語法樹*buminusc后綴式是抽象語法樹的線性表示形式：abc-*bc-*+:=

第三十九頁，共七十二頁，2022年，8月28日抽象語法樹對應(yīng)的代碼：

T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5assigna+*buminusc抽象語法樹*buminusc第四十頁，共七十二頁，2022年，8月28日DAG對應(yīng)的代碼：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象語法樹對應(yīng)的代碼：

T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5第四十一頁，共七十二頁，2022年，8月28日三地址代碼三地址代碼x:=yopz三地址代碼可以看成是抽象語法樹或DAG的一種線性表示第四十二頁，共七十二頁，2022年，8月28日三地址語句的種類x:=yopzx:=opyx:=ygotoLifxrelopygotoL或ifagotoLparamx和callp,n，以及返回語句returnyx:=y[i]及x[i]:=y的索引賦值x:=&y,x:=*y和*x:=y的地址和指針賦值第四十三頁，共七十二頁，2022年，8月28日3、四元式形式：一個帶有四個域的記錄結(jié)構(gòu)：（Op，ARG1，ARG2，Result）注：1）ARG1，ARG2，Result可能是用戶自己定義的變量，也可能是編譯時引進(jìn)的變量。這里Op是雙目運(yùn)算符，若只有一個運(yùn)算量，則是單目運(yùn)算符。

2）四元式中變量采用符號表的入口地址，而不用變量的地址，因為語義分析不僅需要變量的地址，還需要從符號表查到變量的屬性、類型和地址等。第四十四頁，共七十二頁，2022年，8月28日3、四元式形式：例如：a：=b*c+b*d的四元式表示如下：（1）（*，b，c，t1）（2）（*，b，d，t2）（3）（+，t1，t2，t3）（4）（:=，t3，-，a）第四十五頁，共七十二頁，2022年，8月28日4、三元式形式（Op，ARG1，ARG2）注：1）這里三元式本身作為存放結(jié)果的單元。

2）為了在其它三元式中利用當(dāng)前三元式的結(jié)果，需要對三元式進(jìn)行編號。三元式的編號就作為相應(yīng)三元式的結(jié)果值。例如：a：=b*c+b*d的四元式表示如下：（1）（*，b，c）（2）（*，b，d）（3）（+，（1），（2））（4）（:=，（3），a）第四十六頁，共七十二頁，2022年，8月28日8.5布爾表達(dá)式的翻譯布爾表達(dá)式的兩個基本作用:用于邏輯演算,計算邏輯值;用于控制語句的條件式。產(chǎn)生布爾表達(dá)式的文法:E→EorE|EandE|notE|(E)|iropi|i第四十七頁，共七十二頁，2022年，8月28日計算布爾表達(dá)式通常采用兩種方法:1.如同計算算術(shù)表達(dá)式一樣,一步步算 1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=12.采用某種優(yōu)化措施把AorB解釋成 ifAthentrueelseB把AandB解釋成 ifAthenBelsefalse把notA解釋成 ifAthenfalseelsetrue第四十八頁，共七十二頁，2022年，8月28日兩種不同的翻譯方法:第一種翻譯法：AorBandC=D翻譯成 (1)(=,C,D,T1) (2)(and,B,T1,T2) (3)(or,A,T2,T3)第二種翻譯法適合于作為條件表達(dá)式的布爾表達(dá)式使用。第四十九頁，共七十二頁，2022年，8月28日8.5.1數(shù)值表示法aorbandnotc翻譯成

T1:=notc T2:=bandT1 T3:=aorT1a<b的關(guān)系表達(dá)式可等價地寫成

ifa<bthen1else0，翻譯成

100: ifa<bgoto103 101: T:=0 102: goto104 103: T:=1 104:第五十頁，共七十二頁，2022年，8月28日關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式過程emit將三地址代碼送到輸出文件中nextstat給出輸出序列中下一條三地址語句的地址索引每產(chǎn)生一條三地址語句后，過程emit便把nextstat加1第五十一頁，共七十二頁，2022年，8月28日關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式E→E1orE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘a(chǎn)nd’E2.place)}E→notE1 {E.place:=newtemp; emit(E.place‘:=’‘not’E1.place)}E→(E1) {E.place:=E1.place}第五十二頁，共七十二頁，2022年，8月28日關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式Eid1relopid2{E.place:=newtemp;

emit(‘if’id1.placerelop.opid2.place ‘goto’nextstat+3);

emit(E.place‘:=’‘0’);

emit(‘goto’nextstat+2);

emit(E.place‘:=’‘1’)}E→id {E.place:=id.place}a<b翻譯成100: ifa<bgoto103101: T:=0102: goto104103: T:=1104:第五十三頁，共七十二頁，2022年，8月28日布爾表達(dá)式a<borc<dande<f的翻譯結(jié)果100: ifa<bgoto103101: T1:=0 102: goto104103: T1:=1104: ifc<dgoto107105: T2:=0 106: goto108107: T2:=1108:ife<fgoto111109:T3:=0110:goto112111:T3:=1112:T4:=T2andT3113:T5:=T1orT4Eid1relopid2

{E.place:=newtemp; emit(‘if’id1.placerelop.opid2.place ‘goto’nextstat+3); emit(E.place‘:=’‘0’); emit(‘goto’nextstat+2); emit(E.place‘:=’‘1’)}E→id {E.place:=id.place}E→E1orE2

{E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp;emit(E.place‘:=’E1.place‘a(chǎn)nd’E2.place)}第五十四頁，共七十二頁，2022年，8月28日8.5.2作為條件控制的布爾式翻譯條件語句ifEthenS1elseS2賦予E兩種出口:一真一假E.codeS1.codeS2.codeToE.trueToE.falsegotoS.nextS.next……E.true:E.false:第五十五頁，共七十二頁，2022年，8月28日例：把語句:ifa>corb<dthenS1elseS2翻譯成如下的一串三地址代碼

ifa>cgotoL2“真”出口

gotoL1L1: ifb<dgotoL2“真”出口

gotoL3“假”出口L2: (關(guān)于S1的三地址代碼序列) gotoLnextL3: (關(guān)于S2的三地址代碼序列)Lnext:第五十六頁，共七十二頁，2022年，8月28日產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則每次調(diào)用函數(shù)newlabel后都返回一個新的符號標(biāo)號對于一個布爾表達(dá)式E，引用兩個標(biāo)號E.true是E為‘真’時控制流轉(zhuǎn)向的標(biāo)號E.false是E為‘假’時控制流轉(zhuǎn)向的標(biāo)號第五十七頁，共七十二頁，2022年，8月28日產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則 產(chǎn)生式 語義規(guī)則

E→E1orE2

E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code|| gen(E1.false‘:’)||E2.code

E1.codeToE.trueToE1.falseE2.codeToE.trueToE.false第五十八頁，共七十二頁，2022年，8月28日產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則 產(chǎn)生式 語義規(guī)則

E→E1andE2

E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.code|| gen(E1.true‘:’)||E2.codeE1.codeToE.

falseToE1.trueE2.codeToE.trueToE.false第五十九頁，共七十二頁，2022年，8月28日產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則

產(chǎn)生式 語義規(guī)則

E→notE1 E1.true:=E.false; E1.false:=E.true; E.code:=E1.codeE→(E1) E1.true:=E.true; E1.false:=E.false; E.code:=E1.code第六十頁，共七十二頁，2022年，8月28日產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則 產(chǎn)生式 語義規(guī)則

E→id1relopid2E.code:=gen(‘if’id1.place relop.opid2.place‘goto’E.true)|| gen(‘goto’E.false)E→true E.code:=gen(‘goto’E.true)E→false E.code:=gen(‘goto’E.false)第六十一頁，共七十二頁，2022年，8月28日考慮如下表達(dá)式：

a<borc<dande<f

假定整個表達(dá)式的真假出口已分別置為Ltrue和Lfalse，則按定義將生成如下的代碼：

ifa<bgotoLtrue gotoL1 L1: ifc<dgotoL2 gotoLfalse L2: ife<fgotoLtrue gotoLfalse第六十二頁，共七十二頁，2022年，8月28日布爾表達(dá)式的翻譯兩遍掃描為給定的輸入串構(gòu)造一棵語法樹；對語法樹進(jìn)行深度優(yōu)先遍歷，進(jìn)行語義規(guī)則中規(guī)定的翻譯。一遍掃描第六十三頁，共七十二頁，2022年，8月28日一遍掃描實(shí)現(xiàn)布爾表達(dá)式的翻譯采用四元式形式把四元式存入一個數(shù)組中，數(shù)組下標(biāo)就代表四元式的標(biāo)號約定 四元式(jnz,a,-,p) 表示ifagotop

四元式(jrop,x,y,p)表示ifxropygotop

四元式(j,-,-,p)表示gotop第六十四頁，共七十二頁，2022年，8月28日有時,四元式轉(zhuǎn)移地址無法立即知道,我們只好把這個未完成的四元式地址作為E的語義值保存,待機(jī)"回填"。第六十五頁，共七十二頁，2022年，8月28日為非終結(jié)符E賦予兩個綜合屬性E.truelist和E.falselist。它們分別記錄布爾表達(dá)式E所應(yīng)的四元式中需回填“真”、“假”出口的四元式的標(biāo)號所構(gòu)成的鏈表例如:假定E的四元式中需要回填"真"出口的p，q，r三個四元式，則E.truelist為下列鏈:(p)(x，x，x，0)…(q)(x，x，x，p