語法制導(dǎo)翻譯

語法制導(dǎo)翻譯第一頁，共一百零八頁，編輯于2023年，星期三編譯中的語義處理是指兩個功能：

一、審查每個語法結(jié)構(gòu)的靜態(tài)語義，即驗證語法結(jié)構(gòu)合法的程序是否真正有意義。二、如果靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯，即，要么生成程序的一種中間表示形式（中間代碼），要么生成實際的目標(biāo)代碼。第二頁，共一百零八頁，編輯于2023年，星期三教學(xué)內(nèi)容屬性文法與屬性翻譯文法語法制導(dǎo)翻譯概論常見中間語言概述簡單算術(shù)表達式和賦值語句的翻譯布爾表達式的翻譯程序流程控制語句的翻譯含數(shù)組元素及其在賦值語句中的翻譯第三頁，共一百零八頁，編輯于2023年，星期三§5.1屬性文法與屬性翻譯文法第四頁，共一百零八頁，編輯于2023年，星期三

一個屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語義規(guī)則附在文法的每個產(chǎn)生式上，在語法分析過程中，完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動作，從而實現(xiàn)語義處理。屬性文法第五頁，共一百零八頁，編輯于2023年，星期三

屬性，常用以描述事物或人的特征、性質(zhì)、品質(zhì)等等。比如，談到一個物體，可以用“顏色”描述它，談起某人，可以使用“有幽默感”來形容他。對編譯程序使用的語法樹的結(jié)點，可以用“類型”、“值”或“存儲位置”來描述它。第六頁，共一百零八頁，編輯于2023年，星期三

G：是一個上下文無關(guān)文法。

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

F：關(guān)于屬性的屬性斷言或謂詞集。每個斷言與一個產(chǎn)生式相聯(lián).而此斷言只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。屬性文法是一個三元組：A=（G，V，F(xiàn)），其中第七頁，共一百零八頁，編輯于2023年，星期三

如，有文法G為：

E→T1+T2|T1orT2

T→num|true|false

因為T在同一個產(chǎn)生式里出現(xiàn)了兩次，使用上角標(biāo)將它們區(qū)分開。第八頁，共一百零八頁，編輯于2023年，星期三屬性文法記號中常使用N.t的形式表示與非終結(jié)符N相聯(lián)的屬性t。比如可把完成對上面表達式的類型檢查的屬性文法寫成形式：第九頁，共一百零八頁，編輯于2023年，星期三

類型檢查的屬性文法

E→T1+T2｛T1.t=intANDT2.t=int｝

E→T1orT2｛T1.t=boolANDT2.t=bool｝

T→false｛T.t：=bool｝

T→num｛T.t：=int｝

T→true｛T.t：=bool｝

與每個非終結(jié)符T相聯(lián)的有屬性t，t要么是int，要么是bool。與非終結(jié)符E的產(chǎn)生式相聯(lián)的斷言指明：兩個T的屬性必須相同。第十頁，共一百零八頁，編輯于2023年，星期三

1）E→E1+E2｛E.val：=E1.val+E2.val｝可以用如下的方式定義E的“值”的語義：

2）E→1 ｛E.val：=1｝

3）E→0 ｛E.val：=0｝第十一頁，共一百零八頁，編輯于2023年，星期三屬性分成兩類：繼承屬性和綜合屬性，我們不對屬性文法進行理論上的研究而僅僅將它做為工具描述語義分析。在編譯的許多實際應(yīng)用中，屬性和斷言以多種形式出現(xiàn)，也就是說，與每個文法符號相聯(lián)的可以是各種屬性、斷言、以及語義規(guī)則，或者某種程序設(shè)計語言的程序段等等。

第十二頁，共一百零八頁，編輯于2023年，星期三產(chǎn)生式語義規(guī)則（0）L→E

print（E.val）（1）E→E1+T

E.val:=E1.val+T.val（2）E→T

E.val:=T.val（3）T→T1*F

T.val:=T1.val×F.val（4）T→F

T.val:=F.val（5）F→（E）F.val:=E.val（6）F→digit

F.val:=digit.lexval簡單算術(shù)表達式求值的語義描述第十三頁，共一百零八頁，編輯于2023年，星期三

