第6章屬性文法及語法制導(dǎo)翻譯 (編譯原理 陳火旺)

1、1本章在編譯程序中的地位 表格管理詞法分析器語法分析器語義分析與中間代碼產(chǎn)生優(yōu)化器目標(biāo)代碼生成器源程序單詞符號語法單位中間代碼中間代碼目標(biāo)代碼出錯(cuò)處理2教學(xué)要求 掌握： 兩種屬性: 綜合屬性，繼承屬性 基于屬性文法的處理方法-語法制導(dǎo)翻譯方法3教學(xué)內(nèi)容 6.1 屬性文法 綜合屬性，繼承屬性，語義規(guī)則，屬性文法 6.2 基于屬性文法的處理方法 語法制導(dǎo)翻譯，依賴圖法計(jì)算屬性，樹遍歷計(jì)算屬性，一遍掃描的處理方法，抽象語法樹4 CH.6 屬性文法和語法制導(dǎo)翻譯 在分析-綜合模式的編譯器中,語義分析是分析過程的最后一個(gè)步驟，只有在這一步才真正開始考慮程序語言的意義，并著手把它們翻譯成某種中間代碼。這一

2、過程通常采用的方法是屬性文法和語法制導(dǎo)翻譯方法。 語法制導(dǎo)翻譯方法的基本思想是，根據(jù)翻譯的需要設(shè)置文法符號的屬性，用屬性描述語法結(jié)構(gòu)的語義，用屬性的計(jì)算完成翻譯。 屬性文法使文法符號屬性值的計(jì)算和產(chǎn)生式相聯(lián)系。隨著語法分析的進(jìn)行，執(zhí)行屬性值的計(jì)算，從而完成語義分析和翻譯的任務(wù)。 56.1 屬性文法 屬性文法, 也稱屬性翻譯文法或語法制導(dǎo)定義,是Knuth在1968年首先提出來的。 屬性：在上下文無關(guān)文法的基礎(chǔ)上為每個(gè)文法符號X(終結(jié)符或非終結(jié)符)配備若干個(gè)相關(guān)的“值”-這些“值”就稱為文法符號X的屬性。 屬性值的設(shè)置和語法結(jié)構(gòu)的語義以及翻譯程序的需要有關(guān)。 屬性代表與文法符號相關(guān)語義信息，如類

3、型、值、代碼序列、符號表內(nèi)容等6屬性、語義規(guī)則、屬性文法 屬性一般分為兩類：綜合屬性和繼承屬性。 屬性和變量一樣，可以在語法分析過程中進(jìn)行計(jì)算和傳遞。 語義規(guī)則：屬性的計(jì)算規(guī)則。屬性的加工和計(jì)算的過程即是語義處理的過程。 屬性文法：以一個(gè)上下文無關(guān)文法為基礎(chǔ), 為每個(gè)文法符號引進(jìn)一組屬性，對文法的每個(gè)產(chǎn)生式都配備一組與之相關(guān)聯(lián)的屬性的計(jì)算規(guī)則(語義規(guī)則), 這樣得到的文法。 屬性文法是對上下文無關(guān)文法的推廣。7屬性文法、語義規(guī)則(1) 屬性文法的形式： 產(chǎn)生式 語義規(guī)則 . A b:=f(c1,c2,ck) 這里, f 是一個(gè)函數(shù), 表示屬性 b 依賴于屬性 c1,c2,ck，而且規(guī)定b: (

4、1) b是A的一個(gè)綜合屬性并且c1,c2,ck是產(chǎn)生式右部文法符號的屬性； 或者 (2) b是產(chǎn)生式右邊某個(gè)文法符號的一個(gè)繼承屬性并且 c1,c2,ck 是A或產(chǎn)生式右部任何文法符號的屬性 。8 屬性文法的說明(1) P136n(1) (1) 終結(jié)符只有綜合屬性終結(jié)符只有綜合屬性, ,它它由詞法分析器提供由詞法分析器提供n例如例如 digit.lexval 表示單詞符號表示單詞符號“數(shù)數(shù)”的詞法值的詞法值 id.entry 表示單詞符號表示單詞符號“標(biāo)識符標(biāo)識符”的符號表入口的符號表入口n(2) (2) 非終結(jié)符既可以有綜合屬性也可以有繼承非終結(jié)符既可以有綜合屬性也可以有繼承屬性屬性，在，在屬

