6 2 1基于屬性文法的處理方法、S-屬性文法 - 基于屬性文法的處理方法、S-屬性文法1

1、1,編譯原理,第六章 屬性文法和語法制導(dǎo)翻譯,2,第六章 屬性文法和語法制導(dǎo)翻譯,屬性文法 基于屬性文法的處理方法 S-屬性文法的自下而上計算 L-屬性文法和自頂向下翻譯,3,第六章 屬性文法和語法制導(dǎo)翻譯,屬性文法 基于屬性文法的處理方法 S-屬性文法的自下而上計算 L-屬性文法和自頂向下翻譯,4,6.2 基于屬性文法的處理方法,由源程序的語法結(jié)構(gòu)所驅(qū)動的處理辦法就是語法制導(dǎo)翻譯法 語義規(guī)則的計算 產(chǎn)生代碼 在符號表中存放信息 給出錯誤信息 執(zhí)行任何其它動作 對輸入符號串的翻譯也就是根據(jù)語義規(guī)則進行計算的結(jié)果,輸入串,語法樹,按照語義規(guī)則計算屬性,5,6.2 基于屬性文法的處理方法,依賴圖

2、樹遍歷 一遍掃描,6,6.2 基于屬性文法的處理方法,依賴圖 樹遍歷 一遍掃描,7,依賴圖,在一棵語法樹中的結(jié)點的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以由依賴圖(有向圖)來描述 為每一個包含過程調(diào)用的語義規(guī)則引入一個虛綜合屬性b，這樣把每一個語義規(guī)則都寫成 b:=f(c1,c2,ck) 的形式 依賴圖中為每一個屬性設(shè)置一個結(jié)點，如果屬性b依賴于屬性c，則從屬性c的結(jié)點有一條有向邊連到屬性b的結(jié)點。,8,for 語法樹中每一結(jié)點n do for 結(jié)點n的文法符號的每一個屬性a do 為a在依賴圖中建立一個結(jié)點； for語法樹中每一個結(jié)點n do for 結(jié)點n所用產(chǎn)生式對應(yīng)的每一個語義規(guī)則 b

3、:=f(c1,c2,ck ) do for i:=1 to k do 從ci結(jié)點到b結(jié)點構(gòu)造一條有向邊；,9,EE1E2 E.val:=E1.val+E2.val,E1,+,E2,E,val,val,val,10,句子real id1，id2，id3的帶注釋的語法樹的依賴圖,id1,L,id2,L,id3,L,real,T,D,4 type,5 in,6 - addtype(id.entry, L.in),7 in,8 addtype,9 in,10 addtype,1 entry,2 entry,3 entry,產(chǎn) 生 式 語 義 規(guī) 則 DTL L.in := T.type Tint T.

4、type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),11,良定義的屬性文法,如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么稱該文法為良定義的,12,屬性的計算次序,一個依賴圖的任何拓撲排序都給出一個語法樹中結(jié)點的語義規(guī)則計算的有效順序 屬性文法說明的翻譯是很精確的 基礎(chǔ)文法用于建立輸入符號串的語法分析樹 根據(jù)語義規(guī)則建立依賴圖 從依賴圖的拓撲排序中，我們可以得到計算語義規(guī)則的順序,輸入串,語法樹,依賴圖,語義規(guī)則計算次序,13

5、,句子real id1，id2，id3帶注釋的語法樹的依賴圖,a4:=real; a5:=a4 addtype (id3.entry,a5); a7:=a5; addtype (id2.entry,a7); a9:=a7 addtype (id1.entry,a9);,14,6.2 基于屬性文法的的處理方法,依賴圖 樹遍歷 一遍掃描,15,6.2.2 樹遍歷的屬性計算方法,通過樹遍歷的方法計算屬性的值 假設(shè)語法樹已建立，且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性 以某種次序遍歷語法樹，直至計算出所有屬性 深度優(yōu)先，從左到右的遍歷,16,While 還有未被計算的屬性 do VisitNo

6、de(S) /*S是開始符號*/ procedure VisitNode (N:Node) ; begin if N是一個非終結(jié)符 then /*假設(shè)它的產(chǎn)生式為NX1Xm*/ for i :=1 to m do if XiVN then /*即Xi是非終結(jié)符*/ begin 計算Xi的所有能夠計算的繼承屬性； VisitNode (Xi) end; 計算N的所有能夠計算的綜合屬性 end,計算思維的典型方法-遞歸 問題的解決又依賴于類似問題的解決，只不過后者的復(fù)雜程度或規(guī)模較原來的問題更小 一旦將問題的復(fù)雜程度和規(guī)?；喌阶銐蛐r，問題的解法其實非常簡單,17,產(chǎn) 生 式 語 義 規(guī) 則 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.b Xx X.d :=2*X.c Yy Y.f := Y.e*3 Zz Z.g :=Z.h+1,例 考慮屬性的文法G。其中，S有繼承屬性a，綜合屬性b；X有繼承屬性c、綜合屬性d；Y有繼承屬性e、綜合屬性f；Z有繼承屬性h、綜合屬性g,18,假設(shè)S.a的初始值為0，輸入串為xyz,S:a=0,X,Y,Z,x,y,z,Z:h=0 g=1,X:c=1 d=2,S:a=0, b=0,Y:e=0 f=0,產(chǎn) 生 式 語 義 規(guī) 則 SXYZ Z.h := S.a