編譯原理ch6 屬性文法和語法制導翻譯

1、1962年美國斯坦福大學麥克阿瑟（Mcarthur）教授在國際信息加工聯合會年會上作了著名的報告“通往計算機的數學科學”，系統地論述了程序設計語言語義形式化的重要性，以及和程序正確性、語言的正確實施等的關系，并提出在形式語言研究中使用抽象語法和狀態(tài)向量等基本方法形式語義學 。根據形式化的側重面和所使用的數學工具的不同，形式語義學可分成： 操作語義學著重模擬數據加工過程中計算機系統的操作。 指稱語義學主要描述數據加工的結果而不是加工過程的細節(jié)。 公理語義學用公理化的方法描述程序對數據的加工。 代數語義學把程序設計語言看作是刻劃數據和加工數據的一種抽象數據類型，使用研究抽象數據類型的代數方法，來描

2、述程序設計語言的形式語義。丹麥的科學家曾經運用指稱語義學理論成功地實現了Ada語言的編譯系統 。形式語義學方法缺點：符號系統比較復雜，其描述文本不易讀，不能借助這些形式系統自動完成語義處理任務。目前實際應用中比較流行的語義描述和語義處理方法是屬性文法和語法制導翻譯的方法屬性文法基于屬性文法的處理方法 語法制導翻譯 Knuth在1968年提出在上下文無關文法的基礎上，在描述語義動作時，為每個文法符號（終結符和非終結符）配備若干相關的“值”，如“類型”，“地址”等，稱為屬性。對文法的每個產生式配備一組屬性計算規(guī)則稱為語義規(guī)則，它的描述形式為b:=f(c1,c2,ck)，其中b,c1,c2ck為文法

3、符號的屬性，f是一個函數。每個文法符號聯系于一組屬性，且對每個產生式都給出其語義規(guī)則的文法稱為屬性文法。屬性代表與文法符號相關信息，如類型、值、代碼序列、符號表內容等；屬性可以進行計算和傳遞；在一個屬性文法中，對應于每個產生式A都有一組與之相關聯的語義規(guī)則，每條規(guī)則的形式為：b:=f(c1,c2,ck)這里，f是一個函數 （1）b是A的一個屬性，并且c1,c2,ck是產生式右邊文法符號的屬性，則b是A的綜合屬性； （2）b是產生式右邊某個文法符號X的一個屬性，并且c1,c2,ck 是A或產生式右邊任何文法符號的屬性， 則b是X的繼承屬性；屬性b依賴于屬性c1,c2,ck。 產 生 式 LEn

4、EE1+T ETTT1*FTFF (E)Fdigit語語 義義 規(guī)規(guī) 則則print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval對于某個文法符號XVT VN，用 X . type（X的類型），X . cat（X的種別），X .val（X的值或地址）等表示它的屬性。用下標（上角標）區(qū)分同一產生式中相同符號的多次出現。在語法樹中，一個結點的綜合屬性的值由其子結點的屬性值確定。使用自底向上的方法在每一個結點處使用語義規(guī)

5、則計算綜合屬性的值僅僅使用綜合屬性的屬性文法稱S屬性文法 產 生 式 語 義 規(guī) 則LEn print(E.val) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.val :=F.val F (E) F.val :=E.val Fdigit F.val :=digit.lexvaldigit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19n

6、L在語法樹中，一個結點的繼承屬性由此結點的父結點和/或兄弟結點的某些屬性確定用繼承屬性來表示程序設計語言結構中的上下文依賴關系很方便產 生 式 語 義 規(guī) 則 DTLL.in := T.type TintT.type := integer TrealT.type := real LL1, idL1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in)產 生 式 語 義 規(guī) 則 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.i

7、n :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real終結符只有綜合屬性，由詞法分析器提供非終結符既可有綜合屬性也可有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值對出現在產生式右邊的繼承屬性和出現在產生式左邊的綜合屬性都必須提供一個計算規(guī)則。屬性計算規(guī)則中只能使用相應產生式中的文法符號的屬性出現在產生式左邊的繼承屬性和出現在產生式右邊的綜合屬性不由所給的產生式的屬性計算規(guī)則進行計算，它們由其它產生式

