第六章屬性文法和語法制導翻譯從本章開始，我們介紹有關語義分析及翻譯的問題。其處理的方法主要是屬性文法和語法制導翻譯方法。本章中，我們將首先介紹屬性文法的基本概念，然后介紹基于屬性文法的處理方法，討論如何自上而下分析和自下而上分析中實現屬性計算。本章重點掌握前四節6.1屬性文法，6.2基于屬性文法的處理方法，6.3S—屬性文法的自下而上計算，6.4L—屬性文法和自頂向下翻譯。第六章屬性文法和語法制導翻譯6.1屬性文法屬性文法是在上下文無關文法的基礎上為每個文法符號（終結符或非終結符）配備若干個相關的“值”（稱為屬性）。這些屬性代表與文法符號相關的信息，例如它的類型、值、代碼序列、符號表內容等等。屬性和變量一樣，可以進行計算和傳遞。

第六章屬性文法和語法制導翻譯屬性一般分為兩類：綜合屬性和繼承屬性。簡單的說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。

屬性加工加工的過程即是語義處理的過程，對于文法的每一個產生式都配備了一組屬性的計算規則，則稱為語義規則。第六章屬性文法和語法制導翻譯

在一個屬性文法中，對應于每個產生式A都有一套與之相關聯的語義規則，每條語義規則的形式為：b:=f(c1,c2,…,ck)

這里f是一個函數，而且或者

（1）b是A的一個綜合屬性并且c1,c2,…ck是產生式右邊文法符號的屬性；或者

（2）b是產生式右邊某個文法符號的一個繼承屬性并且c1,c2,…ck是A或產生式右邊任何文法符號的屬性

在這兩種情況下，我們都說屬性b依賴于屬性c1,c2…,ck.第六章屬性文法和語法制導翻譯

要特別強掉的是：

（1）終結符只有綜合屬性，它由詞法分析器提供；

（2）非終結符既可以有綜合屬性也可以有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值。

一般來講，對出現在產生式右邊的繼承屬性和出現在產生式左邊的綜合屬性都必須提供一個計算規則，屬性計算規則中只能使用相應產生式的文法符號的屬性，這有利于產生式范圍內“封裝”屬性的依賴性。然而，出現在產生式左邊的繼承屬性和出現在產生式右邊的綜合屬性不由所給的產生式的屬性計算規則進行計算，它們由其它產生式的屬性規則計算,由屬性計算器的參數提供。第六章屬性文法和語法制導翻譯

語義規則所描述的工作可以包括屬性計算、靜態語義檢查、符號表操作、代碼生成等。語義規則可能產生副作用（如產生代碼），也可能不是變元的嚴格函數（如某個規則給出可用的下一個數據單元的地址）。這樣的語義規則通常寫成過程調用，或過程段。

綜合屬性：在語法樹中，一個結點的綜合屬性的值由其子結點的屬性值確定。因此，通常使用自底向上的方法在每一個結點處使用語義規則計算綜合屬性的值。僅僅使用綜合屬性的屬性文法稱S—屬性文法。

繼承屬性：在語法樹中，一個結點的繼承屬性由此結點的父結點和/或兄弟結點的某些屬性確定。用繼承屬性來表示程序語言結構中的上下文依賴關系很方便。第六章屬性文法和語法制導翻譯6.2基于屬性文法的處理方法從概念上講，基于屬性文法的處理過程通常是這樣的：對單詞符號串進行語法分析，構造語法分析樹，然后根據需要遍歷語法樹，并在語法樹的各結點處按語義規則進行計算。輸入串語法樹依賴圖語義規則計算次序這種由源程序的語法結構所驅動的處理辦法就是語法制導翻譯法。語義規則的計算可能產生代碼、在符號表中存放信息、給出錯誤信息或執行任何其它動作。對輸入串的翻譯也就是根據語義規則進行計算得出結果。第六章屬性文法和語法制導翻譯6.2.1依賴圖

如果在一棵語法樹中一個結點的屬性b依賴于屬性c，那么這個結點處計算b的屬性規則必須在確定c的語義規則之后使用。在一顆語法樹中的結點的繼承屬性和綜合屬性之間的相互依賴關系可以用稱作依賴圖的一個有向圖來描述。在為一棵語法樹構造依賴圖以前，我們為每一個包含過程調用的語義規則引入一個虛綜合屬性b，這樣把每一個語義規則都寫成b:=f(c1,c2,…ck)的形式。依賴圖中為每一個屬性設置一個結點，如果屬性b依賴屬性c，則從屬性c的結點有一條有向邊連到屬性b的結點。第六章屬性文法和語法制導翻譯這里要掌握依賴圖的畫法。例如，屬性A.a:=f(X.x,Y.y)