5、性文法的語義規(guī)則中計(jì)算屬性文法的語義規(guī)則中計(jì)算n(3) (3) 關(guān)于屬性計(jì)算的規(guī)定關(guān)于屬性計(jì)算的規(guī)定n 文法的文法的開始符號的所有繼承屬性開始符號的所有繼承屬性作為屬性計(jì)算作為屬性計(jì)算前的初始值。前的初始值。n 一般來講，對出現(xiàn)在產(chǎn)生式一般來講，對出現(xiàn)在產(chǎn)生式 A X1X2Xn左邊左邊的的非終結(jié)符非終結(jié)符A的綜合屬性的綜合屬性和出現(xiàn)在產(chǎn)生式右部的和出現(xiàn)在產(chǎn)生式右部的符號符號Xi的繼承屬性的繼承屬性都必須提供一個(gè)計(jì)算規(guī)則。都必須提供一個(gè)計(jì)算規(guī)則。9屬性文法的說明(2)n 與產(chǎn)生式與產(chǎn)生式 A X1X2Xn 相關(guān)聯(lián)的屬性計(jì)算相關(guān)聯(lián)的屬性計(jì)算不不能有能有A的繼承屬性的繼承屬性和和Xi 的綜合屬性的綜

6、合屬性的計(jì)算規(guī)則。的計(jì)算規(guī)則。n 出現(xiàn)在出現(xiàn)在產(chǎn)生式左邊非終結(jié)符產(chǎn)生式左邊非終結(jié)符A的繼承屬性的繼承屬性和出和出現(xiàn)在產(chǎn)生式右邊符號現(xiàn)在產(chǎn)生式右邊符號Xi 的綜合屬性的綜合屬性由其它產(chǎn)生式由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由屬性計(jì)算器的參數(shù)提供。的屬性規(guī)則計(jì)算或者由屬性計(jì)算器的參數(shù)提供。10屬性文法、語義規(guī)則(2) 屬性文法的形式： 產(chǎn)生式 語義規(guī)則 . A b:=f(c1,c2,ck) 例如 P137.表6.1的屬性文法: EE1+ T E.val := E1.val+ T.val 例如 P139.表6.2的屬性文法: DTL L.in := T.typeLL1 , id L1.in := L.i

7、n綜合屬性綜合屬性綜合屬綜合屬性性繼承屬性繼承屬性繼承屬性繼承屬性繼承屬性繼承屬性11 例例, , P137.P137. 假設(shè)：假設(shè)：產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 A ABC BC A.b:=A.a+B.c A.b:=A.a+B.c C.d C.d:=B.c+1:=B.c+1 A A有綜合屬性有綜合屬性b b和繼承屬性和繼承屬性a a B B有綜合屬性有綜合屬性c c C C有繼承屬性有繼承屬性d d繼承屬性繼承屬性A.aA.a和和綜合綜合屬性屬性B.cB.c在其他適當(dāng)?shù)牡胤接?jì)算。在其他適當(dāng)?shù)牡胤接?jì)算。12語義規(guī)則所描述的工作 語義規(guī)則所描述的工作可以是任何希望的翻譯工作，如: 屬性計(jì)算、靜

