《編譯原理》第5章語法制導翻譯

《《編譯原理》第5章語法制導翻譯》由會員分享，可在線閱讀，更多相關《《編譯原理》第5章語法制導翻譯（98頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、？？為什么進行詞法和語法分析 ？？用A進行歸約表達的是什么意思 看：operand+term EE1+T E1的值+T的值的結果作為E的值即：取來E1的值和T的值做加法運算，結果作為E的值 E.val=E1.val+T.val,第五章 語法制導翻譯,翻譯的任務 首先是語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標代碼。 基本思想 根據(jù)翻譯的需要設置文法符號的屬性，以描述語法結構的語義。 例如，一個變量的屬性有類型，層次，存儲地址等。表達式的屬性有類型，值等。 屬性值的計算和產(chǎn)生式相聯(lián)系。隨著語法分析的進行，執(zhí)行屬性值的計算，完成語義分析和翻譯的任務。,5.1 語法制導翻譯概述,語法制導翻

2、譯的概念描述 在進行語法分析的同時，完成相應的語義處理 EE1 + E2E.val:=E1.val+E2.val 語法結構具有規(guī)定的語義 問題：如何根據(jù)被識別出的語法成分進行語義處理？,1. 語義分析的任務,語義檢查 例：類型、運算、維數(shù)、越界 語義處理 例：變量的存儲分配 例：表達式的求值 例：語句的翻譯（中間代碼的生成） 總目標：生成等價的中間代碼,2. 代碼結構,計算學科：對信息（數(shù)據(jù)表示）描述和變換算法的系統(tǒng)研究 變換：源、目標以及源與目標的對應關系 語句的代碼結構 語句分類： 說明語句符號表的查填 可執(zhí)行語句指令代碼,3. 典型處理方法,對應每一個產(chǎn)生式編制一個語義子程序，當一個產(chǎn)生

3、式獲得匹配時，調用相應的語義子程序實現(xiàn)語義檢查與翻譯 EE1 + TE.val:=E1.val+T.val TT1 * FT.val:=T1.val*F.val F idF.val:=id.val 適宜在完成歸約的時候進行,3. 典型處理方法,在產(chǎn)生式的右部的適當位置，插入相應的語義動作，按照分析的進程，執(zhí)行遇到的語義動作 D T L.in := T.type L T int T.type := integer T real T.type := real L L1.in := L.in L1,id 語義可以看成是相應文法符號的屬性 適宜在進行推導時完成,語義翻譯的流程,輸 入 符 號 串,,

4、分 析 樹,,依 賴 圖,,語 義 規(guī) 則 的 計 算,實際上，編譯中語義翻譯的實現(xiàn)并不是按圖中的流程處理的；而是隨語法分析的進展，識別出一個語法結構，就對它的語義進行分析和翻譯。,語法制導定義是對上下文無關文法的推廣 每個文法符號都有一個相關的屬性集。 綜合屬性:通過分析樹中其子節(jié)點的屬性值計算出來； 繼承屬性:由該節(jié)點的兄弟節(jié)點及父節(jié)點的屬性值計算出來； 依賴圖 語義規(guī)則建立了屬性之間的依賴關系，這些關系可以用圖來表示，這樣的圖稱為依賴圖。,,屬性,5.1 語法制導定義(Syntax-directed definitions),在一個語法制導定義中，AP都有與 之相關聯(lián)的一套語義

5、規(guī)則，規(guī)則形式為 b：= f（c1，c2，，ck）， f是一個函數(shù)，而且或者 1b是A的一個綜合屬性并且c1，c2，，ck 是中的符號的屬性，或者 2b是中的符號的一個繼承屬性并且c1， c2，，ck是A或中的任何文法符號的屬性。 在兩種情況下，都說屬性b依賴于屬性c1，c2，，ck。,5.1.1 語法制導定義的形式,例5.1 臺式計算器程序的語法制導定義（圖52),產(chǎn)生式 語義規(guī)則,,LEn print(Eval)(可看作是L的虛屬性) E E1+T E val := E1 val+T val E T E val := T val T T1*F

