第6章 屬性文法和語法制導(dǎo)翻譯

1、第六章屬性文法和語法制導(dǎo)翻譯第六章屬性文法和語法制導(dǎo)翻譯 “語義分析”是編譯程序最實(shí)質(zhì)性的工作。語義 分析程序在整個(gè)編譯過程中，首次對(duì)源程序的語 義做出解釋，引起源程序發(fā)生質(zhì)的變化，而詞法 分析和語法分析僅是對(duì)源程序形式上的識(shí)別和處 理。 高級(jí)程序語言結(jié)構(gòu)的形式化描述已經(jīng)有比較成熟 的技術(shù)，由于這種形式化描述的完善，使分析器 的構(gòu)造甚至自動(dòng)構(gòu)造是比較容易的。 1 編譯程序的語義分析涉及到語言的語義，語義形 式化是個(gè)專門的研究課題. 形式語義學(xué)（如指稱語義學(xué)、公理語義學(xué)、操作 語義學(xué)等）的研究從20世紀(jì)60年代已經(jīng)開始， 并且在理論研究方面也有了重要的進(jìn)展。但不論 哪種方法，其本身的符號(hào)系統(tǒng)比較

2、繁雜，其描述 文本不易讀，尚不便借助這些形式系統(tǒng)自動(dòng)完成 語義處理任務(wù)。并且在工程實(shí)現(xiàn)和應(yīng)用方面還有 一定的差距。 2 目前實(shí)際應(yīng)用中較流行的語義描述和語義處理方 法主要還是屬性文法和語法制導(dǎo)翻譯方法。但它 仍不是一種形式系統(tǒng)，只是比較接近形式化。 語法制導(dǎo)翻譯方法的實(shí)質(zhì)是在語法分析過程中同 時(shí)進(jìn)行語義處理的翻譯技術(shù)。這種方法使用屬性 文法為工具來說明程序設(shè)計(jì)語言的語義。 3 第六章屬性文法和語法制導(dǎo)翻譯第六章屬性文法和語法制導(dǎo)翻譯 6.1 屬性文法 6.2 基于屬性文法的處理方法 6.3 S屬性文法的自下而上計(jì)算 6.4 L屬性文法和自頂向下翻譯 6.5 自下而上計(jì)算繼承屬性 4 6.1 屬

3、性文法 一、基本概念 1、屬性 廣廣義義：用以描述事物或人的特征、性：用以描述事物或人的特征、性質(zhì)質(zhì)、品、品質(zhì)質(zhì)等等。等等。 屬屬性文法中：代表性文法中：代表與與文法符文法符號(hào)號(hào)相相關(guān)關(guān)的信息，其信息的信息，其信息 值值即即為屬為屬性性值值。 例如：其類型、值、代碼序列、符號(hào)表內(nèi)容等。例如：其類型、值、代碼序列、符號(hào)表內(nèi)容等。 5 6.1 屬性文法 （1 1）屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。）屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。 （2 2）屬性加工的過程即是語義處理的過程。）屬性加工的過程即是語義處理的過程。 （3 3）屬性）屬性 綜合屬性：用于綜合屬性：用于“自下而上自下而上”傳遞信息。

4、傳遞信息。 繼承屬性：用于繼承屬性：用于“自上而下自上而下”傳遞信息。傳遞信息。 6 6.1 屬性文法 2 2、語義規(guī)則、語義規(guī)則 為為文法的每一文法的每一個(gè)產(chǎn)個(gè)產(chǎn)生式配生式配備備的的屬屬性的性的計(jì)計(jì)算算 規(guī)則規(guī)則，稱為語義規(guī)則稱為語義規(guī)則。 3 3、屬性文法、屬性文法 上下文無上下文無關(guān)關(guān)文法文法 + 語義規(guī)則語義規(guī)則 = 屬屬性文法性文法 7 6.1 屬性文法 二、基本規(guī)則 1、語義規(guī)則的形式： 產(chǎn)生式產(chǎn)生式A A 的語義規(guī)則的一般形式為的語義規(guī)則的一般形式為b:=f(cb:=f(c1 1,c ,c2 2,c,ck k) ) 其中：其中：(1) f是一個(gè)函數(shù)；是一個(gè)函數(shù)； (2) 或者或者

