屬性文法和語法制導編譯

1、第六章第六章 屬性文法和語法制導翻譯屬性文法和語法制導翻譯內(nèi)容內(nèi)容 屬性文法屬性文法 基于屬性文法的處理方法基于屬性文法的處理方法 S-屬性文法的自下而上計算屬性文法的自下而上計算 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯 自下而上計算繼承屬性自下而上計算繼承屬性第六章第六章 屬性文法和語法制導翻譯屬性文法和語法制導翻譯 語義語義：一組規(guī)則，用它可以定義一個程序的：一組規(guī)則，用它可以定義一個程序的意義。意義。 描述方法：描述方法：自然語言描述：隱藏錯誤、二義性和不完整性自然語言描述：隱藏錯誤、二義性和不完整性形式描述：形式描述：F 操作語義操作語義(PL/1)(PL/1)F 指稱語義指

2、稱語義(ADA)(ADA)F 代數(shù)語義代數(shù)語義(PASCAL)(PASCAL)屬性文法屬性文法第六章第六章 屬性文法和語法制導翻譯屬性文法和語法制導翻譯 編譯中的語義處理包括兩個功能編譯中的語義處理包括兩個功能： （1）審查每個語法結(jié)構(gòu)的靜態(tài)語義，即驗證）審查每個語法結(jié)構(gòu)的靜態(tài)語義，即驗證語法結(jié)構(gòu)合法的程序是否真正有意義。也稱為語法結(jié)構(gòu)合法的程序是否真正有意義。也稱為靜態(tài)語義分析或靜態(tài)審查靜態(tài)語義分析或靜態(tài)審查；（2）如果靜態(tài)語義正確，則執(zhí)行真正的翻譯，）如果靜態(tài)語義正確，則執(zhí)行真正的翻譯，即即生成中間代碼生成中間代碼或生成實際的目標代碼?；蛏蓪嶋H的目標代碼。 以上工作普遍基于以上工作普遍基

3、于屬性文法和語法制導翻屬性文法和語法制導翻譯方法譯方法。6.1 屬性文法屬性文法 屬性文法屬性文法（也稱屬性翻譯文法）（也稱屬性翻譯文法）Knuth在在1968年提出年提出在上下文無關(guān)文法的基礎(chǔ)上，為每個文法在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號（終結(jié)符或非終結(jié)符）配備若干相關(guān)符號（終結(jié)符或非終結(jié)符）配備若干相關(guān)的的“值值”（稱為（稱為屬性屬性）。）。屬性代表與文法符號相關(guān)信息，如類型、值、屬性代表與文法符號相關(guān)信息，如類型、值、代碼序列、符號表內(nèi)容等代碼序列、符號表內(nèi)容等屬性可以進行計算和傳遞屬性可以進行計算和傳遞語義規(guī)則語義規(guī)則：對于文法的每個產(chǎn)生式都配備了一：對于文法的每個產(chǎn)生式都配備

4、了一組屬性的計算規(guī)則組屬性的計算規(guī)則6.1 屬性文法屬性文法 屬性屬性綜合屬性綜合屬性：“自下而上自下而上”傳遞信息傳遞信息繼承屬性繼承屬性：“自上而下自上而下”傳遞信息傳遞信息 在一個屬性文法中，對應(yīng)于每個產(chǎn)生式在一個屬性文法中，對應(yīng)于每個產(chǎn)生式A 都都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為：為：b:=f(c1, c2, , ck)這里，這里，f是一個函數(shù)，而且或者是一個函數(shù)，而且或者1. b是是A的一個的一個綜合屬性綜合屬性并且并且c1,c2,ck是產(chǎn)生式右邊是產(chǎn)生式右邊文法符號的屬性，或者文法符號的屬性，或者2. b是產(chǎn)生式右邊某個文法符號

5、的一個是產(chǎn)生式右邊某個文法符號的一個繼承屬性繼承屬性并且并且c1,c2,ck 是是A或產(chǎn)生式右邊任何文法符號的屬性。或產(chǎn)生式右邊任何文法符號的屬性。在兩種情況下，屬性在兩種情況下，屬性b依賴于屬性依賴于屬性c1,c2,ck。6.1 屬性文法屬性文法 說明說明終結(jié)符只有綜合屬性終結(jié)符只有綜合屬性，由詞法分析器提供，由詞法分析器提供非終結(jié)符既可有綜合屬性也可有繼承屬性，非終結(jié)符既可有綜合屬性也可有繼承屬性，文法文法開始符號的所有繼承屬性作為屬性計算前的初始開始符號的所有繼承屬性作為屬性計算前的初始值值對出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式對出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性

