編譯原理語(yǔ)法制導(dǎo)翻譯和中間代碼生成.doc

《編譯原理語(yǔ)法制導(dǎo)翻譯和中間代碼生成.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

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

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

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

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

5、G為：E→T1+T2

6、T1orT2T→num

7、true

8、false因?yàn)門在同一個(gè)產(chǎn)生式里出現(xiàn)了兩次，使用上角標(biāo)將它們區(qū)分開(kāi)。對(duì)輸入串3+4的語(yǔ)法樹(shù)如圖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)語(yǔ)義審查屬性文法記號(hào)中常使用N.t的形式表示與非終結(jié)符N相聯(lián)的屬性t。比如可把完成對(duì)上面表達(dá)式的類型檢查的屬性文法寫(xiě)成圖7-1-2的形式。與每個(gè)非終結(jié)符T相聯(lián)的有屬性t，t要么是int，要么是bool。與非終結(jié)符E的產(chǎn)生式相

9、聯(lián)的斷言指明：兩個(gè)T的屬性必須相同。圖7-1-1(b)是圖7-1-1(a)語(yǔ)法樹(shù)結(jié)點(diǎn)帶有語(yǔ)義信息的表示。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類型檢查的屬性文法屬性文法最早出自克努特筆下。他把屬性分成兩類：繼承屬性和綜合屬性，我們不對(duì)屬性文法進(jìn)行理論上的研究而僅僅將它做為工具描述語(yǔ)義分析。在編譯的許多實(shí)際應(yīng)用中

10、，屬性和斷言以多種形式出現(xiàn)，也就是說(shuō)，與每個(gè)文法符號(hào)相聯(lián)的可以是各種屬性、斷言、以及語(yǔ)義規(guī)則，或者某種程序設(shè)計(jì)語(yǔ)言的程序段等等。下面再給出一些例子。例1：簡(jiǎn)單算術(shù)表達(dá)式求值的語(yǔ)義描述。產(chǎn)生式語(yǔ)義規(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.

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