在該描述中，每個非終結(jié)符都有一個屬性：一個整數(shù)值的稱作val的屬性。按照語義規(guī)則對每個產(chǎn)生式來說，它的左部E，T，F(xiàn)的屬性值的計算來自它右部的非終結(jié)符，這種屬性稱作綜合屬性。單詞digit僅有綜合屬性，它的值是由詞法分析程序提供的。和產(chǎn)生式L→E相聯(lián)的語義規(guī)則是一個過程，打印由E產(chǎn)生的表達式的值。我們可以理解為L的屬性是空的或是虛的。第十四頁，共一百零八頁，編輯于2023年，星期三5.2語法制導(dǎo)翻譯的概述基本思想： 在語法分析過程中，隨著分析的步步進展，每當(dāng)使用一條產(chǎn)生式進行推導(dǎo)（對于自上而下分析）或歸約（對于自下而上分析），就執(zhí)行該產(chǎn)生式所對應(yīng)的語義動作，完成相應(yīng)的翻譯工作。語法制導(dǎo)翻譯就是把語言的一些屬性附加到代表語言結(jié)構(gòu)的文法符號上，這些屬性值是由附加到文法產(chǎn)生式的“語義規(guī)則”中計算的，也就是為每個產(chǎn)生式配備翻譯子程序，即語義子程序。語法制導(dǎo)翻譯法不論對自上而下分析或自下而上分析都適用。第十五頁，共一百零八頁，編輯于2023年，星期三翻譯的任務(wù)：語法結(jié)構(gòu)的靜態(tài)語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標(biāo)代碼。使用的方法:稱作語法制導(dǎo)翻譯?；舅枷耄ê喲灾?根據(jù)翻譯的需要設(shè)置文法符號的屬性(這些屬性代表與文法符號相關(guān)的信息)，以描述語法結(jié)構(gòu)的語義。第十六頁，共一百零八頁，編輯于2023年，星期三屬性一般分為兩類：綜合屬性和繼承屬性。簡單的說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。屬性加工的過程即是語義處理的過程，對于文法的每一個產(chǎn)生式都配備了一組屬性的計算規(guī)則，則稱為語義規(guī)則。第十七頁，共一百零八頁，編輯于2023年，星期三一個屬性文法它包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語法規(guī)則附在文法的每個產(chǎn)生式上。在一個語法制導(dǎo)定義中，A→P都有與之相關(guān)聯(lián)的一套語義規(guī)則，規(guī)則形式為

b：=f（c1，c2，…，ck），f是一個函數(shù)，而且

1．b是A的一個綜合屬性并且c1，c2，…，ck是中的符號的屬性，或者

2．b是中的符號的一個繼承屬性并且c1，c2，…，ck是A或中的任何文法符號的屬性。在兩種情況下，都說

屬性b依賴于屬性c1，c2，…，ck。語法制導(dǎo)定義的形式第十八頁，共一百零八頁，編輯于2023年，星期三

一般來講，對出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提供一個計算規(guī)則，屬性計算規(guī)則中只能使用相應(yīng)產(chǎn)生式的文法符號的屬性，這有利于產(chǎn)生式范圍內(nèi)“封裝”屬性的依賴性。然而，出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給的產(chǎn)生式的屬性計算規(guī)則進行計算，它們由其它產(chǎn)生式的屬性規(guī)則計算,由屬性計算器的參數(shù)提供。特例：開始符號沒有繼承屬性，在開始時要確定；終結(jié)符則只能有綜合屬性，而不能有繼承屬性。非終結(jié)符既可有綜合屬性也可有繼承屬性第十九頁，共一百零八頁，編輯于2023年，星期三語義規(guī)則所描述的工作可以包括屬性計算、靜態(tài)語義檢查、符號表操作、代碼生成等。語義規(guī)則可能產(chǎn)生副作用（如產(chǎn)生代碼），也可能不是變元的嚴(yán)格函數(shù)（如某個規(guī)則給出可用的下一個數(shù)據(jù)單元的地址）。這樣的語義規(guī)則通常寫成過程調(diào)用，或過程段。綜合屬性：在語法樹中，一個結(jié)點的綜合屬性的值由其子結(jié)點的屬性值確定。因此，通常使用自底向上的方法在每一個結(jié)點處使用語義規(guī)則計算綜合屬性的值。僅僅使用綜合屬性的屬性文法稱S—屬性文法。繼承屬性：在語法樹中，一個結(jié)點的繼承屬性由此結(jié)點的父結(jié)點和/或兄弟結(jié)點的某些屬性確定。用繼承屬性來表示程序語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便。第二十頁，共一百零八頁，編輯于2023年，星期三例6.1臺式計算器程序的語法制導(dǎo)定義（表6.1)產(chǎn)生式語義規(guī)則S’Eprint(Eval)EE1+TEval:=E1val+TvalETEval:=TvalTT1*FTval:=T1val*FvalTFTval:=FvalF(E)Fval:=EvalFdigitFval:=digitlexval每個文法符號和一個屬性值val聯(lián)系，屬性值的設(shè)置和語法結(jié)構(gòu)的語義以及翻譯程序的需要有關(guān)。例如：把左例中的類型擴充到int和real。第二十一頁，共一百零八頁，編輯于2023年，星期三綜合屬性

S-屬性定義唯獨只使用綜合屬性的語法制導(dǎo)定義。結(jié)點屬性值的計算正好和自底向上分析建立分析樹結(jié)點同步進行。例6.2輸入：3*5+4n

第二十二頁，共一百零八頁，編輯于2023年，星期三digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19例6.2輸入3*5+4nLEnEE1+TETTT1*FTFF(E)Fdigit第二十三頁，共一百零八頁，編輯于2023年，星期三

◆綜合屬性值的計算方法

對于s-屬性定義通常使用自底向上的分析方法在建立每一個結(jié)點處綜合屬性值使用語義規(guī)則來計算即：哪個產(chǎn)生式進行歸約后，就執(zhí)行那個產(chǎn)生式的s-屬性定義計算屬性的值，從葉結(jié)點到根結(jié)點進行計算。第二十四頁，共一百零八頁，編輯于2023年，星期三繼承屬性繼承屬性值是由此結(jié)點的父結(jié)點和／或兄弟結(jié)點的某些屬性值來決定的。例描述說明語句中各種變量的類型信息的語義規(guī)則。

