第六章 屬性文法和語法制導翻譯(第九周)

1、第六章 屬性文法和語 法制導翻譯程序語言語義的形式化描述形式語義學n1962年美國斯坦福大學麥克阿瑟（年美國斯坦福大學麥克阿瑟（Mcarthur）教）教授在國際信息加工聯(lián)合會年會上作了著名的報授在國際信息加工聯(lián)合會年會上作了著名的報告告“通往計算機的數(shù)學科學通往計算機的數(shù)學科學”，系統(tǒng)地論述了，系統(tǒng)地論述了程序設計語言語義形式化的重要性，以及和程序程序設計語言語義形式化的重要性，以及和程序正確性、語言的正確實施等的關系，并提出在形正確性、語言的正確實施等的關系，并提出在形式語言研究中使用抽象語法和狀態(tài)向量等基本方式語言研究中使用抽象語法和狀態(tài)向量等基本方法法形式語義學形式語義學 。形式語義學分

2、類n根據形式化的側重面和所使用的數(shù)學工具的不根據形式化的側重面和所使用的數(shù)學工具的不同，形式語義學可分成：同，形式語義學可分成：操作語義學操作語義學著重模擬數(shù)據加工過程中計算機系統(tǒng)著重模擬數(shù)據加工過程中計算機系統(tǒng)的操作。的操作。指稱語義學指稱語義學主要描述數(shù)據加工的結果而不是加工主要描述數(shù)據加工的結果而不是加工過程的細節(jié)。過程的細節(jié)。公理語義學公理語義學用公理化的方法描述程序對數(shù)據的加用公理化的方法描述程序對數(shù)據的加工。工。 代數(shù)語義學代數(shù)語義學把程序設計語言看作是刻劃數(shù)據和加把程序設計語言看作是刻劃數(shù)據和加工數(shù)據的一種抽象數(shù)據類型，使用研究抽象數(shù)據類型工數(shù)據的一種抽象數(shù)據類型，使用研究抽象數(shù)

3、據類型的代數(shù)方法，來描述程序設計語言的形式語義。的代數(shù)方法，來描述程序設計語言的形式語義。語義分析方法n丹麥的科學家曾經運用指稱語義學理論成功地實丹麥的科學家曾經運用指稱語義學理論成功地實現(xiàn)了現(xiàn)了Ada語言的編譯系統(tǒng)語言的編譯系統(tǒng) 。n形式語義學方法缺點：符號系統(tǒng)比較復雜，其描形式語義學方法缺點：符號系統(tǒng)比較復雜，其描述文本不易讀，不能借助這些形式系統(tǒng)自動完成述文本不易讀，不能借助這些形式系統(tǒng)自動完成語義處理任務。語義處理任務。n目前實際應用中比較流行的語義描述和語義處理目前實際應用中比較流行的語義描述和語義處理方法是方法是屬性文法屬性文法和和語法制導翻譯語法制導翻譯的方法的方法內容線索n屬性

4、文法屬性文法n基于屬性文法的處理方法基于屬性文法的處理方法 n語法制導翻譯語法制導翻譯 屬性文法nKnuth在在1968年提出年提出n在上下文無關文法的基礎上，在描述語義動作時，為在上下文無關文法的基礎上，在描述語義動作時，為每個文法符號（終結符和非終結符）配備若干相關的每個文法符號（終結符和非終結符）配備若干相關的“值值”，如，如“類型類型”，“地址地址”等，稱為等，稱為屬性屬性。n對文法的每個產生式配備一組屬性計算規(guī)則稱為對文法的每個產生式配備一組屬性計算規(guī)則稱為語義語義規(guī)則規(guī)則，它的描述形式為，它的描述形式為b:=f(c1,c2,ck)，其中，其中b,c1,c2ck為文法符號的屬性，為文

5、法符號的屬性，f是一個函數(shù)。是一個函數(shù)。n每個文法符號聯(lián)系于一組屬性，且每個文法符號聯(lián)系于一組屬性，且對每個產生式都給對每個產生式都給出其語義規(guī)則的文法稱為出其語義規(guī)則的文法稱為屬性文法屬性文法。屬性和語義規(guī)則n屬性代表與文法符號相關信息，如類型、值、代碼序列、符號表內容屬性代表與文法符號相關信息，如類型、值、代碼序列、符號表內容等等；n屬性可以進行計算和傳遞屬性可以進行計算和傳遞；n在一個屬性文法中，對應于每個產生式在一個屬性文法中，對應于每個產生式A 都有都有一組一組與之相關聯(lián)的與之相關聯(lián)的語義規(guī)則，每條規(guī)則的形式為：語義規(guī)則，每條規(guī)則的形式為：b:=f(c1,c2,ck)這里，這里，f是