6、 T val := T1 val*F val T F T val := F val F (E) F val := E val F digit F val := digitlexval,,S-屬性定義 僅僅使用綜合屬性的語法制導定義。 結點屬性值的計算正好和自底向上分析建立分析樹結點同步進行。 例 5 .2 輸入：3*5+4n,,5.1.2 綜合屬性,digitlexval:=3,Fval:=3,,,Tval:=3,digitlexval:=5,,Fval:=5,Tval:=15,,,*,,,Eval:=15,+,digitlexval:=4,,Fval:=4,

7、Tval:=4,,Eval:=19,,,,L,,n,,,,,,,,,,,,,,,綜合屬性值的計算方法 對于s-屬性定義，通常使用自底向上的分析方法，在建立每一個結點處使用語義規(guī)則來計算綜合屬性值，即在用哪個產(chǎn)生式進行歸約后，就執(zhí)行那個產(chǎn)生式的s-屬性定義計算屬性的值，從葉結點到根結點進行計算。 5.1.3 繼承屬性 繼承屬性值是由此結點的父結點和或兄弟結點的某些屬性值來決定的。 例5 . 3 變量說明的屬性定義 int a,b,c,,表5.2 帶有繼承屬性L.in的語法制導定義,,,,產(chǎn)生式 語義規(guī)則 DTL Lin:=T type T int T ty

8、pe :=integer T real T type :=real L L1,id L1 in :=L in addtype(id entry,L in) L id addtype(id entry,L in),,,T,L,L,id3,L,id2,D,id1,,,,,,,,real,,,,,,,,1 entry,2 entry,3 entry,4 type,in 5,6,in 7,8,in 9,10,,,,,,,,,,依賴圖的構造方法 for 分析樹中的每個結點n do for 與結點n對應的文法符號的每個屬性a do 在依賴圖中為a構

9、造一個結點； for 分析樹的每個結點n do for 結點n所用產(chǎn)生式對應的每條 語義規(guī)則 b:f（c1，c2，，ck ) do for i:=1 to k do 從結點ci到結點b構造一條有向邊；,5.1.4 依賴圖_獲得語義規(guī)則的計算順序,例5-5 圖55分析樹的依賴圖,,拓撲排序 一個無環(huán)有向圖的拓撲排序是圖中 結點的任何順序m1，m2，，mk，使得 邊必須是從序列中前面的結點指向后面的 結點，也就是說，如果mimj是mi到mj的 一條邊,那么在 序列中mi必須出現(xiàn)在mj的 前面。 若依賴圖中無環(huán)，則存在一個拓撲排序，它就是屬性值的計算順序。,5.1.5

10、 計算順序,1， 2， 3，4，5，6，7，8，9，10 a4:=real; a5:=a4; addtype(id3entry,a5); a7:=a5; addtype(id2entry,a7); a9:=a7; addtype(id1entry,a9);,例5 . 6 圖5 . 7的拓撲排序是：,分析樹法: 輸入串分析樹依賴圖計算次序 基于規(guī)則的方法： 在構造編譯器時，用手工或專門的工具來分析語義規(guī)則,確定屬性值的計算順序。 忽略語義規(guī)則的方法：在分析過程中翻譯，那么計算順序由分析方法來確定而表面上與語義規(guī)則無關。這種方法限制了能被實現(xiàn)的語法制導定義的種類。 后兩

11、種方法不必顯式構造依賴圖，因此時空效率更高。,計算語義規(guī)則的方法,抽象語法（abstract syntax） 從具體語法中抽象出語言結構的本質性的東西，而不考慮語言的具體符號表示，從而可簡化語義的形式描述。 在不同的語言中賦值語句有不同的寫法： x=y; x:=y; yx 等等，可以用抽象形式 assignment(variable,expression) 把前面各種具體形式統(tǒng)一起來。,5.2 語法樹（syntax tree）的構造,表示程序層次結構的樹，它把分析樹中對語義無關緊要的成分去掉，是分析樹的抽象形式 ，也稱作語法結構樹，或結構樹。 語法樹是常用的一種中間表示形式。 把語法分