6、都必須提供一個計算規(guī)則。左邊的綜合屬性都必須提供一個計算規(guī)則。屬性屬性計算規(guī)則中只能使用相應(yīng)產(chǎn)生式中的文法符號的計算規(guī)則中只能使用相應(yīng)產(chǎn)生式中的文法符號的屬性屬性出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給的產(chǎn)生式的屬性計算規(guī)則邊的綜合屬性不由所給的產(chǎn)生式的屬性計算規(guī)則進行計算，進行計算，它們由其它產(chǎn)生式的屬性規(guī)則計算或它們由其它產(chǎn)生式的屬性規(guī)則計算或者由屬性計算器的參數(shù)提供者由屬性計算器的參數(shù)提供6.1 屬性文法屬性文法 語義規(guī)則語義規(guī)則所描述的工作可以包括屬性計算、所描述的工作可以包括屬性計算、靜態(tài)語義檢查、符號表操作、代碼生成等

7、靜態(tài)語義檢查、符號表操作、代碼生成等等。等。 例，考慮非終結(jié)符例，考慮非終結(jié)符A，B和和C，其中，其中，A有有一個繼承屬性一個繼承屬性a和一個綜合屬性和一個綜合屬性b，B有綜有綜合屬性合屬性c，C有繼承屬性有繼承屬性d。產(chǎn)生式。產(chǎn)生式ABC可能有規(guī)則可能有規(guī)則 C.d:=B.c+1 A.b:=A.a+B.c而屬性而屬性A.a和和B.c在其它地方計算在其它地方計算 n 屬性文法的例子：簡單算術(shù)表達式求值的語義描述。屬性文法的例子：簡單算術(shù)表達式求值的語義描述。非終結(jié)符非終結(jié)符E、T及及F都有一個都有一個綜合屬性綜合屬性val，符號符號digit有一個綜合屬性有一個綜合屬性lexval，它的值由詞

8、法分析器提供。，它的值由詞法分析器提供。與產(chǎn)生式與產(chǎn)生式LE對應(yīng)的語義規(guī)則僅僅是打印由對應(yīng)的語義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達產(chǎn)生的算術(shù)表達式的值的一個過程，我們可認為這條規(guī)則定義了式的值的一個過程，我們可認為這條規(guī)則定義了L的一個的一個虛屬性虛屬性。某些某些非終結(jié)符加下標非終結(jié)符加下標是為了區(qū)分一個產(chǎn)生式中同一非終結(jié)符多是為了區(qū)分一個產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)次出現(xiàn)語語 義義 規(guī)規(guī) 則則 L EE E1+TE TT T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val

9、T.val:=F.valF.val:=E.valF.val:=digit.lexval產(chǎn)生式產(chǎn)生式6.1 屬性文法屬性文法 綜合屬性綜合屬性在語法樹中，一個結(jié)點的綜合屬性的值由其子在語法樹中，一個結(jié)點的綜合屬性的值由其子結(jié)點的屬性值確定。結(jié)點的屬性值確定。使用自底向上的方法在每一個結(jié)點處使用語義使用自底向上的方法在每一個結(jié)點處使用語義規(guī)則計算綜合屬性的值規(guī)則計算綜合屬性的值 僅僅使用綜合屬性的屬性文法稱僅僅使用綜合屬性的屬性文法稱S屬性文屬性文法法結(jié)點屬性值的計算正好和自底向上分析建立分析樹結(jié)點同步進行。表達式表達式3*5+4n的帶注釋的語法樹的帶注釋的語法樹(語義動作打印數(shù)值語義動作打印數(shù)值

10、19) digit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19nL6.1 屬性文法屬性文法 繼承屬性繼承屬性在語法樹中，一個結(jié)點的繼承屬性由此結(jié)點的在語法樹中，一個結(jié)點的繼承屬性由此結(jié)點的父結(jié)點和父結(jié)點和/或兄弟結(jié)點的某些屬性確定或兄弟結(jié)點的某些屬性確定用繼承屬性來表示程序設(shè)計語言結(jié)構(gòu)中的上下用繼承屬性來表示程序設(shè)計語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便文依賴關(guān)系很方便6.1 屬性文法屬性文法 產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則 DTLL.in

11、 := T.type TintT.type := integer TrealT.type := real LL1, idL1.in :=L.in addtype(id.type, L.in) Lid addtype(id.type, L.in) 句子句子real id1，id2，id3的帶注釋的語法樹的帶注釋的語法樹 id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real6.2 基于屬性文法的處理方法基于屬性文法的處理方法 語法制導翻譯語法制導翻譯即基于屬性文法的處理過程處理過程是：對單詞符號串進行語法分析，構(gòu)造語法分析樹，然后根據(jù)

