第八章語法制導(dǎo)翻譯和中間代碼生成

1、第八章 語法制導(dǎo)翻譯和中間代碼生成課前索引【課前思考】回顧第一章介紹的編譯過程，理解語義分析在編譯過程中的位置和作用什么是中間表示（中間代碼），為什么要中間表示？"語法制導(dǎo)翻譯”是什么含義？高級(jí)語言語句的結(jié)構(gòu)和低級(jí)語言結(jié)構(gòu)的不同?！緦W(xué)習(xí)目標(biāo)】明確語義分析在編譯過程所處的階段和作用。掌握屬性文法的基本概念。使用屬性文法和語法制導(dǎo)翻譯方法描述具體的語義分析和產(chǎn)生中間代碼。【學(xué)習(xí)指南】緊接在詞法分析和語法分析之后，編譯程序要做的工作就是進(jìn)行靜態(tài)語義檢查和翻譯。 靜態(tài)語義檢查通常包括：類型檢查，控制流檢查，一致性檢查，相關(guān)名字檢查及名字的作用 域分析等等。雖然源程序可以直接翻譯為目標(biāo)語言代碼

2、，但是許多編譯程序都采用了獨(dú)立于機(jī)器的，復(fù)雜性介于源語言和機(jī)器語言之間的中間語言。其好處便于進(jìn)行與目標(biāo)機(jī)無關(guān)的 代碼優(yōu)化，也使得編譯的前后端接口清晰，編譯程序結(jié)構(gòu)在邏輯上更簡明【難重點(diǎn)】翻譯時(shí)源語句到目標(biāo)語句結(jié)構(gòu)上的變換。語法制導(dǎo)翻譯實(shí)現(xiàn)的方法。 Yacc和語法制導(dǎo)翻譯.【知識(shí)結(jié)構(gòu)】語法制號(hào)翻譯和中問代碼生成A語叟處理工員一一靜悲語女檢查_源稈序劉中閭代碼的翻譯"隔性立法和語法制導(dǎo)翻譯一_雇性立法定女 丄”靜霑語義描述舉例中間代碼的走式佰語句的（四無式）翻譯一布爾表達(dá)式的翻譯一控制語句的初譯 簡單說明語甸的嘲譯Yag和語袪制導(dǎo)翻譯編譯程序的任務(wù)是把源程序翻譯成目標(biāo)程序，這個(gè)目標(biāo)程序必

3、須和源程序的語義等 同，也就是說 ,盡管它們的語法結(jié)構(gòu)完全不同， 但它們所表達(dá)的結(jié)果應(yīng)完全相同 .通常， 在詞 法分析程序和語法分析程序?qū)υ闯绦虻恼Z法結(jié)構(gòu)進(jìn)行分析之后,要么由語法分析程序直接調(diào)用相應(yīng)的語義子程序進(jìn)行語義處理，要么首先生成語法樹或該結(jié)構(gòu)的某種表示，再進(jìn)行 語義處理 .編譯中的語義處理是指兩個(gè)功能：第一，審查每個(gè)語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法 結(jié)構(gòu)合法的程序是否真正有意義。有時(shí)把這個(gè)工作稱為靜態(tài)語義分析或靜態(tài)審查。第二， 如果靜態(tài)語義正確， 語義處理則要執(zhí)行真正的翻譯， 即 ,或者將源程序翻譯成程序的一種中 間表示形式（中間代碼） ，或者將源程序翻譯成目標(biāo)代碼。本章引入屬性文法和語

4、法制導(dǎo)翻譯方法的基本思想，介紹幾種典型的中間代碼形式， 最后討論一些語法成分的翻譯工作。靜態(tài)語義分析 通常包括： 類型檢查。驗(yàn)證程序中執(zhí)行的每個(gè)操作是否遵守語言的類型系統(tǒng)的過程。, 編譯程序必須報(bào)告不符合類型系統(tǒng)的信息 . 控制流檢查 .控制流語句必須使控制轉(zhuǎn)移到合法的地方.例如，在 C 語言中 break 語句使控制跳離包括該語句的最小while 、for 或 switch 語句。如果不存在包括它的這樣的語句，則就報(bào)錯(cuò)。 一致性檢查。在很多場(chǎng)合要求對(duì)象只能被定義一次。例如 Pascal 語言規(guī)定同一標(biāo) 識(shí)符在一個(gè)分程序中只能被說明一次,同一 case 語句的標(biāo)號(hào)不能相同， 枚舉類型的元素不能

5、重復(fù)出現(xiàn)等等。 相關(guān)名字檢查 .有時(shí)， 同一名字必須出現(xiàn)兩次或多次 . 例如 ,Ada 語言程序中， 循環(huán)或 程序塊可以有一個(gè)名字，出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，編譯程序必須檢查這兩個(gè)地方用 的名字是相同的。 名字的作用域分析所謂 中間代碼 ,也稱中間語言 ,是復(fù)雜性介于源程序語言和機(jī)器語言的一種表示形式。 為什么有的編譯程序直接生成目標(biāo)代碼,有的編譯程序采用中間代碼 .一般 ,快速編譯程序直接生成目標(biāo)代碼 ,沒有將中間代碼翻譯成目標(biāo)代碼的額外開銷。但是為了使編譯程序結(jié)構(gòu)在邏輯上更為簡單明確 ,常采用中間代碼， 這樣可以將與機(jī)器相關(guān)的某些實(shí)現(xiàn)細(xì)節(jié)置于代碼生 成階段仔細(xì)處理， 并且可以在中間代碼一