12、析和翻譯分開。語法分析過程中完成翻譯有許多優(yōu)點，但也有一些不足： 1.適于語法分析的文法可能不完全反映語言成分的自然層次結構； 2. 由于語法分析方法的限制，對分析樹結點的訪問順序和翻譯需要的訪問順序不一致。,語法樹,產(chǎn)生式sif B then S1 else S2的語法樹 if-then-else | B S1 S2 賦值語句的語法樹 assignment variable expression 在語法樹中，運算符號和關鍵字都不在葉結點，而是在內部結點中出現(xiàn)。,,,5.2.1 語法樹,構造表達式的語法樹使用的函數(shù) 1. mknode(op,left,

13、right) 建立一個標記為op的運算符結點，兩個域left和right是指向左右運算對象的指針。 2mkleaf(id,entry) 建立一個標記為id的標識符結點,其域entry是指向該標識符在符號表中相應表項的指針。 3. mkleaf(num,val) 建立一個標記為num的數(shù)結點，域val用于保存該數(shù)的值。返回指向新建立結點的指針。,5.2.2 構造表達式的語法樹,id,,,to entry a,num 4,,,,,,,id,,,to entry c,+,,,,圖5-8 a-4+c的語法樹,,5.2.3 構造語法樹的語法制導定義,產(chǎn)生式 語義規(guī)則 EE1+T E

14、.nptr:=mknode(+,E1.nptr,T.nptr) E E1-T E.nptr:=mknode(-,E1.nptr,T.nptr) E T E.nptr:=T.nptr T (E) T.nptr:=E.nptr T id T.nptr:=mkleaf(id,id.entry) T num T.nptr:=mkleaf(num,num.val),,,圖5-10 a-4+c的語法樹的構造,,無環(huán)有向圖 （Directed Acyclic Graph，簡稱dag) 用途：提取表達式中的公共子表達式，以取得目標程序的局部優(yōu)化。 方法：執(zhí)行mknode和mkleaf時，檢查是