6、一個函數(shù)是一個函數(shù) （1）b是是A的一個屬性的一個屬性，并且并且c1,c2,ck是產生式右邊文法符號的屬是產生式右邊文法符號的屬性，性，則則b是是A的的綜合屬性綜合屬性； （2）b是產生式右邊某個文法符號是產生式右邊某個文法符號X的一個屬性的一個屬性，并且并且c1,c2,ck 是是A或產生式右邊任何文法符號的屬性或產生式右邊任何文法符號的屬性， b是是X的的繼承屬性繼承屬性；屬性屬性b依賴于屬性依賴于屬性c1,c2,ck。 產產 生生 式式 LEn EE1+T ETTT1*FTFF (E)Fdigit語語 義義 規(guī)規(guī) 則則print(E.val) E.val := E1.val+T.val E

7、.val :=T.val T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval簡單臺式計算器的屬性文法記號表示n對于某個文法符號對于某個文法符號XVT VN，用，用 X . type（X的類型），的類型），X . cat（X的種的種別），別），X .val（X的值或地址）等表示它的值或地址）等表示它的的屬性屬性。n用用下標下標（上角標）區(qū)分同一產生式中（上角標）區(qū)分同一產生式中相相同符號的多次出現(xiàn)同符號的多次出現(xiàn)。綜合屬性n在語法樹中，一個結點的在語法樹中，一個結點的綜合屬性綜合屬性的值由的值由其其子結點子

8、結點的屬性值確定。的屬性值確定。n使用自底向上的方法在每一個結點處使用使用自底向上的方法在每一個結點處使用語義規(guī)則計算綜合屬性的值語義規(guī)則計算綜合屬性的值n僅僅使用綜合屬性的屬性文法稱僅僅使用綜合屬性的屬性文法稱S屬性文屬性文法法3*5+4n的帶注釋的語法樹的帶注釋的語法樹 digit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19nL 產產 生生 式式 語語 義義 規(guī)規(guī) 則則LEn print(E.val) EE1+T E.val := E1.v

9、al+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.lexval繼承屬性n在語法樹中，一個結點的在語法樹中，一個結點的繼承屬性繼承屬性由此結由此結點的點的父結點和父結點和/或兄弟結點或兄弟結點的某些屬性確定的某些屬性確定n用繼承屬性來表示程序設計語言結構中的用繼承屬性來表示程序設計語言結構中的上下文依賴關系很方便上下文依賴關系很方便產產 生生 式式 語語 義義 規(guī)規(guī) 則則 DTLL.in := T.type TintT.ty

10、pe := integer TrealT.type := real LL1, idL1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in)帶繼承屬性L.in的屬性文法句子real id1，id2，id3的帶注釋的語法樹 id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real產產 生生 式式 語語 義義 規(guī)規(guī) 則則 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.i

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

12、應產生式中的文法符號的屬性符號的屬性n出現(xiàn)在出現(xiàn)在產生式左邊的繼承屬性產生式左邊的繼承屬性和出現(xiàn)在和出現(xiàn)在產生式右邊的綜合屬性產生式右邊的綜合屬性不由所不由所給的產生式的屬性計算規(guī)則進行計算，它們由其它產生式的屬性規(guī)則給的產生式的屬性計算規(guī)則進行計算，它們由其它產生式的屬性規(guī)則計算或者由屬性計算器的參數(shù)提供計算或者由屬性計算器的參數(shù)提供n語義規(guī)則所描述的工作可以包括語義規(guī)則所描述的工作可以包括屬性計算屬性計算、靜態(tài)語義檢查靜態(tài)語義檢查、符號表操符號表操作作、代碼生成代碼生成等等。等等。例例. 考慮非終結符考慮非終結符A，B和和C，其中，其中， 產生式產生式ABC可能可能有語義有語義規(guī)則規(guī)則 C

