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

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

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

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

4、。 66.1 屬性文法2 2、語義規(guī)則、語義規(guī)則 為為文法的每一文法的每一個產(chǎn)個產(chǎn)生式配生式配備備的的屬屬性的性的計計算算規(guī)則規(guī)則，稱為語義規(guī)則稱為語義規(guī)則。3 3、屬性文法、屬性文法上下文無上下文無關(guān)關(guān)文法文法 + 語義規(guī)則語義規(guī)則 = 屬屬性文法性文法76.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是一個函數(shù)；是一個函數(shù)； (2) 或者或者b A的綜合屬性的綜合屬性，且，且c1,c2,ck是是中文中文 法符號的屬性；法符號的屬性； (3)

5、 或者或者b 中某個文法符號的繼承屬性，中某個文法符號的繼承屬性，且且 c1,c2,ck是是A或或中任何文法符號的屬性。中任何文法符號的屬性。屬性屬性b依賴于屬性依賴于屬性c1,c2,ck86.1 屬性文法2、VTVN的屬性(1) VT 只有只有綜綜合合屬屬性，由性，由詞詞法分析器提供。法分析器提供。(2) VN 既既可有可有綜綜合合屬屬性也可有性也可有繼繼承承屬屬性，性， 文法文法開開始符始符號號S的所有的所有繼繼承承屬屬性作性作為屬為屬性性 計計算前的初始算前的初始值值。96.1 屬性文法3、屬性的計算/獲得(1) 產(chǎn)產(chǎn)生式右生式右邊邊的的繼繼承承屬屬性性 產(chǎn)產(chǎn)生式左生式左邊邊的的綜綜合合

6、屬屬性性(2) 產(chǎn)產(chǎn)生式左生式左邊邊的的繼繼承承屬屬性性 產(chǎn)產(chǎn)生式右生式右邊邊的的綜綜合合屬屬性性由該產(chǎn)生式提供的計由該產(chǎn)生式提供的計算規(guī)則計算獲得算規(guī)則計算獲得由其它產(chǎn)生式的屬性由其它產(chǎn)生式的屬性規(guī)則計算或由屬性計規(guī)則計算或由屬性計算器的參數(shù)提供算器的參數(shù)提供106.1 屬性文法例例6.1：C.d:=B.c+1A.b:=A.a+B.c 產(chǎn)生式 ABC 的規(guī)則：C.d右部繼承屬性右部繼承屬性A.b左部綜合屬性左部綜合屬性A.a左部繼承屬性左部繼承屬性B.c右部綜合屬性右部綜合屬性116.1 屬性文法例例6.2：一個簡單臺式計算器的屬性文法產(chǎn)生式語義規(guī)則LEnEE1+TETTT1*FTFF(E)

7、FdigitPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval12產(chǎn)生式語義規(guī)則DTLTintTrealLL1,idLidaddtype(id.entry,L.in)T.type:=integerT.type:=realL1.in:=L.inL.in:=T.typeaddtype(id.entry,L.in)13產(chǎn)生式語義規(guī)則SXYZXxYyZzZ.h:=S.aX.c:=Z.gS.b:=X.d-2Y.e:=S.bX.d:=2*X.cY.

8、f:=Y.e*3Z.g:=Z.h+1146.1 屬性文法二、綜合屬性1 1、語法樹中、語法樹中, ,一個結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)一個結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn) 的屬性值確定。的屬性值確定。2 2、通常使用自底向上的方法在每一個結(jié)點(diǎn)處使用語、通常使用自底向上的方法在每一個結(jié)點(diǎn)處使用語 義規(guī)則計算綜合屬性的值。義規(guī)則計算綜合屬性的值。S屬性文法：屬性文法：僅使用綜合屬性的屬性文法僅使用綜合屬性的屬性文法156.1 屬性文法例例6.3：例6.2的表中定義的屬性文法說明了一個臺式計算器，該計算器讀入一個可含數(shù)字、括號和+、*運(yùn)算符的算術(shù)表達(dá)式，并打印表達(dá)式的值，每個輸入行以n作為結(jié)束。假設(shè)表達(dá)式

9、為3*5+4，后跟一個換行符n。則程序打印數(shù)值則程序打印數(shù)值19。其帶注釋的語法樹其帶注釋的語法樹16三、繼承屬性1 1、語法樹中、語法樹中, ,一個結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)一個結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和或兄弟結(jié)點(diǎn)的某些屬性確定。點(diǎn)和或兄弟結(jié)點(diǎn)的某些屬性確定。6.1 屬性文法、用繼承屬性來表示程序設(shè)計語言結(jié)構(gòu)中的上下、用繼承屬性來表示程序設(shè)計語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便。文依賴關(guān)系很方便。176.1 屬性文法例例6.：帶繼承屬性L.in的屬性文法產(chǎn)生式語義規(guī)則DTLTintTrealLL1,idLidaddtype(id.entry,L.in)T.type:=integerT.t