文法定義了一種說明語句，該說明語句的形式由關(guān)鍵字int或real開頭，后跟一個標(biāo)識符表，每個標(biāo)識符間有逗號隔開。非終結(jié)符號T有一個綜合屬性type，它的值由關(guān)鍵字int或real決定。與產(chǎn)生式D->TL相聯(lián)的語義L.in:=T.type將L.in的屬性值置為該說明語句指定的類型。屬性L.in將沿著語法樹傳遞到下邊的結(jié)點使用，與L產(chǎn)生式相聯(lián)的規(guī)則里使用了它。過程addtype的功能是把每個標(biāo)識符的類型信息登錄在符號表中相關(guān)項中。第二十五頁，共一百零八頁，編輯于2023年，星期三

帶有繼承屬性L.in的語法制導(dǎo)定義

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

DTLLin:=TtypeTintTtype:=integerTrealTtype:=realLL1,idL1

in:=Linaddtype(identry,Lin)Lidaddtype(identry,Lin)第二十六頁，共一百零八頁，編輯于2023年，星期三分析reali1,i2,i3DTLrealLi3Li2i1T.typeL.inrealL.ini3.entryL.ini2.entryi1.entry第二十七頁，共一百零八頁，編輯于2023年，星期三語法制導(dǎo)翻譯的實現(xiàn)途徑以自下而上（LR分析）的語法制導(dǎo)翻譯來說明將LR分析器能力擴大，增加在歸約后調(diào)用語義規(guī)則的功能增加語義棧，語義值放到與符號棧同步操作的語義棧中，多項語義值可設(shè)多個語義棧，棧結(jié)構(gòu)為：狀態(tài)棧符號棧語義棧SmXmXm.val………S1X1X1.valS0#-第二十八頁，共一百零八頁，編輯于2023年，星期三例簡單算術(shù)表達式求值的屬性文法L→E{print(E.val)}E→E1+T {E.val:＝E1.val+T.val}E→T {E.val:＝T.val}T→T1*digit {T.val:＝T1.val*digit.lexval}T→digit {T.val:＝digit.lexval}

狀態(tài)ACTIONGOTOd+*#ET0S3

12

1S4

acc2r3

S5r3

33r5r5

r54S3

75S6

6

r4r4

r47r2S5r2第二十九頁，共一百零八頁，編輯于2023年，星期三步驟狀態(tài)棧語義棧符號棧剩余輸入串ActionGOTO00-#2＋3*5＃S3103--#2＋3*5＃r52202-2#T＋3*5＃r31301-2#E＋3*5＃S44014-2-#E+3*5＃S350143-2--#E+3*5＃r5760147-2-3#E+T*5＃S5701475-2-3-#E+T*5＃S68014756-2-3-5#E+T*5＃r4790147-2-15#E+T#r211001-17#E#acc分析并計算2＋3*5的過程如下:第三十頁，共一百零八頁，編輯于2023年，星期三語義子程序一個語義子程序描述了一個產(chǎn)生式對應(yīng)的翻譯工作。這些工作有：改變編譯程序某些變量的值、查填各種符號表、發(fā)現(xiàn)并報告源程序錯誤、產(chǎn)生中間代碼。在描述語義動作時需要為每個文法符號賦以各種不同的語義值：類型、地址、代碼值等。如果一個產(chǎn)生式中一個符號多次出現(xiàn)，就用上角標(biāo)來區(qū)分，如：E=E(1)+E(2)第三十一頁，共一百零八頁，編輯于2023年，星期三

假定我們現(xiàn)在要分析的語法成分是簡單算術(shù)表達式，所完成的語義的處理不是將它翻譯成中間代碼或目標(biāo)代碼，而是計算表達式的值。采用的描述系統(tǒng)是上節(jié)的例1。假如語法分析方法是自下而上的。在用某一產(chǎn)生式進行歸約的同時就執(zhí)行相應(yīng)的語義動作，在分析出一個句子時，這個句子的“值”也就同時產(chǎn)生了，例如輸入串是3*5+4。第三十二頁，共一百零八頁，編輯于2023年，星期三LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹第三十三頁，共一百零八頁，編輯于2023年，星期三

法制導(dǎo)翻譯的具體實現(xiàn)途徑不困難。假定有一個LR語法分析器，現(xiàn)在把它的分析棧擴充，使得每個文法符號都跟有語義值同時把LR分析器的能力擴大，使它不僅執(zhí)行語法分析任務(wù)，且能在用某個產(chǎn)生式進行歸約的同時調(diào)用相應(yīng)的語義子程序，完成在屬性文法中描述的語義動作。每步工作后的語義值保存在擴充的分析棧里“語義值”欄中。采用LR分析，其中使用d代替digit。分析和計值2+3*5的過程。第三十四頁，共一百零八頁，編輯于2023年，星期三