12、需要遍歷語法樹并在語法樹的各結(jié)點處按語義規(guī)則進行計算。 由源程序的語法結(jié)構(gòu)所驅(qū)動的處理辦法就是由源程序的語法結(jié)構(gòu)所驅(qū)動的處理辦法就是語語法制導翻譯法法制導翻譯法 語義規(guī)則的計算可能產(chǎn)生代碼、在符號表中存放信息、給出錯誤信息或執(zhí)行其他動作。對輸入符號串的翻譯就是根據(jù)語義規(guī)則進行計算的結(jié)果。輸入串輸入串語法樹語法樹依賴圖依賴圖語義規(guī)則計算次序語義規(guī)則計算次序6.2.1 依賴圖依賴圖 在一棵語法樹中的結(jié)點的繼承屬性和綜合屬性之在一棵語法樹中的結(jié)點的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以由稱作間的相互依賴關(guān)系可以由稱作依賴圖依賴圖的一個有向的一個有向圖來描述圖來描述 為每一個包含過程調(diào)用的語義規(guī)則引

13、入一個虛綜為每一個包含過程調(diào)用的語義規(guī)則引入一個虛綜合屬性合屬性b，這樣把每一個語義規(guī)則都寫成，這樣把每一個語義規(guī)則都寫成b:=f(c1,c2,ck)的形式的形式 依賴圖中為每一個屬性設(shè)置一個結(jié)點，如果屬性依賴圖中為每一個屬性設(shè)置一個結(jié)點，如果屬性b依賴于屬性依賴于屬性c，則從屬性，則從屬性c的結(jié)點有一條有向邊的結(jié)點有一條有向邊連到屬性連到屬性b的結(jié)點。的結(jié)點。6.2.1 依賴圖依賴圖 依賴圖的構(gòu)造算法依賴圖的構(gòu)造算法：for 語法樹中每一結(jié)點語法樹中每一結(jié)點n do for 結(jié)點結(jié)點n的文法符號的每一個屬性的文法符號的每一個屬性a do 為為a在依賴圖中建立一個結(jié)點在依賴圖中建立一個結(jié)點；

14、for 語法樹中每一個結(jié)點語法樹中每一個結(jié)點n do for 結(jié)點結(jié)點n所用產(chǎn)生式對應(yīng)的每一個語義規(guī)則所用產(chǎn)生式對應(yīng)的每一個語義規(guī)則 b:=f(c1,c2,ck ) do for i:=1 to k do 從從ci結(jié)點到結(jié)點到b結(jié)點構(gòu)造一條有向邊結(jié)點構(gòu)造一條有向邊； EE1E2 E.val:=E1.val+E2.val E1+E2Evalvalval句子句子real id1，id2，id3的帶注釋的語法樹的的帶注釋的語法樹的依賴圖依賴圖id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entry6.2.1 依賴圖依賴圖 如果一屬性文法不存在屬

15、性之間的循環(huán)依如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么稱該文法為賴關(guān)系，那么稱該文法為良定義的良定義的 6.2.1 依賴圖依賴圖 屬性的計算次序?qū)傩缘挠嬎愦涡蛞粋€依賴圖的任何一個依賴圖的任何拓撲排序拓撲排序都給出一個語法樹中都給出一個語法樹中結(jié)點的語義規(guī)則計算的有效順序結(jié)點的語義規(guī)則計算的有效順序 屬性文法說明的翻譯是很精確的屬性文法說明的翻譯是很精確的基礎(chǔ)文法用于建立輸入符號串的語法分析樹基礎(chǔ)文法用于建立輸入符號串的語法分析樹根據(jù)計算語義規(guī)則建立依賴圖根據(jù)計算語義規(guī)則建立依賴圖從依賴圖的拓撲排序中，我們可以得到計算語義從依賴圖的拓撲排序中，我們可以得到計算語義規(guī)則的順序規(guī)則的順序 輸

16、入串輸入串語法樹語法樹依賴圖依賴圖語義規(guī)則計算次序語義規(guī)則計算次序句子句子real id1，id2，id3的帶注釋的語法樹的帶注釋的語法樹的依賴圖的依賴圖id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7);a9:=a7addtype (id1.entry,a9);6.2.2 樹遍歷的屬性計算方法樹遍歷的屬性計算方法 通過樹遍歷的方法計算屬性的值通過樹遍歷的方法計算屬性的值 假設(shè)語法樹已經(jīng)建立起了，并且

17、樹中已帶有開假設(shè)語法樹已經(jīng)建立起了，并且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性始符號的繼承屬性和終結(jié)符的綜合屬性 以某種次序遍歷語法樹，直至計算出所有屬性以某種次序遍歷語法樹，直至計算出所有屬性深度優(yōu)先，從左到右的遍歷深度優(yōu)先，從左到右的遍歷 無循環(huán)的屬性文法計算算法：無循環(huán)的屬性文法計算算法：While 還有未被計算的屬性還有未被計算的屬性 doVisitNode(S) /*S是開始符號是開始符號*/procedure VisitNode (N:Node) ;begin if N是一個非終結(jié)符是一個非終結(jié)符 then /*假設(shè)它的產(chǎn)生式為假設(shè)它的產(chǎn)生式為NX1Xm*/ for i :

