編譯原理6-4.1-L屬性文法-翻譯模式PPT學(xué)習(xí)課件

1、第六章 屬性文法和語(yǔ)法制導(dǎo)翻譯,6.1 屬性文法 6.2 基于屬性文法的處理方法 6.3 S-屬性文法的自下而上計(jì)算 6.4 L-屬性文法和自頂向下翻譯 6.5 自下而上計(jì)算繼承屬性,6.4 L-屬性文法和自頂向下翻譯,6.4.1 翻譯模式 6.4.2 自頂向下翻譯 6.4.3 遞歸下降翻譯器的設(shè)計(jì),L-屬性文法,L-屬性文法可通過(guò)一次遍歷就計(jì)算出所有屬性值。 諸如LL(1)這種自上而下分析方法的分析過(guò)程，從概念上說(shuō)可以看成是深度優(yōu)先建立語(yǔ)法樹(shù)的過(guò)程 我們可以在自上而下語(yǔ)法分析的同時(shí)實(shí)現(xiàn)L-屬性文法的計(jì)算。,L-屬性文法,一個(gè)屬性文法稱(chēng)為 L-屬性文法 如果對(duì)于每個(gè)產(chǎn)生式 AX1X2Xn， 其

2、每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性， 或者是Xj(1=j= n)的一個(gè)繼承屬性 , 且這個(gè)繼承屬性?xún)H依賴(lài)于： (1) 產(chǎn)生式Xj的左邊符號(hào)X1，X2，Xj-l的屬性 (2) A的繼承屬性 S-屬性文法一定是L-屬性文法,L-屬性文法的例子 6.1 節(jié) 表6.1 表6.2,表6.7 非L-屬性文法的例子,因?yàn)?Q.i 依賴(lài)于右部符號(hào)R的綜合屬性R.s,6.4.1 翻譯摸式,翻譯模式（Translation schemes） 一種適合語(yǔ)法制導(dǎo)翻譯的另一種描述形式。 在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語(yǔ)義規(guī)則（語(yǔ)義動(dòng)作），用花括號(hào)括起來(lái)，插入到產(chǎn)生式右部的合適位置上。,R addop T R,

3、 print( addop.lexme) R,ET R R addop T print( addop.lexme) R | T num print( num. lexme) ,例: 將含有+和-運(yùn)算的中綴表達(dá)式翻譯為后綴形式,如 表達(dá)式 9-+2 后綴表示為 9 - 2 +,翻譯模式給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算的次序,這樣就可把某些實(shí)現(xiàn)細(xì)節(jié)表示出來(lái)。,圖6.10 9+2 的說(shuō)明動(dòng)作的語(yǔ)法分析樹(shù),E,T,R,9,print(9),T,print(),R,5,print(5),+,T,print(+),2,print(2),R,1,2,3,4,5,把語(yǔ)義動(dòng)作看作是終結(jié)符號(hào) 按深度優(yōu)先次序遍歷分析樹(shù)，

4、即得到,9,5,2,ET R R addop T print( addop.lexme) R | T num print( num. lexme) ,參考輸出后綴式的屬性文法,例如，假設(shè)有下面的產(chǎn)生式和語(yǔ)義規(guī)則： T T1* F T. val := T1.val * F. val 建立翻譯模式： T T1* F T. val := T1. val * F. val,只需要綜合屬性時(shí), 可以這樣建立翻譯模式: 為每一個(gè)語(yǔ)義規(guī)則建立一個(gè)包含賦值的動(dòng)作, 并把這個(gè)動(dòng)作放在相應(yīng)的產(chǎn)生式右邊的末尾。,如果既有綜合屬性又有繼承屬性，在建立翻譯模式時(shí)就必須滿(mǎn)足三個(gè)條件 (1)產(chǎn)生式右邊的符號(hào)的繼承屬性必須在