接受15）##E-1701r114）##E+T—2—(15)169r313）##E+T*F—2—3—501697(10)r612）##E+T*5—2—3——01697511）5##E+T*—2—3—0169710）*5##E+T—2—30169r49）*5##E+F—2—30163r68）*5##E+3—2——01657）3*5##E+—2—0166）+3*5##E—201r25）+3*5##T—202r44）+3*5##F—203r63）+3*5##2——052）2+3*5##—01）留余輸入串符號棧語義棧狀態(tài)棧歸約動作步驟2+3*5的分析和計值過程第三十五頁，共一百零八頁，編輯于2023年，星期三所謂“中間代碼”是一種結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)，這種記號系統(tǒng)可以設(shè)計為多種多樣的形式，重要的設(shè)計原則為兩點：一是容易生成；二是容易將它翻譯成目標(biāo)代碼。編譯程序所使用的中間代碼有多種形式。常見的有逆波蘭記號、三元式、四元式和樹形表示。中間代碼形式§5.3常見中間語言概述第三十六頁，共一百零八頁，編輯于2023年，星期三

逆波蘭記號是最簡單的一種中間代碼表示形式，早在編譯程序出現(xiàn)之前，它就用于表示算術(shù)表達式，是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的。這種表示法將運算對象寫在前面，把運算符號寫在后面，比如把a+b寫成ab+，把a*b寫成ab*，用這種表示法表示的表達式也稱做后綴式。

逆波蘭記號第三十七頁，共一百零八頁，編輯于2023年，星期三

程序設(shè)計語言中的逆波蘭表示：

a+b

ab+

a+b*c

abc*+（a+b）*c

ab+c*

a:=b*c+b*d

abc*bd*+:=第三十八頁，共一百零八頁，編輯于2023年，星期三

后綴表示法表示表達式，其最大的優(yōu)點是最易于計算機處理表達式。利用一個棧，自左至右掃描算術(shù)表達式（后綴表示）。每碰到運算對象，就把它推進棧；碰到運算符，若該運算符是二目的，則對棧頂部的兩個運算對象實施運算，并將運算結(jié)果代替這兩個運算對象而進棧。若是一目運算符，則對棧頂元素執(zhí)行該運算，并以運算結(jié)果代替該元素進棧。最后的結(jié)果留在棧頂。第三十九頁，共一百零八頁，編輯于2023年，星期三

B@CD*+（它的中綴表示為-B+C*D，使用@表示一目減）的計值過程為：

1、B進棧；

2、對棧頂元素施行一目減運算，并將結(jié)果代替棧頂，即-B置于棧頂；

3、C進棧；

4、D進棧；第四十頁，共一百零八頁，編輯于2023年，星期三

5、棧頂兩元素相乘，兩元素退棧，相乘結(jié)果置棧頂；

由于后綴式表示上的簡潔和計值的方便，特別適用于解釋執(zhí)行的程序設(shè)計語言的中間表示，也方便具有堆棧體系的計算機的目標(biāo)代碼生成。

6、棧頂兩元素相加，兩元素退棧，相加結(jié)果進棧，現(xiàn)在棧頂存放的是整個表達式的值。第四十一頁，共一百零八頁，編輯于2023年，星期三

把表達式及各種語句表示成一組三元式。每個三元式三個組成部分是：算符op，第一運算對象ARG1，和第二運算對象ARG2。

三元式表示第四十二頁，共一百零八頁，編輯于2023年，星期三a:=b*c+b*d的三元式表示為：

（1）（*，b，c）（2）（*，b，c）（3）（+，（1），（2））（4）（:=，（3），a）第四十三頁，共一百零八頁，編輯于2023年，星期三：=a

+**

b

c

b

d

樹形表示是三元式表示翻版。上述三元式可表示成下面的樹表示：第四十四頁，共一百零八頁，編輯于2023年，星期三*

T1

T2e1*e2+

T1T2e1+e2——T1-e1

表達式的樹形表示很容易實現(xiàn)：簡單變量或常數(shù)的樹就是該變量或常數(shù)自身，如果表達式e1和e2的樹分別為T1和T2，那么e1+e2，e1*e2，-e1的樹分別為：第四十五頁，共一百零八頁，編輯于2023年，星期三例：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））第四十六頁，共一百零八頁，編輯于2023年，星期三

間接三元式：間接三元式序列間接碼表（1）（-

C

D）（1）（2）（*B（1））（2）（3）（+

A（2））（3）（4）（^（1）N）（1）（5）（/

E（4））（4）（6）（+（3）（5）)（5）（6）

A+B*（C-D）+E/（C-D）^N第四十七頁，共一百零八頁，編輯于2023年，星期三

四元式是一種比較普遍采用的中間代碼形式。四元式的四個組成成分是：算符op，第一和第二運算對象ARG1和ARG2及運算結(jié)果RESULT。運算對象和運算結(jié)果有時指用戶自己定義的變量，有時指編譯程序引進的臨時變量。四元式第四十八頁，共一百零八頁，編輯于2023年，星期三

a:=b*c+b*d的四元式表示如下：

（1）（*，b，c，t1）（2）（*，b，d，t2）（3）（*，t1，t2，t3）（4）（:=，t3，＿，a）第四十九頁，共一百零八頁，編輯于2023年，星期三

A+B*（C-D）+E/（C-D）^N

四元式：（1）（-

C

D

T1）（2）（*B

T1

T2）（3）（+

A

T2

T3）（4）（-

C

D

T4）（5）（^

T4

N

T5）（6）（/

E

T5

T6）（7）（+

T3

T6

T7）

逆波蘭：ABCD-*+ECD–N/+第五十頁，共一百零八頁，編輯于2023年，星期三

四元式和三元式的主要不同在于，四元式對中間結(jié)果的引用必須通過給定的名字，而三元式是通過產(chǎn)生中間結(jié)果的三元式編號。也就是說，四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的。第五十一頁，共一百零八頁，編輯于2023年，星期三