13、.d:=B.c+1 A.b:=A.a+B.c而屬性而屬性A.a和和B.c在其它地方計算在其它地方計算 綜合屬性綜合屬性繼承屬性繼承屬性AbaBcCd內容線索屬性文法屬性文法n基于屬性文法的處理方法基于屬性文法的處理方法 n語法制導翻譯語法制導翻譯 概述n由源程序的語法結構所驅動的處理辦法就由源程序的語法結構所驅動的處理辦法就是是語法制導翻譯法語法制導翻譯法依賴圖依賴圖樹遍歷樹遍歷一遍掃描一遍掃描輸入串輸入串語法樹語法樹依賴圖依賴圖語義規(guī)則計算次序語義規(guī)則計算次序n基于屬性文法的處理過程基于屬性文法的處理過程依賴圖n在一棵語法樹中的結點的繼承屬性和綜合屬性之間的相互在一棵語法樹中的結點的繼承屬性

14、和綜合屬性之間的相互依賴關系可以由稱作依賴關系可以由稱作依賴圖依賴圖的一個有向圖來描述的一個有向圖來描述n為每一個包含過程調用的語義規(guī)則引入一個為每一個包含過程調用的語義規(guī)則引入一個虛綜合屬性虛綜合屬性b，這樣把每一個語義規(guī)則都寫成這樣把每一個語義規(guī)則都寫成b:=f(c1,c2,ck)的形式的形式n依賴圖中為每一個屬性設置一個結點，如果依賴圖中為每一個屬性設置一個結點，如果屬性屬性b依賴于依賴于屬性屬性c，則，則從屬性從屬性c的結點有一條有向邊連到屬性的結點有一條有向邊連到屬性b的結點的結點。依賴圖構造算法for 語法樹中每一結點語法樹中每一結點n do for 結點結點n的文法符號的每一個屬

15、性的文法符號的每一個屬性a do 為為a在依賴圖中建立一個結點；在依賴圖中建立一個結點；for 語法樹中每一個結點語法樹中每一個結點n do for 結點結點n所用產生式對應的每一個語義規(guī)則所用產生式對應的每一個語義規(guī)則b:=f(c1,c2,ck ) dofor i:=1 to k do 從從ci結點到結點到b結點構造一條有向邊；結點構造一條有向邊； EE1E2 E.val:=E1.val+E2.val E1+E2Evalvalval句子句子real idreal id1 1，idid2 2，idid3 3的的帶注釋的語法樹的依賴圖帶注釋的語法樹的依賴圖id1L,id2L,id3LrealTD

16、4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10 addtype1entry2entry3entry產產 生生 式式 語語 義義 規(guī)規(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) 說明n一條求值規(guī)則只有在其各變元值均已求得一條求值規(guī)則只有在其各變元值均已求得的情況下才可以使用；的情況下才可以使用；n如果一屬性

17、文法不存在屬性之間的循環(huán)依如果一屬性文法不存在屬性之間的循環(huán)依賴關系，那么稱該文法為良定義的賴關系，那么稱該文法為良定義的 樹遍歷的屬性計算方法n通過樹遍歷的方法計算屬性的值通過樹遍歷的方法計算屬性的值 假設語法樹已建立，且樹中已帶有開始符號的假設語法樹已建立，且樹中已帶有開始符號的繼承屬性和終結符的綜合屬性繼承屬性和終結符的綜合屬性 以某種次序遍歷語法樹，直至計算出所有屬性以某種次序遍歷語法樹，直至計算出所有屬性n深度優(yōu)先，從左到右的遍歷深度優(yōu)先，從左到右的遍歷 While 還有未被計算的屬性還有未被計算的屬性 doVisitNode(S) /*S是開始符號是開始符號*/procedure

18、VisitNode (N:Node) ;begin if N是一個非終結符是一個非終結符 then /*假設它的產生式為假設它的產生式為NX1Xm*/ for i :=1 to m do if Xi VN then /*即即Xi是非終結符是非終結符*/ begin 計算計算Xi的所有能夠計算的繼承屬性；的所有能夠計算的繼承屬性； VisitNode (Xi) end; 計算計算N的所有能夠計算的綜合屬性的所有能夠計算的綜合屬性end產產 生生 式式語語 義義 規(guī)規(guī) 則則 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*

19、X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1 例例 考慮屬性的文法考慮屬性的文法G。其中，。其中，S有繼承屬性有繼承屬性a，綜合屬性，綜合屬性b；X有繼承屬性有繼承屬性c、綜合屬性、綜合屬性d；Y有繼承屬性有繼承屬性e、綜合屬、綜合屬性性f；Z有繼承屬性有繼承屬性h、綜合屬性、綜合屬性g 假設假設S.a的初始值為的初始值為0，輸入串為，輸入串為xyzS:a=0XYZxyzZ:h=0 g=1X:c=1 d=2S:a=0, b=0Y:e=0 f=0產產 生生 式式 語義規(guī)則語義規(guī)則 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e :=