15、否已有相同的結點，若有，則返回相應結點的指針。,5.2.4 表達式的無環(huán)有向圖,例5.9 表達式 aa*(b-c)+(b-c)*d 的dag,+,*,d,+,*,a,,c,b,,,,,,,,,,在分析棧中使用一個附加的域來存放綜合屬性值。下圖為一個帶有綜合屬性值域的分析棧：,state,val,...,X,X.x,Y,...,Y.y,...,...,Z,Z.z,top,,,5.3 S-屬性定義及其自底向上的計算,A b:=f(c1,c2,,ck) b是A的綜合屬性，ci(1 ik)是中符號的屬性。綜合屬性的值是在自底向上的分析過程中，每次歸約之前進行計算的。 AXYZ Aa:=f(X x,

16、Y y,Z z),A a,X x Y y Z z,,,,top,state,val,...,...,X,X.x,Y,Y.y,Z,Z.z,,state,val,...,...,A,A .a,,top,定義式 A .a:=f(X.x, Y.y, Z.z)（抽象）變成valntop:=f(valtop-2,valtop-1,valtop)（具體可執(zhí)行代碼）。在執(zhí)行代碼段之前執(zhí)行： ntop:=top-r+1 r是句柄的長度 執(zhí)行代碼段后執(zhí)行： top:=ntop;,產(chǎn)生式 代碼段(和圖52對比） LEn printf(valntop) E E+T valntop:=valtop-2

17、+valtop E T T T*F valntop:=valtop-2*valtop T F F (E) valntop:=valtop-1 F digit,,,例5.10 用LR分析器實現(xiàn)臺式計算器(圖516）,表5.5 翻譯輸入3*5+4n所做的移動,輸入 state val 使用的產(chǎn)生式,3*5+4n - -,*5+4n 3 3,*5+4n F 3 Fdigit,*5+4n T 3 TF,5+4n T* 3-,+4n T* 5 3-5,+4n T* F 3-5 F digit,+4n T

18、 15 T T*F,+4n E 15 E T,4n E+ 15-,n E+4 15-4,n E+F 15-4 F digit,n E+T 15-4 T F,n E 19 E E+T,En 19 -,L 19 L En,采用自底向上分析，例如LR分析，首先給出S-屬性定義，然后，把S-屬性定義變成可執(zhí)行的代碼段，這就構成了翻譯程序。象一座建筑，語法分析是構架，歸約處有一個“掛鉤”，語義分析和翻譯的代碼段（語義子程序）就掛在這個鉤子上。這樣，隨著語法分析的進行，歸約前調用相應的語義子程序,

19、完成翻譯的任務。,總結,在語法分析過程中進行語義分析和翻譯，屬 性的計算順序受到語法分析建立分析樹結點順序的限制。 一種自然的計算屬性的順序是按深度優(yōu)先訪問分析樹結點的順序，它適應多種自底向上和自頂向下的翻譯方法。 L-屬性定義 可用于按深度優(yōu)先順序計算屬性值。,5.4 L-屬性定義,procedure dfvisit(n:node); begin for n 的每個子結點m(從左至右) do begin 計算m的繼承屬性； dfvisit(m) end; 計算n的綜合屬性 end;,深度優(yōu)先順序計算屬性,定義 一個語法制導定義是

20、L-屬性定義，如果AX1X2XnP,其每一個語義規(guī)則中的每一個屬性都是一個綜合屬性，或是Xj(1j n)的一個繼承屬性，這個繼承屬性僅依賴于 1.產(chǎn)生式中Xj的左邊符號X1，X2，Xj-1的屬性； 2A的繼承屬性。 每一個S-屬性定義都是L-屬性定義。,5.4.1 L-屬性定義,圖519 非L-屬性的語法制導定義,產(chǎn)生式,語義規(guī)則,ALM A QR,L.i:=l(A.i) M.i:=m(L.s) A.s:=f(M.s) R.i:=r(A.i) Q.i:=q(R.s) A.s:=f(Q.s),圖519的語法制導定義不是L-屬性定義 文法符號Q的繼承屬性依賴于它右邊文法符號R的屬性,,定義

21、翻譯模式是語法制導定義的一種便于翻譯的書寫形式。其中屬性與文法符號相對應，語義規(guī)則或語義動作用花括號 括起來，可被插入到產(chǎn)生式右部的任何合適的位置上。 這是一種語法分析和語義動作交錯的表示法，它表達在按深度優(yōu)先遍歷分析樹的過程中何時執(zhí)行語義動作。 翻譯模式給出了使用語義規(guī)則進行計算的順序?？煽闯墒欠治鲞^程中翻譯的注釋。,5.4.2 翻譯模式,將帶有+號和-號的中綴表達式翻譯成后綴表達式： ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val) 把語義動作看成終結符號，輸入9-5+2,其分析樹如圖520，當按深度優(yōu)先遍歷它，

22、執(zhí)行遍歷中訪問的語義動作，將輸出 9 5 - 2 + 它是輸入表達式9-5+2的后綴式。,例5.12 一個簡單的翻譯模式,圖5.10 9-5+2的帶語義動作的分析樹,,條件：語法制導定義是L-屬性定義 保證語義動作不會引用還沒有計算的屬性值。 1. 只需要綜合屬性的情況： 為每一個語義規(guī)則建立一個包含賦值的動作，并把這個動作放在相應的產(chǎn)生式右邊的末尾。 例如：TT1*F Tval:=T1 val*F val TT1*F Tval:=T1 val*F val,設計翻譯模式（根據(jù)語法制導定義）,2. 既有綜合屬性又有繼承屬性 產(chǎn)生式右邊的符號的繼承屬性必須在這個符號以前的動

23、作中計算出來。 一個動作不能引用這個動作右邊符號的綜合屬性。 產(chǎn)生式左邊非終結符號的綜合屬性只有在它所引用的所有屬性都計算出來以后才能計算。計算這種屬性的動作通常可放在產(chǎn)生式右端的末尾。,設計翻譯模式（根據(jù)語法制導定義）,下面的翻譯模式不滿足要求： SA1A2 A1in:=1; A2 in:=2 A a print(A in) 例5.13 從L-屬性制導定義建立一個滿足上面 要求的翻譯模式。 使用文法產(chǎn)生的語言是數(shù)學排版語言EQN E sub 1val 編排結果,E,1,val,B.ps:=10 S.ht:=B.ht B1.ps:=B.ps B2.ps:=B.ps

24、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,SB B B1 B2 B B1 sub B2 B text,產(chǎn)生式,語義規(guī)則,圖5-22 盒子的大小和高度的語法制導定義,,,,B是盒子； BBB表示兩個盒子的并置； BB sub B表示第二個盒子是第一個盒子的下標； ps是繼承屬性，影響公式的高度；正文的實際高度 等于正文的標準高度乘以B.ps； B的高度由綜合屬性ht表示 ； texth可根據(jù)text的性質查表得到； shrink把B2的尺

25、寸縮小30%； disp把B2向下偏置。,SB.ps:=10 BS.ht:=B.ht B B1.ps:=B.ps B1 B2.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) BtextB.ht:=text.h*B.ps,從圖5-22構造的翻譯模式,用翻譯模式構造自頂向下翻譯。 5.5.1 從翻譯模式中消除左遞歸 對于一個翻譯模式，若采用自頂向下分析，必須消除左遞歸和提取左公因子，在改寫基本