18、=1 to m do if not Xi VT then /*即即Xi是非終結(jié)符是非終結(jié)符*/ begin 計算計算Xi的所有能夠計算的繼承屬性；的所有能夠計算的繼承屬性； VisitNode (Xi) end;計算計算N的所有能夠計算的綜合屬性的所有能夠計算的綜合屬性end產(chǎn)產(chǎn) 生生 式式語語 義義 規(guī)規(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 G。其中，。其中，S S有繼承屬性有繼承屬性a a，

19、綜，綜合屬性合屬性b b；X X有繼承屬性有繼承屬性c c、綜合屬性、綜合屬性d d；Y Y有繼承有繼承屬性屬性e e、綜合屬性、綜合屬性f f；Z Z有繼承屬性有繼承屬性h h、綜合屬性、綜合屬性g g 假設(shè)假設(shè)S.a的初始值為的初始值為0，輸入串為，輸入串為xyzS:a=0XYZxyzZ:h=0 g=1X:c=1 d=2S:a=0, b=0Y:e=0 f=0產(chǎn)產(chǎn) 生生 式式語語 義義 規(guī)規(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 6.2

20、.3 一遍掃描的處理方法一遍掃描的處理方法 一遍掃描的處理方法是在語法分析的同時一遍掃描的處理方法是在語法分析的同時計算屬性值計算屬性值 所采用的語法分析方法所采用的語法分析方法屬性的計算次序?qū)傩缘挠嬎愦涡?L屬性文法屬性文法適合于一遍掃描的自上而下分適合于一遍掃描的自上而下分析析 S屬性文法屬性文法適合于一遍掃描的自下而上分適合于一遍掃描的自下而上分析析 6.2.3 一遍掃描的處理方法一遍掃描的處理方法 所謂所謂語法制導翻譯法語法制導翻譯法，直觀上說就是為文，直觀上說就是為文法中每個產(chǎn)生式配上一組語義規(guī)則，并且法中每個產(chǎn)生式配上一組語義規(guī)則，并且在語法分析的同時執(zhí)行這些語義規(guī)則在語法分析的同

21、時執(zhí)行這些語義規(guī)則 語義規(guī)則就被計算的時機語義規(guī)則就被計算的時機在自上而下語法分析中，一個產(chǎn)生式匹配輸入在自上而下語法分析中，一個產(chǎn)生式匹配輸入串成功時串成功時在自下而上分析中，當一個產(chǎn)生式被用于進行在自下而上分析中，當一個產(chǎn)生式被用于進行歸約時歸約時6.2.4 抽象語法樹抽象語法樹 在語法樹中去掉那些對翻譯不必要的信息，在語法樹中去掉那些對翻譯不必要的信息，從而獲得更有效的源程序中間表示。這種從而獲得更有效的源程序中間表示。這種經(jīng)變換后的語法樹稱之為經(jīng)變換后的語法樹稱之為抽象語法樹抽象語法樹(Abstract Syntax Tree)BS1S2if_then_elseq Sif B then

22、 S1 else S2q 3*5+4*54+3建立表達式的抽象語法樹建立表達式的抽象語法樹 mknode (op,left,right) 建立一個運算符號建立一個運算符號結(jié)點，標號是結(jié)點，標號是op，兩個域，兩個域left和和right分別分別指向左子樹和右子樹。指向左子樹和右子樹。 mkleaf (id,entry) 建立一個標識符結(jié)點，建立一個標識符結(jié)點，標號為標號為id，一個域，一個域eutry指向標識符在符號指向標識符在符號表中的入口。表中的入口。 mkleaf (num,ral) 建立一個數(shù)結(jié)點，標號建立一個數(shù)結(jié)點，標號為為num，一個域，一個域ral用于存放數(shù)的值。用于存放數(shù)的值。

23、建立抽象語法樹的語義規(guī)則建立抽象語法樹的語義規(guī)則產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則 EE1+TE.nptr := mknode( +, E1.nptr, T.nptr ) EE1-TE.nptr := mknode( -, E1.nptr, T.nptr ) ETE.nptr := T.nptr T (E) T.nptr := E.nptr TidT.nptr := mkleaf( id, id.entry ) Tnum T.nptr := mkleaf( num, num.val ) a4c的抽象語法樹的抽象語法樹E nptrT nptrE nptrTo entry for aET n

24、ptrid-T nptridid-idnum4+To entry for c+num6.3 S-屬性文法的自下而上計算屬性文法的自下而上計算 S-屬性文法屬性文法：只含有綜合屬性：只含有綜合屬性 綜合屬性可以在分析輸入符號串的同時由綜合屬性可以在分析輸入符號串的同時由自下而上的分析器來計算。自下而上的分析器來計算。 分析器可以保存與棧中文法符號有關(guān)的綜分析器可以保存與棧中文法符號有關(guān)的綜合屬性值，每當進行歸約時，新的屬性值合屬性值，每當進行歸約時，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號的屬就由棧中正在歸約的產(chǎn)生式右邊符號的屬性值來計算。性值來計算。6.3 S-屬性文法的自下而上計算屬性文法

25、的自下而上計算 在分析棧中使用一個附加的域來存放綜合在分析棧中使用一個附加的域來存放綜合屬性值屬性值 假設(shè)語義規(guī)則假設(shè)語義規(guī)則A.a:=f(X.x,Y.y,Z.z)是對應(yīng)于是對應(yīng)于產(chǎn)生式產(chǎn)生式AXYZ的的 Sm Z.z Z Sm-1 Y.y Y Sm-2 X.x X S0 # TOP Sm-2 A.a A S0 # TOP 產(chǎn)生式產(chǎn)生式 代代 碼碼 段段 LEnprint(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*Fvalntop := valtop-2*valtop TFF (E)valntop :=valtop-1Fdigit 翻譯輸入翻譯

26、輸入3 3* *5+4n5+4n所做的移動所做的移動輸入輸入 stateval 用到的產(chǎn)生式用到的產(chǎn)生式 3*5+4n *5+4n 3 3 *5+4n F 3 Fdigit *5+4n T 3 TF 5+4n T*3 - +4n T*53 - 5 +4n T*F3 - 5 Fdigit +4n T 15 TT*F翻譯輸入翻譯輸入3 3* *5+4n5+4n所做的移動所做的移動 輸入輸入 stateval 用到的產(chǎn)生式用到的產(chǎn)生式 +4n E 15 ET 4n E+15- n E+415- 4 n E+F15- 4 Fdigit n E+T15- 4 TF n E 19 EE+T En19- L

27、 19 LEn6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯 通過深度優(yōu)先的方法對語法樹進行遍歷，通過深度優(yōu)先的方法對語法樹進行遍歷，計算屬性文法的所有屬性值計算屬性文法的所有屬性值 LL（1）：自上而下分析方法，深度優(yōu)先）：自上而下分析方法，深度優(yōu)先建立語法樹建立語法樹6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯 一個屬性文法稱為一個屬性文法稱為L-屬性文法屬性文法，如果對于，如果對于每個產(chǎn)生式每個產(chǎn)生式AX1X2Xn，其每個語義規(guī)，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是則中的每個屬性或者是綜合屬性，或者是Xj(1 j n)的一個繼承屬性且這個繼承屬性的一個繼

28、承屬性且這個繼承屬性僅依賴于：僅依賴于：(1) 產(chǎn)生式產(chǎn)生式Xj的左邊符號的左邊符號X1，X2，Xj-1的屬的屬性；性；(2) A的繼承屬性。的繼承屬性。 S-屬性文法一定是屬性文法一定是L-屬性文法屬性文法6.4 L-屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯 產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則 ALM L.i := l(A.i) M.i :=m(l.s) AQR R.i := r(A.i) Q.i :=q(R.s) A.s :=f(Q.s) 上述文法不是上述文法不是L-屬性文法，屬性文法，Q的繼承屬性的繼承屬性Q.i依賴于它右邊的文法符號的屬性依賴于它右邊的文法符號的屬性R.s 6

29、.4.1 翻譯模式翻譯模式 翻譯模式翻譯模式：給出了使用語義規(guī)則進行計：給出了使用語義規(guī)則進行計算的次序，這樣就可把某些實現(xiàn)細節(jié)表算的次序，這樣就可把某些實現(xiàn)細節(jié)表示出來示出來 在翻譯模式中，和文法符號相關(guān)的屬性在翻譯模式中，和文法符號相關(guān)的屬性和語義規(guī)則（這里我們也稱和語義規(guī)則（這里我們也稱語義動作語義動作），），用花括號用花括號 括起來，插入到產(chǎn)生式右部括起來，插入到產(chǎn)生式右部的合適位置上的合適位置上 可將語義動作當成終結(jié)符可將語義動作當成終結(jié)符n翻譯模式示例：翻譯模式示例：把帶加號和減號的中綴表把帶加號和減號的中綴表達式翻譯成相應(yīng)的后綴表達式達式翻譯成相應(yīng)的后綴表達式 ETR Raddo

30、p T print(addop.lexeme) R1 | Tnum print(num.val)-ETR9print(9)TR5print(5)print(-)+T2print(2)Rprint(+) 輸入串輸入串9-5+2 后綴表達式后綴表達式95-2+6.4.1 翻譯模式翻譯模式 設(shè)計翻譯模式時，必須保證當某個動作引設(shè)計翻譯模式時，必須保證當某個動作引用一個屬性時它必須是有定義的。用一個屬性時它必須是有定義的。 L-屬性文法本身就能確保每個動作不會引屬性文法本身就能確保每個動作不會引用尚未計算出來的屬性。用尚未計算出來的屬性。 6.4.1 翻譯模式翻譯模式 建立翻譯模式建立翻譯模式:當只需

31、要綜合屬性時：當只需要綜合屬性時：為每一個語義規(guī)則建立為每一個語義規(guī)則建立一個包含賦值的動作，并把這個動作放在相應(yīng)一個包含賦值的動作，并把這個動作放在相應(yīng)的產(chǎn)生式右邊的末尾的產(chǎn)生式右邊的末尾 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 TT1*F T.val:=T1.valF.val建立產(chǎn)生式和語義動作：建立產(chǎn)生式和語義動作： TT1*F T.val:=T1.valF.val6.4.1 翻譯模式翻譯模式 建立翻譯模式建立翻譯模式:如果既有綜合屬性又有繼承屬性，在建立翻譯模式時就如果既有綜合屬性又有繼承屬性，在建立翻譯模式時就必須保證：必須保證：1. 產(chǎn)生式產(chǎn)生式右邊的符號的繼承屬性必須在這個符號以前的動作

32、中右邊的符號的繼承屬性必須在這個符號以前的動作中計算出來計算出來。2. 一個動作不能引用這個動作右邊的符號的綜合屬性一個動作不能引用這個動作右邊的符號的綜合屬性。3. 產(chǎn)生式左邊非終結(jié)符的綜合屬性只有在它所引用的所有屬性產(chǎn)生式左邊非終結(jié)符的綜合屬性只有在它所引用的所有屬性都計算出來以后才能計算。都計算出來以后才能計算。計算這種屬性的動作通常可放在產(chǎn)生計算這種屬性的動作通?？煞旁诋a(chǎn)生式右端的末尾式右端的末尾。如下列翻譯模式不滿足條件如下列翻譯模式不滿足條件1： SA1A2 A1.in:=1; A2.in:=2 Aa print(A.in)6.4.1 翻譯模式翻譯模式 基于數(shù)學格式語言基于數(shù)學格式

33、語言EQN給定輸入給定輸入 E sub 1 .valE1.val識別輸入并進行格式安放的識別輸入并進行格式安放的L-L-屬性文法屬性文法 產(chǎn)產(chǎn) 生生 式式語語 義義 規(guī)規(guī) 則則SBB.ps :=10S.ht :=B.htBB1B2 B1.ps :=B.ps B2.ps :=B.ps B.ht := max(B1.ht, B2.ht)BB1 sub B2B1.ps :=B.ps B2.ps :=shrink(B.ps) B.ht :=disp(B1.ht, B2.ht)Btext B.ht :=text.hB.ps翻譯模式翻譯模式 S B.ps:=10 B S.ht:=B.ht B B1.ps:

34、=B.ps B1 B2.ps:=B.ps B2 B.ht:=max(B1.ht,B2.ht) B B1.ps:=B.ps B1 sub B2.ps:=shrink(B.ps) B2 B.ht:=disp(B1.ht,B2.ht) B textB.ht:=text.hB.ps6.4.2 自頂向下翻譯自頂向下翻譯 動作是在處于相同位置上的符號被展開動作是在處于相同位置上的符號被展開（匹配成功）時執(zhí)行的。（匹配成功）時執(zhí)行的。 為了構(gòu)造不帶回溯的自頂向下語法分析，為了構(gòu)造不帶回溯的自頂向下語法分析，必須消除文法中的左遞歸必須消除文法中的左遞歸 當當消除一個翻譯模式的基本文法的左遞歸消除一個翻譯模式的

35、基本文法的左遞歸時同時考慮屬性時同時考慮屬性適合帶綜合屬性的翻適合帶綜合屬性的翻譯模式譯模式 6.4.2 自頂向下翻譯自頂向下翻譯 關(guān)于算術(shù)表達式的左遞歸文法相應(yīng)的翻譯關(guān)于算術(shù)表達式的左遞歸文法相應(yīng)的翻譯模式模式EE1+TE.val:=E1.val+T.valEE1-T E.val:=E1.val-T.valET E.val:=T.valT(E)T.val:=E.valTnumT.val:=num.val 消除左遞歸，構(gòu)造新的翻譯模式消除左遞歸，構(gòu)造新的翻譯模式 E TR.i:=T.val RE.val:=R.sR + TR1.i:=R.i+T.val R1R.s:=R1.sR - TR1.i

36、:=R.i-T.val R1R.s:=R1.sR R.s:=R.iT ( E ) T.val:=E.valT num T.val:=num.val計算表達式計算表達式9 95 52 2 ETRnumnum.val=9T.val=9R.i=9-TRnumnum.val=5T.val=5R.i=4+TRnumnum.val=2T.val=2R.i=6 R.s=6R.s=6R.s=6E.s=6自頂向下分析一般方法自頂向下分析一般方法 假設(shè)有翻譯模式：假設(shè)有翻譯模式： AA1YA.a:=g(A1.a,Y.y) AXA.a:=f(X.x)它的每個文法符號都有一個綜合屬性，用小寫它的每個文法符號都有一個綜

37、合屬性，用小寫字母表示，字母表示，g和和f是任意函數(shù)。是任意函數(shù)。q消除左遞歸：消除左遞歸： AXR RYR | q翻譯模式變?yōu)榉g模式變?yōu)?：A XR.i:=f (X.x) RA.a:=R.sR Y R1.i:=g(R.i,Y.y) R1R.s:=R1.sR R.s:=R.iXYY XA A.a=f(X.x)Y1A A.a=g(f(X.x),Y1.y)Y2A A.a=g(g(f(X.x),Y1.y), Y2.y) XYY AXR R.i=f(X.x)Y1R R.i= g(f(X.x),Y1.y)Y2R R.i= g(g(f(X.x),Y1.y), Y2.y) R.s= g(g(f(X.x),

38、Y1.y), Y2.y) R.s= g(g(f(X.x),Y1.y), Y2.y)R.s= g(g(f(X.x),Y1.y), Y2.y)A.a= g(g(f(X.x),Y1.y), Y2.y)構(gòu)造抽象語法樹的構(gòu)造抽象語法樹的屬性文法定義轉(zhuǎn)化屬性文法定義轉(zhuǎn)化成翻譯模式成翻譯模式 EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptr構(gòu)造抽象語法樹的構(gòu)造抽象語法樹的屬性文法定義轉(zhuǎn)化屬性文法定義轉(zhuǎn)化成翻譯模式成翻譯模式 E TR.i:=T.nptr RE.nptr:=R.s