5、b A的綜合屬性的綜合屬性，且，且c1,c2,ck是是中文中文 法符號(hào)的屬性；法符號(hào)的屬性； (3) 或者或者b 中某個(gè)文法符號(hào)的繼承屬性，中某個(gè)文法符號(hào)的繼承屬性，且且 c1,c2,ck是是A或或中任何文法符號(hào)的屬性。中任何文法符號(hào)的屬性。 屬性屬性b依賴于屬性依賴于屬性c1,c2,ck 8 6.1 屬性文法 2、VTVN的屬性 (1) VT 只有只有綜綜合合屬屬性，由性，由詞詞法分析器提供。法分析器提供。 (2) VN 既既可有可有綜綜合合屬屬性也可有性也可有繼繼承承屬屬性，性， 文法文法開開始符始符號(hào)號(hào)S的所有的所有繼繼承承屬屬性作性作為屬為屬性性 計(jì)計(jì)算前的初始算前的初始值值。 9 6

6、.1 屬性文法 3、屬性的計(jì)算/獲得 (1) 產(chǎn)產(chǎn)生式右生式右邊邊的的繼繼承承屬屬性性 產(chǎn)產(chǎn)生式左生式左邊邊的的綜綜合合屬屬性性 (2) 產(chǎn)產(chǎn)生式左生式左邊邊的的繼繼承承屬屬性性 產(chǎn)產(chǎn)生式右生式右邊邊的的綜綜合合屬屬性性 由該產(chǎn)生式提供的計(jì)由該產(chǎn)生式提供的計(jì) 算規(guī)則計(jì)算獲得算規(guī)則計(jì)算獲得 由其它產(chǎn)生式的屬性由其它產(chǎn)生式的屬性 規(guī)則計(jì)算或由屬性計(jì)規(guī)則計(jì)算或由屬性計(jì) 算器的參數(shù)提供算器的參數(shù)提供 10 6.1 屬性文法 例例6.1： C.d:=B.c+1 A.b:=A.a+B.c 產(chǎn)生式 ABC 的規(guī)則： C.d右部繼承屬性右部繼承屬性 A.b左部綜合屬性左部綜合屬性 A.a左部繼承屬性左部繼承屬

7、性 B.c右部綜合屬性右部綜合屬性 11 6.1 屬性文法 例例6.2：一個(gè)簡(jiǎn)單臺(tái)式計(jì)算器的屬性文法 產(chǎn)生式語義規(guī)則 LEn EE1+T ET TT1*F TF F(E) Fdigit 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 12 產(chǎn)生式語義規(guī)則 DTL Tint Treal LL1,id Lid addtype(id.entry,L.in) T.type:=integer T.type:=real L1.in:

8、=L.in L.in:=T.type addtype(id.entry,L.in) 13 產(chǎn)生式語義規(guī)則 SXYZ Xx Yy Zz Z.h:=S.a X.c:=Z.g S.b:=X.d-2 Y.e:=S.b X.d:=2*X.c Y.f:=Y.e*3 Z.g:=Z.h+1 14 6.1 屬性文法 二、綜合屬性 1 1、語法樹中、語法樹中, ,一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn) 的屬性值確定。的屬性值確定。 2 2、通常使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語、通常使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語 義規(guī)則計(jì)算綜合屬性的值。義規(guī)則計(jì)算綜合屬性的值。 S屬性文法：