20、S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1 一遍掃描的處理方法n一遍掃描的處理方法是在語法分析的同時一遍掃描的處理方法是在語法分析的同時計算屬性值計算屬性值 所采用的語法分析方法所采用的語法分析方法屬性的計算次序屬性的計算次序nL屬性文法屬性文法適合于一遍掃描的自上而下分適合于一遍掃描的自上而下分析析nS屬性文法屬性文法適合于一遍掃描的自下而上分適合于一遍掃描的自下而上分析析內容線索屬性文法屬性文法基于屬性文法的處理方法基于屬性文法的處理方法 n語法制導翻譯語法制導翻譯 語法制導翻譯n直觀上說就是為每個產生式配上一個翻譯子程序（稱語義直觀上說就

21、是為每個產生式配上一個翻譯子程序（稱語義動作或語義子程序），并且在動作或語義子程序），并且在語法分析語法分析的同時執(zhí)行它。的同時執(zhí)行它。n語義動作一方面規(guī)定了產生式語義動作一方面規(guī)定了產生式產生的符號串產生的符號串的意義，另一的意義，另一方面又按照這種意義規(guī)定了生成中間代碼應做的方面又按照這種意義規(guī)定了生成中間代碼應做的基本動作基本動作。n定義：在語法分析過程中，當一個產生式定義：在語法分析過程中，當一個產生式獲得匹配獲得匹配（自上（自上而下分析）和而下分析）和用于歸約用于歸約（自下而上分析）時，此產生式對（自下而上分析）時，此產生式對應的語義子程序進入工作，完成既定翻譯任務，產生中間應的語義

22、子程序進入工作，完成既定翻譯任務，產生中間代碼。代碼。例例. 定義算術表達式定義算術表達式E的的“值值”的語義動作：的語義動作：1. EE(1)+E(2) E.VAL := E(1).VAL+E(2).VAL2. E0E.VAL := 03. E1 E.VAL := 1 上述語義動作雖然不產生中間代碼，但產生上述語義動作雖然不產生中間代碼，但產生式式1、2、3所產生的句子有了具體意義，而且，所產生的句子有了具體意義，而且，能按照其語義動作，在分析句子的同時一步能按照其語義動作，在分析句子的同時一步一步地算出每個句子的一步地算出每個句子的“值值”。語法制導翻譯的作用n如果語義動作不是簡單的計值程

23、序，而是某種中如果語義動作不是簡單的計值程序，而是某種中間代碼的產生程序，那么隨著語法分析的進展，間代碼的產生程序，那么隨著語法分析的進展，這種代碼也逐步生成。這種代碼也逐步生成。n語法制導翻譯的作用語法制導翻譯的作用產生中間代碼，產生中間代碼，產生目標指令，產生目標指令，對輸入串進行解釋執(zhí)行。對輸入串進行解釋執(zhí)行。非語法制導翻譯方法n與語法制導翻譯方法相對的是非語法制導與語法制導翻譯方法相對的是非語法制導翻譯，即翻譯程序將不受輸入語言的文法翻譯，即翻譯程序將不受輸入語言的文法的控制，如形式語義學的翻譯方法。的控制，如形式語義學的翻譯方法。語法制導翻譯的例子n一個語法制導翻譯的基礎是一個文法，

24、其中翻譯成分依附一個語法制導翻譯的基礎是一個文法，其中翻譯成分依附在每一產生式上。在每一產生式上。例例. .下列翻譯模式，它定義翻譯，即對每個輸入下列翻譯模式，它定義翻譯，即對每個輸入x x，其輸出是，其輸出是x x的逆轉。定義此翻譯的規(guī)則是的逆轉。定義此翻譯的規(guī)則是 產生式產生式 翻譯式翻譯式 (1)s0s(2)s1s (3)s (1)s=s0(2)s=s1 (3)s= 輸入輸出對可由輸入輸出對可由( , )表示，其中表示，其中 是輸入句子形式，而是輸入句子形式，而 是輸是輸出句子形式。出句子形式。 (S,S)開始用產生式開始用產生式s0s來擴展得到來擴展得到(0S,S0). 再用一次規(guī)則再用一次規(guī)則(1)，得到，得到(00S,S00)。 再用規(guī)則再用規(guī)則(2)，就得到，就得到(001S,S100)。 然后應用規(guī)則然后應用規(guī)則(3)并得到并得到(001,100