26、文法時考慮屬性值的計算。 例5.14 圖524的帶左遞歸的文法的翻譯模式被轉換成圖525的帶右遞歸的文法的翻譯模式。,5.5 自頂向下的翻譯,EE1+T E val:=E1val+T val E E1-T E val:=E1 val-T val E T E.val:=T val T (E) T val:=E val T num T val:=num val,帶左遞歸的文法的翻譯模式,ET Ri:=T val RE val:=R s R TR1i:=R.i+T. val R1R. s:=R1 s R- TR1 i:=R i-Tval

27、 R1R s:=R1 s RR s:=R i T（ E ） T val:=E.val Tnum T val:=num val,經(jīng)過轉換的帶有右遞歸文法的翻譯模式,E val=6,Tval=9,R i=9; R s= 6,,,9,,,,T val=5,,5,,R i=4; R s= 6,+,T val=2,R i=6; R s= 6,,,,2,,,,,,,,,,,,,,,,,圖526 表達式9-5+2的計算,左遞歸翻譯模式 AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x) （5.2） 每一個文法符號都有一個綜合屬性，用相應的小寫字母表示，g和

28、f是任意函數(shù)。 消除左遞歸，文法轉換成 AX R RY R| （5.3）,關于左遞歸翻譯模式更一般化的討論,再考慮語義動作，翻譯模式變?yōu)椋? AX Ri:=f(X x) R A. a:=R. s RY R1 i:=g（R i,Y y） R1 R s:=R1 s RR s:=R i （5.4） 經(jīng)過轉換的翻譯模式與圖525中一樣,使用R的繼承屬性i和綜合屬性s。 （5.2）和（5.4）的結果是一樣的, 為什么？,關于左遞歸翻譯模式更一般化的討論,A a=g(g(f(X x),Y1 y),Y2 y),A a=g(f(X x),Y1 y)

29、,A a=f(X x),Y2,Y1,X,,,,,,,,,,,(a),,輸入：XY1Y2,A,Ri=f(X x),R i=g(f(X x),Y1 y),R i=g(g(f(X x),Y1 y),Y2 y),,Y2,Y1,X,,,,,,,,,,,,,,,,(b),EE1+T Enptr :=mknode(+,E1 nptr,T nptr) EE1-T Enptr :=mknode(-,E1 nptr,T nptr) ET Enptr :=T nptr 從翻譯模式中消除左遞歸，變成圖528的翻譯模式。,例5.15 表達式建立語法樹的翻譯模式,ET Ri:=T nptr R E n

30、ptr:=R s R T R1 i:=mknode(+,R i,T nptr) R1 R s:=R1 s R- T R1 i:=mknode(-,R i,T nptr) R1 R s:=R1 s R R s:=R i T( E ) T nptr:=E nptr Tid T nptr:=mkleaf(id, id entry) Tnum T nptr:=mkleaf(num,num val),使用繼承屬性構造語法樹,E,i,R,s,T,id,R,-,T,num,i,R,T,,,,,,,,,+,id,,,,,,id,,num 4,,id,,-,,,+,,,to