39、R + TR1.i:=mknode(+,R.i,T.nptr) R1R.s:=R1.sR TR1.i:=mknode(,R.i,T.nptr) R1R.s:=R1.sR R.s:=R.iT ( E )T.nptr:=E.nptrT idT.nptr:=mkleaf(id,id.entry)T numT.nptr:=mkleaf(num,num.val)使用繼承屬性構(gòu)造使用繼承屬性構(gòu)造a a4 4c c的抽象語法樹的抽象語法樹ETRidTo entry for aidT.nptr-Tnumnum4T.nptrR. i-R+TRidTo entry for cidT.nptrR. i+R. i R

40、. sR. sR. sE.nptr6.4.3 遞歸下降翻譯器的設(shè)計遞歸下降翻譯器的設(shè)計 如何在遞歸下降分析中實現(xiàn)翻譯模式，構(gòu)如何在遞歸下降分析中實現(xiàn)翻譯模式，構(gòu)造造遞歸下降翻譯器遞歸下降翻譯器 設(shè)計遞歸下降翻譯器的方法設(shè)計遞歸下降翻譯器的方法6.4.3 遞歸下降翻譯器的設(shè)計遞歸下降翻譯器的設(shè)計 設(shè)計遞歸下降翻譯器的方法：設(shè)計遞歸下降翻譯器的方法：1. 對每個非終結(jié)符對每個非終結(jié)符A構(gòu)造一個函數(shù)過程構(gòu)造一個函數(shù)過程，對對A的每的每個繼承屬性設(shè)置一個形式參數(shù)個繼承屬性設(shè)置一個形式參數(shù)，函數(shù)的返回值為函數(shù)的返回值為A的綜合屬性的綜合屬性（作為記錄，或指向記錄的一個指針，（作為記錄，或指向記錄的一個指