8、態(tài)語義檢查、符號表操作、中間代碼生成、報(bào)告出錯(cuò)， 等等。 語義規(guī)則可能產(chǎn)生副作用(如產(chǎn)生代碼)，也可能不是變元的嚴(yán)格函數(shù) b:=f(c1,c2,ck) ，如某個(gè)規(guī)則給出可用的下一個(gè)數(shù)據(jù)單元的地址。這樣的語義規(guī)則通常寫成過程調(diào)用或過程段- 這時(shí)認(rèn)為定義了一個(gè)虛屬性。13屬性文法舉例：P137.表6.1 一個(gè)簡單的臺式計(jì)算器的屬性文法。輸入一個(gè)含+、*、(、)和數(shù)字的算術(shù)表達(dá)式(文法的句子), 計(jì)算并輸出其值, 輸入行以 n 結(jié)束。 產(chǎn)生式 語義規(guī)則 LEn Print(E.val) EE1+T E.val:=E1.val+T.val ET E.val:=T.val TT1*F T.val:=T1

9、.val*F.val TF T.val:=F.val F(E) F.val:=E.val Fdigit F.val:=digit.lexval1. 非終結(jié)符非終結(jié)符E, T, FE, T, F有綜有綜合屬性合屬性val - val - 表達(dá)式值表達(dá)式值2.2. 終結(jié)符終結(jié)符digitdigit有綜合屬有綜合屬性性lexval - lexval - 數(shù)的二進(jìn)制數(shù)的二進(jìn)制值，由詞法分析器提供值，由詞法分析器提供3. 3. 注：注：同一個(gè)產(chǎn)生式的相同一個(gè)產(chǎn)生式的相同非終結(jié)符加上同非終結(jié)符加上下標(biāo)下標(biāo)，以，以區(qū)分這些非終結(jié)符的屬性區(qū)分這些非終結(jié)符的屬性值引用的二義性值引用的二義性14兩種屬性：綜合屬性

10、 綜合屬性用于“自下而上”傳遞信息。 綜合屬性：在語法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。 通常結(jié)合使用自下而上的分析方法在每一個(gè)結(jié)點(diǎn)處使用語義規(guī)則計(jì)算綜合屬性的值 - 由下層子結(jié)點(diǎn)的屬性值計(jì)算上層父結(jié)點(diǎn)的綜合屬性值，隨著自下而上語法分析的進(jìn)行，最終可計(jì)算出開始符號的綜合屬性值。A X1 X2 XnA.b X1. .c1 X2 .c.c2 Xn . ckA X1X2Xn b:=f(c1,c2,ck) 帶注釋的帶注釋的語法樹語法樹15綜合屬性舉例：例6.1 綜合屬性的使用及其自下而上的計(jì)算過程 P137.表6.1臺式計(jì)算器的屬性文法，輸入一個(gè)表達(dá)式(以n結(jié)尾)，計(jì)算并打印其值。

11、例如：輸入表達(dá)式 3*5+4n，輸出數(shù)值19。 P138.圖6.1給出了輸入串3*5+4n的帶注釋的語法樹 屬性化的語法樹。 綜合屬性X.val值隨著自下而上語法分析的進(jìn)行，自下而上的計(jì)算、傳遞和流動(dòng) - 在每次歸約時(shí)執(zhí)行語義規(guī)則，計(jì)算屬性值，最終計(jì)算出開始符號的綜合屬性值，打印出來完成翻譯。見下頁圖16digit lexval digit lexvaldigit lexval F val T1 val F val T val* E1 val F val T val+ E valLnPrint(E.val)翻譯翻譯3 3* *5+45+4n n求表達(dá)式值求表達(dá)式值=3=3=5=5=15=15=

12、4=4=4=19=317兩種屬性：繼承屬性 繼承屬性用于“自上而下”傳遞信息。 繼承屬性：在語法樹中，一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和(或)兄結(jié)點(diǎn)的某些屬性確定。 可以用繼承屬性來表示程序語言結(jié)構(gòu)中的上下文依賴關(guān)系。 繼承屬性的計(jì)算可以結(jié)合自上而下的語法分析進(jìn)行。A X1 X XnA. ck X1. .c1 X.b Xn A X1X2Xn b:=f(c1,c2,ck) 18 表表6.2 6.2 帶有繼承屬性帶有繼承屬性L.inL.in的屬性文法的屬性文法 產(chǎn)生式 語義規(guī)則 DTL L in:= T type T int T type := integer T real T type :=