四元式表示很類似于三地址指令，有時把這類中間表示稱為“三地址代碼”因為這種表示可看作一種虛擬三地址機的通用匯編碼，即這種虛擬機的每條“指令”包含操作符和三個地址，兩個是為運算對象的，一個是為結(jié)果的。這種表示對于代碼優(yōu)化和目標(biāo)代碼生成都較有利。第五十二頁，共一百零八頁，編輯于2023年，星期三

為了更直觀，把四元式的形式寫成簡單賦值形式。比如把上述四元式序列寫成：

（1）t1:=b*c（2）t2:=b*d（3）t3:=t1+t2（4）a:=t3把（jump，—，—，L）寫成gotoL把（jrop，B，C，L）寫成ifBropCgotoL。為了敘述的方便，兩種形式我們將同時使用。第五十三頁，共一百零八頁，編輯于2023年，星期三語法制導(dǎo)生成后綴式利用算符優(yōu)先進行語法分析設(shè)置一個一維數(shù)組POST來寄存后綴式，初值為1，然后再為產(chǎn)生式配置語義子程序：(1)EE(1)OPE(2) {POST[k]:=OP；k:=k+1}(2)E(E(1)) {}(3)Ei {POST[k]:=ENTRY(i)；k:=k+1}假設(shè)已經(jīng)有了算符優(yōu)先表，則利用算符優(yōu)先分析法分析，在對素短語進行歸約時，執(zhí)行上述的語義子程序，可得到后綴式。第五十四頁，共一百零八頁，編輯于2023年，星期三語法制導(dǎo)生成后綴式利用優(yōu)先函數(shù)進行語法指導(dǎo)翻譯設(shè)置一個一維數(shù)組POST存放后綴式，并t初：=1;POST[t]:=0;下推棧初始指針K:=1;S[k]=#翻譯算法如下：(1)從左至右掃描源程序串，每次讀一字符給a；(2)若g(a)>f(s[k])則k:=k+1,s[k]:=a，轉(zhuǎn)(1);(3)若g(a)<f(s[k])則s[k]上彈并送至POST[t],t:=t+1;k:=k-1，轉(zhuǎn)(2)；(4)若g(a)=f(s[k])且不等于1，則上彈s[k];k:=k-1，轉(zhuǎn)(1)(5)若g(a)=f(s[k])=1，結(jié)束。第五十五頁，共一百零八頁，編輯于2023年，星期三后綴式的計算后綴式的計算過程：自左至右掃描后綴式，每碰到運算量就把它推進棧，每碰到k目算符就把它作用于棧頂?shù)膋項，并將運算結(jié)果來代替這k項。后綴式產(chǎn)生中間代碼：自左至右掃描后綴式，每碰到運算量就把它推進棧，每碰到k目算符就把它作用于棧頂?shù)膋項，并生成相應(yīng)的中間代碼，并以結(jié)果的臨時變量序號代替該棧頂?shù)膋項。第五十六頁，共一百零八頁，編輯于2023年，星期三后綴式的推廣(1)賦值語句A:=E，后綴式為：AE:=(2)轉(zhuǎn)向語句GOTOL的后綴式為：L’jmp(3)條件語句ifx>ythenm:=xelsem:=y1234567891011121314xy>11jezmx:=14jmy:=…第五十七頁，共一百零八頁，編輯于2023年，星期三三元式表達式以及各種語句都可以表示成三元式序列，由算符OP，第一運算量ARG1，第二運算量ARG2組成，形勢如下：(op,ARG1,ARG2)例：A+B*C可表示成：(1)(*,B,C)(2)(+,A,(1))第五十八頁，共一百零八頁，編輯于2023年，星期三樹+AB*+CAB+-*CBAA+B(A+B)*C-A+B*C主要用于表達式和賦值語句第五十九頁，共一百零八頁，編輯于2023年，星期三§5.4簡單算術(shù)表達式和賦值語句的翻譯賦值語句文法：Ai:=E EE+E|E*E|-E|(E)|i為了實現(xiàn)翻譯，需要一些語義變量和過程：NEWTEMP：函數(shù)，返回一個臨時變量序號；ENTRY(i)：函數(shù)，查找變量i的入口地址；GEN(OP,ARG1,ARG2,RESULT)：語義過程，產(chǎn)生一個四元式，并填入四元式表；E.PLACE：與給終結(jié)符E相聯(lián)系的語義變量，可能式某變量的入口地址，或者為臨時變量序號。第六十頁，共一百零八頁，編輯于2023年，星期三類型轉(zhuǎn)換在一個表達式中，可能出現(xiàn)各種不同類型的變量或常量，編譯程序必須做到拒絕接受某種混合運算或者產(chǎn)生有關(guān)類型轉(zhuǎn)換的指令。在混合運算情況下，每個非終結(jié)符的語義值必須添加類型信息。我們用E.MODE表示非終結(jié)符E的類型信息，E.MODE的值為r(實型)或int(整型)第六十一頁，共一百零八頁，編輯于2023年，星期三類型轉(zhuǎn)換如：產(chǎn)生式EE(1)opE(2)的語義動作中關(guān)于E.MODE的規(guī)則可定義為：{IFE(1).MODE=intandE(2).MODE=intTHENE.MODE=intELSEE.MODE=r}需添加一各類型轉(zhuǎn)換的四元式：(itr,A1,--,T)意味著把整型量A1轉(zhuǎn)換成實型，結(jié)果存放在T中。此外，對于運算符應(yīng)指出相應(yīng)的類型。第六十二頁，共一百零八頁，編輯于2023年，星期三類型轉(zhuǎn)換如：X:=Y+I*J，X,Y為實型，I,J為整型，則相應(yīng)的四元式序列應(yīng)為：(*i,I,J,T1)(itr,T1,--,T2)(+r,Y,T2,T3)(:=,T3,--,X)第六十三頁，共一百零八頁，編輯于2023年，星期三簡單賦值語句的四元式翻譯