9、屬性文法：僅使用綜合屬性的屬性文法僅使用綜合屬性的屬性文法 15 6.1 屬性文法 例例6.3：例6.2的表中定義的屬性文法說明了一個(gè)臺(tái) 式計(jì)算器，該計(jì)算器讀入一個(gè)可含數(shù)字、括號(hào)和+、 *運(yùn)算符的算術(shù)表達(dá)式，并打印表達(dá)式的值，每個(gè) 輸入行以n作為結(jié)束。假設(shè)表達(dá)式為3*5+4，后跟一 個(gè)換行符n。 則程序打印數(shù)值則程序打印數(shù)值19。 其帶注釋的語法樹其帶注釋的語法樹 16 三、繼承屬性 1 1、語法樹中、語法樹中, ,一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié) 點(diǎn)和或兄弟結(jié)點(diǎn)的某些屬性確定。點(diǎn)和或兄弟結(jié)點(diǎn)的某些屬性確定。 6.1 屬性文法 、用繼承屬性來表示程序設(shè)計(jì)語言結(jié)構(gòu)

10、中的上下、用繼承屬性來表示程序設(shè)計(jì)語言結(jié)構(gòu)中的上下 文依賴關(guān)系很方便。文依賴關(guān)系很方便。 17 6.1 屬性文法 例例6.：帶繼承屬性L.in的屬性文法 產(chǎn)生式語義規(guī)則 DTL Tint Treal LL1,id Lid addtype(id.entry,L.in) T.type:=integer T.type:=real L1.in:=L.in L.in:=T.type addtype(id.entry,L.in) 18 輸入串輸入串: real id1,id2,id3的帶注釋的語法樹的帶注釋的語法樹 D D T.type=realT.type=realL.in=realL.in=real

11、realreal L.in=realL.in=real L.in=realL.in=real，id2id2 id3id3 ， id1id1 19 1 1、構(gòu)造依賴圖的方法、構(gòu)造依賴圖的方法: : 輸入串語法樹依賴圖語義規(guī)則的計(jì) 算次序進(jìn)行語義規(guī)則計(jì)算，得到翻譯結(jié)果 6.2 基于屬性文法的處理方法 2 2、遍歷語法樹的方法、遍歷語法樹的方法 單詞符號(hào)串單詞符號(hào)串 語法分析語法分析 語法分析樹語法分析樹 遍歷遍歷 計(jì)算計(jì)算 3 3、可用一遍掃描實(shí)現(xiàn)屬性文法的語義規(guī)則計(jì)算。、可用一遍掃描實(shí)現(xiàn)屬性文法的語義規(guī)則計(jì)算。 20 一、依賴圖 1、定義：一個(gè)表示一棵語法樹中結(jié)點(diǎn)的繼承 屬性和綜合屬性之間的相互

12、依賴關(guān) 系的有向圖。 6.2 基于屬性文法的處理方法 21 2、依賴圖的構(gòu)造方法 （1）構(gòu)造依賴圖以前，先為每一個(gè)包含過程調(diào) 用的語義規(guī)則引入一個(gè)虛綜合屬性b，在每 一個(gè)語義規(guī)則均寫成b:=f（c1 1，c2 2， ck k）的 形式； （2）在依賴圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)； （3）若屬性b依賴于屬性c，則從屬性c的結(jié)點(diǎn)有 一條有向邊連到屬性b的結(jié)點(diǎn)。 6.2 基于屬性文法的處理方法 22 例例6.5：AXY A.a:=f(X.x,Y.y) X.i:=g(A.a,Y.y) 6.2 基于屬性文法的處理方法 23 3、例題 例例6.6：將下面的產(chǎn)生式應(yīng)用于語法樹中 產(chǎn)生式語義規(guī)則 EE1+E2

13、 E.val:=E1.val+E2.val E E E E1 1 + + E E2 2 val valval E.Val是從 E1.val和E2.val 綜合得出 6.2 基于屬性文法的處理方法 24 產(chǎn)生式語義規(guī)則 DTL Tint Treal LL1,id Lid addtype(id.entry,L.in) T.type:=integer T.type:=real L1.in:=L.in L.in:=T.type addtype(id.entry,L.in) 25 D D T TL L realreal L L L L ， id2id2 id3id3 ， id1id1 a4：=real