13、real L L1, id L1 in := L in addtype(id entry, L in) L id addtype(id entry, L in)n 例例6.26.2 說明句的帶有繼承屬性計(jì)算的屬性文法說明句的帶有繼承屬性計(jì)算的屬性文法 T.type 是是 綜合屬性綜合屬性 - 標(biāo)識符標(biāo)識符的類型的類型 L.in 為為 繼承屬性繼承屬性 - 傳遞類傳遞類 型信息型信息19繼承屬性的使用和計(jì)算：例6.2 繼承屬性的使用及其自上而下的計(jì)算過程 P137.表6.2的屬性文法，用繼承屬性 L.in 為說明語句中的各個(gè)標(biāo)識符提供類型信息。 例如：說明語句 real a, b, c; int

14、 i, j, k; T.type是綜合屬性, 由說明語句中的關(guān)鍵字 real / int確定, 結(jié)合產(chǎn)生式Tint 或Treal 賦值 T.type := integer 或 real。Tint T.type:=integerTreal T.type:=realT.typeintintT.typereal20繼承屬性的使用和計(jì)算：例6.2續(xù) 例6.2, P137.表6.2屬性文法，用繼承屬性 in為說明語句中的各個(gè)標(biāo)識符提供類型信息。 L.in 繼承屬性, 在DTL L.in:=T.type LL1 , id L1.in:=L.in 中計(jì)算。D T.type L.inL.inL1.in ， i

15、d 依賴依賴于兄于兄依賴依賴于父于父nAddtype(id.entry, L.in)Addtype(id.entry, L.in)把標(biāo)識符的類型信息把標(biāo)識符的類型信息填入符號表填入符號表, , 入口為入口為id.entry - id.entry - 這個(gè)過程定義這個(gè)過程定義了一個(gè)了一個(gè)虛屬性虛屬性。21圖6.2 說明語句 real id1,id2,id3的帶有繼承屬性的語法樹繼承屬性繼承屬性 in的值自上的值自上而下從左到右計(jì)算、而下從左到右計(jì)算、傳遞和流動(dòng)。傳遞和流動(dòng)。三個(gè)三個(gè)L結(jié)點(diǎn)的結(jié)點(diǎn)的 L.in分分別給出標(biāo)識符別給出標(biāo)識符id1、id2和和id3的類型。的類型。過程過程addtype(

16、id.entry,L.in)把把 id 的類型填入符號的類型填入符號表。表。id3T.type=realDL.in=realL.in=realrealL.in=real,id1id2,226.2 基于屬性文法的處理方法 屬性文法： 產(chǎn)生式 語義規(guī)則 . A b:=f(c1,c2,ck) 語義規(guī)則的計(jì)算可以執(zhí)行任何翻譯動(dòng)作。對輸入串的翻譯也就是根據(jù)語義規(guī)則進(jìn)行計(jì)算得出結(jié)果。 屬性文法是比較抽象的翻譯說明，隱藏了一些實(shí)現(xiàn)細(xì)節(jié), 主要是無須指明翻譯時(shí)語義規(guī)則的計(jì)算次序。 本節(jié)討論語義規(guī)則的計(jì)算方法，指明屬性文法中語義規(guī)則的計(jì)算次序，從而把語義規(guī)則改造為計(jì)算屬性的語義程序，把靜態(tài)的語義規(guī)則改寫為可動(dòng)態(tài)