31、entry for a,to entry for c,,,,,,,nptr,nptr,nptr,,,,,,,算法5.1 預測語法制導翻譯器的建立 輸入：一個帶有適合預測分析的基礎文法 的語法制導翻譯模式。 輸出：一個語法制導翻譯器的代碼。 方法：在預測分析器中加入語義動作代碼。 1AVN,建立一個可遞歸調用的函數(shù)過程A。為A的每一個繼承屬性都設置一個形式參數(shù)，函數(shù)的返回值是A的綜合屬性值。 2.函數(shù)過程A的代碼（指用符號形式表示的數(shù)據(jù)和程序）要根據(jù)當前的輸入符號來決定使用哪一個產(chǎn)生式。,5.5.2 預測翻譯器的設計,,,3與每一個產(chǎn)生式有關的代碼，從左到右根椐產(chǎn)生式右部是單詞符號、非終結

32、符號還是語義動作，分別是： （a）對于帶有綜合屬性x的單詞符號X，x存放在X.x中，Match(X)。 （b）對于BVN，編寫一個賦值語句c：= B（b1, b2, ，bk)其中， b1, b2, ，bk是繼承屬性，c是綜合屬性。 （c）對于每個動作，動作的代碼抄進翻譯器中，用代表屬性的變量來代替對屬性的每一次引用。,5.5.2 預測翻譯器的設計,例5.16 ： Raddop TR1i:=mknode（addop lexeme， R i， T nptr） R1R.s:=R1.s R R.s:=R.i （55） 遞歸下降構造語法樹 function

33、R（in: syntax-tree-node）： syntaX-tree-node； var nptr,i1,s1,s： syntax-tree-node; addoplexeme:char；, IF lookahead=addop THEN /*產(chǎn)生式Raddop T R*/ addoplexeme:=lexval; match(addop); nptr:=T; i1:=mknode(addoplexeme,in,nptr); s1:=R(i1); s:=s1 ; ELSE s:=

34、in; /*產(chǎn)生式R*/ return (s); ,5.6 L屬性的自底向上計算,在自底向上分析的框架中實現(xiàn)L屬性定義的方法 它能實現(xiàn)任何基于LL(1)文法的L屬性定義 也能實現(xiàn)許多（但不是所有的）基于LR(1) 的L屬性定義,5.6 L屬性的自底向上計算,5.6.1 刪除翻譯方案中嵌入的動作 E T R R + T print (+)R1 | T print ()R1 | T num print (num.val),5.6 L屬性的自底向上計算,5.6.1 刪除翻譯方案中嵌入的動作 E T R R + T print (+)R1 | T print ()R1 | T num pr

35、int (num.val) 在文法中加入產(chǎn)生的標記非終結符，讓每個嵌入動作由不同標記非終結符M代表，并把該動作放在產(chǎn)生式M 的右端,5.6 L屬性的自底向上計算,5.6.1 刪除翻譯方案中嵌入的動作 E T R R + T print (+)R1 | T print ()R1 | T num print (num.val) 在文法中加入產(chǎn)生的標記非終結符，讓每個嵌入動作由不同標記非終結符M代表，并把該動作放在產(chǎn)生式M 的右端 E T R R + T M R1 | T N R1 | T num print (num.val) M print (+) N print (),5.6 L屬性的自

36、底向上計算,5.6.2 分析棧上的繼承屬性 屬性位置能預測 例 int p, q, r D T L.in = T.type L T int T. type = integer T real T. type = real L L1.in = L.in L1, id addtype (id.entry, L.in ) L id addtype (id.entry, L.in ),5.6 L屬性的自底向上計算,,5.6 L屬性的自底向上計算,屬性的位置不能預測 S aACC.i = A.s S bABCC.i = A.s C cC.s = g(C.i),5.6 L屬性的自底向上計算,屬性的

37、位置不能預測 S aACC.i = A.s S bABCC.i = A.s C cC.s = g(C.i) 增加標記非終結符 S aACC.i = A.s S bABMCM.i = A.s; C.i = M.s C cC.s = g(C.i) M M.s = M.i,5.6 L屬性的自底向上計算,5.6.3 模擬繼承屬性的計算 繼承屬性是某個綜合屬性的一個函數(shù) S aACC.i = f (A.s) C cC.s = g(C.i) 增加標記非終結符，把f(A.s)的計算移到對標記非終結符歸約時進行 S aANCN.i = A.s; C.i = N.s N N.s = f (N.i) C cC.s