對應于產生式AXY的語義規則,這條語義規則確定了依賴于屬性X.x和Y.y的綜合屬性A.a。如果在語法樹中應用這個產生式，那么在依賴圖中會有三個結點A.a,X.x,和Y.y。由于A.a依賴X.x，所以有一條有向邊從X.x到A.a.由于A.a也依賴于Y.y，所以還有一條有向邊從Y.y連到A.a.如果與產生式AXY對應的語義規則還有：X.i:=g(A.a,Y.y)那么，圖中還應有兩條有向邊，一條從A.a連到X.i，另一條從Y.y連到X.i,因為X.i依賴于A.a和Y.y.第六章屬性文法和語法制導翻譯[例6.3]當下面的產生式應用于語法樹時，我們就像圖6.4所示的那樣把有向邊加到依賴圖中。產生式語義規則EE1+E2E.val:=E1.val+E2.val第六章屬性文法和語法制導翻譯

[例6.4]下頁的圖是書中圖6.2（P139）帶注釋語法樹的依賴圖。依賴圖中的結點由數字來標識，這些數字將在討論屬性的計算次序時用到。從代表T.type的結點4有一條邊連到代表L.in的結點5，因為根據產生式DTL的語義規則L1.in=L.in,可知L1.in依賴于L.in.第六章屬性文法和語法制導翻譯所以有兩條向下的邊分別進入結點7和9。每一個于L產生式有關的語義規則addtype(id.entry,L.in)都產生一個虛屬性，結點6、8和10都為這些虛屬性構造的。如果一屬性文法不存在屬性之間的循環依賴關系，那么該文法為良定義的。為了設計編譯程序，我們只處理良定義的屬性文法。第六章屬性文法和語法制導翻譯

屬性的計算次序一個有向非循環圖的拓撲序是圖中結點的任何順序m1,m2,…mk,使得邊必須是從序列中前面的結點指向后面的結點。也就是說，如果mimj是mi到mj的一條邊，那么在序列中mi必須出現在mj之前。一個依賴圖的任何拓撲排序都給出一個語法樹中結點的語義規則計算的有效順序。這就是說，在拓撲排序中，在一個結點上，語義規則b:=f（c1,c2,…ck)中的屬性c1,c2…ck在計算b以前都是可用的。第六章屬性文法和語法制導翻譯6.2.2樹遍歷的屬性計算方法通過樹遍歷計算屬性值得方法很多種。這些方法都假設語法樹已經建立起了，并且樹中已帶有開始符號的繼承屬性和終結符的綜合屬性。然后以某種次序遍歷語法樹，直至計算出所有的屬性。最常用的遍歷方法是深度優先，從左到右的遍歷方法。第六章屬性文法和語法制導翻譯6.2.3一遍掃描的處理方法與樹遍歷的屬性計算方法不同，一遍掃描的方法是在語法分析的同時計算屬性值。如果按這種一遍掃描的編譯程序模型來理解語法制導翻譯方法的話，所謂語法制導翻譯法，直觀上說是為文法中每個產生式配上一組語義規則，并且在語法分析的同時執行這些語義規則.在自上而下的語義分析中,若一個產生式匹配輸入串成功,或者在自下而上分析中,當一個產生式被用于進行歸約時,此產生式相應的語義規則就被計算,完成有關語義分析和代碼生成的工作.第六章屬性文法和語法制導翻譯6.2.4抽象語法樹

