屬性文法和語法制導(dǎo)翻譯

1、第六章 屬性文法和語法制導(dǎo)翻譯本章概述本章中，我們將首先介紹屬性文法的基本概念，然后介紹基于屬性文法的處理方法，討論如何在自上而下分析和自下而上分析中實現(xiàn)屬性的計算。主要學(xué)習(xí)內(nèi)容：語法制導(dǎo)翻譯的基本思想，屬性文法的基本概念，基于屬性文法的處理方法，在自上而下分析和自下而上分析中的屬性計算。學(xué)習(xí)目標：理解語法制導(dǎo)翻譯和屬性文法的基本思想和方法，掌握屬性的計算方法。學(xué)習(xí)重點和難點：屬性的計算的方法。6.1屬性文法屬性文法是Knuth在1968年首先提出的。它是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號（終結(jié)符或非終結(jié)符）配備若干相關(guān)的“值”（稱為屬性）。這些屬性代表與文法符號相關(guān)信息，例如它的類型、

2、值、代碼序列、符號表內(nèi)容等等。屬性與變量一樣，可以進行計算和傳遞。屬性加工的過程即是語義處理的過程。對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。屬性通常分為兩類：綜合屬性和繼承屬性。簡單地說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。在一個屬性文法中，對應(yīng)于每個產(chǎn)生式Aa都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為：b:=f(c1,c2,ck)這里，f是一個函數(shù)，而且或者(1). b是A的一個綜合屬性并且c1,c2,ck是產(chǎn)生式右邊文法符號的屬性；或者(2). b是產(chǎn)生式右邊某個文法符號的一個繼承屬性并且c1,c2,ck 是A或產(chǎn)生式右邊任何文法

3、符號的屬性。在兩種情況下，我們都說屬性b依賴于屬性c1,c2,ck。語義規(guī)則所描述的工作可以包括屬性計算、靜態(tài)語義檢查、符號表操作、代碼生成等等。語義規(guī)則可能產(chǎn)生副作用（如產(chǎn)生代碼），也可能不是變元的嚴格函數(shù)（如某個規(guī)則給出可用的下一個數(shù)據(jù)單元的地址）。這樣的語義規(guī)則通常寫成過程調(diào)用或過程段。綜合屬性在實際中被廣泛應(yīng)用。在語法樹中，一個結(jié)點的綜合屬性的值由其子結(jié)點的屬性值確定。因此，通常使用自底向上的方法在每一個結(jié)點處使用語義規(guī)則計算綜合屬性的值。僅僅使用綜合屬性的屬性文法稱S屬性文法。在語法樹中，一個結(jié)點的繼承屬性由此結(jié)點的父結(jié)點和/或兄弟結(jié)點的某些屬性確定。用繼承屬性來表示程序設(shè)計語言結(jié)構(gòu)

4、中的上下文依賴關(guān)系很方便。例如，我們可以利用一個繼承屬性來跟蹤一個標識符，看它是出現(xiàn)在賦值號的左邊還是右邊，以確定是需要這個標識符的地址還是值。盡管我們有可能僅用綜合屬性來改寫一個屬性文法，但是使用帶有繼承屬性的屬性文法有時更為自然。6.2基于屬性文法的的處理方法從概念上講，基于屬性文法的處理過程通常是這樣的：對單詞符號串進行語法分析，構(gòu)造語法分析樹，然后根據(jù)需要遍歷語法樹并在語法樹的各結(jié)點處按語義規(guī)則進行計算（如圖6.1所示）。這種由源程序的語法結(jié)構(gòu)所驅(qū)動的處理辦法稱為語法制導(dǎo)翻譯法。語義規(guī)則的計算可能產(chǎn)生代碼、在符號表中存放信息、給出錯誤信息或執(zhí)行任何其它動作。對輸入符號串的翻譯也就是根據(jù)

5、語義規(guī)則進行計算的結(jié)果。然而，一個具體的實現(xiàn)并不一定非要按圖5.1的輪廓不可。在某些情況下可用一遍掃描實現(xiàn)屬性文法的語義規(guī)則計算。也就是說在語法分析的同時完成語義規(guī)則的計算，無須明顯地構(gòu)造語法樹或構(gòu)造屬性之間的依賴圖。因為單遍實現(xiàn)對于編譯效率非常重要，所以這一章的許多部分都是討論這些特殊情況。有一個重要的子類稱為“L屬性文法”，對于該類屬性文法，不用顯式構(gòu)造語法樹就可以實現(xiàn)翻譯。也就是說，基于屬性文法的處理方法通常有兩類：1樹遍歷的屬性計算方法通過樹遍歷計算屬性值的方法有多種。這些方法都假設(shè)語法樹已經(jīng)建立起了，并且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語法樹，直至計