8、的屬性規(guī)則計算或者由屬性計算器的參數提供語義規(guī)則所描述的工作可以包括屬性計算、靜態(tài)語義檢查、符號表操作、代碼生成等等。例. 考慮非終結符A，B和C，其中， A有一個繼承屬性a和一個綜合屬性b; B有綜合屬性c; C有繼承屬性d。 產生式ABC可能有語義規(guī)則 C.d:=B.c+1 A.b:=A.a+B.c 而屬性A.a和B.c在其它地方計算 屬性文法基于屬性文法的處理方法 語法制導翻譯 由源程序的語法結構所驅動的處理辦法就是語法制導翻譯法 (1) 依賴圖 (2) 樹遍歷 (3) 一遍掃描輸入串輸入串語法樹語法樹依賴圖依賴圖語義規(guī)則計算次序語義規(guī)則計算次序n基于屬性文法的處理過程基于屬性文法的處理

9、過程在一棵語法樹中的結點的繼承屬性和綜合屬性之間的相互依賴關系可以由稱作依賴圖的一個有向圖來描述為每一個包含過程調用的語義規(guī)則引入一個虛綜合屬性b，這樣把每一個語義規(guī)則都寫成b:=f(c1,c2,ck)的形式依賴圖中為每一個屬性設置一個結點，如果屬性b依賴于屬性c，則從屬性c的結點有一條有向邊連到屬性b的結點（即需先有c才能計算b）。for 語法樹中每一結點n do for 結點n的文法符號的每一個屬性a do 為a在依賴圖中建立一個結點；for 語法樹中每一個結點n do for 結點n所用產生式對應的每一個語義規(guī)則b:=f(c1,c2,ck ) dofor i:=1 to k do 從ci

10、結點到b結點構造一條有向邊； EE1E2 E.val:=E1.val+E2.val E1+E2Evalvalval產 生 式 語 義 規(guī) 則 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10 addtype1entry2entry3

11、entry一條求值規(guī)則只有在其各變元值均已求得的情況下才可以使用；如果一屬性文法不存在屬性之間的循環(huán)依賴關系，那么稱該文法為良定義的 通過樹遍歷的方法計算屬性的值 假設語法樹已建立，且樹中已帶有開始符號的繼承屬性和終結符的綜合屬性 以某種次序遍歷語法樹，直至計算出所有屬性 深度優(yōu)先，從左到右的遍歷 While 還有未被計算的屬性 doVisitNode(S) /*S是開始符號*/procedure VisitNode (N:Node) ;begin if N是一個非終結符 then /*假設它的產生式為NX1Xm*/ for i :=1 to m do if XiVN then /*即Xi是非

12、終結符*/ begin 計算Xi的所有能夠計算的繼承屬性； VisitNode (Xi) end; 計算N的所有能夠計算的綜合屬性end產 生 式語 義 規(guī) 則 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1 例：考慮屬性文法例：考慮屬性文法G。其中，。其中，S有繼承屬性有繼承屬性a、綜合屬性、綜合屬性b；X有有繼承屬性繼承屬性c、綜合屬性、綜合屬性d；Y有繼承屬性有繼承屬性e、綜合屬性、綜合屬性f；Z有繼承有繼承屬性屬性h、綜合屬性、綜合屬性gS:a=

13、0XYZxyzZ:h=0 g=1X:c=1 d=2S:a=0, b=0Y:e=0 f=0產 生 式 語義規(guī)則 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1 第一次遍歷結束第二次遍歷結束第三次遍歷結束一遍掃描的處理方法是在語法分析的同時計算屬性值 所采用的語法分析方法 屬性的計算次序L屬性文法適合于一遍掃描的自上而下分析S屬性文法適合于一遍掃描的自下而上分析屬性文法基于屬性文法的處理方法 語法制導翻譯 直觀上說就是為每個產生式配上一個翻譯子程序（稱語義動

14、作或語義子程序），并且在語法分析的同時執(zhí)行它。語義動作一方面規(guī)定了產生式產生的符號串的意義，另一方面又按照這種意義規(guī)定了生成中間代碼應做的基本動作。定義：在語法分析過程中，當一個產生式獲得匹配（自上而下分析）和用于歸約（自下而上分析）時，此產生式對應的語義子程序進入工作，完成既定翻譯任務，產生中間代碼。例. 定義算術表達式E的“值”的語義動作：1. EE(1)+E(2) E.VAL := E(1).VAL+E(2).VAL2. E0E.VAL := 03. E1 E.VAL := 1 上述語義動作雖然不產生中間代碼，但產生式1、2、3所產生的句子有了具體意義，而且，能按照其語義動作，在分析句子