首先對id表示的單詞定義一屬性，用做語義變量，用Lookup（）表示審查是否出現(xiàn)在符號表中，如在，則返回一指向該登錄項的指針，否則返回nil。語義過程emit表示輸出四元式到輸出文件上。語義過程newtemp表示生成一臨時變量，每調(diào)用一次，生成一新的臨時變量。語義變量E.place，表示存放E值的變量名在符號表的登錄項或一整數(shù)碼產(chǎn)生式和語義描述：第六十四頁，共一百零八頁，編輯于2023年，星期三

（1）S→id:=E｛p:=lookup（）；

ifp≠nilthen emit（p′:=′E.place）

elseerror｝

（2）E→E1+E2｛E.place:=newtemp；

emit（E.place′:

=′E1.place′+′E2.place）｝

（3）E→E1*E2｛E.place:=newtemp；

Emit（E.place′:

=′E1.place′*′E2.place第六十五頁，共一百零八頁，編輯于2023年，星期三

（4）E→—E1｛E.place:=newtemp；

Emit（E.place′:=′

′uminus′E1.place）｝

（5）E（E1）｛E.place:=E1.place｝

（6）Eid｛P:=lookup（）ifPnilthen

E.place:=Pelseerror｝第六十六頁，共一百零八頁，編輯于2023年，星期三§5.5布爾表達式的翻譯在程序設(shè)計語言中，布爾表達式的兩個作用：做控制語句中的條件表達式；用于邏輯符值語句中布爾表達式演算。布爾表達式由布爾運算符作用于布爾變量(或常量)或關(guān)系表達式形成。布爾運算符有:∧(與)、∨(或)、┐(非)關(guān)系表達式為：E(1)ropE(2)，其中rop為關(guān)系運算符，E(1)

和E(2)為算術(shù)表達式。第六十七頁，共一百零八頁，編輯于2023年，星期三布爾表達式的翻譯布爾表達式文法簡化如下：EE∧E|E∨E|┐E|(E)|i|EaropEb

布爾表達式在邏輯演算中的翻譯布爾表達式演算預(yù)算數(shù)表達式演算非常相似。在翻譯為中間代碼時，為每個產(chǎn)生式配上相應(yīng)語義子程序。如：A∨B∧C=D第六十八頁，共一百零八頁，編輯于2023年，星期三控制語句中布爾式的翻譯根據(jù)布爾表達式的特點，可以用if-then-else來解釋布爾表達式，如：

A∨B==>ifAthentrueelseB;A∧B==>ifAthenBelsefalse;┐A==>ifAthenfalseelsetrue;出現(xiàn)在條件語句IfEthenS1elseS2中的布爾表達式E作用僅在于控制對S1和S2選擇。第六十九頁，共一百零八頁，編輯于2023年，星期三控制語句中布爾式的翻譯IfEthenS1elseS2轉(zhuǎn)移條件E可以翻譯成三種形式的四元式序列：(jnz,A1,_,p)(jθ,A1,A2,p)(j,_,_,p)E的代碼序列S1的代碼序列S2的代碼序列條件語句的代碼結(jié)構(gòu)第七十頁，共一百零八頁，編輯于2023年，星期三例：ifA∨B<DthenS1elseS2可翻譯為如下的四元式序列：(1)(jnz,A,_,5)(2)(j,_,_,3)(3)(j<,B,D,5)(4)(j,_,_,p+1)(5)(關(guān)于S1的四元式序列)(p)(j,_,_,q)(p+1)(關(guān)于S2的四元式序列)(q)(j≥,B,D,p+1)第七十一頁，共一百零八頁，編輯于2023年，星期三一個布爾式的真假出口往往不能在產(chǎn)生四元式的同時就確定。解決方法是暫時保存該四元式的地址作為E的語義值，等表達式的四元式產(chǎn)生完了之后在來回填這個轉(zhuǎn)移目標(biāo)。為了實現(xiàn)上述過程，需要改寫文法如下：