6、算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。2一遍掃描的處理方法與樹遍歷的屬性計算方法不同，一遍掃描的處理方法是在語法分析的同時計算屬性值，而不是語法分析構(gòu)造語法樹之后進行屬性的計算，而且無需構(gòu)造實際的語法樹。因為一遍掃描的處理方法與語法分析器的相互作用，它與下面兩個因素密切相關(guān)：(1). 所采用的語法分析方法。(2). 屬性的計算次序。如果按這種一遍掃描的編譯程序模型來理解語法制導(dǎo)翻譯方法的話，所謂語法制導(dǎo)翻譯法，直觀上說就是為文法中每個產(chǎn)生式配上一組語義規(guī)則，并且在語法分析的同時執(zhí)行這些語義規(guī)則。在自上而下語法分析中，若一個產(chǎn)生式匹

7、配輸入串成功，或者，在自下而上分析中，當一個產(chǎn)生式被用于進行歸約時，此產(chǎn)生式相應(yīng)的語義規(guī)則就被計算，完成有關(guān)的語義分析和代碼產(chǎn)生的工作。可見，在這種情況下，語法分析工作和語義規(guī)則的計算是穿插進行的。如果在一棵語法樹中一個結(jié)點的屬性b依賴于屬性c，那么這個結(jié)點處計算b的語義規(guī)則必須在確定c的語義規(guī)則之后使用。在一棵語法樹中的結(jié)點的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以由稱作依賴圖的一個有向圖來描述。一條求值規(guī)則只有在其各變元值均已求得的情況下才可以使用。但有時候可能會出現(xiàn)一個屬性對另一個屬性的循環(huán)依賴關(guān)系。例如，p、c1、c2都是屬性，若有如下求值規(guī)則p:=f1(c1)、c1:=f2(c2)、

8、c2:=f3(p)時，就無法對p求值。如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么稱該文法為良定義的。6.3 S-屬性文法的自下而上計算所謂S-屬性文法，指的是只含有綜合屬性的屬性文法。綜合屬性可以在分析輸入符號串的同時由自下而上的分析器來計算。分析器可以保存與棧中文法符號有關(guān)的綜合屬性值，每當進行歸約時，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號的屬性值來計算。S-屬性文法的翻譯器通?？山柚贚R分析器實現(xiàn)。在S-屬性文法的基礎(chǔ)上，LR分析器可以改造為一個翻譯器，在對輸入串進行語法分析的同時對屬性進行計算。在自下而上的分析方法中，我們使用一個棧來存放已經(jīng)分析過的子樹的信息。為了對S-屬性

9、文法進行計算，通常擴充分析器中的棧來存放這些綜合屬性值。如圖6.2所示。6.4 L-屬性文法和自頂向下翻譯一個屬性文法稱為L-屬性文法，如果對于每個產(chǎn)生式AX1X2Xn，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj(1jn)的一個繼承屬性且這個繼承屬性僅依賴于：(1) 產(chǎn)生式Xj的左邊符號X1，X2，Xj-1的屬性；(2) A的繼承屬性。S-屬性文法一定是L-屬性文法，因為（1）、（2）限制只用于繼承屬性。L-屬性文法允許我們通過一次遍歷就計算出所有屬性值。諸如LL（1）這種自上而下分析方法的分析過程，從概念上說可以看成是深度優(yōu)先建立語法樹的過程，因此，我們可以在自上而下語法分析的同時

10、實現(xiàn)L屬性文法的計算。屬性文法（有時也稱語法制導(dǎo)定義）可以看作是關(guān)于語言翻譯的高級規(guī)范說明，其中隱去實現(xiàn)細節(jié)，使用戶從明確說明翻譯順序的工作中解脫出來。另一種適合語法制導(dǎo)翻譯的描述形式，稱為翻譯模式（Translation schemes, 也稱為翻譯方案）。翻譯模式給出了使用語義規(guī)則進行計算的次序，這樣就可把某些實現(xiàn)細節(jié)表示出來。在翻譯模式中，和文法符號相關(guān)的屬性和語義規(guī)則（這里我們也稱語義動作或語義子程序），用花括號 括起來，插入到產(chǎn)生式右部的合適位置上。這樣翻譯模式給出了使用語義規(guī)則進行計算的順序。通常,我們用翻譯模式描述L-屬性文法在自頂向下分析中的實現(xiàn),以便于說明動作的順序和屬性計算