10、ype:=realL1.in:=L.inL.in:=T.typeaddtype(id.entry,L.in)18輸入串輸入串: real id1,id2,id3的帶注釋的語法樹的帶注釋的語法樹D DT.type=realT.type=realL.in=realL.in=realrealrealL.in=realL.in=realL.in=realL.in=real，id2id2id3id3，id1id1191 1、構(gòu)造依賴圖的方法、構(gòu)造依賴圖的方法: :輸入串語法樹依賴圖語義規(guī)則的計算次序進(jìn)行語義規(guī)則計算，得到翻譯結(jié)果6.2 基于屬性文法的處理方法2 2、遍歷語法樹的方法、遍歷語法樹的方法單詞

11、符號串單詞符號串語法分析語法分析語法分析樹語法分析樹遍歷遍歷計算計算3 3、可用一遍掃描實(shí)現(xiàn)屬性文法的語義規(guī)則計算。、可用一遍掃描實(shí)現(xiàn)屬性文法的語義規(guī)則計算。20一、依賴圖1、定義：一個表示一棵語法樹中結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互依賴關(guān)系的有向圖。6.2 基于屬性文法的處理方法212、依賴圖的構(gòu)造方法（1）構(gòu)造依賴圖以前，先為每一個包含過程調(diào)用的語義規(guī)則引入一個虛綜合屬性b，在每一個語義規(guī)則均寫成b:=f（c1 1，c2 2， ck k）的形式；（2）在依賴圖中為每一個屬性設(shè)置一個結(jié)點(diǎn)；（3）若屬性b依賴于屬性c，則從屬性c的結(jié)點(diǎn)有一條有向邊連到屬性b的結(jié)點(diǎn)。6.2 基于屬性文法的處理方

12、法22例例6.5：AXY A.a:=f(X.x,Y.y) X.i:=g(A.a,Y.y)6.2 基于屬性文法的處理方法233、例題例例6.6：將下面的產(chǎn)生式應(yīng)用于語法樹中產(chǎn)生式語義規(guī)則EE1+E2 E.val:=E1.val+E2.valE EE E1 1 + + E E2 2 valvalval E.Val是從E1.val和E2.val綜合得出6.2 基于屬性文法的處理方法24產(chǎn)生式語義規(guī)則DTLTintTrealLL1,idLidaddtype(id.entry,L.in)T.type:=integerT.type:=realL1.in:=L.inL.in:=T.typeaddtype(i

13、d.entry,L.in)25D DT TL LrealrealL LL L，id2id2id3id3，id1id1a4：=reala5：=a4Addtype(id3.entry，a5)；a7：=a5；addtype(id2.entry，a7)；a9：=a7；Addtype(id1.entry，a9)；拓?fù)湫蛄衋1,a2,a3,a4,a5,a6,a7,a8,a9,a1026二、樹遍歷的屬性計算方法1、方法A、前提：假設(shè)語法樹已經(jīng)建立起來了，且樹中已 有如下信息：開始符號繼承屬性 終結(jié)符綜合屬性B、遍歷：以某種次序遍歷語法樹，直至計算出所 有屬性。 遍歷方法：深度優(yōu)先，從左到右遍歷方法：深度優(yōu)先

14、，從左到右6.2 基于屬性文法的處理方法276.2 基于屬性文法的處理方法2、算法While While 還有未被計算的屬性還有未被計算的屬性 dodoVisitNode(S)VisitNode(S)/ /* *S S是開始符號是開始符號* */ /procedure VisitNode(N:Node);procedure VisitNode(N:Node);beginbegin If N If N是一個非終結(jié)符是一個非終結(jié)符 thenthen / /* * 假設(shè)它的產(chǎn)生式為假設(shè)它的產(chǎn)生式為N NX X1 1XXm m * */ / for i:=1 to m do for i:=1 to m

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

16、屬有繼承屬性性c，綜合屬性，綜合屬性d；Y有繼承屬性有繼承屬性e，綜合屬性，綜合屬性f；Z有繼承屬性有繼承屬性h，綜合屬性，綜合屬性g。 3、舉例例例6.9：考慮下表所給的屬性文法考慮下表所給的屬性文法G G。產(chǎn)生式語義規(guī)則SXYZXxYyZzZ.h:=S.aX.c:=Z.gS.b:=X.d-2Y.e:=S.bX.d:=2*X.cY.f:=Y.e*3Z.g:=Z.h+16.2 基于屬性文法的處理方法29S:a=0XYZxy(a)zS:a=0XYZ：h=0 g=1xy(b)z30S:a=0,b=0X:c=1 d=2Y:e=0 f=0Z：h=0 g=1xy(d)zS:a=0,b=0X:c=1 d=

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