EEAE|E0E|┐E|(E)|i|EaropEaEAE∧E0E∨第七十二頁，共一百零八頁，編輯于2023年，星期三控制語句中布爾式的翻譯為了實現(xiàn)，對于每個非終結(jié)符，需要賦予E.TC和E.FC兩項語義值，分別記錄表達式E所對應(yīng)的四元式需回填“真”“假”出口的四元式的地址所構(gòu)成的鏈。例：假定E的四元式中需回填“真”出口的有p,q,r三個四元式，可構(gòu)成一條“真”鏈(TC)，E.TC的值是鏈?zhǔn)?r)：(p)(x,x,x,0)……(q)(x,x,x,p)……(r)(x,x,x,q)第七十三頁，共一百零八頁，編輯于2023年，星期三為了處理E.TC和E.FC兩項語義值，需要下面的語義變量和過程：NXQ指示器：指向下一個將要形成但尚未形成的四元式的地址(編號)。初值為1，值型一次GEN后自動累加1；MERG(p1,p2)函數(shù)過程：把以p1和p2為鏈?zhǔn)椎膬蓷l鏈合并為一，返回合并后的鏈?zhǔn)祝籅ACKPATCH(p,t)過程：回填過程，把p所鏈接的每個四元式的第四區(qū)段都填為t。第七十四頁，共一百零八頁，編輯于2023年，星期三控制語句中布爾式的翻譯例：A∨B<C∧D=E翻譯后的四元式為：(1)(jnz,A,_,0)(2)(j,_,_,(3))(3)(j<,B,C,(5))(4)(j,_,_,0)(5)(j=,D,E,1)(6)(j,_,_,4)TC頭FC頭第七十五頁，共一百零八頁，編輯于2023年，星期三

程序設(shè)計語言中的布爾表達式有兩個作用。一是計算邏輯值，二是用做改變控制流語句中的條件表達式，如if-then，if-then-else，或是while-do語句中那樣。布爾表達式是由布爾算符（and，or和not）施于布爾變量或關(guān)系表達式而成。即布爾表達式的形式為E1ropE2，其中E1和E2都是算術(shù)表達式，rop是關(guān)系符，如〈=<，=，〉=，≠等等。布爾表達式的翻譯第七十六頁，共一百零八頁，編輯于2023年，星期三

計算布爾表達式的值有兩種辦法，第一種辦法，如同計算算術(shù)表達式一樣，步步計算出各部分的真假值，最后計算出整個表達式的值。例如，用數(shù)1表示true，用0表示false。那么布爾表達式1or（not0and0）or0的計算過程是：布達表達式的翻譯方法

1or（not0and0）or0

=1or（1and0）or0

=1or0or0

=1or0

=1第七十七頁，共一百零八頁，編輯于2023年，星期三

另一種計算方法是采取某種優(yōu)化措施，只計算部分表達式，例如要計算AorB，若計算出A的值為1，那么B的值就無需再計算了，因為不管B的值為何結(jié)果，AorB的值都為1。

上述兩種方法對于不包含布爾函數(shù)調(diào)用的表達式是沒有什么差別的。但是，假若一個布爾式中會有布爾函數(shù)調(diào)用，并且這種函數(shù)調(diào)用引起副作用（如有對全局量的賦值）時，這兩種方法未必等價。采用哪種方法取決于程序設(shè)計語言的語義。第七十八頁，共一百零八頁，編輯于2023年，星期三

若按第一種辦法計算布爾表達式。布爾表達式aorbandnotc翻譯成四元式序列為：（1）t1:=notc（2）t1:=bandt1（3）t1:=aort2

對于像a<b這樣的關(guān)系表達式，可看成等價的條件語句ifa<bthen1else0，它翻譯成的四元式序列為：（1）ifa<bgoto（4）（2）t:=0（3）goto（5）（4）t:=1（5）…第七十九頁，共一百零八頁，編輯于2023年，星期三

下面給出了按第一種辦法計算布爾表達式的值，將布爾表達式翻譯成四元式的描述，其中nextstat給出的輸出序列中下一四元式序號。emit過程每被調(diào)用一次，nextstat增加1。第八十頁，共一百零八頁，編輯于2023年，星期三

E→E1orE2｛E.place:=newtemp；

emit（E.place′:=′E1.place′

or′E2.place）｝

E→E1andE2｛E.place:=newtemp

emit（E.place′:=′E1.place′

and′E2.place）｝

E→notE1

｛E.place:=newtemp：；

emit（E.place′:=′

not′E1.place）｝第八十一頁，共一百零八頁，編輯于2023年，星期三

E→（E1）｛E.place:=E1.place｝

E→id1relopid2｛E.place:=newtemp；

emit（′if′id1.place

relop.opid2.place′goto′nextstat+3）；

emit（E.place′:=′′0′）

emit（′goto′nextstat+2）