15、的同時一步一步地算出每個句子的“值”。如果語義動作不是簡單的計值程序，而是某種中間代碼的產生程序，那么隨著語法分析的進展，這種代碼也逐步生成。語法制導翻譯的作用 產生中間代碼 產生目標指令 對輸入串進行解釋執(zhí)行 根據輸入語言的文法（輸入文法），根據輸入語言的文法（輸入文法），分析各產生式的語義，即分析要求計算分析各產生式的語義，即分析要求計算機完成的操作，分別編寫出完成這些操機完成的操作，分別編寫出完成這些操作的子程序和程序段（稱語義子程序），作的子程序和程序段（稱語義子程序），并把它們的名字作為動作符號插入到輸并把它們的名字作為動作符號插入到輸入文法各產生式右部的適當位置上，從入文法各產生式

16、右部的適當位置上，從而形成翻譯文法。而形成翻譯文法。 在語法分析過程中，就能在分析符號在語法分析過程中，就能在分析符號串的同時，執(zhí)行由翻譯文法所確定的，串的同時，執(zhí)行由翻譯文法所確定的，與該符號串相對應的動作序列，即按動與該符號串相對應的動作序列，即按動作符號的順序調用相應的子程序完成翻作符號的順序調用相應的子程序完成翻譯任務。譯任務。與語法制導翻譯方法相對的是非語法制導翻譯，即翻譯程序將不受輸入語言的文法的控制，如形式語義學的翻譯方法。ET1 + T2 if T1.type = int and T2.type = int then E.type := int else error E T1

17、or T2 if T1.type = bool and T2.type = bool then E.type := bool else error T n T.type := int T b T.type := bool 語法制導的一個具體實現#-S0XX.VALSm-1YY.VALSmLR分析器的棧加入分析器的棧加入語義值語義值。狀態(tài)狀態(tài)值值符號符號TOP輸入串：輸入串： n + n5+-ET1 + T2 if T1.type = int and T2.type= int E.type :=int else error E T1 or T2 if T1.type = bool and T2.

18、type=bool E.type :=bool else error T n T.type := intT b T.type := bool 2Tint0#-4nint6Tint1Eint4nint輸入串輸入串n + b4nint0#-2Tint0#-5+-2Tint0#-3bbool5+-2Tint0#-6Tbool5+-2Tint0#-1Eerror0#-ET1 + T2 if T1.type = int and T2.type= int E.type :=int else error E T1 or T2 if T1.type = bool and T2.type=bool E.type

19、 :=bool else error T n T.type := intT b T.type := bool 構造翻譯器的基本思想 綜合屬性可以在分析輸入串的語法結構同時，由自下而上的分析器來計算。 在分析器中，保存與棧中文法符號有關的綜合屬性值，每當歸約時，新的文法符號的綜合屬性值就由棧中正在歸約的產生式的右部符號的屬性值來計算。 Z Z.z Y Y.y X X.x #top state val當用 A AXYZXYZ 歸約時: A A.a #top其中： A.a = f (X.x , Y.y , Z.z ) state val 輸入串 動作動作 # _ 3*5+4n #3 _3 *5+4n

20、 進棧 #F _3 *5+4n 歸約 #T _3 *5+4n 歸約 #T* _3_ 5+4n 進棧 #T*5 _3_5 +4n 進棧 #T*F _3_5 +4n 歸約 #T _15 +4n 歸約 #E _15 +4n 歸約 state val 輸入串 動作動作 #E+ _15_ 4n 進棧 #E+4 _15_4 n 進棧 #E+F _15_4 n 歸約 #E+T _15_4 n 歸約 #E _19 n 歸約 #En _19 進棧 #L “19 ” 歸約 LEn EE1+T ET TT1*F TF F(E) Fdigit print ( val top ) valntop = val top-2

21、 +val top valntop = val top-2 * *val top val ntop = valtop-1 L-屬性文法 如果每個產生式AX1X2Xn ，其對應的語義規(guī)則中的每個屬性，或者是綜合屬性，或者是Xj的一個繼承屬性且這個繼承屬性僅依賴于： （1）產生式中Xj的左邊符號X1，X2， Xj-1的屬性 （2）A的繼承屬性（注：A也在Xj的左側）以下文法是否為以下文法是否為L-L-屬性文法？屬性文法？不是。因為文法符號Q的繼承屬性Q.i依賴于它右邊的文法符號R的屬性R.sS-屬性文法一定是L-屬性文法，為什么？ 屬性文法可以看成是關于語言翻譯的高級規(guī)格說明，它隱去了實現的細節(jié)，