6、級(jí)進(jìn)行優(yōu)化工作使得代碼優(yōu)化比較容易實(shí)現(xiàn)。 文 檔為個(gè)人收集整理，來源于網(wǎng)絡(luò)8。 1 屬性文法語義形式化是個(gè)專門的研究課題，目前有各種各樣的方法和記號(hào)不斷推出，例如操作 語義學(xué)、公理語義學(xué)和指稱語義學(xué)。語義形式化 （語義建模）有幾種模型 文法模型 - 屬性文法 命令式或操作式模型 - - - 操作語義學(xué) 應(yīng)用式模型 - 指稱語義學(xué) 公理式模型 公理語義學(xué) 規(guī)格說明模型 - 代數(shù)數(shù)據(jù)類型 屬性文法將在我們的講義中介紹 .操作語義描述一段程序的含義是通過執(zhí)行該段程序 所改變的計(jì)算機(jī)（無論是真實(shí)計(jì)算機(jī)還是虛擬計(jì)算機(jī)）狀態(tài)來反映。計(jì)算機(jī)里所有的寄存 器的值和存儲(chǔ)單元的值作為計(jì)算機(jī)的狀態(tài)。For （exp

7、r1 ； expr2；expr3） 的操作語義表示： exprl;Loop： if expr2=0 goto outxpr3;goto loopout:.O 公理語義概念是隨著程序正確性的證明而發(fā)展的。當(dāng)正確性證明能構(gòu)造時(shí)表明程序執(zhí)行它的規(guī)格說明所描述的計(jì)算.在一個(gè)證明中， 每一個(gè)語句之前之后都有一個(gè)邏輯表達(dá)式對(duì)程序的變量進(jìn)行約束，以此說明這個(gè)語句的含義一般的記號(hào)是P S Q o指稱語義的基本概念是給每一段程序?qū)嶓w定義一個(gè)數(shù)學(xué)意義上的對(duì)象，和一個(gè)從實(shí)體 實(shí)例向數(shù)學(xué)意義對(duì)象的映射的函數(shù)。規(guī)格說明模型通過描述實(shí)現(xiàn)一個(gè)程序的各種函數(shù)間的關(guān)系來說明語義。如表明一個(gè)實(shí)現(xiàn)服從任何兩個(gè)函數(shù)間的這種關(guān)系，則可

8、以聲明這個(gè)實(shí)現(xiàn)是此規(guī)格說明的正確實(shí)現(xiàn)。本文為互聯(lián)網(wǎng)收集，請(qǐng)勿用作商業(yè)用途不論哪種方法 ,其本身的符號(hào)系統(tǒng)比較繁雜 ,其描述文本不易讀，目前編譯程序尚不便借助這些形式系統(tǒng)自動(dòng)完成語義處理任務(wù)現(xiàn)在很多編譯程序采用語法制導(dǎo)翻譯方法。這仍不是一種形式系統(tǒng)，但它是比較接近形式化的。這種方法使用屬性文法為工具來說明程序設(shè) 計(jì)語言的語義。一個(gè)屬性文法包含一個(gè)上下文無關(guān)文法和一系列語義規(guī)則，這些語義規(guī)則 附在文法的每個(gè)產(chǎn)生式上，在語法分析過程中，完成這些語義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn) 語義處理 .首先簡單介紹屬性文法。所謂屬性，其涉及的概念比較廣泛，常用以描述事物或人的特征、性質(zhì)，品質(zhì)等等。比如，談到一個(gè)物體，

9、可以用 ”顏色”描述它，談起某人，可以使用 ”有幽默感”來形容他。對(duì) 編譯程序使用的語法樹的結(jié)點(diǎn)，可以用 ”類型"、 ”值"或”存儲(chǔ)位置 "來描述它 .屬性文法（也稱屬性翻譯文法 ）是 Knuth 在 1968 年首先提出的 .它是在上下文無關(guān)文法的基 礎(chǔ)上，為每個(gè)文法符號(hào) （終結(jié)符或非終結(jié)符）配備若干相關(guān)的"值”（稱為屬性） .這些屬性代表與文法符號(hào)相關(guān)信息 ，例如它的類型、值、代碼序列、符號(hào)表內(nèi)容等等.屬性與變量一樣 ，可以進(jìn)行計(jì)算和傳遞屬性加工的過程即是語義處理的過程。對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為語義規(guī)則。形式上講，一個(gè)屬性

10、文法是一個(gè)三元組,A =（ G,V , F），一個(gè)上下文無關(guān)文法 G; 個(gè)屬性的有窮集 V和關(guān)于屬性的斷言或謂詞的有窮集Fo每個(gè)斷言與文法的某產(chǎn)生式相聯(lián) .如果對(duì) G 中的某一輸入串而言 （句子）， A 中的所有斷言對(duì) 該輸入串的語法樹結(jié)點(diǎn)的屬性全為真，則該串也是A語言中的句子。編譯程序的靜態(tài)語義審查工作就是驗(yàn)證關(guān)于所編譯的程序的斷言是否全部為真 .比如，有文法 G 為：ET 1 + T2|T1 or T2Ttnum|true | false（因?yàn)門在同一個(gè)產(chǎn)生式里出現(xiàn)了兩次，使用上角標(biāo)將它們區(qū)分開。） 對(duì)輸入串 3+4 的語法樹如圖 81（A）圖 8 1 靜態(tài)語義審查(a)(b)屬性文法記號(hào)

11、中常使用 N .T的形式表示與非終結(jié)符N相聯(lián)的屬性t。比如可把對(duì)上面表達(dá)式的類型檢查的屬性文法寫成圖& 2的形式。與每個(gè)非終結(jié)符T相聯(lián)的有屬性t，t要么是int,要么是bool。與非終結(jié)符E的產(chǎn)生式相聯(lián)的斷言指明：兩個(gè)T的屬性必須相同。圖8. 1的(b)是圖8.1(a)語法樹結(jié)點(diǎn)帶有語義信息的表示圖& 2類型檢查的屬性文法Et 1+T2 T 1.t= int ANDT2.t= intET 1orT2 T 1.t= bool ATD T 2° t= boolTt num T。t ：= int Tt true T.t ： = bool Tt falseT。 t ：= bo