emit(E.place′:=′′1′）｝

E→ture｛E.place：=newtemp；

emit(E.place′:=′′1′）｝

E→false（｛E.place：=newtemp；

emit（E.place′:=′′0′）｝第八十二頁，共一百零八頁，編輯于2023年，星期三

E→id1relopid2｛E.place:=newtemp；

emit（′if′id1.place

relop.opid2.place′

goto′nextstat+3）；

emit（E.place′:=′′0′）

emit（′goto′nextstat+2）

emit（E.place′:=′′1′）｝

E→ture｛E.place：=newtemp；

emit（E.place′:=′′1′）｝

E→false（｛E.place：=newtemp；

emit（E.place′:=′′0′）｝第八十三頁，共一百零八頁，編輯于2023年，星期三

E.false控制語句S?ifEthenS1

elseS2E的代碼E.trueE.true:S1的代碼gotooutE.false:S2的代碼out:第八十四頁，共一百零八頁，編輯于2023年，星期三

作為條件轉(zhuǎn)移的E，僅把E翻譯成代碼是一串條件轉(zhuǎn)和無條件轉(zhuǎn)四元式。翻譯的基本思路是，對于E為aropb的形式生成代碼為：ifaropbgotoE.true和gotoE.false。第八十五頁，共一百零八頁，編輯于2023年，星期三

對于E為E1orE2的形式，若E1是真，則可知道E為真即E1的真出口和E的真出口一樣。如果E1是假，那么必須計算E2，E1的假出口就是E2代碼的第一個四元式標(biāo)號，這時E2的真出口和假出口分別與E的真出口和假出口一樣。

類似的考慮適于E1andE2的情形。E1的翻譯理解容易，只需調(diào)換E1的真假出口即可得到E的真假出口。第八十六頁，共一百零八頁，編輯于2023年，星期三

1、把條件轉(zhuǎn)移布爾表達式

E翻譯成僅含條件真轉(zhuǎn)和無條件轉(zhuǎn)的四元式：

E:

a

rop

b

?

If

a

rop

b

goto

E.true

goto

E.false第八十七頁，共一百零八頁，編輯于2023年，星期三如：a<borc<dande<f

可翻譯成如下四元式：（1）ifa<b

goto

E.true（2）goto（3）（3）ifc<dgoto（5）（4）gotoE.false（5）ife<fgotoE.true（6）gotoE.false（翻譯不是最優(yōu)）第八十八頁，共一百零八頁，編輯于2023年，星期三（1）if

a<b

goto（7）（2）goto（3）（3）if

c<d

goto（5）（4）goto（p+1）（5）if

e<f

goto（7）（6）goto（p+1）（7）（S1的四元式……）（p）goto（q）（p+1）（s2四元式……）（q）（E.true）（1）和（5）拉鏈（真）（E.false）（4）和（6）拉鏈（假）語句ifa<borc<dande<fthes1else

s2的四元式第八十九頁，共一百零八頁，編輯于2023年，星期三

上述四元式（1）和（5），（4）和（6）的轉(zhuǎn)移地址并不能產(chǎn)生這些四元式的同時得知。例如（1）和（5）的轉(zhuǎn)移地址是在整個布爾表達式的四元式產(chǎn)生完畢之后才得知。因此要回填這個地址。為了記錄需回填地址的四元式，常采用一種“拉鏈”的辦法。把需回填E.true的四元式拉成一鏈，把需回填E.false的四元式拉成一鏈，分別稱做“真”鏈和“假”鏈。第九十頁，共一百零八頁，編輯于2023年，星期三2．拉鏈返填……（10）

gotoL（10）goto0…………鏈尾

（10）（20）gotoL（20）goto10

……

……（30）

gotoL（30）goto20

……

……鏈頭（30）（40）L:……

（40）L:?第九十一頁，共一百零八頁，編輯于2023年，星期三§5.6控制語句的翻譯標(biāo)號和轉(zhuǎn)移語句(1)先定義后使用(2)先使用后定義NAMEINFORMATIONCAT….定義否地址……L標(biāo)號已S.QUAD……L’標(biāo)號未r(p)(x,x,x,0)

……(q)(x,x,x,p)

……(r)(x,x,x,q)第九十二頁，共一百零八頁，編輯于2023年，星期三IF語句的翻譯描述IF語句的文法如下：SifEthenS(1)

或SifEThenS(1)elseS(2)翻譯過程大致如下：(1)翻譯E，獲得一組四元式；(2)掃描E的真出口，回填；假出口尚不知；(3)翻譯S(1)

，可以使IF語句也可以使其他；(4)遇到else，S(1)

結(jié)束，生成一條無條件轉(zhuǎn)移四元式；但出口不明，需解決嵌套的情況；(5)翻譯S(2)

，結(jié)束。第九十三頁，共一百零八頁，編輯于2023年，星期三IF語句的翻譯為了完成翻譯，需改寫產(chǎn)生式如下：產(chǎn)生式SifEthenS(1)elseS(2)

改寫為：CifEthenTCS(1)elseSTS(2)產(chǎn)生式SifEthenS(1)

改寫為：CifEthenSCS(1)第九十四頁，共一百零八頁，編輯于2023年，星期三IF語句的翻譯例：試翻譯IfathenifbthenA:=2elseA:=3elseifcthenA:=4elseA:=5第九十五頁，共一百零八頁，編輯于2023年，星期三WHILE語句的翻譯文法：SWhileEdoS(1)翻譯過程大致如下：(1)翻譯E，待填E.TC，E.FC鏈；(2)掃描do后，回填E.TC；(3)翻譯S(1)語句稱代碼段，無條件轉(zhuǎn)移到E代碼段的第一條四元式，若S(1)有語句鏈，也應(yīng)轉(zhuǎn)到E代碼段的第一條四元式。第九十六頁，共一百零八頁，編輯于2023年，星期三REPEAT語句的翻譯文法：SrepeatS(1)untilE翻譯過程大致如下：(1)翻譯S(1)

，留下待回填語句鏈S(1).CHIAN(2)掃描until后，回填S(1).CHIAN(3)翻譯E代碼段，留待填的E.TC和E.FC；E.FC應(yīng)無條件轉(zhuǎn)移到REPEAT語句的第一個四元式。第九十七頁，共一百零八頁，編輯于2023年，星期三§5.7數(shù)