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

《編譯原理 第七章 語法制導(dǎo)翻譯和中間代碼生成》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第七章語法制導(dǎo)翻譯和中間代碼生成編譯程序的任務(wù)是把源程序翻譯成目標(biāo)程序，這個目標(biāo)程序必須和源程序的語義等同，也就是說，盡管它們的語法結(jié)構(gòu)完全不同，但它們所表達的結(jié)果應(yīng)完全相同。通常，在詞法分析程序和語法分析程序?qū)υ闯绦虻恼Z法結(jié)構(gòu)進行分析之后，要么由語法分析程序直接調(diào)用相應(yīng)的語義子程序進行語義處理，要么首先生成語法樹或該結(jié)構(gòu)的某種表示，再進行語義處理。編譯中的語義處理是指兩個功能：第一，審查每個語法結(jié)構(gòu)的靜態(tài)語義，即驗證語法結(jié)構(gòu)合法的程序是否真正有意義。第二，如果靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯，即，

2、要么生成程序的一種中間表示形式（中間代碼），要么生成實際的目標(biāo)代碼。為什么有的編譯程序直接生成目標(biāo)代碼，有的編譯程序采用中間代碼，所謂中間代碼，也稱中間語言，是復(fù)雜性介于源程序語言和機器語言的一種表示形式。一般，快速編譯程序直接生成目標(biāo)代碼，沒有將中間代碼翻譯成目標(biāo)代碼的額外開銷。但是為了使編譯程序結(jié)構(gòu)在邏輯上更為簡單明確，常采用中間代碼，這樣可以將與機器相關(guān)的某些實現(xiàn)細節(jié)置于代碼生成階段仔細處理，并且可以在中間代碼一級進行優(yōu)化工作使得代碼優(yōu)化比較容易實現(xiàn)。本章重點：屬性文法、語法制導(dǎo)翻譯方法的基本思想、幾

3、種典型的中間代碼形式、一些語法成分的翻譯工作。第一節(jié)屬性文法現(xiàn)在很多編譯程序采用語法制導(dǎo)翻譯方法。這仍不是一種形式系統(tǒng)，但它是比較接近形式化的。這種方法使用屬性文法為工具來說明程序設(shè)計語言的語義。一個屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語義規(guī)則附在文法的每個產(chǎn)生式上，在語法分析過程中，完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動作，從而實現(xiàn)語義處理。首先簡單介紹屬性文法。屬性，常用以描述事物或人的特征、性質(zhì)、品質(zhì)等等。比如，談到一個物體，可以用“顏色”描述它，談起某人，可以使用“有幽默感”來

4、形容他。對編譯程序使用的語法樹的結(jié)點，可以用“類型”、“值”或“存儲位置”來描述它。形式上講，一個屬性文法是一個三元組，A=（G，V，F(xiàn)），一個上下文無關(guān)文法G；一個屬性的有窮集V和關(guān)于屬性的斷言或謂詞的有窮集F。每個屬性與文法的某個非終結(jié)符或終結(jié)符相聯(lián)。每個斷言與文法的某產(chǎn)生式相聯(lián)。如果對G中的某一輸入串而言（句子），A中的所有斷言對該輸入串的語法樹結(jié)點的屬性全為真，則該串也是A語言中的句子。編譯程序的靜態(tài)語義審查工作就是驗證關(guān)于所編譯的程序的斷言是否全部為真。比如，有文法G為：E→T1+T2

5、T1orT

6、2T→num

7、true

8、false因為T在同一個產(chǎn)生式里出現(xiàn)了兩次，使用上角標(biāo)將它們區(qū)分開。對輸入串3+4的語法樹如圖7-1-1（a）{T1.t=int}ET+T43(a){T2.t=int}E{T1.t=T2.t}T+T43(b)圖7-1-1靜態(tài)語義審查屬性文法記號中常使用N.t的形式表示與非終結(jié)符N相聯(lián)的屬性t。比如可把完成對上面表達式的類型檢查的屬性文法寫成圖7-1-2的形式。與每個非終結(jié)符T相聯(lián)的有屬性t，t要么是int，要么是bool。與非終結(jié)符E的產(chǎn)生式相聯(lián)的斷言指明：兩個T的屬性必須相同。圖7

9、-1-1(b)是圖7-1-1(a)語法樹結(jié)點帶有語義信息的表示。E→T1+T2{T1.t=intANDT2.t=int}T→true{T.t：=bool}E→T1orT2{T1.t=boolANDT2.t=bool}T→false{T.t：=bool}T→num{T.t：=int}圖7-1-2類型檢查的屬性文法屬性文法最早出自克努特筆下。他把屬性分成兩類：繼承屬性和綜合屬性，我們不對屬性文法進行理論上的研究而僅僅將它做為工具描述語義分析。在編譯的許多實際應(yīng)用中，屬性和斷言以多種形式出現(xiàn)，也就是說，與每個文法

10、符號相聯(lián)的可以是各種屬性、斷言、以及語義規(guī)則，或者某種程序設(shè)計語言的程序段等等。下面再給出一些例子。例1：簡單算術(shù)表達式求值的語義描述。產(chǎn)生式語義規(guī)則（0）L→Eprint(E.val)（1）E→E1+TE.val：=E1.val+T.val（2）E→TE.val：=T.val（3）T→T1*FT.val：=T1.val×F.val（4）T→FT.val：=F.val（5）F→(E)F.val：=E.val（6）F→digitF.val：=digit.lexval在該描述中，每個非終結(jié)符都有一個屬性：一個整

11、數(shù)值的稱作val的屬性。按照語義規(guī)則對每個產(chǎn)生式來說，它的左部E，T，F(xiàn)的屬性值的計算來自它右部的非終結(jié)符，這種屬性稱作綜合屬性。單詞digit僅有綜合屬性，它的值是由詞法分析程序提供的。和產(chǎn)生式L→E相聯(lián)的語義規(guī)則是一個過程，打印由E產(chǎn)生的表達式的值。我們可以理解為L的屬性是空的或是虛的。第二節(jié)語法制導(dǎo)翻譯概論在語法分析過程中，隨著分析的步步進展，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序（或語義規(guī)則描述的語義動作）進行