17、執(zhí)行的語義動(dòng)作 - 語法制導(dǎo)翻譯方法。23語法制導(dǎo)翻譯法 語法制導(dǎo)翻譯法：由源程序的語法結(jié)構(gòu)所驅(qū)動(dòng)的處理辦法。 這種處理方法是基于屬性文法的處理過程： 對單詞符串進(jìn)行語法分析, 構(gòu)造帶屬性的語法樹 根據(jù)需要遍歷語法樹, 并在語法樹的各結(jié)點(diǎn)處按語義規(guī)則進(jìn)行計(jì)算即得翻譯結(jié)果。 P139.圖6.3 語法制導(dǎo)翻譯的輪廓: 輸入串語法樹(帶屬性注釋)語法分析深度優(yōu)先樹遍歷對輸入串的翻譯結(jié)果進(jìn)行計(jì)算拓?fù)渑判?語義規(guī)則 計(jì)算次序 結(jié)點(diǎn)屬性間依賴 關(guān)系的依賴圖 構(gòu)造24 所謂遍歷是指沿著某條搜索路線，依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。25一遍掃描的語法制導(dǎo)翻譯一

18、遍掃描的語法制導(dǎo)翻譯n一個(gè)具體的一個(gè)具體的語法制導(dǎo)翻譯語法制導(dǎo)翻譯的實(shí)現(xiàn)不一定非要的實(shí)現(xiàn)不一定非要按圖按圖6.36.3的輪廓不可。在某些情況下可用一遍的輪廓不可。在某些情況下可用一遍掃描實(shí)現(xiàn)屬性文法的語義規(guī)則計(jì)算掃描實(shí)現(xiàn)屬性文法的語義規(guī)則計(jì)算 - - 即即在在語法分析的同時(shí)完成語義規(guī)則的計(jì)算語法分析的同時(shí)完成語義規(guī)則的計(jì)算。無須無須明顯地構(gòu)造語法樹或依賴圖明顯地構(gòu)造語法樹或依賴圖。n此節(jié)以后的各節(jié)以及此節(jié)以后的各節(jié)以及CH7.CH7.都討論這種特殊方都討論這種特殊方法法 - - 一遍掃描的語法制導(dǎo)翻譯方法。一遍掃描的語法制導(dǎo)翻譯方法。n一遍掃描的語法制導(dǎo)翻譯輪廓一遍掃描的語法制導(dǎo)翻譯輪廓: :

19、 輸入串輸入串 翻譯結(jié)果翻譯結(jié)果語法分析的同時(shí)語法分析的同時(shí)完成語義規(guī)則的計(jì)算完成語義規(guī)則的計(jì)算26 6.2.1 依賴圖 語義規(guī)則建立了屬性之間的依賴關(guān)系，這些關(guān)系可以用圖來表示，這樣的圖稱為屬性依賴圖。 語法樹結(jié)點(diǎn)屬性的依賴圖是一個(gè)有向圖： 結(jié)點(diǎn)：語法樹結(jié)點(diǎn)的屬性(綜合屬性或繼承屬性) 有向邊：屬性的依賴關(guān)系，如果屬性b依賴于屬性c，即b:= f(c)，則:n語義規(guī)則語義規(guī)則 b:= f(c1,c2, , ck)，b可能是一個(gè)虛綜合屬性可能是一個(gè)虛綜合屬性(即即沒有沒有b, f是一個(gè)過程是一個(gè)過程)，其依，其依賴圖見右圖。賴圖見右圖。n依賴圖構(gòu)造方法見依賴圖構(gòu)造方法見P140.bcbc1ck

20、c227 依賴圖：例6.3 簡例: 下面屬性文法的依賴圖： AXY A.a:=f(X.x, Y.y) X.i:=g(A.a, Y.y) n例例6.3: 下面的屬性文法的依賴圖下面的屬性文法的依賴圖nEE1+E2 E.val:=E1.val+E2.val語法樹語法樹EE1 + E2依賴圖依賴圖 P141. 圖圖6.4E.valE1.valE2.valA.aX.iX.xY.yA XY28例例6.4 6.4 圖圖6.5 句子句子 real id1,id2,id3的語法樹及依賴圖的語法樹及依賴圖TLLid3Lid2Did1real,4typein 5L.in:=T.typein 7L1.in:=L.i