12、ol屬性文法中的屬性分成兩類：繼承屬性和綜合屬性，簡單地說，綜合屬性用”自上而上傳遞信息，而繼承屬性用于"自上而下"傳遞信息。在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式Aa都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為b := f (c 1,C2 ,C k)這里，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,C我們不對(duì)屬性文法進(jìn)行理論上的研究而僅僅將它做為工具描述

13、語義分析。在編譯的許 多實(shí)際應(yīng)用中，屬性和斷言以多種形式出現(xiàn)，也就是說，與每個(gè)文法符號(hào)相聯(lián)的可以是各種屬 性、斷言、以及語義規(guī)則，或者某種程序設(shè)計(jì)語言的程序段等等。一般說來，對(duì)出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提 供一個(gè)計(jì)算規(guī)則。屬性計(jì)算規(guī)則中只能使用相應(yīng)產(chǎn)生式中的文法符號(hào)的屬性，這有助于在 產(chǎn)生式范圍內(nèi)"封裝”屬性的依賴性。然而，出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式 右邊的綜合屬性不由所給的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由屬性計(jì)算器的參數(shù)提供。語義規(guī)則所描述的工作可以包括屬性計(jì)算、靜態(tài)語義檢查、符號(hào)表操作、代碼生成等

14、等.語義規(guī)則可能產(chǎn)生副作用(如產(chǎn)生代碼)，也可能不是變?cè)膰?yán)格函數(shù)(如某個(gè)規(guī)則給出可用的下一個(gè)數(shù)據(jù)單元的地址)。這樣的語義規(guī)則通常寫成過程調(diào)用或過程段。下面再給出一些例子。f8-1-1。swf在該描述中，每個(gè)非終結(jié)符都有一個(gè)屬性：一個(gè)整數(shù)值的稱作val的屬性。按照語義規(guī)則對(duì)每個(gè)產(chǎn)生式來說，它的左部E, T，F(xiàn)的屬性值的計(jì)算來自它右部的非終結(jié)符，這種屬性稱作綜合屬性單詞digit僅有綜合屬性，它的值是由詞法分析程序提供的。和產(chǎn)生式LE相聯(lián)的語義規(guī)則是一個(gè)過程，打印由E產(chǎn)生的表達(dá)式的值。我們可以理解為L的屬性是空的或是虛的。例8.2中的文法定義了一種說明語句，該說明語句的形式是由關(guān)鍵字int或re

15、al開頭，后面是一個(gè)標(biāo)識(shí)符表，每個(gè)標(biāo)識(shí)符由逗號(hào)隔開。非終結(jié)符T有一個(gè)綜合屬性type,它的值由關(guān)鍵字決定（int或real）。與產(chǎn)生式TL相聯(lián)的語義規(guī)則 L.in : = T.type將L.in的屬 性值置為該說明語句指定的類型。屬性L.in將被沿著語法樹傳遞到下邊的結(jié)點(diǎn)使用，與L產(chǎn)生式相聯(lián)的規(guī)則里使用了它。描述說明語句中各種變量的類型信息的語義規(guī)則，這個(gè)例子里，繼承屬性在說明 中為各個(gè)標(biāo)識(shí)符提供類型信息。產(chǎn)生式語義規(guī)則(1) D TL L。 in ：= T.type(2)int To Type ：= integer(3)real T.Type ：= real(4) LL 1, id L1.i

16、n ： = L o inaddtype (id。 entry, L.in ) (5) Lt idaddtype(id.entry , L。 in) 圖8.3是句子intid1, id2的語法樹，使用表示屬性的傳遞情況在語法樹中，一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性確定。與L產(chǎn)生式相聯(lián)的語義規(guī)則中有一個(gè)過程調(diào)用addtype,過程addtype的功能是把每個(gè)標(biāo)識(shí)符的類型信息登錄在符號(hào)表的相關(guān)項(xiàng)中。圖8。3屬性信息傳遞情況屬性文法看作是允許為每個(gè)終結(jié)符和非終結(jié)符配備一些屬性的文法。它既能描述程序 設(shè)計(jì)語言的語法，又為語義處理提供了方便屬性文法里的屬性有不同的類型，可以象變量一

17、樣地被賦值。賦值規(guī)則附加于語法規(guī)則之上。賦值與語法同時(shí)進(jìn)行，賦值過程就是語義處理過程。在推導(dǎo)語法樹的時(shí)候，諸屬性的值被計(jì)算并通過賦值規(guī)則層層傳遞。有的從語法 規(guī)則左邊向右邊傳，有的從右邊向左邊傳。語法推導(dǎo)樹最后完成時(shí)，就得到開始符號(hào)的屬性 值也就是整個(gè)程序的語義個(gè)人收集整理勿做商業(yè)用途& 2語法制導(dǎo)翻譯編譯程序的整個(gè)任務(wù)就是把源程序翻譯為目標(biāo)程序。實(shí)際上每個(gè)編譯階段都可以看成 是完成一定的翻譯任務(wù)：詞法分析階段把字符流翻譯為單詞流，語法分析階段把單詞流翻 譯為語法樹，目標(biāo)代碼生成階段把語法樹翻譯為匯編語言等等。在語法分析過程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語義子程序(或語

18、義規(guī)則描述的語義動(dòng)作)進(jìn)行翻譯的辦法稱作語法制導(dǎo)翻譯假如我們要把中綴算術(shù)表達(dá)式翻譯為后綴波蘭表示形式(后綴波蘭表示形式參見8。3.1),給出如下語義描述：iT + E 1 E 。 code=T.code | | E1。 code|+ iT E 。 code=T。 code Tf F * T 1 T.code=F。 code | |T1.code |* Tt F T 。 code =F。code Ff (E) F。code = E.code Ft a F.code = a 其中使用E。code, T.code和F.code分別表示相應(yīng)的后綴式，” |表示后綴式的連接。如果對(duì)于輸入串a(chǎn)+a*a采用