18、計算次序33上節(jié)課的內(nèi)容：屬性文法屬性綜合屬性繼承屬性產(chǎn)生式+屬性計算規(guī)則（語義規(guī)則）AX1XK A.a=Xi.x= 屬性計算方法123 S-屬性文法-6.3L-屬性文法-6.4346.2 基于屬性文法的處理方法例例2 2：構(gòu)造表達(dá)式產(chǎn)生抽象語法樹（Abstract Syntax Tree）的屬性文法1、定義：在語法樹中去掉那些對翻譯不必要的信息，從而獲得更有效的源程序中間表示，這種經(jīng)變換后的語法樹稱之為抽象語法樹。注：注：抽象語法樹中，操作符和關(guān)鍵字都不作為葉抽象語法樹中，操作符和關(guān)鍵字都不作為葉 結(jié)點(diǎn)出現(xiàn)。結(jié)點(diǎn)出現(xiàn)。35抽象語法樹內(nèi)部結(jié)點(diǎn)外部結(jié)點(diǎn)操作符關(guān)鍵字標(biāo)識符常數(shù)如：a+3*b的抽象語

19、法樹+a*3b366.2 基于屬性文法的處理方法2、如何建立表達(dá)式的抽象語法樹（1）方法：通過為每一個運(yùn)算分量或運(yùn)算符號都建立一個結(jié)點(diǎn)來為子表達(dá)式建立子樹； 運(yùn)算符號結(jié)點(diǎn)的各個子結(jié)點(diǎn)分別表示該運(yùn)算符號的各個運(yùn)算分量的子表達(dá)式組成的子樹的根。376.2 基于屬性文法的處理方法（2）抽象語法樹中每個結(jié)點(diǎn)可由包含幾個域的記錄來實(shí)現(xiàn)。 運(yùn)算符號結(jié)點(diǎn)：一個域運(yùn)算符號 其它域指向運(yùn)算符號分量的結(jié)點(diǎn)的指針 結(jié)點(diǎn)：附加的域存放結(jié)點(diǎn)的屬性值/指向?qū)傩灾档闹羔槨?86.2 基于屬性文法的處理方法（3）建立帶有二目算符的表達(dá)式的抽象語法樹結(jié)點(diǎn)的函數(shù)： mknode(op,left,right) mkleaf(id,

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

21、 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è)計產(chǎn)生表達(dá)式抽象語法樹的屬性文法？E E1+TE E1-TE TT (E)T idT num41產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則E E1+TE E1-TE TT (E)T idT num為表達(dá)式建立抽象語法樹的屬性文法為表達(dá)式建立抽象語法樹的屬性文法T. nptr:=mkleaf(num,num.val)T. nptr:=mkleaf(id,id

22、.entry)T. nptr:=E. nptrE. nptr:=T. nptrE.nptr:=mkNode(+,E1. nptr,T. nptr)E. nptr:=mkNode(-,E1. nptr,T. nptr)42E nptrTnptrE nptrET nptrnumTnptrid+id ididnum4 4帶注釋的語法分析樹帶注釋的語法分析樹To entry for aTo entry for c436.3 S-屬性文法的自下而上計算1 1、S-S-屬性文法：屬性文法： 只含綜合屬性的屬性文法。只含綜合屬性的屬性文法。2 2、S-S-屬性文法的翻譯借助于屬性文法的翻譯借助于LRLR分析

23、器來實(shí)現(xiàn)分析器來實(shí)現(xiàn)輸入串輸入串輸出輸出棧棧 分析表分析表a1 ai an #LR分析程序分析程序action gotoSm Xm s1 x1s0 #LR分析器443、對分析棧改造、對分析棧改造 狀態(tài)棧 符號棧 屬性棧S0 # -Sm-1 x x.valSm y y.val453、對分析棧改造、對分析棧改造 自底向上分析法中：棧存放已經(jīng)分析過的子樹的內(nèi)容附加域存放綜合屬性 數(shù)組State：元素一個指向LR(1)分析表的指針(索引），指向表中某個狀態(tài) 文法符號為隱含在State中而不需存在棧中數(shù)組Val：符號的屬性值Stateval466.1 屬性文法例例6.2：一個簡單臺式計算器的屬性文法產(chǎn)生