21、nin 9L1.in:=L.in3 entry6addtype(id.entry,L.in )2 entry8addtype(id.entry,L.in )1 entry10addtype(id.entry,L.in )結(jié)點(diǎn)1、2、3是id.entry屬性結(jié)點(diǎn)6、8、10代表虛屬性有向邊表示屬性的依賴關(guān)系數(shù)字標(biāo)識結(jié)點(diǎn)表示計(jì)算次序29良定義的屬性文法 對語義規(guī)則 b:= f(c1,c2, , ck)來說, 只有在屬性 c1,c2, ,ck均已知的情況才可以使用來計(jì)算b。 但，有時(shí)會(huì)出現(xiàn)一個(gè)屬性對另一個(gè)屬性的循環(huán)依賴關(guān)系。 如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么該屬性文法為良定義的。為了

22、設(shè)計(jì)編譯程序，我們只處理良定義的屬性文法。 例如 設(shè)p，c1，c2都是屬性，以下計(jì)算規(guī)則就無法對p求值。 p:=f1(c1) c1:=f2(c2) c2:=f3(p) DAG圖：良定義屬性文法的依賴圖， 無環(huán)有向圖(Directed Acyclic Graph) pc2c130 依賴圖法：屬性的計(jì)算次序 1. 一個(gè)有向非循環(huán)圖(DAG圖)的拓?fù)湫? 是圖中結(jié)點(diǎn)的任何順序 m1, m2, , mk, 使得有向邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)。 也就是說，如果 mi mj 是 mi 到 mj 的一條邊，那么在序列中 mi 必須出現(xiàn)在 mj 之前。 2.一個(gè)依賴圖(DAG圖)的任何拓?fù)渑判蚨?/p>

23、給出一個(gè)語法樹中結(jié)點(diǎn)的語義規(guī)則計(jì)算的有效順序。 這就是說，在拓?fù)渑判蛑校谝粋€(gè)結(jié)點(diǎn)上，語義規(guī)則 b:= f(c1,c2, ck)中的屬性 c1,c2, ck 在計(jì)算b以前都是可用的。31n例例6.5 P141.圖圖6 . 5的依賴圖的一個(gè)拓?fù)渑判蚴牵旱囊蕾噲D的一個(gè)拓?fù)渑判蚴牵?1， 2， 3，4，5，6，7，8，9，10n由此拓?fù)湫蚩梢缘玫较旅娴某绦蛴纱送負(fù)湫蚩梢缘玫较旅娴某绦?an代表與代表與n有關(guān)的屬有關(guān)的屬性性), 該程序把該程序把3個(gè)標(biāo)識符個(gè)標(biāo)識符 a, b, c 的類型信息的類型信息(real)填入填入符號表中每個(gè)標(biāo)識符對應(yīng)的符號表項(xiàng)中。符號表中每個(gè)標(biāo)識符對應(yīng)的符號表項(xiàng)中。程序程序

24、a4:=real; 語義規(guī)則語義規(guī)則 T.type:=real a5:=a4; L.in:=T.type addtype(id3 entry, a5); 虛屬性虛屬性 6 a7:=a5; L1.in:=L.in addtype(id2 entry, a7); 虛屬性虛屬性 8 a9:=a7; L1.in:=L.in addtype(id1 entry, a9); 虛屬性虛屬性 10依賴圖法屬性的計(jì)算次序：例依賴圖法屬性的計(jì)算次序：例 32n屬性文法說明的語法制導(dǎo)翻譯是很精確的：屬性文法說明的語法制導(dǎo)翻譯是很精確的：n(1) (1) 基礎(chǔ)文法用于建立輸入串的語法分析基礎(chǔ)文法用于建立輸入串的語法分