41、針，記錄中有若干域，每個屬性對應(yīng)一個域）。為了記錄中有若干域，每個屬性對應(yīng)一個域）。為了簡單，我們假設(shè)每個非終結(jié)只有一個綜合屬性。簡單，我們假設(shè)每個非終結(jié)只有一個綜合屬性。A對應(yīng)的函數(shù)過程中，為出現(xiàn)在對應(yīng)的函數(shù)過程中，為出現(xiàn)在A的產(chǎn)生式中的每一的產(chǎn)生式中的每一個文法符號的每一個屬性都設(shè)置一個局部變量個文法符號的每一個屬性都設(shè)置一個局部變量。2. 非終結(jié)符非終結(jié)符A對應(yīng)的函數(shù)過程中，根據(jù)當前的輸對應(yīng)的函數(shù)過程中，根據(jù)當前的輸入符號決定使用哪個產(chǎn)生式候選。入符號決定使用哪個產(chǎn)生式候選。6.4.3 遞歸下降翻譯器的設(shè)計遞歸下降翻譯器的設(shè)計 設(shè)計遞歸下降翻譯器的方法：設(shè)計遞歸下降翻譯器的方法：3. 每

42、個產(chǎn)生式對應(yīng)的程序代碼中，按照從左到每個產(chǎn)生式對應(yīng)的程序代碼中，按照從左到右的次序，對于單詞符號（終結(jié)符）、非終結(jié)右的次序，對于單詞符號（終結(jié)符）、非終結(jié)符和語義動作分別作以下工作：符和語義動作分別作以下工作：qi) 對于帶有綜合屬性對于帶有綜合屬性x的終結(jié)符的終結(jié)符X，把，把x的值存入為的值存入為X.x設(shè)置的設(shè)置的變量中。然后產(chǎn)生一個匹配變量中。然后產(chǎn)生一個匹配X的調(diào)用，并繼續(xù)讀入一個輸入符的調(diào)用，并繼續(xù)讀入一個輸入符號。號。qii) 對于每個非終結(jié)符對于每個非終結(jié)符B，產(chǎn)生一個右邊帶有函數(shù)調(diào)用的賦值，產(chǎn)生一個右邊帶有函數(shù)調(diào)用的賦值語句語句c=B(b1,b2,bk)，其中，其中，b1,b2,