5、這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來(lái)。 (2)一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號(hào)的綜合屬性。 (3)產(chǎn)生式左邊非終結(jié)符的綜合屬性只有在它所引用的所有屬性都計(jì)算出來(lái)以后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通?？煞旁诋a(chǎn)生式右端的末尾。,下面的翻譯模式不滿(mǎn)足上述三個(gè)條件中的第一個(gè)條件: (1)產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來(lái)。 SA1 A2 A1. in:=1; A2. in:=2 Aa print(A. in) ,可以改為 S A1. in:1 A1 A2. in:=2 A2,print(A.in),1,print(A.in),2,A1. in:1; A2. in:=2,3,該屬性還沒(méi)

6、有定義,S A1. in:1 A1 A2. in:=2 A2,print(A.in),1,print(A.in),S,A,a,A,a,2,A2. in:=2,3,A1. in:1,4,例: 給定一個(gè)L-屬性文法, 建立一個(gè)滿(mǎn)足上述三個(gè)條件的翻譯模式。,基于數(shù)學(xué)格式語(yǔ)言EQN 給定輸人E sub 1 .Val EQN把E，1和.val分別按不同的大小放在相關(guān)的位置上，如圖所示。,圖6.11 盒子的語(yǔ)法制導(dǎo)安放,非終結(jié)符B(表示盒子)代表一個(gè)公式， 產(chǎn)生式BBB 代表兩個(gè)盒子并置， BB1 sub B2 代表B2的大小比B1的小,并且放在下角標(biāo)的位置,表6.8 盒子大小和高度的屬性文法,使B2.p

7、s減少30%,把盒子B2向下放置,繼承屬性ps影響 公式的高度,綜合屬性B.ht代表 B的高度,查表獲得,S B.ps := 10 BS.ht := B.ht B B1.ps := B.ps B1B2.ps := B.ps B2B.ht := max(B1.ht, B2.ht ) B B1.ps :=B.ps B1 sub B2.ps := shrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) B textB.ht := text.h B.ps ,圖6.12 從表6.8構(gòu)造出的翻譯模式,為文法 G:S ( L ) | a L L , S | S 寫(xiě)一個(gè)翻譯方案

8、，它輸出每個(gè)a的嵌套深度 例如:對(duì)于( a , ( a , a) ) ，輸出的結(jié)果是 1 2 2,S S. depth := 0 S S L. depth := S. depth + 1 ( L ) S a print (S. depth) L L1. depth := L. depth L1 , S. depth := L. depth S L S. depth := L. depth S,補(bǔ)充例1,S,(,L,),L,S,S S. depth := 0 S S L. depth := S. depth + 1 ( L ) S a print (S. depth) L L1. depth :

9、= L. depth L1 , S. depth := L. depth S L S. depth := L. depth S,( a , ( a , a) ),S,a,(,L,),L,S,S,a,a,0,1,1,1,1,1,2,2,2,2,2,2,為文法 G:S ( L ) | a L L , S | S 寫(xiě)一個(gè)翻譯方案,打印出每個(gè)a在句子中是第幾個(gè)字符 例如,當(dāng)句子是 ( a , ( a , ( a , a ) , (a) ) )時(shí)， 打印的結(jié)果是 2 5 8 10 14,補(bǔ)充例2,S S. in := 0 S S L. in := S. in + 1 ( L ) S. out := L.

10、 out + 1 S a S. out := S. in + 1; print (S. out) L L1. in := L. in L1 , S. in := L1. out + 1 S L. out := S. out L S. in := L. in S L. out := S. out ,L. in := S. in + 1,S. out := L. out + 1 ,L1. in := L. in ,S. in := L1. out + 1 ,L. out := S. out ,S. in := L. in ,L. out := S. out ,S. out := S. in + 1; print (S. out) ,S. out := S. in + 1; print (S. out) ,S,(,L,),L,S,S,a,a,S.in=0,S S. in := 0 S S L. in := S. in + 1 ( L ) S. out := L. out + 1 S a S. out := S. in + 1; prin