25、析樹樹( (可帶屬性注釋可帶屬性注釋); );n(2) (2) 構(gòu)造對應(yīng)語法樹的依賴圖構(gòu)造對應(yīng)語法樹的依賴圖; ;n(3) (3) 對依賴圖進(jìn)行拓?fù)渑判驅(qū)σ蕾噲D進(jìn)行拓?fù)渑判? ;n(4) (4) 從拓?fù)湫虻玫接?jì)算語義規(guī)則的次序從拓?fù)湫虻玫接?jì)算語義規(guī)則的次序; ;n(5) (5) 按此次序計(jì)算語義規(guī)則便得到輸入串按此次序計(jì)算語義規(guī)則便得到輸入串的翻譯結(jié)果。的翻譯結(jié)果。依賴圖法屬性的計(jì)算次序：說明依賴圖法屬性的計(jì)算次序：說明 336.2.2 樹遍歷的屬性計(jì)算方法 通過語法樹遍歷計(jì)算屬性值的方法有很多種。這些方法都假設(shè)： 1. 語法樹已經(jīng)建立起來了，并且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性

26、。 2. 然后以某種次序遍歷語法樹，直至計(jì)算出所有結(jié)點(diǎn)的屬性值。 最常用的遍歷方法是深度優(yōu)先，對語法樹自上而下從左到右遍歷的方法。對遍歷到的結(jié)點(diǎn)計(jì)算其所有能夠計(jì)算的屬性值。可能需要使用多次樹遍歷，直到把所有的結(jié)點(diǎn)的所有屬性都計(jì)算出來。 P142. 有一個(gè)深度優(yōu)先樹遍歷的算法，對任何良定義的屬性文法進(jìn)行屬性的計(jì)算。用例子說明。34深度優(yōu)先樹遍歷計(jì)算屬性：例6.6 P143.表6.3的屬性文法。屬性S.a(=0)繼, S.b綜; X.c繼, X.d綜; Y.e繼, Y.f綜; Z.h繼, Z.g綜 圖6.6 產(chǎn)生式 語義規(guī)則 SXYZ X.c:=Z.g Y.e:=S.b Z.h:=S.a S.b:

27、=X.d-2 Xx X.d:=2*X.c Yy Y.f:=Y.e*3 Zz Z.g:=Z.h+1xyz.h=0第一次遍歷第一次遍歷 S.a=0 XYZ.g=1.d=2.c=1.b=0第二次遍歷第二次遍歷 .e=0.f=0第三次遍歷第三次遍歷 35 6.2.3 一遍掃描的處理方法 與樹遍歷的屬性計(jì)算方法不同，一遍掃描的處理方法是在語法分析的同時(shí)計(jì)算屬性值。 這種屬性計(jì)算方法與兩個(gè)因素密切相關(guān): 1. 所采用的語法分析方法(自上而下或自下而上)。 2. 屬性的計(jì)算次序，即語法分析到什么時(shí)候計(jì)算屬性。 一遍掃描的處理方法語義規(guī)則執(zhí)行的時(shí)間: 1. 在自上而下語法分析中，若一個(gè)產(chǎn)生式匹配輸入串成功時(shí)執(zhí)