24、式語義規(guī)則LEnEE1+TETTT1*FTFF(E)FdigitPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval47狀態(tài)棧 符號棧 屬性棧S0 # -Sm-2 E E.valSm -1 + -考慮：考慮：EE1+T E.val:=E1.val+T.valSm T T.valS E E.val轉(zhuǎn)換為：轉(zhuǎn)換為：EE1+T valntop:=valtop-2+valtop48產(chǎn)生式語義規(guī)則LEnEE1+TETTT1*FTFF(E)Fdigi

25、tPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval把下面文法的語義規(guī)則轉(zhuǎn)換為對屬性棧的操作：把下面文法的語義規(guī)則轉(zhuǎn)換為對屬性棧的操作：Print(valtop)Valntop=valtop-2+valtopValntop=valtop-1Valntop=valtop-2*valtop496.11 舉例L En E E1+TE TT T1*FT FF ( E )F digit 輸入串 3*5+4n輸入輸入stateval產(chǎn)生式產(chǎn)生式3*

26、5+4n*5+4n33*5+4nF3F digit*5+4nT3T F5+4nT*3 +4nT*53 5+4nT*F3 5F digit+4nT15T T*F+4nE15E T4nE+15 nE+415 4nE+F15 4F digitnE+T15 4T FnE19E E+TEn19 L19L En產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則E E1+TE E1-TE TT (E)T idT num為表達(dá)式建立抽象語法樹的屬性文法為表達(dá)式建立抽象語法樹的屬性文法T. nptr:=mkleaf(num,num.val)T. nptr:=mkleaf(id,id.entry)T. nptr:=E. nptrE.n

27、ptr:=mkNode(+,E1. nptr,T. nptr)E. nptr:=mkNode(-,E1. nptr,T. nptr) E. nptr:=T. nptrnptrntop:=mkNode(+,nptrtop-2, nptrtop)nptrntop:=mkNode(-,nptrtop-2, nptrtop)nptrntop=nptrtop-1nptrntop=mkleaf(id,id.entry)nptrntop=mkleaf(num,num.val)516.4 L-屬性文法和自頂向下翻譯對語法分析樹進(jìn)行一次深度優(yōu)先遍歷就能對語法分析樹進(jìn)行一次深度優(yōu)先遍歷就能計算出所有的屬性。計算出

28、所有的屬性。即即在自上而下建立語法樹的過程中完成對屬在自上而下建立語法樹的過程中完成對屬性的計算。性的計算。L-屬性文法52AX1Xj.XkAX1.XjXkA.a=Xj.x=536.4 L-屬性文法和自頂向下翻譯L-屬性文法：屬性文法： 對任意產(chǎn)生式AX1X2Xn，其每個語義規(guī)則中的屬性或者是綜合屬性，或者Xj是一個繼承屬性，且僅依賴與 （1）X1X2Xj-1； （2）A的繼承屬性。S-屬性文法是L-屬性文法的一個特例。546.4 L-屬性文法和自頂向下翻譯 判定下面屬性文法是否是L-屬性文法。產(chǎn)生式語義規(guī)則A LMA QRL.i:=l(A.i)M.i:=m(L.s)R.i:=r(A.i)A.

29、s:=f(Q.s)Q.i:=q(R.s)556.4.1 翻譯模式 屬性文法是語言翻譯的高級規(guī)范說明。 翻譯模式：翻譯模式： 描述文法符號屬性的語義規(guī)則和計算次序。 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) 輸入：952ETRRR9Pr(9) TPr() TPr()5Pr(5)2Pr(2)深度優(yōu)先遍歷后輸出： 952建立翻譯模式的方法：1、產(chǎn)生式右邊的符號的繼承屬性必須在這個符號以前的動作中計算出來；2、一個動作不能引用

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

31、max(B1.ht,B2.ht)606.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í)現(xiàn)，適用綜合和繼承屬性的計算。61EE1+T E.val:=E1.val+T.valEE1T E.val:=E1.valT.valET E.val:=T.valT(E) T.val:=E.valTnum T.val:=num

32、.valET R.i := T.val R E.val:=R.sR+ T R1.i := R.i +T.val R1 R.s := R1.sR T R1.i := R.i T.val R1 R.s := R1.sR R.s := R.sT(E T.val:=E.val)Tnum T.val:=num.valE T R R R 9 T+ T 2 5計算表達(dá)式 952 .val=9 .val=5 .val=263ET R.i := T.valR E.val:=R.sR+ T R1.i := R.i +T.valR1 R.s := R1.sRT R1.i := R.i T.val R1 R.s := R1.sR R.s := R.i T(E