建立表達式的抽象語法樹,我們通過為每個運算分量或運算符號都建立一個結點來為子表達式建立子樹.運算符號結點的各子結點分別是表示該運算符號的各個運算分量的子表達式組成的子樹的根.第六章屬性文法和語法制導翻譯抽象語法樹中的每一個結點可以由包含幾個域的記錄來實現的.在一個運算符號對應的結點中,一個域標識運算符號，其它域包含指向運算分量的結點的指針。運算符號通常叫做這個結點的標號。當我們進行翻譯時，抽象語法樹中的結點可能會用附加域來存放結點的屬性值(或指向屬性的指針）。第六章屬性文法和語法制導翻譯6.3S—屬性文法的自下而上計算

這一節我們考慮這樣一類屬性文法：S—屬性文法，它只含有綜合屬性。下面我們討論分析棧中的綜合屬性。在自底向上的分析法中。我們使用一個棧來存放已經分析過的子樹的信息?，F在我們可以在分析棧中使用一個附域來存放綜合屬性值。圖6.9表示的是一個帶有一個屬性值空間的分析棧的例子。Stateval……XX.xYY.yZZ.z……圖6.9top第六章屬性文法和語法制導翻譯我們假設圖中的棧是由一對數組state和val來實現的。每一個state元素都是一個指向LR(1)分析表的指針（或索引）。（注意，文法符號隱含在state中而不需要存儲在棧中）。然而，如果像第五章中的那樣把文法符號存入棧中時，那么當第i個state對應的符號為A時，val[i]中就存放語法樹中與結點A對應的屬性值。設當棧頂由指針top指示。我們假設綜合屬性是剛好在每次歸約前計算的。假設語義規則A.a:=f(X.x,Y.y,Z.z)是對應于產生式AXYZ的。在把XYZ歸約成A以前，屬性Z.z的值放在val[top]中，Y.y的值放在val[top-1]中，X.x的值放在val[top-2]中。如果一個符號沒有綜合屬性，那么數組val中相應的元素就不定義。歸約后，top值減2，A的狀態存放在state[top]中（也就是X的位置）綜合屬性A.a的值存放在val[top]中。第六章屬性文法和語法制導翻譯

6.4L—屬性文法和自頂向下翻譯

一個屬性文法稱為L—屬性文法：如果對于每個產生式AX1X2…Xn其每個語義規則中的每個屬性或者是綜合屬性，或者是Xj(1<=j<=n)的一個繼承屬性且這個繼承屬性僅依賴于：（1）產生式Xj的左邊符號X1,X2,…Xj-1的屬性（2）A的繼承屬性。第六章屬性文法和語法制導翻譯6.4.1翻譯模式

屬性文法可以看成是關于語言翻譯的高級規范說明，其中隱去實現細節，使用戶從明確說明翻譯順序的工作中解脫出來。下面我們討論一種適合語法制導翻譯的另一種描述形式，稱為翻譯模式。翻譯模式給出了使用語義規則進行計算的次序，這樣就可以把某些實現細節表示出來。在翻譯模式中，和文法符號相關的屬性和語義規則（這里我們也稱語義動作），用花括號{}括起來，插入到產生式右部的合適位置上。這樣翻譯模式給出了使用語義規則進行計算的順序。第六章屬性文法和語法制導翻譯如果既有綜合屬性又有繼承屬性，在建立翻譯模式時就必須特別小心：（1）產生式右邊的符號的繼承屬性必須在這個符號以前的動作中計算出來。（2）一個動作不能引用這個動作右邊符號的綜合屬性。（3）產生式左邊非終結符的綜合屬性只有在它所引用的所有屬性都計算出來后才能計算。計算這種屬性的動作通常可放在產生式右端的末尾。第六章屬性文法和語法制導翻譯6.4.2自頂向下翻譯

在第四章我們知道，為了構造不帶回溯的自頂向下語法分析，必須消除文法中的左遞歸?，F在我們把前面消除左遞歸的方法加以擴充,當消除一個翻譯模式的基本語法的左遞歸時同時考慮屬性。這種方法適合帶綜合屬性的翻譯模式。這樣許多文法可以使用自頂向下分析來實現。第六章屬性文法和語法制導翻譯對于自頂向下的分析，我們假設動作是在處于相同位置上的符號被展開（匹配成功）時執行的。一個符號的繼承屬性必須由出現這個符號之前的動作來計算，產生式左邊非終結符的綜合屬性必須在它的所依賴的所有屬性都計算出來之后才能被計算。第六章屬性文法和語法制導翻譯下面我們把轉換左遞規翻譯模式的方法推廣到一般，以便進行自頂向下分析：假設我們有下面的翻譯模式：AA1Y{A.a:=g(A1.a,Y.y)}AX{A.a:=f(X.x)}其每個文法符號都有一個綜合屬性，用小寫字母表示，g和f是任意函數。利用第四章消除左遞歸的算法，可將其轉換成下面文法：AXRRYR|ε第六章屬性文法和語法制導翻譯

再考慮語義動作，翻譯模式變為：A→X{R.i:=f(X.x)}R{A.a:=R.s}R→Y{R1.i:=g((R.i),Y.y)}R1{R.s:=R1.s}R→ε{R.s:=R.i}經過轉換的翻譯模式，使用了R的繼承屬性i和綜合屬性s.第六章屬性文法和語法制導翻譯

6.4.3遞歸下降翻譯器的設計6.5自下而上計算繼承屬性第六章屬性文法和語法制導翻譯例題與習題解答[例6.1]某程序設計語言說明部分的語法制導定義如下：D→TLT→intT→realL→L1,idL→id給出語法制導定義及自底向上的翻譯模式，并比較兩者的不同。解：語法制導定義為：D→TL{L.in:=T.type}T→int{T.type:=integer}T→real{T.type:=real}L→L1,id{L1.in:=L.in,addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}第六章屬性文法和語法制導翻譯

自底向上分析的翻譯模式為：D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}從上述定義看兩者的區別僅在于在翻譯模式中把語義動作插入在規則右部的任意位置。而語法制導中把語義動作都放在產生式的最后。第六章屬性文法和語法制導翻譯[例6.2]在一個移入——歸約的分析中采用以下的語法制導的翻譯模式，在某產生式歸約時，立即執行括號中的動作。A→aB{print“0”}A→c{print“1”}B→Ab{print“2”}當分析器輸入為aacbb時，打印的字符串是什么?第六章屬性文法和語法制導翻譯解：分析器的分析過程如右圖：由于分析器采用移入歸約的方式進行分析，符號串aacbb的分析過程將按標號進行，而按一產生式歸約時立即執行括號中的動作所以分析器打印的字符為：12020語義動作E.nptr:=mknode(‘+’,E1.nptr,T.nptr)E.nptr:=mknode(‘*’,E1.nptr,T.np