28、行與此產(chǎn)生式相應(yīng)的語義規(guī)則。 2. 在自下而上語法分析中，當(dāng)一個(gè)產(chǎn)生式被用于進(jìn)行歸約時(shí)，此產(chǎn)生式相應(yīng)的語義規(guī)則就被計(jì)算。36一遍掃描的處理方法 按一遍掃描的編譯程序模型來理解語法制導(dǎo)翻譯方法，直觀上說是為基礎(chǔ)文法的每個(gè)產(chǎn)生式配上一組語義規(guī)則，并且在語法分析的同時(shí)執(zhí)行這些語義規(guī)則。 一遍掃描的屬性計(jì)算方法是語法分析工作和語義規(guī)則的計(jì)算穿插進(jìn)行。但以語法分析作主導(dǎo)。 S-屬性文法(僅含綜合屬性的屬性文法)可用于一遍掃描的自下而上分析。 L-屬性文法(含有繼承屬性的屬性文法)可用于一遍掃描的自上而下分析。376.2.4 抽象語法樹 語法制導(dǎo)翻譯以語法樹作基礎(chǔ), 實(shí)際上, 語法樹可以作為一種合適的中間

29、語言形式。 現(xiàn)在對語法樹進(jìn)行改造，去掉那些對翻譯不必要的信息，將語法樹進(jìn)行抽象 - 抽象語法樹。 在表達(dá)式的抽象語法樹中，運(yùn)算符、關(guān)鍵字不作葉子結(jié)點(diǎn)而作為內(nèi)部結(jié)點(diǎn)，葉子結(jié)點(diǎn)只是運(yùn)算量。 抽象語法樹也可以屬性化，給結(jié)點(diǎn)加上屬性變成帶附注的抽象語法樹。 語法制導(dǎo)翻譯既可以基于語法分析樹也可以基于抽象語法樹進(jìn)行，采用的基本方法是一樣的。38抽象語法樹：簡例 例，為下面文法的句子 a-4+c 建立抽象語法樹。 E E+T | ET | T T (E) T id | num 為每個(gè)運(yùn)算量或運(yùn)算符號都建立一個(gè)結(jié)點(diǎn)。 可以根據(jù)表達(dá)式的運(yùn)算順序自下而上的構(gòu)造 - 手工構(gòu)造。a+c4抽象語法樹抽象語法樹運(yùn)算符作

30、內(nèi)運(yùn)算符作內(nèi)部結(jié)點(diǎn)部結(jié)點(diǎn)id(a)E E TE + TTnum(4)id(c )語法樹語法樹39抽象語法樹的實(shí)現(xiàn) 抽象語法樹中的每一個(gè)結(jié)點(diǎn)可以由包含幾個(gè)域的記錄來實(shí)現(xiàn)；有向邊用指針實(shí)現(xiàn)。 在一個(gè)運(yùn)算量對應(yīng)的結(jié)點(diǎn)(葉結(jié))中,一個(gè)域標(biāo)識運(yùn)算量，另一個(gè)域是該運(yùn)算量的屬性值(或指針)。 在一個(gè)運(yùn)算符號對應(yīng)的結(jié)點(diǎn)中,一個(gè)域標(biāo)識運(yùn)算符號，其它域包含指向運(yùn)算分量的結(jié)點(diǎn)的指針。運(yùn)算符號通常叫做這個(gè)結(jié)點(diǎn)的標(biāo)號。 進(jìn)行翻譯時(shí)，抽象語法樹中的結(jié)點(diǎn)可能會(huì)用附加域來存放結(jié)點(diǎn)的屬性值(或指向?qū)傩缘闹羔槪?。numvalid .op . .To entry of id右子樹根結(jié)右子樹根結(jié)左子樹根結(jié)左子樹根結(jié)40n建立表達(dá)式的抽象語法樹使用的函數(shù)建立表達(dá)式的抽象語法樹使用的函數(shù), 這些函數(shù)返回這些函數(shù)返回新建立結(jié)點(diǎn)的指針。新建立結(jié)點(diǎn)的指針。n1. mknode(op, left, right) 建立一個(gè)建立一個(gè)運(yùn)算符號結(jié)點(diǎn)運(yùn)算符號結(jié)點(diǎn)，標(biāo)號是標(biāo)號是 op, 兩個(gè)域兩個(gè)域 left 和和 right 指向左右運(yùn)算分指向左右運(yùn)算分量結(jié)點(diǎn)的指針。量