38、 = g(C.i),5.6 L屬性的自底向上計算,例 數(shù)學排版語言EQN 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 ,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.

39、6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.7 遞歸計算,回顧：語法制導定義的實現(xiàn) 分析樹方法 邊分析邊進行屬性計算，只能完成L屬性計算（忽略規(guī)則的方法） 本節(jié)介紹先分析后計算的方法，不局限于L屬性計算（基于規(guī)則的方法） 為每個非終結符構造一個屬性計算函數(shù)，但是該函數(shù)不含語法分析部分 為非終結符的不同綜合屬性構造不同的函數(shù),5.7 遞歸計算,5.7.1 自左向右遍歷 為B構造一個屬性計算函數(shù) S B.ps = 10 BS.ht = B.ht B B1.ps = B.ps B1B2.ps

40、 = 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 ,5.7 遞歸計算,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結點n的產(chǎn)生式 of B B1 B2: ps1 = ps; ht1 = B(child(n,1), ps1); ps2 = ps; ht2 = B(child(n,2), ps2); return

41、max(ht1, ht2);,B B1.ps = B.ps B1B2.ps = B.ps B2B.ht = max(B1.ht, B2.ht ) ,5.7 遞歸計算,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結點n的產(chǎn)生式 of B B1 sub B2: ps1 = ps; ht1 = B(child(n,1), ps1); ps2 = shrink(ps); ht2 = B(child(n,3), ps2); return disp(ht1, ht2);,B B1.ps = B.ps B1sub B2.ps = sh

42、rink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) ,5.7 遞歸計算,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結點n的產(chǎn)生式 of B text: return ps text.h; default: error end,B textB.ht = text.h B.ps ,5.7 遞歸計算,5.7.2 其它遍歷方法 按所需次序訪問結點的子結點，可用于非L屬性定義 A LM L.i = l(A.i); M.i = m(L.s); A.s = f (M.s) A QR R.i = r(A.i

43、); Q.i = q(R.s); A.s = f (Q.s),5.7 遞歸計算,A LM:/* 從左到右的次序 */ li = l(ai); ls = L(child(n,1), li); mi = m(ls); ms = M(child(n,2), mi); return f (ms);,5.7 遞歸計算,A QR:/* 從右到左的次序 */ ri = r(ai); rs = R(child(n,2), ri); qi = q(rs); qs = Q(child(n,1), qi); return f (qs);,5.7 遞歸計算,5.7.3 多次遍歷 S E E.i = g(E.s);

44、S.r = E.t E E1E2 E.s = fs(E1.s, E2.s); E1.i = fi1(E.i); E2.i = fi2(E.i); E.t = ft (E1.t, E2.t) E id E.s = id.s; E.t = h(E.i),5.7 遞歸計算,綜合屬性t不可能和s在同一遍掃描中完成計算,5.7 遞歸計算,function Sr(n); begin s = Es(child(n,1)); i = g(s); t = Et(child(n,1), i); return t end;,5.7 遞歸計算,function Es(n); | function Et(n,

45、i); begin | begin case 在結點n的產(chǎn)生式 of | case 在結點n的產(chǎn)生式 of E E1 E2: |E E1 E2: s1 = Es(child(n,1));| i1= fi1(i); s2 = Es(child(n,2));| t1 = Et(child(n,1), i1); return fs(s1, s2); | i2 = fi2(i); E id: | t2 = Et(child(n,2), i2); return id.s; | return ft(t1, t2); default: |E id: error | return h(i); end |default: end; | error |end | end;,本章要點,語義規(guī)則的兩種描述方法：語法制導的定義和翻譯方案 設計簡單問題的語法制導定義和翻譯方案，這是本章的重點和難點 語義規(guī)則的三種計算方法：分析樹方法、基于規(guī)則的方法和忽略規(guī)則的方法 S屬性的自底向上計算（邊分析邊計算） L屬性的自上而下計算（邊分析邊計算） L屬性的自底向上計算（邊分析邊計算） 遞歸計算（先分析后計算）,