19、最左分析，其形成的推導(dǎo)過程為：E T+EF+E a+Ea+T a+T* 廠-a+F*L-a+a*La+a*a(a ,) a是輸入句子和句型，B是翻譯的輸出形式，則有：(E, E.code)(T+E , T。 code | E。code | |+) T (F+E, F。code | |E。code|+)一(a+E, a| | E.code|+) r (a+T, a | T。 code | |+)(a+F*, a | |F.code|T.code|+)* *一 (a+a , a|a| | T。code | | +)(a+a*F, a| | a | F.code | | *+)*=> (a+a

20、 a, a| | a | |a | | +)去掉a | |a | |a | | +中的連結(jié)符，得到中綴表 達(dá)式a+a*a的后綴式 aaa+個(gè)人收集整理，勿做商業(yè)用途假定我們現(xiàn)在要分析的語法成分是簡單算術(shù)表達(dá)式，所完成的語義處理不是將它翻譯成中間代碼或是目標(biāo)代碼，而是計(jì)算表達(dá)式的值。采用的描述系統(tǒng)是上節(jié)的例8.1。假如語法分析方法是自下而上的.在用某一產(chǎn)生式進(jìn)行歸約的同時(shí)就執(zhí)行相應(yīng)的語義動(dòng)作，在分析出一個(gè)句子時(shí)，這個(gè)句子的”值"也就同時(shí)產(chǎn)生了，例如輸入串是2+3* 5,其語法樹如圖8。4(a),在第一步歸約用到了產(chǎn)生式(6)，執(zhí)行的語義動(dòng)作是置F. val的值為單詞digit值，我們把

21、語法樹中每個(gè)結(jié)點(diǎn)的語義值括在該結(jié)點(diǎn)處。那么第一步歸約并完成語義動(dòng)作后的情形 在圖& 4 (b)中指出。繼續(xù)進(jìn)行分析，第七次歸約后的情形在圖8。4(c)中指出。歸約至E時(shí)，它的值17也計(jì)算出來了。圖8。4語法制導(dǎo)方法計(jì)算表達(dá)式L1EL1EL1EZNE1 TE1卜TE1 4-TTZN(2)(15)密 T】* FT T】* F1 1 111 1F F 51 123FF 5(e)這里再給出一種翻譯模式，也是把中綴形式的算術(shù)表達(dá)式映射到后綴波蘭表示：i T + E E=TE+ i T E=T F * T T=FT * F T =F i (E) F = E i a F = a 句子a+a*a的一個(gè)

22、推導(dǎo)過程：E一 T+EF+E一 a+E .： a+T a+F*T ' a+a*T ' a+a F 1 a+a*a伴隨著句子a+a*a的這個(gè)推導(dǎo)過程，按照上述翻譯模式所進(jìn)行的一步步翻譯：* *E一 TE+ FE+ aE+ aT+ aFT + aaT + - aaF + aaa +語法制導(dǎo)翻譯的具體實(shí)現(xiàn)途徑不困難。假定有一個(gè)LR語法分析器，現(xiàn)在把它的分析棧擴(kuò)充，使得每個(gè)文法符號(hào)都跟有語義值，即把棧的結(jié)構(gòu)看成圖8.5所示那樣。圖8.5擴(kuò)充的分析棧Smy,ValySm 1x,Valx。S0一#狀態(tài)棧語義值符號(hào)棧圖8。 6 LR分析表狀態(tài)ACTION (動(dòng)作)GOTO (轉(zhuǎn)換)d+*()

23、#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108r6s119r1s7r1r110r3r3r3r311r5r5r5r5同時(shí)把LR分析器的能力擴(kuò)大，使它不僅執(zhí)行語法分析任務(wù)，且能在用某個(gè)產(chǎn)生式進(jìn)行 歸約的同時(shí)調(diào)用相應(yīng)的語義子程序，完成在例8.1的屬性文法中描述的語義動(dòng)作每步工作后的語義值保存在擴(kuò)充的分析棧里"語義值”欄中。采用的LR分析表見圖& 6,其中使用d代替digit。分析和計(jì)值2+3衣5的過程列在圖8.7中。圖& 7 2+3*5的分析和計(jì)值過程步驟歸約動(dòng)作狀態(tài)棧語義棧（值棧）符

24、號(hào)棧留余輸入串10一#2+3*5#205-#2+3*5#3r603-2#F+3*5#4r402一 2# T+3 * 5 #5r201-2#E+3 * 5#60162# E+3* 5 #701652-# E+3* 5 #8r601632 3# E+F*5 #9r40169-2 3# E+T* 5#10016972 3#E+T 5 #110169752-3-# E+T -5#12r601697(10)-2-2 5#E+T -F#13r30169-2- (15)# E+T#14t101(17)#E#15接受按照上述實(shí)現(xiàn)辦法，若把語義子程序改為產(chǎn)生某種中間代碼的動(dòng)作，那么則可在語法 分析的制導(dǎo)下，隨著

25、分析的進(jìn)展逐步生成中間代碼8.3中間代碼的形式編譯程序所使用的中間代碼有多種形式。常見的有逆波蘭記號(hào)、三元式、四元式和樹 形表示。下面分別將它們做一介紹8.3。1逆波蘭記號(hào)逆波蘭記號(hào)是最簡單的一種中間代碼表示形式，早在編譯程序出現(xiàn)之前，它就用于表 示算術(shù)表達(dá)式，是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的。這種表示法將運(yùn)算對(duì)象寫在前面，把運(yùn)算符號(hào)寫在后面，比如把a(bǔ)+b寫成ab+,把a(bǔ)*b寫成ab*，用這種表示法表示的表達(dá)式也稱做后綴式。圖& 8給出了程序設(shè)計(jì)語言中的簡單表達(dá)式和賦值語句相應(yīng)的逆波蘭表示形式：圖8.8逆波蘭表示程序設(shè)計(jì)語言中的表示逆波蘭表示a+bab+a+b * cabc* +(a+b

26、) *cab+c*a； =b * c+b * dabc* bd*+:=后綴表示法表示表達(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é)果留在棧頂。例如BCD*+ （它的中綴表示為一 B+C * D，使用表示一目減）的計(jì)值過程為：1。B進(jìn)棧；2. 對(duì)棧頂元素施行一目減運(yùn)算，并將結(jié)果代替棧頂，即- B置于棧頂；3. C進(jìn)棧；