14、a5：=a4 Addtype(id3.entry，a5)； a7：=a5； addtype(id2.entry，a7)； a9：=a7； Addtype(id1.entry，a9)； 拓?fù)湫蛄?a1,a2,a3,a4,a5,a6,a7,a8,a9,a10 26 二、樹遍歷的屬性計(jì)算方法 1、方法 A、前提：假設(shè)語法樹已經(jīng)建立起來了，且樹中已 有如下信息：開始符號(hào)繼承屬性 終結(jié)符綜合屬性 B、遍歷：以某種次序遍歷語法樹，直至計(jì)算出所 有屬性。 遍歷方法：深度優(yōu)先，從左到右遍歷方法：深度優(yōu)先，從左到右 6.2 基于屬性文法的處理方法 27 6.2 基于屬性文法的處理方法 2、算法 While Wh

15、ile 還有未被計(jì)算的屬性還有未被計(jì)算的屬性 dodo VisitNode(S)VisitNode(S)/ /* *S S是開始符號(hào)是開始符號(hào)* */ / procedure VisitNode(N:Node);procedure VisitNode(N:Node); beginbegin If N If N是一個(gè)非終結(jié)符是一個(gè)非終結(jié)符 thenthen / /* * 假設(shè)它的產(chǎn)生式為假設(shè)它的產(chǎn)生式為N NX X1 1XXm m * */ / for i:=1 to m do for i:=1 to m do if not Xif not Xi iVVT T then / then /* *

16、即即X Xi i是非終結(jié)符是非終結(jié)符 * */ / beginbegin 計(jì)算計(jì)算X Xi i的所有能夠計(jì)算的繼承屬性的所有能夠計(jì)算的繼承屬性; ; VisitNode(XVisitNode(Xi i) ) end;end; 計(jì)算計(jì)算N N的所有能夠計(jì)算的綜合屬性的所有能夠計(jì)算的綜合屬性 endend 注：只要文法的屬性是非循環(huán)定義的，則每次掃注：只要文法的屬性是非循環(huán)定義的，則每次掃 描至少有一個(gè)屬性值被計(jì)算出來。描至少有一個(gè)屬性值被計(jì)算出來。 28 其中，其中，S有繼承屬性有繼承屬性a，綜合屬性，綜合屬性b；X有繼承屬有繼承屬 性性c，綜合屬性，綜合屬性d；Y有繼承屬性有繼承屬性e，綜合屬

17、性，綜合屬性f； Z有繼承屬性有繼承屬性h，綜合屬性，綜合屬性g。 3、舉例 例例6.9：考慮下表所給的屬性文法考慮下表所給的屬性文法G G。 產(chǎn)生式語義規(guī)則 SXYZ Xx Yy Zz Z.h:=S.a X.c:=Z.g S.b:=X.d-2 Y.e:=S.b X.d:=2*X.c Y.f:=Y.e*3 Z.g:=Z.h+1 6.2 基于屬性文法的處理方法 29 S:a=0 X YZ x y (a) z S:a=0 XYZ：h=0 g=1 xy (b) z 30 S:a=0,b=0 X:c=1 d=2 Y:e=0 f=0 Z：h=0 g=1 x y (d) z S:a=0,b=0 X:c=1

18、 d=2 YZ：h=0 g=1 x y (c) z 31 6.2 基于屬性文法的處理方法 三、一遍掃描的處理方法 1、特點(diǎn) 在語法分析的同時(shí)計(jì)算屬性值，而不是語法分析 構(gòu)造語法樹之后進(jìn)行屬性的計(jì)算，而且無需構(gòu)造 實(shí)際的語法樹。 注：注：采用該處理方法采用該處理方法 ，當(dāng)一個(gè)屬性值不再用于計(jì)，當(dāng)一個(gè)屬性值不再用于計(jì) 算其它屬性值時(shí)，編譯程序就不必再保留這個(gè)屬算其它屬性值時(shí)，編譯程序就不必再保留這個(gè)屬 性值。如果需要，可把語義值存到文件中。性值。如果需要，可把語義值存到文件中。 32 6.2 基于屬性文法的處理方法 2、相關(guān)因素： （1）所使用的語法分析方法 L-屬性文法一遍掃描的自上而下分析 S