43、bk是為是為B的繼承屬性設(shè)的繼承屬性設(shè)置的變量，置的變量，c是為是為B的綜合屬性設(shè)置的變量。的綜合屬性設(shè)置的變量。qiii) 對于語義動作，把動作的代碼抄進分析器中，用代表屬性對于語義動作，把動作的代碼抄進分析器中，用代表屬性的變量來代替對屬性的每一次引用。的變量來代替對屬性的每一次引用。構(gòu)造抽象語法樹的構(gòu)造抽象語法樹的屬性文法定義轉(zhuǎn)化屬性文法定義轉(zhuǎn)化成翻譯模式成翻譯模式 E TR.i:=T.nptr RE.nptr:=R.sR + TR1.i:=mknode(+,R.i,T.nptr) R1R.s:=R1.sR TR1.i:=mknode(,R.i,T.nptr) R1R.s:=R1.sR

44、R.s:=R.iT ( E )T.nptr:=E.nptrT idT.nptr:=mkleaf(id,id.entry)T numT.nptr:=mkleaf(num,num.val)遞歸下降翻譯器實現(xiàn)遞歸下降翻譯器實現(xiàn) 非終結(jié)符非終結(jié)符E、R、T的函數(shù)及其參數(shù)類型的函數(shù)及其參數(shù)類型 functionE:AST-node;functionR(in:AST-node): AST-node;functionT: AST-node; 用用oddop代表和代表和 R oddop TR1.i:=mknode(addop,lexme, R.i,T.nptr) R1R.s:=R1.s R R.s:=R.i遞