27、4。D進(jìn)棧；5. 棧頂兩元素相乘，兩元素退棧，相乘結(jié)果置棧頂；6。棧頂兩元素相加，兩元素退棧，相加結(jié)果進(jìn)棧，現(xiàn)在棧頂存放的是整個(gè)表達(dá)式的值。由于后綴式表示上的簡潔和計(jì)值的方便，特別適用于解釋執(zhí)行的程序設(shè)計(jì)語言的中間表示，也方便具有堆棧體系的計(jì)算機(jī)的目標(biāo)代碼生成。逆波蘭表示很容易擴(kuò)充到表達(dá)式以外的范圍。在圖& 8中已見到了賦值語句的后綴表示的例子。只要遵守運(yùn)算對(duì)象后直接緊跟它們的運(yùn)算符的規(guī)則即可.比如把轉(zhuǎn)語句GOTO L寫為"L jump ”運(yùn)算對(duì)象L為語句標(biāo)號(hào)，運(yùn)算符jump表示轉(zhuǎn)到某個(gè)標(biāo)號(hào)。 再比如條件語句 if E then S1 else S2可表示為：ES1S2Y，把

28、if then else看成三目運(yùn)算符，用Y來表示。又如 數(shù)組元素 A 下標(biāo)表達(dá)式 1>, 下標(biāo)表達(dá)式 n可表示為 <下標(biāo)表達(dá)式1下標(biāo)表 達(dá)式2><下標(biāo)表達(dá)式nA subs，運(yùn)算符Subs表示求數(shù)組的下標(biāo)。當(dāng)然，這些擴(kuò)充的后綴表示的計(jì)值遠(yuǎn)比后綴表達(dá)式的計(jì)值復(fù)雜得多，要注意對(duì)新添加的運(yùn)算符的含義正確處理。以圖& 8中的賦值語句為例，當(dāng)計(jì)算到：=時(shí)，執(zhí)行的是將表達(dá)式B*C+B * D的值送到變量a,所以,而在執(zhí)行完賦值后，棧中并不產(chǎn)生結(jié)果值， 這與算術(shù)的 二目運(yùn)算符是不一樣的，另外，因?yàn)樾枰氖莂的地址，而不是a的值，這也必須注意到。本文為互聯(lián)網(wǎng)收集，請(qǐng)勿用作商業(yè)用

29、途832三元式和樹形表示另一類中間代碼形式是三元式。把表達(dá)式及各種語句表示成一組三元式.每個(gè)三元式由三個(gè)部分組成，分別是：算符op,第一運(yùn)算對(duì)象 ARG1和第二運(yùn)算對(duì)象 ARG2。運(yùn)算對(duì)象可能是源程序中的變量，也可能是某個(gè)三元式的結(jié)果，用三元式的編號(hào)表示。例如a： =b衣c+b衣d的表示為：宀 b, c)(2) ( * , b, d)(3) (+ (1 ),(2)(4) (: =(2), a)與后綴式不同，三元式中含有對(duì)中間計(jì)算結(jié)果的顯式引用，比如三元式(1)表示的是b* c的結(jié)果。三元式(3)中的(1 )和(2)分別表示第一個(gè)三元式和第二個(gè)三元式的結(jié)果.對(duì)于一目算符 op,只需選用一個(gè)運(yùn)算對(duì)

30、象，不妨規(guī)定只用ARG1.至于多目算符，可用若干個(gè)相繼的三元式表示。樹形表示是三元式表示的翻版.上述三元式可表示成下面的樹表示：L cb d表達(dá)式的樹形表示很容易實(shí)現(xiàn)：簡單變量或常數(shù)的樹就是該變量或常數(shù)自身，如果表達(dá)式&和e2的樹分別為Ti和T2,那么ei+e2, ei*e2, ei的樹分別為：+/ * -/ /G1 + ££匸九Ci + Cr"1二目運(yùn)算對(duì)應(yīng)二叉子樹，多目運(yùn)算對(duì)應(yīng)多叉子樹，不過，為了便于安排存儲(chǔ)空間，一棵多叉子樹可以通過引進(jìn)新結(jié)而表示成一棵二叉子樹。& 3.3四元式四元式是一種比較普遍采用的中間代碼形式。四元式的四個(gè)組成成分是：算

31、符op,第一和第二運(yùn)算對(duì)象 ARG1和ARG 及運(yùn)算結(jié)果 RESULT。運(yùn)算對(duì)象和運(yùn)算結(jié)果有時(shí)指用戶自己定義的變量，有時(shí)指編譯程序引進(jìn)的臨時(shí)變量。例如a： =b*c+b * d的四兀式表示如下：(1) ( * ,b,c, t1)(*,b,d,t2)(3) (+ ,t1, t2, t3)(：=,t3, , a)四元式和三元式的主要不同在于，四元式對(duì)中間結(jié)果的引用必須通過給定的名字，而 三元式是通過產(chǎn)生中間結(jié)果的三元式編號(hào)。也就是說，四元式之間的聯(lián)系是通過臨時(shí)變量 實(shí)現(xiàn)的。也許讀者已經(jīng)發(fā)現(xiàn)，四元式表示很類似于三地址指令，確實(shí)，有時(shí)把這類中間表示稱 為”三地址代碼”因?yàn)檫@種表示可看作一種虛擬三地址機(jī)