19、-屬性文法一遍掃描的自下而上分析 （2）屬性的計(jì)算次序 33 上節(jié)課的內(nèi)容： 屬性文法 屬性 綜合屬性 繼承屬性 產(chǎn)生式+屬性計(jì)算規(guī)則（語義規(guī)則） AX1XK A.a= Xi.x= 屬性計(jì)算方法 1 2 3 S-屬性文法-6.3 L-屬性文法-6.4 34 6.2 基于屬性文法的處理方法 例例2 2：構(gòu)造表達(dá)式產(chǎn)生抽象語法樹（Abstract Syntax Tree）的屬性文法 1、定義：在語法樹中去掉那些對(duì)翻譯不必要 的信息，從而獲得更有效的源程序 中間表示，這種經(jīng)變換后的語法樹 稱之為抽象語法樹。 注：注：抽象語法樹中，操作符和關(guān)鍵字都不作為葉抽象語法樹中，操作符和關(guān)鍵字都不作為葉 結(jié)點(diǎn)出

20、現(xiàn)。結(jié)點(diǎn)出現(xiàn)。 35 抽象語法樹 內(nèi)部結(jié)點(diǎn) 外部結(jié)點(diǎn) 操作符 關(guān)鍵字 標(biāo)識(shí)符 常數(shù) 如：a+3*b的抽象語法樹 + a* 3 b 36 6.2 基于屬性文法的處理方法 2、如何建立表達(dá)式的抽象語法樹 （1）方法：通過為每一個(gè)運(yùn)算分量或運(yùn)算符號(hào)都 建立一個(gè)結(jié)點(diǎn)來為子表達(dá)式建立子樹； 運(yùn)算符號(hào)結(jié)點(diǎn)的各個(gè)子結(jié)點(diǎn)分別表示該運(yùn)算 符號(hào)的各個(gè)運(yùn)算分量的子表達(dá)式組成的子樹的根。 37 6.2 基于屬性文法的處理方法 （2）抽象語法樹中每個(gè)結(jié)點(diǎn)可由包含幾個(gè)域的記錄 來實(shí)現(xiàn)。 運(yùn)算符號(hào)結(jié)點(diǎn)：一個(gè)域運(yùn)算符號(hào) 其它域指向運(yùn)算符號(hào)分量的結(jié)點(diǎn)的指針 結(jié)點(diǎn)：附加的域存放結(jié)點(diǎn)的屬性值/指向?qū)傩灾档闹羔槨?38 6.2 基于

21、屬性文法的處理方法 （3）建立帶有二目算符的表達(dá)式的抽象語法樹結(jié)點(diǎn) 的函數(shù)： mknode(op,left,right) mkleaf(id,entry) mkleaf(num,ral) 每個(gè)函數(shù)均返回一個(gè)指向新建立結(jié)點(diǎn)的指針。 39 6.2 基于屬性文法的處理方法 例例6.10：下面一系列函數(shù)調(diào)用建立了表達(dá)式下面一系列函數(shù)調(diào)用建立了表達(dá)式a-4+ca-4+c的抽的抽 象語法樹（如圖）。在這個(gè)序列中，象語法樹（如圖）。在這個(gè)序列中，p p1 1,p ,p2 2, ,p ,p5 5是指向是指向 結(jié)點(diǎn)的指針，結(jié)點(diǎn)的指針，entryaentrya和和entrycentryc分別是指向符號(hào)表中的標(biāo)分別

22、是指向符號(hào)表中的標(biāo) 識(shí)符識(shí)符a a和和c c的指針。的指針。 id + - idnum 4 to entry for ato entry for c (1) p1:=mkleaf(id,entrya); (2) p2:=mkleaf(num,4); (3) p3:=mknode(-,p1,p2); (4) p4:=mkleaf(id,entryc); (5) p5:=mknode(+,p3,p4) （4）如何設(shè)計(jì)產(chǎn)生表達(dá)式抽象語法樹的屬性文法？ E E1+T E E1-T E T T (E) T id T num 41 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則 E E1+T E E1-T E T T (E

23、) T id T num 為表達(dá)式建立抽象語法樹的屬性文法為表達(dá)式建立抽象語法樹的屬性文法 T. nptr:=mkleaf(num,num.val) T. nptr:=mkleaf(id,id.entry) T. nptr:=E. nptr E. nptr:=T. nptr E.nptr:=mkNode(+,E1. nptr,T. nptr) E. nptr:=mkNode(-,E1. nptr,T. nptr) 42 E nptr T nptr E nptr ET nptr num T nptr id + id id idnum4 4 帶注釋的語法分析樹帶注釋的語法分析樹 To entry