11、的順序，。我們知道，為了構(gòu)造不帶回溯的自頂向下語法分析，我們必須消除文法中的左遞歸。把前面討論過的消除左遞歸的算法加以擴充，當消除一個翻譯模式的基本文法的左遞歸時同時考慮屬性。這種方法適合帶綜合屬性的翻譯模式。這樣，許多屬性文法可以使用自頂向下分析來實現(xiàn)。我們把轉(zhuǎn)換左遞歸翻譯模式的方法推廣到一般，以便進行自頂向下分析。假設(shè)我們有下面的翻譯模式： AA1Y A.a:=g(A1.a,Y.y) AX A.a:=f(X.x) (5.1)它的每個文法符號都有一個綜合屬性，用小寫字母表示，g和f是任意函數(shù)。利用第四章消除左遞歸的算法，可將其轉(zhuǎn)換成下面的文法： AXR RYR | e 再考慮語義動作，翻譯模

12、式變?yōu)椋?AX R.i:=f (X.x) R A.a:=R.s RY R1.i:=g(R.i)Y.y (5.2) R1 R.s:=R1.s Re R.s:=R.i 如果語法分析采用的是自頂向下的遞歸下降分析法，則可以在遞歸下降分析中實現(xiàn)翻譯模式，構(gòu)造遞歸下降翻譯器。對給定的適合于自頂向下翻譯的翻譯模式，下面給出設(shè)計遞歸下降翻譯器的方法。1. 對每個非終結(jié)符A構(gòu)造一個函數(shù)過程，對A的每個繼承屬性設(shè)置一個形式參數(shù)，函數(shù)的返回值為A的綜合屬性（作為記錄，或指向記錄的一個指針，記錄中有若干域，每個屬性對應(yīng)一個域）。為了簡單，我們假設(shè)每個非終結(jié)只有一個綜合屬性。A對應(yīng)的函數(shù)過程中，為出現(xiàn)在A的產(chǎn)生式中的

13、每一個文法符號的每一個屬性都設(shè)置一個局部變量。2. 非終結(jié)符A對應(yīng)的函數(shù)過程中，根據(jù)當前的輸入符號決定使用哪個產(chǎn)生式候選。3. 每個產(chǎn)生式對應(yīng)的程序代碼中，按照從左到右的次序，對于單詞符號（終結(jié)符）、非終結(jié)符和語義動作分別作以下工作：i) 對于帶有綜合屬性x的終結(jié)符X，把x的值存入為X.x設(shè)置的變量中。然后產(chǎn)生一個匹配X的調(diào)用，并繼續(xù)讀入一個輸入符號。ii) 對于每個非終結(jié)符B，產(chǎn)生一個右邊帶有函數(shù)調(diào)用的賦值語句c=B(b1,b2,bk)，其中，b1,b2,bk是為B的繼承屬性設(shè)置的變量，c是為B的綜合屬性設(shè)置的變量。iii) 對于語義動作，把動作的代碼抄進分析器中，用代表屬性的變量來代替對屬

14、性的每一次引用。6.5 L-自下而上計算繼承屬性這里，我們討論在自下而上的分析過程中實現(xiàn)L-屬性文法的方法。這種方法可以實現(xiàn)任何基于LL（1）文法的L-屬性文法，它還可以實現(xiàn)許多（不是所有）基于LR（1）文法的L-屬性文法。在自下而上的翻譯方法中，要求把所有的語義動作都放在產(chǎn)生式的末尾，而在遞歸下降翻譯方法中，需要在產(chǎn)生式右部的不同地方嵌入語義動作。有一種轉(zhuǎn)換方法，從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作它，使所有嵌入的動作都出現(xiàn)在產(chǎn)生式的末尾，這樣就可以自下而上處理繼承屬性。轉(zhuǎn)換方法是，在基礎(chǔ)文法中加入新的產(chǎn)生式，這種產(chǎn)生式的形式為Me，其中M為新引入的一個標記非終結(jié)符。我們把嵌入在產(chǎn)生式中的每個語義動作用不同的標記非終結(jié)符M代替，并把這個動作放在產(chǎn)生式Me的末尾。例如，下面翻譯模式 ETR RT print ()R | T print ()R|e Tnum print (num.val)使用標記非終結(jié)符號M和N轉(zhuǎn)換為 ETR RTMR | TNR | e Tnum print (num.val) Me print () Ne print ()兩