22、從而使用戶從明確說明翻譯順序的工作中解脫出來。 翻譯模式是適合語法制導翻譯的另一種描述形式，它給出了使用語義規(guī)則進行計算的次序，這樣就把實現的細節(jié)表示了出來。 在翻譯模式中， 通過把語義規(guī)則插入產生式右部的合適位置上，來給出屬性的計算次序。 ETR R+TR R-TR R Tnum 分析一下輸入串分析一下輸入串9 - 5： E T R 9 - T R 5 95- E T R 9 - T R 5 + T R 2 后綴后綴：9 5 2 +95-2+ ETR R+TR print (+) R-TR print (-) R Tnum print( num.val ) ETR R+T print (+)

23、 R R-T print (-) R R Tnum print( num.val ) L-屬性文法能確保每個動作都能計算出來。 如何設計一個合理的翻譯模式？ 1）當一個屬性文法只有綜合屬性時，則語義動作放在產生式的后面即可； 2）當屬性文法既有綜合屬性，又有繼承屬性時，一般要求建立的翻譯模式滿足下面三個條件： 1） 產生式右邊的繼承屬性必須在這個符號以前計算出來； 2） 一個動作不能引用這個動作右邊符號的綜合屬性； 3）產生式左邊符號的綜合屬性，只有在它引用的所有屬性都計算出來之后才計算。這種動作放在產生式的末尾。例：將以下屬性文法改寫為翻譯模式。 BB1B2 B1.ps=B.ps B2.ps

24、=B.ps B.ht=max(B1.ht , B2.ht) 改寫為： B B1.ps=B.ps B1 B2.ps=B.ps B2 B.ht=max(B1.ht , B2.ht) L-屬性文法是如何在自上而下的分析中的實現？ 為了便于說明動作的順序和屬性計算的順序，用翻譯模式來進行描述屬性文法。 為了構造不帶回溯的自上而下的語法分析，必須消除左遞歸。那么，當消除一個翻譯模式中產生式的左遞歸時，如何修改屬性呢？ 先考慮僅含綜合屬性的翻譯模式。 EE1+T E.val =E1.val+T.val EE1-T E.val =E1.val-T.val ET E.val=T.val T(E) T.val=

25、E.val Tnum T.val=num.val 考慮輸入串：9-5+2 E E + T E - T 4 T 5 9 T.val=9 E.val=9 T.val=5 E.val=4 T.val=4 E.val=8 ETR R-TR | +TR | T(E) | num再考慮輸入串：9-5+2先畫出語法樹，再考慮自上而下的翻譯過程 E T R 9 - T R1 5 + T R2 2 T.val=9 R.i=9T.val=5R1.i=4T.val=2R2.i=6E.val=6 ?T num T.val=num.val ET R R.i=T.val R- T R1 R1.i=R.i-T.val ET

26、 R.i=T.val R E.val=R.s R-T R1.i=R.i-T.val R1 R.s=R1.s R+T R1.i=R.i+T.val R1 R.s=R1.s R R.s=R.i T(E) T.val=E.val T num T.val=num.val 假設：每個文法符號只有一個綜合屬性 AA1Y A.a= g (A1.a , Y.y) AX A.a=f (X.x) 消除左遞歸后的翻譯模式為： AX R.i= f(X.x) R A.a=R.s RY R1.i=g(R.i , Y.y ) R1 R.s=R1.s R R.s=R.i A A Y2 A Y1X A X R Y1 R Y2

27、R A2.a=f(X.x)A1.a=g( A2.a , Y1.y )A.a=g( A1.a , Y2.y )R.i=f(X.x)R1.i=g( R.i, Y1.y )R2.i=g( R1.i ,Y2.y )自下而上翻譯自上而下翻譯 EE1+T E.nptr =mknode(+, E1.nptr ,T.nptr EE1-T E.nptr =mknode(-, E1.nptr ,T.nptr ET E.nptr=T.nptr ET R R-T R1 R R.i = T.nptr E.nptr = R.s R1.i = mknode(-, R.nptr ,T.nptr ) R.s = R1.s R.s = R.i 消除左遞歸后在自下而上的分析過程中如何實現L-屬性文法？ 下面方法可以實現基于LL(1)文法的屬性文法，也可以實現許多基于LR(1)文法的