語(yǔ)法制導(dǎo)翻譯和中間代碼

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

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

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

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

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

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

3、子界類型中的下界和上界類型是否相容？下界是否小于等于上界？第六頁(yè)，共七十二頁(yè)，編輯于2023年，星期一二、動(dòng)態(tài)語(yǔ)義處理

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

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

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

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

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

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

..

..

規(guī)則n相關(guān)的屬性等式第十一頁(yè)，共七十二頁(yè)，編輯于2023年，星期一【例】用屬性文法表示簡(jiǎn)單的無(wú)符號(hào)整數(shù)文法：

number→numberdigit|digit

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

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

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

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

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

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

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

產(chǎn)生式語(yǔ)義規(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語(yǔ)義過(guò)程L的屬性為空E、T、F的val為綜合屬性digit僅有綜合屬性由詞法分析程序提供第十六頁(yè)，共七十二頁(yè)，編輯于2023年，星期一【例8.2】

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

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

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

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

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

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

第十九頁(yè)，共七十二頁(yè)，編輯于2023年，星期一

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

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

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

for

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

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

for

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

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

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

fori:=1tokdo

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

對(duì)于給定的一棵語(yǔ)法分析樹、依賴圖是按下面步驟構(gòu)造出來(lái)的：第二十一頁(yè)，共七十二頁(yè)，編輯于2023年，星期一【例如】屬性A.a:=f(X.x,Y.y)

對(duì)應(yīng)于產(chǎn)生式AXY的語(yǔ)義規(guī)則,這條語(yǔ)義規(guī)則確定了依賴于屬性X.x和Y.y的綜合屬性A.a。如果在語(yǔ)法樹中應(yīng)用這個(gè)產(chǎn)生式，那么在依賴圖中會(huì)有三個(gè)結(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對(duì)應(yīng)的語(yǔ)義規(guī)則還有：

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

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

S-屬性文法的翻譯器通?？山柚鶯R分析器來(lái)實(shí)現(xiàn)在分析棧中使用一個(gè)附加的域來(lái)存放綜合屬性值假設(shè)語(yǔ)義規(guī)則A.a:=f(X.x,Y.y,Z.z)是對(duì)應(yīng)于產(chǎn)生式A→XYZ的第二十五頁(yè)，共七十二頁(yè)，編輯于2023年，星期一 產(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)生式語(yǔ)義規(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第二十六頁(yè)，共七十二頁(yè)，編輯于2023年，星期一輸入 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 第二十七頁(yè)，共七十二頁(yè)，編輯于2023年，星期一輸入 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 第二十八頁(yè)，共七十二頁(yè)，編輯于2023年，星期一輸入 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 第二十九頁(yè)，共七十二頁(yè)，編輯于2023年，星期一8.2.3L-屬性文法和自頂向下翻譯

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

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

的后綴式就是E的后綴式。第三十四頁(yè)，共七十二頁(yè)，編輯于2023年，星期一1、后綴表示式逆波蘭表示法不用括號(hào)。只要知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都能對(duì)它進(jìn)行唯一分解。

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

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

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

第三十九頁(yè)，共七十二頁(yè)，編輯于2023年，星期一抽象語(yǔ)法樹對(duì)應(yīng)的代碼：

T1:=-c T2:=b*T1

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

a:=T5assigna+*buminusc抽象語(yǔ)法樹*buminusc第四十頁(yè)，共七十二頁(yè)，編輯于2023年，星期一DAG對(duì)應(yīng)的代碼：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象語(yǔ)法樹對(duì)應(yīng)的代碼：

T1:=-c T2:=b*T1

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

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

2）四元式中變量采用符號(hào)表的入口地址，而不用變量的地址，因?yàn)檎Z(yǔ)義分析不僅需要變量的地址，還需要從符號(hào)表查到變量的屬性、類型和地址等。第四十四頁(yè)，共七十二頁(yè)，編輯于2023年，星期一3、四元式形式：例如：a：=b*c+b*d的四元式表示如下：（1）（*，b，c，t1）（2）（*，b，d，t2）（3）（+，t1，t2，t3）（4）（:=，t3，-，a）第四十五頁(yè)，共七十二頁(yè)，編輯于2023年，星期一4、三元式形式（Op，ARG1，ARG2）注：1）這里三元式本身作為存放結(jié)果的單元。

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

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

ifa<bthen1else0，翻譯成

100: ifa<bgoto103 101: T:=0 102: goto104 103: T:=1 104:第五十頁(yè)，共七十二頁(yè)，編輯于2023年，星期一關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式過(guò)程emit將三地址代碼送到輸出文件中nextstat給出輸出序列中下一條三地址語(yǔ)句的地址索引每產(chǎn)生一條三地址語(yǔ)句后，過(guò)程emit便把nextstat加1第五十一頁(yè)，共七十二頁(yè)，編輯于2023年，星期一關(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}第五十二頁(yè)，共七十二頁(yè)，編輯于2023年，星期一關(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:第五十三頁(yè)，共七十二頁(yè)，編輯于2023年，星期一布爾表達(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)}第五十四頁(yè)，共七十二頁(yè)，編輯于2023年，星期一8.5.2作為條件控制的布爾式翻譯條件語(yǔ)句ifEthenS1elseS2賦予E兩種出口:一真一假E.codeS1.codeS2.codeToE.trueToE.falsegotoS.nextS.next……E.true:E.false:第五十五頁(yè)，共七十二頁(yè)，編輯于2023年，星期一例：把語(yǔ)句:ifa>corb<dthenS1elseS2翻譯成如下的一串三地址代碼

ifa>cgotoL2“真”出口

gotoL1L1: ifb<dgotoL2“真”出口

gotoL3“假”出口L2: (關(guān)于S1的三地址代碼序列) gotoLnextL3: (關(guān)于S2的三地址代碼序列)Lnext:第五十六頁(yè)，共七十二頁(yè)，編輯于2023年，星期一產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則每次調(diào)用函數(shù)newlabel后都返回一個(gè)新的符號(hào)標(biāo)號(hào)對(duì)于一個(gè)布爾表達(dá)式E，引用兩個(gè)標(biāo)號(hào)E.true是E為‘真’時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào)E.false是E為‘假’時(shí)控制流轉(zhuǎn)向的標(biāo)號(hào)第五十七頁(yè)，共七十二頁(yè)，編輯于2023年，星期一產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則 產(chǎn)生式 語(yǔ)義規(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第五十八頁(yè)，共七十二頁(yè)，編輯于2023年，星期一產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則

產(chǎn)生式 語(yǔ)義規(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第五十九頁(yè)，共七十二頁(yè)，編輯于2023年，星期一產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則

產(chǎn)生式 語(yǔ)義規(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第六十頁(yè)，共七十二頁(yè)，編輯于2023年，星期一產(chǎn)生布爾表達(dá)式三地址代碼的語(yǔ)義規(guī)則 產(chǎn)生式 語(yǔ)義規(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)第六十一頁(yè)，共七十二頁(yè)，編輯于2023年，星期一考慮如下表達(dá)式：

a<borc<dande<f

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

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

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

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