24、for a To entry for c 43 6.3 S-屬性文法的自下而上計(jì)算 1 1、S-S-屬性文法：屬性文法： 只含綜合屬性的屬性文法。只含綜合屬性的屬性文法。 2 2、S-S-屬性文法的翻譯借助于屬性文法的翻譯借助于LRLR分析器來實(shí)現(xiàn)分析器來實(shí)現(xiàn) 輸入串輸入串 輸出輸出 棧棧 分析表分析表 a1 ai an # LR分析程序分析程序 action goto Sm Xm s1 x1 s0 # LR 分 析 器 44 3、對(duì)分析棧改造、對(duì)分析棧改造 狀態(tài)棧 符號(hào)棧 屬性棧 S0 # - Sm-1 x x.val Sm y y.val 45 3、對(duì)分析棧改造、對(duì)分析棧改造 自底向上分析

25、法中： 棧存放已經(jīng)分析過的子樹的內(nèi)容 附加域存放綜合屬性 數(shù)組State：元素一個(gè)指向LR(1)分析表的 指針(索引），指向表中某個(gè)狀態(tài) 文法符號(hào)為隱含在State中而不需存在棧中 數(shù)組Val：符號(hào)的屬性值 Stateval 46 6.1 屬性文法 例例6.2：一個(gè)簡(jiǎn)單臺(tái)式計(jì)算器的屬性文法 產(chǎn)生式語義規(guī)則 LEn EE1+T ET TT1*F TF F(E) Fdigit 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

26、47 狀態(tài)棧 符號(hào)棧 屬性棧 S0 # - Sm-2 E E.val Sm -1 + - 考慮：考慮：EE1+T E.val:=E1.val+T.val Sm T T.val S E E.val 轉(zhuǎn)換為：轉(zhuǎn)換為：EE1+T valntop:=valtop-2+valtop 48 產(chǎn)生式語義規(guī)則 LEn EE1+T ET TT1*F TF F(E) Fdigit 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 把下面文法的

27、語義規(guī)則轉(zhuǎn)換為對(duì)屬性棧的操作：把下面文法的語義規(guī)則轉(zhuǎn)換為對(duì)屬性棧的操作： Print(valtop) Valntop=valtop-2+valtop Valntop=valtop-1 Valntop=valtop-2*valtop 49 6.11 舉例 L En E E1+T E T T T1*F T F F ( E ) F digit 輸入串 3*5+4n 輸入輸入stateval產(chǎn)生式產(chǎn)生式 3*5+4n *5+4n33 *5+4nF3F digit *5+4nT3T F 5+4nT*3 +4nT*53 5 +4nT*F3 5F digit +4nT15T T*F +4nE15E T 4n

28、E+15 nE+415 4 nE+F15 4F digit nE+T15 4T F nE19E E+T En 19 L19L En 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則 E E1+T E E1-T E T T (E) T id T num 為表達(dá)式建立抽象語法樹的屬性文法為表達(dá)式建立抽象語法樹的屬性文法 T. nptr:=mkleaf(num,num.val) T. nptr:=mkleaf(id,id.entry) T. nptr:=E. nptr E.nptr:=mkNode(+,E1. nptr,T. nptr) E. nptr:=mkNode(-,E1. nptr,T. nptr) E. np

29、tr:=T. nptr nptrntop:=mkNode(+,nptrtop-2, nptrtop) nptrntop:=mkNode(-,nptrtop-2, nptrtop) nptrntop=nptrtop-1 nptrntop=mkleaf(id,id.entry) nptrntop=mkleaf(num,num.val) 51 6.4 L-屬性文法和自頂向下翻譯 對(duì)語法分析樹進(jìn)行一次深度優(yōu)先遍歷就能對(duì)語法分析樹進(jìn)行一次深度優(yōu)先遍歷就能 計(jì)算出所有的屬性。計(jì)算出所有的屬性。即即 在自上而下建立語法樹的過程中完成對(duì)屬在自上而下建立語法樹的過程中完成對(duì)屬 性的計(jì)算。性的計(jì)算。 L-屬性文法

30、 52 A X1Xj. Xk AX1.XjXk A.a= Xj.x= 53 6.4 L-屬性文法和自頂向下翻譯 L-屬性文法：屬性文法： 對(duì)任意產(chǎn)生式AX1X2Xn，其每個(gè)語義規(guī)則中 的屬性或者是綜合屬性，或者Xj是一個(gè)繼承屬性， 且僅依賴與 （1）X1X2Xj-1； （2）A的繼承屬性。 S-屬性文法是L-屬性文法的一個(gè)特例。 54 6.4 L-屬性文法和自頂向下翻譯 判定下面屬性文法是否是L-屬性文法。 產(chǎn)生式語義規(guī)則 A LM A QR L.i:=l(A.i) M.i:=m(L.s) R.i:=r(A.i) A.s:=f(Q.s) Q.i:=q(R.s) 55 6.4.1 翻譯模式 屬性

31、文法是語言翻譯的高級(jí)規(guī)范說明。 翻譯模式：翻譯模式： 描述文法符號(hào)屬性的語義規(guī)則和計(jì)算次序。 E TR R addop T pr(addop.lex) R1| T num pr(num.val) 56 翻 譯 模 式 舉 例 E TR R addop T pr(addop.lex) R1| T num pr(num.val) 輸入：952 E T R R R 9Pr(9) TPr() TPr() 5Pr(5) 2Pr(2) 深度優(yōu)先遍歷后 輸出： 952 建立翻譯模式的方法： 1、產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符號(hào)以 前的動(dòng)作中計(jì)算出來； 2、一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊符號(hào)的綜合屬性；

32、 3、產(chǎn)生式左邊非終結(jié)符的綜合屬性只能在它所引用 的所有屬性都計(jì)算出來以后才能計(jì)算。通常這類 動(dòng)作可放在產(chǎn)生式右端的末尾。 58 例：把下面屬性文法修改為翻譯模式： 產(chǎn)生式語義規(guī)則 S B B B1B2 B B1subB2 B text B.ps=10 S.ht=B.ht B1.ps=B.ps B2.ps=B.ps B.ht=max(B1.ht,B2.ht) B1.ps=B.ps B2.ps=shrink(B.ps) B.ht=disp(B1.ht,B2.ht) B.ht=text.h*B.ps 59 S B.ps=10 BS.ht=B.ht B B1.ps=B.ps B1B2.ps=B.ps

33、 B2B.ht=max(B1.ht,B2.ht) 60 6.4.2 自頂向下翻譯 消除左遞歸： 規(guī)則 P P| (1) P P (2) P P| 直接左遞歸： P P1| P2 | | Pm| 1 | 2 | | n | (i ) 消除方法： P 1P | 2P | | nP P 1P| 2P| | mP | 在自頂向下分析過程中，在消除左遞歸的同時(shí) 考慮屬性計(jì)算，這樣許多屬性文法可以使用自頂 向下來實(shí)現(xiàn)，適用綜合和繼承屬性的計(jì)算。 61 EE1+T E.val:=E1.val+T.val EE1T E.val:=E1.valT.val ET E.val:=T.val T(E) T.val:=

34、E.val Tnum T.val:=num.val ET 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.s T(E T.val:=E.val) Tnum T.val:=num.val E T R R R 9 T + T 2 5 計(jì)算表達(dá)式 952 .val=9 .val=5 .val=2 63 ET R.i := T.valR E.val:=R.s R+ T R1.i := R.i +T.valR1 R.s := R1.s RT R1.i := R.i T.val R1 R.s := R1.s R R.s := R.i T(E T.val:=E.val) Tnum T.val:=num