45、歸下降翻譯器實現(xiàn)遞歸下降翻譯器實現(xiàn) 產(chǎn)生式產(chǎn)生式Raddop TR| 的分析過程的分析過程 procedare R; begin if sym=addop then begin advance;T; R end else begin /*do nothing*/ end end; 在此基礎(chǔ)上在此基礎(chǔ)上,構(gòu)造屬性文法的函數(shù)過程構(gòu)造屬性文法的函數(shù)過程: function R (in:AST-node): AST-node; var nptr, i1,s1,s: AST-node; addoplexeme: char; begin if sym=addop then begin /*產(chǎn)生式產(chǎn)生式Ra

46、ddop TR */ addoplexeme:=lexval; advance; nptr:=T; i1:=mknode (addoplexeme, in, nptr); s1:=R (i1) s:=s1 end else s:=in; return s end;6.5 自下而上計算繼承屬性自下而上計算繼承屬性 在自下而上的分析過程中實現(xiàn)在自下而上的分析過程中實現(xiàn)L-屬性文屬性文法的方法法的方法 可實現(xiàn)任何基于可實現(xiàn)任何基于LL（1）文法的）文法的L-屬性文屬性文法，還可以實現(xiàn)許多（不是所有）基于法，還可以實現(xiàn)許多（不是所有）基于LR（1）文法的）文法的L-屬性文法屬性文法6.5.1從翻譯模式

47、中去掉嵌入在產(chǎn)生式中間的動從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作作 要求把所有的語義動作都放在產(chǎn)生式的要求把所有的語義動作都放在產(chǎn)生式的末尾末尾 轉(zhuǎn)換方法，它可以使所有嵌入的動作都轉(zhuǎn)換方法，它可以使所有嵌入的動作都出現(xiàn)在產(chǎn)生式的末尾出現(xiàn)在產(chǎn)生式的末尾 加入新的產(chǎn)生式加入新的產(chǎn)生式M 把嵌入在產(chǎn)生式中的每個語義動作用不同的把嵌入在產(chǎn)生式中的每個語義動作用不同的標記非終結(jié)符標記非終結(jié)符M代替，并把這個動作放在產(chǎn)代替，并把這個動作放在產(chǎn)生式生式M 的末尾的末尾 6.5.1從翻譯模式中去掉嵌入在產(chǎn)生式中間的動從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作作 翻譯模式翻譯模式 E TRR T print () R | T print ()R| T num print (num.val) 轉(zhuǎn)換為轉(zhuǎn)換為 E TRR TMR | TNR | T num print (num.val)M print ()N print ()6.5.2 分析棧中的繼承屬性分析棧中的繼承屬性 屬性位置能預(yù)測L歸約時，T恰在右部下面 例: int p, q, r D T L.in := T.type LT int T. type := integerT real T. type := realL L1.in := L.in L1, id addtype