32、的通用匯編碼，即這種虛擬機(jī)的每條"指令"包含操作符和三個(gè)地址，兩個(gè)是為運(yùn)算對(duì)象的，一個(gè)是為結(jié)果的。這種表示對(duì)于 代碼優(yōu)化和目標(biāo)代碼生成都較有利.有時(shí) ,為了更直觀， 也把四元式的形式寫成簡單賦值形式或更易理解的形式。比如把上述四元式序列寫成：1)tl :=b*c2)t2 :=b * d3)t3 :=t1+t24)a :=t3把( jump， L )寫成 goto L把(jrop , B, C, L)寫成 if B rop C goto L本書中 ,為了敘述的方便，兩種形式將同時(shí)使用。如何用四元式表示各種語句， 以及翻譯各種語句的語義描述， 將在后面各節(jié)陸續(xù)討論 為了復(fù)習(xí)與鞏

33、固一下前面所學(xué)習(xí)的幾種中間代碼的形式,下面舉一個(gè)例子，分別用幾種中間代碼的形式來表示例：A + B *( C D ) + E / ( C D ) ANA四元式：1)(-CD T1 )2)(*BT1T2)3)(+AT2T3)4)(CDT4)5)(AT4NT5)6)(/ET5T6)7)(+T3T6T7)三元式：( 1)(CD)( 2)(*B(1)(3)(+A2)( 4)(CD)( 5)(A (4)N(6)( / E (5 ) ( 7)( +( 3)( 6)間接三元式 ：間接三元式序列( 1)( C D)( 2)( * B ( 1) )(3) ( + A (2)(4) ( 1) N)( 5)( /

34、E ( 4) ( 6)( +( 3)( 5)間接碼表( 1)(2)( 3)(1)( 4)(5)( 6)間接碼表表面了執(zhí)行間接三元式的順序8.4 簡單賦值語句的(四元式)翻譯在 8。3。3的四元式中，使用變量名字本身表示運(yùn)算對(duì)象ARG1 和 ARG2 ，用 ti 表示RESULT 。在實(shí)際實(shí)現(xiàn)中，它們或者是一個(gè)指針,指向符號(hào)表的某一登錄項(xiàng) ,或者是一個(gè)臨時(shí)變量的整數(shù)碼 .在對(duì)賦值語句翻譯為四元式的描述中，我們將表明怎樣查找這樣的符號(hào)表登錄項(xiàng)。首先對(duì)id表示的單詞定義一屬性 id . name,用做語義變量，用 Lookup (id . name) 表示審查id . name是否出現(xiàn)在符號(hào)表中，如

35、在，則返回一指向該登錄項(xiàng)的指針，否則返回nil.語義過程emit表示輸出四元式到輸出文件上。語義過程newtemp表示生成一個(gè)臨時(shí)變量，每調(diào)用一次，生成一新的臨時(shí)變量。語義變量E. place，表示存放E值的變量名在符號(hào)表的登錄項(xiàng)或一整數(shù)碼(若此變量是一個(gè)臨時(shí)變量 )圖 8。 9 列出了翻譯賦值語句到四元 式的語義描述。這里的語義工作包括對(duì)變量進(jìn)行 "先定義后使用 ”的檢查。圖 8。 9 賦值語句的四元式翻譯(1) S tid : =E p： =lookup ( id . name);if p 豐 nilthenEmit (p'： ='E place) else er

36、ror(2) E tE1+E2 Eplace： =newtemp；Emit (Eplace ：' =' 1E.place ' 2+'pElace) (3) EtE 1E2 EplaceE： =newtemp；Emit (E. place '： =' E. place ' *2Eplace)(4) E tE1 E . placeE ： =newtemp；Emit(E. place：' ='' uminu1s.' pElace )(5) E t( E1)E. place： =E1. place(6) Et id

37、 p:=look up( id. name)；if p 工 nil then E . placeE： =p else error實(shí)際上 ,在一個(gè)表達(dá)式中可能會(huì)出現(xiàn)各種不同類型的變量或常數(shù),而不是像圖8.9 中的id 假定為都是同一類型。也就是說,編譯程序還應(yīng)執(zhí)行這樣的語義動(dòng)作：對(duì)表達(dá)式中的運(yùn) 算對(duì)象應(yīng)進(jìn)行類型檢查 ,如不能接受不同類型的運(yùn)算對(duì)象的混合運(yùn)算,則應(yīng)指出錯(cuò)誤； 如能接受混合運(yùn)算, 則應(yīng)進(jìn)行類型轉(zhuǎn)換的語義處理。 假如, 圖 8.9 中的表達(dá)式可以有混合運(yùn)算 ,id 可以是實(shí)型量也可以是整型量,并且約定 ,當(dāng)兩個(gè)不同類型的量進(jìn)行運(yùn)算時(shí),必須首先將整型量轉(zhuǎn)換為實(shí)型量。為進(jìn)行類型轉(zhuǎn)換的語義處

38、理，增加語義變量，用E. type表示E的類型信息，E. type的值或?yàn)閕nt或?yàn)閞eal,此外，為區(qū)別整型加(乘)和實(shí)型加(乘)，把+ (*) 分別寫作+i(*i)和+r嚴(yán)r)。用一目算符itr表示將整型運(yùn)算對(duì)象轉(zhuǎn)換成實(shí)型.這樣,圖 8.9中的第( 3)條產(chǎn)生式及其有關(guān)語義描述如圖8。 10。圖 8。 10 類型轉(zhuǎn)換的語義處理產(chǎn)生式語義動(dòng)作EtE 1E2 E . place： =newtemp；if E1. type = int AND E 2. type = int then begin emit( E.place, '： =', E1. place, ' i&#

39、39;, E2. place)；E. type： =intendelse if E1. type = real AND E 2. type= real then begin emit （E. place, '： =' 1E place,*", E2. place）;E. type : =realendelse if E1. type = int/* and E 2. type=real * / thenbegin t： =newtemp；emit（t， ,： =,， , it，r E,1. place）； emit（E. place，,： =,， t, ,r,，*E2

40、. place）；E. type： =realendelse /*E1 type = real and E2. type = int * / begin t： =newtemp；emit（t,：, =, ; , it2r.,pl,aEce）； emit（ E. place， ,： =, ,1E. place, *, r,， t）;E. type： =realend；圖8.9中的例子里，與非終結(jié)符E相聯(lián)的語義值有 E. place，還有E. type。語義 值的設(shè)計(jì)是與語義處理的描述相關(guān)的.大家回顧一下 PL/0 編譯程序中對(duì)賦值語句的語義處理,其中對(duì)賦值語句左部的標(biāo)識(shí)符，檢查它的種類（kind

41、 ）,若不是變量名，則指出錯(cuò)誤，若是變量名， 才生成賦值運(yùn)算的代碼。 對(duì)右部表達(dá)式中作為運(yùn)算對(duì)象的標(biāo)識(shí)符,檢查其是否變量名或常量名，是，生成相應(yīng)代碼，不是（即是過程名 ），則指出錯(cuò)誤 .這一點(diǎn)若用語義規(guī) 則描述的話，還應(yīng)增加一語義值，與非終結(jié)符相聯(lián),比如用 E. kind 表示。賦值語句中會(huì)含有復(fù)雜數(shù)據(jù)類型，如數(shù)組元素、記錄（結(jié)構(gòu)）的引用。這種情況的翻 譯工作要復(fù)雜些，我們將在后面給予專門討論。8。 5 布爾表達(dá)式的翻譯程序設(shè)計(jì)語言中的布爾表達(dá)式有兩個(gè)作用。 一是計(jì)算邏輯值， 更多的情況是二 ,用做改 變控制流語句中的條件表達(dá)式，如在if then， if-then-else ，或是 whil

42、e do 語句中那樣 .布爾表達(dá)式是由布爾算符and， or 和 not 施于布爾變量或關(guān)系表達(dá)式而成.即布爾表達(dá)式的形式為Ei rop E2,其中Ei和E2都是算術(shù)表達(dá)式，rop是關(guān)系符，如=v ,= ,=,舞等。 有的語言， 如 PL/1 ，允許更通用的表達(dá)式 ,其中，布爾算符，算術(shù)算符和關(guān)系算符可以施于 任何類型的表達(dá)式，并不區(qū)別布爾值和算術(shù)值，只不過在需要時(shí)執(zhí)行強(qiáng)制變換。為簡單起 見，我們只考慮如下文法生成的布爾表達(dá)式 .iE and E | E or E| not E|id rop id|true|false并且按通常習(xí)慣，約定布爾算符的優(yōu)先順序 (從高到低)為not、and、or,

43、并且and和or服從左結(jié)合。8。 5。 1 布爾表達(dá)式的翻譯方法 通常，計(jì)算布爾表達(dá)式的值有兩種辦法 ,第一種辦法，如同計(jì)算算術(shù)表達(dá)式一樣，步步 計(jì)算出各部分的真假值，最后計(jì)算出整個(gè)表達(dá)式的值。例如，用數(shù)值1表示true,用0表示false。那么布爾表達(dá)式 1 or (not 0 and 0) or 0的計(jì)算過程是：1 or(not 0 and 0)or 0=1 or(1 and 0) or 0=1 or 0 or 0=1 or 0=1另一種計(jì)算方法是采取某種優(yōu)化措施，只計(jì)算部分表達(dá)式，例如要計(jì)算A or B ，若計(jì)算出 A 的值為 1，那么 B 的值就無需再計(jì)算了，因?yàn)椴还?B 的值為何結(jié)果

44、， A or B 的值都 為 1 。 個(gè)人收集整理，勿做商業(yè)用途上述兩種方法對(duì)于不包含布爾函數(shù)調(diào)用的表達(dá)式是沒有什么差別的。但是，假若一個(gè) 布爾式中會(huì)有布爾函數(shù)調(diào)用，并且這種函數(shù)調(diào)用引起副作用(如有對(duì)全局量的賦值 )時(shí)，這兩種方法未必等價(jià)。采用哪種方法取決于程序設(shè)計(jì)語言的語義，有些語言規(guī)定，函數(shù)過程 調(diào)用應(yīng)不影響這個(gè)調(diào)用處環(huán)境的計(jì)值，或者說，函數(shù)過程的工作不許產(chǎn)生副作用，在這種 規(guī)定下 ,可以任選其中一種。若按第一種辦法計(jì)算布爾表達(dá)式。 布爾表達(dá)式 a or b and not c 翻譯成的四元式序列為：(1) ti : =not c(2) t2 : =b and t1(3) t3 : =a

45、or t2對(duì)于像av b這樣的關(guān)系表達(dá)式，可看成等價(jià)的條件語句if a v b then 1else 0,它翻譯成的四元式序列為：( 1) if av b goto ( 4)(2) t : =0( 3)goto (5 )( 4)t: =1(5) 其中用臨時(shí)變量t存放布爾表達(dá)式av b的值，(5)為后續(xù)的四元式序號(hào)。圖 8.11 給出了按第一種辦法計(jì)算布爾表達(dá)式的值， 將布爾表達(dá)式翻譯成四元式的描述 , 在該描述中使用了過程 newtemp和emit，其含義同前，過程 nextstat給出在輸出序列中下 一四元式序號(hào) ,emit 過程每被調(diào)用一次， nextstat 增加 1。 文檔為個(gè)人收集整

46、理，來源于網(wǎng)絡(luò) 圖 8。 11 用數(shù)值表示布爾值的翻譯方案E 1 or E2 E. place : =newtemp ;emit(E . place : =' E. place ' or2.Eplace)EE 1 and E2 E. place : =newtemp ;emit(E . place '： =' E. place ' and. place)i not E1 E. place : =newtemp :;emit (E. place : =' not1. Eplace)i (E1) E. place : =E1. placei id 1

47、 relop id 2 E. place : =newtemp;emit (' if 1'. i0lace relop id 2. place ' goto nextstat+3); emit (E. place '： ='' 0 ');emit( ' goto ' nextstat+2emit (E. place '： = ' ') 1zi true E. place : =newtemp ;emit (E. place '： =' ') 1i falseE . place

48、 : =newtemp; emit(E . place '： = ' ' ')控制語句中布爾表達(dá)式的翻譯現(xiàn)在討論出現(xiàn)在if then ； if then else和while do等語句中的布爾表達(dá)式E的翻譯。這三種語句的語法為：St if E then S 1|if E then S1 else S2 I while E do S 1這些語句的代碼結(jié)構(gòu)示意分別在圖& 12 (a) (b) (c)中，其中使用。和。兩個(gè)出口分別用于表示E為真和假時(shí)控制流向的轉(zhuǎn)移。分別叫真出口和假出口。圖8.12控制語句的代碼結(jié)構(gòu)biginE的代碼工彳的代碼口jiunp o

49、utjuirp beg in呼的代碼1ffllt:(c) awhile E do S'1代硯結(jié)構(gòu)(b) if E then 51else SE 代碼結(jié)構(gòu)在控制語句中，布爾表達(dá)式E作為控制流轉(zhuǎn)移的條件，僅把其翻譯成一串條件轉(zhuǎn)和無條件轉(zhuǎn)的四元式代碼。比如將布爾表達(dá)式E=a rop b翻譯成四元式代碼：if a rop b goto E . true 禾口goto E. false這里使用E. true和E. false分別表示布爾表達(dá)式E的”真"”假”出口轉(zhuǎn)移目標(biāo)。下面將多處使用它們。對(duì)于E為E1 or E2的形式，若E1是真，則可知道 E為真即E1的真出口和E的真出口 一樣。如

50、果E1是假，那么必須計(jì)算 E2, E1的假出口應(yīng)是E2代碼的第一個(gè)四元式標(biāo)號(hào)，這 時(shí)E2的真出口和假出口分別與E的真出口和假出口一樣。類似的考慮適于E為E1 and E2的情形.E為not E1的翻譯更容易，只需調(diào)換E1的真假出口即可得到 E的真假出口 .例如布爾表達(dá)式 a<b or c d and e> f翻譯為如下四元式序列：(1) if a v b goto E. true(2) goto (3)(3) if c v d goto (5)(4) goto E. false(5) is e> f goto E . true2)是不需要的。這種問題可留(6) goto E

51、. false這樣生成的四元式顯然不是最優(yōu)的，如四元式(待代碼優(yōu)化階段解決在例8。3中，我們使用 E. true和E. false分別表示整個(gè)表達(dá)式 av b or cv d ande>f的真、假出口，而 E. true和E. false的值并不能在產(chǎn)生四元式的同時(shí)就知道。為了 看清這一點(diǎn)，我們把該表達(dá)式放在條件語句中考慮，如語句if a v b or c v d and e> f then S1 else S 的四元式序列為(1) ifavbgoto (7)/*( 7)是整個(gè)布爾表達(dá)式的真出口*/(2) goto (3)(3) ifcv dgoto(5)(4) goto (p+1

52、) 1*( p+1)是整個(gè)布爾表達(dá)式的假出口*/(5) if e> f goto (7)(6) goto (p+1)(7) (關(guān)于S1的四元式)實(shí)際上，上述四元式(1)和(5), (4)和(6)的轉(zhuǎn)移地址并不能在產(chǎn)生這些四元式的同時(shí) 得知。例如(1)和(5)的轉(zhuǎn)移地址為(7),它是在整個(gè)布爾表達(dá)式的四元式序列生成之后 才回填的地址。為了記錄需回填地址的四元式，常采用一種"拉鏈”的辦法。把需回填E. true 的四元式拉成一鏈，把需回填E. false的四元式拉成一鏈，分別稱做"真"鏈和"假"鏈。用一個(gè)例子說明拉鏈?zhǔn)侨绾畏绞?，若有四元式序?/p>

53、：(10)gotoE.true(20)gotoE.true(30)gotoE.true則把需回填E. true的四兀式（10）,（20）和（30）鏈成(10) goto(0)(20)goto(10)(30)goto(20)把地址（30）稱作鏈?zhǔn)?0為鏈尾標(biāo)志，即地址（10）為鏈尾。如何描述回填，我們不再介紹，有興趣的同學(xué)可閱讀參考書。8。 6 控制語句的翻譯8.6.1 條件轉(zhuǎn)移考慮 if then,if then else 和 while do 語句，在圖 8。 12 中已給出了它們的代碼結(jié)構(gòu)。這 里我們使用下面文法 GS 定義這些語句 :GS(1) St if E then S(2) | i

54、f E then S else S(3) |while E do S(4) |beg in L end(5) |A( 6) LtL； S I S其中各非終結(jié)符號(hào)的意義是：s-語句L- 語句串A-賦值句E 布爾表達(dá)式回想在上一節(jié) ,討論控制語句中的布爾表達(dá)式的翻譯時(shí),使用 Etrue 和 Efalse 分別指出尚待回填”真、”假”出口的四元式串， 如對(duì)于條件語句if E then S1 else S2,在掃描到then 時(shí)才能知道E的”真”出口，而E的”假"出口只有處理了 S1之后，到達(dá)else時(shí)才明確即是說， 必須將E. false的值傳下去，以便到達(dá)相應(yīng)的else時(shí)才進(jìn)行回填。另外，E為真時(shí)，S1語句執(zhí)行完時(shí)意味著整個(gè)if then else語句也已執(zhí)行完畢，因此應(yīng)在S1之后