《語法制導(dǎo)翻譯》PPT課件.ppt

語法制導(dǎo)翻譯,？為什么進行詞法和語法分析 ？用A進行歸約表達的是什么意思 看：operand+term EE1+T E1的值+T的值的結(jié)果作為E的值即：取來E1的值和T的值做加法運算，結(jié)果作為E的值 E.val=E1.val+T.val,第五章 語法制導(dǎo)翻譯,翻譯的任務(wù) 首先是語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標代碼。 基本思想 根據(jù)翻譯的需要設(shè)置文法符號的屬性，以描述語法結(jié)構(gòu)的語義。 例如，一個變量的屬性有類型，層次，存儲地址等。表達式的屬性有類型，值等。 屬性值的計算和產(chǎn)生式相聯(lián)系。隨著語法分析的進行，執(zhí)行屬性值的計算，完成語義分析和翻譯的任務(wù)。,5.1 語法制導(dǎo)翻譯概述,語法制導(dǎo)翻譯的概念描述 在進行語法分析的同時，完成相應(yīng)的語義處理 EE1 + E2 E.val:=E1.val+E2.val 語法結(jié)構(gòu)具有規(guī)定的語義 問題：如何根據(jù)被識別出的語法成分進行語義處理？,1. 語義分析的任務(wù),語義檢查 例：類型、運算、維數(shù)、越界 語義處理 例：變量的存儲分配 例：表達式的求值 例：語句的翻譯（中間代碼的生成） 總目標：生成等價的中間代碼,2. 代碼結(jié)構(gòu),計算學(xué)科：對信息（數(shù)據(jù)表示）描述和變換算法的系統(tǒng)研究 變換：源、目標以及源與目標的對應(yīng)關(guān)系 語句的代碼結(jié)構(gòu) 語句分類： 說明語句符號表的查填 可執(zhí)行語句指令代碼,3. 典型處理方法,對應(yīng)每一個產(chǎn)生式編制一個語義子程序，當(dāng)一個產(chǎn)生式獲得匹配時，調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯 EE1 + T E.val:=E1.val+T.val TT1 * F T.val:=T1.val*F.val F id F.val:=id.val 適宜在完成歸約的時候進行,3. 典型處理方法,在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分析的進程，執(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 語義可以看成是相應(yīng)文法符號的屬性 適宜在進行推導(dǎo)時完成,語義翻譯的流程,輸 入 符 號 串,分 析 樹,依 賴 圖,語 義 規(guī) 則 的 計 算,實際上，編譯中語義翻譯的實現(xiàn)并不是按圖中的流程處理的；而是隨語法分析的進展，識別出一個語法結(jié)構(gòu)，就對它的語義進行分析和翻譯。,語法制導(dǎo)定義是對上下文無關(guān)文法的推廣 每個文法符號都有一個相關(guān)的屬性集。 綜合屬性:通過分析樹中其子節(jié)點的屬性值計算出來； 繼承屬性:由該節(jié)點的兄弟節(jié)點及父節(jié)點的屬性值計算出來； 依賴圖 語義規(guī)則建立了屬性之間的依賴關(guān)系，這些關(guān)系可以用圖來表示，這樣的圖稱為依賴圖。,屬性,5.1 語法制導(dǎo)定義(Syntax-directed definitions),在一個語法制導(dǎo)定義中，AP都有與 之相關(guān)聯(lián)的一套語義規(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 語法制導(dǎo)定義的形式,例5.1 臺式計算器程序的語法制導(dǎo)定義（圖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 T val := T1 val*F val T F T val := F val F (E) F val := E val F digit F val := digitlexval,S-屬性定義 僅僅使用綜合屬性的語法制導(dǎo)定義。 結(jié)點屬性值的計算正好和自底向上分析建立分析樹結(jié)點同步進行。 例 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,Tval:=4,Eval:=19,L,n,綜合屬性值的計算方法 對于s-屬性定義，通常使用自底向上的分析方法，在建立每一個結(jié)點處使用語義規(guī)則來計算綜合屬性值，即在用哪個產(chǎn)生式進行歸約后，就執(zhí)行那個產(chǎn)生式的s-屬性定義計算屬性的值，從葉結(jié)點到根結(jié)點進行計算。 5.1.3 繼承屬性 繼承屬性值是由此結(jié)點的父結(jié)點和或兄弟結(jié)點的某些屬性值來決定的。 例5 . 3 變量說明的屬性定義 int a,b,c,表5.2 帶有繼承屬性L.in的語法制導(dǎo)定義,產(chǎn)生式 語義規(guī)則 DTL Lin:=T type T int T type :=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,依賴圖的構(gòu)造方法 for 分析樹中的每個結(jié)點n do for 與結(jié)點n對應(yīng)的文法符號的每個屬性a do 在依賴圖中為a構(gòu)造一個結(jié)點； for 分析樹的每個結(jié)點n do for 結(jié)點n所用產(chǎn)生式對應(yīng)的每條 語義規(guī)則 b:f（c1，c2，ck ) do for i:=1 to k do 從結(jié)點ci到結(jié)點b構(gòu)造一條有向邊；,5.1.4 依賴圖_獲得語義規(guī)則的計算順序,例5-5 圖55分析樹的依賴圖,拓撲排序 一個無環(huán)有向圖的拓撲排序是圖中 結(jié)點的任何順序m1，m2，mk，使得 邊必須是從序列中前面的結(jié)點指向后面的 結(jié)點，也就是說，如果mimj是mi到mj的 一條邊,那么在 序列中mi必須出現(xiàn)在mj的 前面。 若依賴圖中無環(huán)，則存在一個拓撲排序，它就是屬性值的計算順序。,5.1.5 計算順序,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ī)則的方法： 在構(gòu)造編譯器時，用手工或?qū)ｉT的工具來分析語義規(guī)則,確定屬性值的計算順序。 忽略語義規(guī)則的方法：在分析過程中翻譯，那么計算順序由分析方法來確定而表面上與語義規(guī)則無關(guān)。這種方法限制了能被實現(xiàn)的語法制導(dǎo)定義的種類。 后兩種方法不必顯式構(gòu)造依賴圖，因此時空效率更高。,計算語義規(guī)則的方法,抽象語法（abstract syntax） 從具體語法中抽象出語言結(jié)構(gòu)的本質(zhì)性的東西，而不考慮語言的具體符號表示，從而可簡化語義的形式描述。 在不同的語言中賦值語句有不同的寫法： x=y; x:=y; yx 等等，可以用抽象形式 assignment(variable,expression) 把前面各種具體形式統(tǒng)一起來。,5.2 語法樹（syntax tree）的構(gòu)造,表示程序?qū)哟谓Y(jié)構(gòu)的樹，它把分析樹中對語義無關(guān)緊要的成分去掉，是分析樹的抽象形式 ，也稱作語法結(jié)構(gòu)樹，或結(jié)構(gòu)樹。 語法樹是常用的一種中間表示形式。 把語法分析和翻譯分開。語法分析過程中完成翻譯有許多優(yōu)點，但也有一些不足： 1.適于語法分析的文法可能不完全反映語言成分的自然層次結(jié)構(gòu)； 2. 由于語法分析方法的限制，對分析樹結(jié)點的訪問順序和翻譯需要的訪問順序不一致。,語法樹,產(chǎn)生式sif B then S1 else S2的語法樹 if-then-else | B S1 S2 賦值語句的語法樹 assignment variable expression 在語法樹中，運算符號和關(guān)鍵字都不在葉結(jié)點，而是在內(nèi)部結(jié)點中出現(xiàn)。,5.2.1 語法樹,構(gòu)造表達式的語法樹使用的函數(shù) 1. mknode(op,left,right) 建立一個標記為op的運算符結(jié)點，兩個域left和right是指向左右運算對象的指針。 2mkleaf(id,entry) 建立一個標記為id的標識符結(jié)點,其域entry是指向該標識符在符號表中相應(yīng)表項的指針。 3. mkleaf(num,val) 建立一個標記為num的數(shù)結(jié)點，域val用于保存該數(shù)的值。返回指向新建立結(jié)點的指針。,5.2.2 構(gòu)造表達式的語法樹,id,to entry a,num 4,id,to entry c,+,圖5-8 a-4+c的語法樹,5.2.3 構(gòu)造語法樹的語法制導(dǎo)定義,產(chǎn)生式 語義規(guī)則 EE1+T E.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的語法樹的構(gòu)造,無環(huán)有向圖 （Directed Acyclic Graph，簡稱dag) 用途：提取表達式中的公共子表達式，以取得目標程序的局部優(yōu)化。 方法：執(zhí)行mknode和mkleaf時，檢查是否已有相同的結(jié)點，若有，則返回相應(yīng)結(jié)點的指針。,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,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+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 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í)行的代碼段，這就構(gòu)成了翻譯程序。象一座建筑，語法分析是構(gòu)架，歸約處有一個“掛鉤”，語義分析和翻譯的代碼段（語義子程序）就掛在這個鉤子上。這樣，隨著語法分析的進行，歸約前調(diào)用相應(yīng)的語義子程序,完成翻譯的任務(wù)。,總結(jié),在語法分析過程中進行語義分析和翻譯，屬 性的計算順序受到語法分析建立分析樹結(jié)點順序的限制。 一種自然的計算屬性的順序是按深度優(yōu)先訪問分析樹結(jié)點的順序，它適應(yīng)多種自底向上和自頂向下的翻譯方法。 L-屬性定義 可用于按深度優(yōu)先順序計算屬性值。,5.4 L-屬性定義,procedure dfvisit(n:node); begin for n 的每個子結(jié)點m(從左至右) do begin 計算m的繼承屬性； dfvisit(m) end; 計算n的綜合屬性 end;,深度優(yōu)先順序計算屬性,定義 一個語法制導(dǎo)定義是L-屬性定義，如果AX1X2XnP,其每一個語義規(guī)則中的每一個屬性都是一個綜合屬性，或是Xj(1j n)的一個繼承屬性，這個繼承屬性僅依賴于 1.產(chǎn)生式中Xj的左邊符號X1，X2，Xj-1的屬性； 2A的繼承屬性。 每一個S-屬性定義都是L-屬性定義。,5.4.1 L-屬性定義,圖519 非L-屬性的語法制導(dǎo)定義,產(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的語法制導(dǎo)定義不是L-屬性定義 文法符號Q的繼承屬性依賴于它右邊文法符號R的屬性,定義 翻譯模式是語法制導(dǎo)定義的一種便于翻譯的書寫形式。其中屬性與文法符號相對應(yīng)，語義規(guī)則或語義動作用花括號 括起來，可被插入到產(chǎn)生式右部的任何合適的位置上。 這是一種語法分析和語義動作交錯的表示法，它表達在按深度優(yōu)先遍歷分析樹的過程中何時執(zhí)行語義動作。 翻譯模式給出了使用語義規(guī)則進行計算的順序?？煽闯墒欠治鲞^程中翻譯的注釋。,5.4.2 翻譯模式,將帶有+號和-號的中綴表達式翻譯成后綴表達式： ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val) 把語義動作看成終結(jié)符號，輸入9-5+2,其分析樹如圖520，當(dāng)按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問的語義動作，將輸出 9 5 - 2 + 它是輸入表達式9-5+2的后綴式。,例5.12 一個簡單的翻譯模式,圖5.10 9-5+2的帶語義動作的分析樹,條件：語法制導(dǎo)定義是L-屬性定義 保證語義動作不會引用還沒有計算的屬性值。 1. 只需要綜合屬性的情況： 為每一個語義規(guī)則建立一個包含賦值的動作，并把這個動作放在相應(yīng)的產(chǎn)生式右邊的末尾。 例如：TT1*F Tval:=T1 val*F val TT1*F Tval:=T1 val*F val,設(shè)計翻譯模式（根據(jù)語法制導(dǎo)定義）,2. 既有綜合屬性又有繼承屬性 產(chǎn)生式右邊的符號的繼承屬性必須在這個符號以前的動作中計算出來。 一個動作不能引用這個動作右邊符號的綜合屬性。 產(chǎn)生式左邊非終結(jié)符號的綜合屬性只有在它所引用的所有屬性都計算出來以后才能計算。計算這種屬性的動作通?？煞旁诋a(chǎn)生式右端的末尾。,設(shè)計翻譯模式（根據(jù)語法制導(dǎo)定義）,下面的翻譯模式不滿足要求： SA1A2 A1in:=1; A2 in:=2 A a print(A in) 例5.13 從L-屬性制導(dǎo)定義建立一個滿足上面 要求的翻譯模式。 使用文法產(chǎn)生的語言是數(shù)學(xué)排版語言EQN E sub 1val 編排結(jié)果,E,1,val,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,SB B B1 B2 B B1 sub B2 B text,產(chǎn)生式,語義規(guī)則,圖5-22 盒子的大小和高度的語法制導(dǎo)定義,B是盒子； BBB表示兩個盒子的并置； BB sub B表示第二個盒子是第一個盒子的下標； ps是繼承屬性，影響公式的高度；正文的實際高度 等于正文的標準高度乘以B.ps； B的高度由綜合屬性ht表示 ； texth可根據(jù)text的性質(zhì)查表得到； shrink把B2的尺寸縮小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構(gòu)造的翻譯模式,用翻譯模式構(gòu)造自頂向下翻譯。 5.5.1 從翻譯模式中消除左遞歸 對于一個翻譯模式，若采用自頂向下分析，必須消除左遞歸和提取左公因子，在改寫基本文法時考慮屬性值的計算。 例5.14 圖524的帶左遞歸的文法的翻譯模式被轉(zhuǎn)換成圖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 R1R s:=R1 s RR s:=R i T（ E ） T val:=E.val Tnum T val:=num val,經(jīng)過轉(zhuǎn)換的帶有右遞歸文法的翻譯模式,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） 每一個文法符號都有一個綜合屬性，用相應(yīng)的小寫字母表示，g和f是任意函數(shù)。 消除左遞歸，文法轉(zhuǎn)換成 AX R RY R| （5.3）,關(guān)于左遞歸翻譯模式更一般化的討論,再考慮語義動作，翻譯模式變?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)過轉(zhuǎn)換的翻譯模式與圖525中一樣,使用R的繼承屬性i和綜合屬性s。 （5.2）和（5.4）的結(jié)果是一樣的, 為什么？,關(guān)于左遞歸翻譯模式更一般化的討論,A a=g(g(f(X x),Y1 y),Y2 y),A a=g(f(X x),Y1 y),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 nptr:=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),使用繼承屬性構(gòu)造語法樹,E,i,R,s,T,id,R,-,T,num,i,R,T,+,id,id,num 4,id,-,+,to entry for a,to entry for c,nptr,nptr,nptr,算法5.1 預(yù)測語法制導(dǎo)翻譯器的建立 輸入：一個帶有適合預(yù)測分析的基礎(chǔ)文法 的語法制導(dǎo)翻譯模式。 輸出：一個語法制導(dǎo)翻譯器的代碼。 方法：在預(yù)測分析器中加入語義動作代碼。 1AVN,建立一個可遞歸調(diào)用的函數(shù)過程A。為A的每一個繼承屬性都設(shè)置一個形式參數(shù)，函數(shù)的返回值是A的綜合屬性值。 2.函數(shù)過程A的代碼（指用符號形式表示的數(shù)據(jù)和程序）要根據(jù)當(dāng)前的輸入符號來決定使用哪一個產(chǎn)生式。,5.5.2 預(yù)測翻譯器的設(shè)計,3與每一個產(chǎn)生式有關(guān)的代碼，從左到右根椐產(chǎn)生式右部是單詞符號、非終結(jié)符號還是語義動作，分別是： （a）對于帶有綜合屬性x的單詞符號X，x存放在X.x中，Match(X)。 （b）對于BVN，編寫一個賦值語句c：= B（b1, b2, ，bk)其中， b1, b2, ，bk是繼承屬性，c是綜合屬性。 （c）對于每個動作，動作的代碼抄進翻譯器中，用代表屬性的變量來代替對屬性的每一次引用。,5.5.2 預(yù)測翻譯器的設(shè)計,例5.16 ： Raddop TR1i:=mknode（addop lexeme， R i， T nptr） R1R.s:=R1.s R R.s:=R.i （55） 遞歸下降構(gòu)造語法樹 function 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:=in; /*產(chǎn)生式R*/ return (s); ,5.6 L屬性的自底向上計算,在自底向上分析的框架中實現(xiàn)L屬性定義的方法 它能實現(xiàn)任何基于LL(1)文法的L屬性定義 也能實現(xiàn)許多（但不是所有的）基于LR(1) 的L屬性定義,5.6.1 刪除翻譯方案中嵌入的動作 E T R R + T print (+)R1 | T print ()R1 | T num print (num.val),5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6.1 刪除翻譯方案中嵌入的動作 E T R R + T print (+)R1 | T print ()R1 | T num print (num.val) 在文法中加入產(chǎn)生的標記非終結(jié)符，讓每個嵌入動作由不同標記非終結(jié)符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)生的標記非終結(jié)符，讓每個嵌入動作由不同標記非終結(jié)符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屬性的自底向上計算,5.6.2 分析棧上的繼承屬性 屬性位置能預(yù)測 例 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屬性的自底向上計算,屬性的位置不能預(yù)測 S aAC C.i = A.s S bABC C.i = A.s C c C.s = g(C.i),5.6 L屬性的自底向上計算,屬性的位置不能預(yù)測 S aAC C.i = A.s S bABC C.i = A.s C c C.s = g(C.i) 增加標記非終結(jié)符 S aAC C.i = A.s S bABMC M.i = A.s; C.i = M.s C c C.s = g(C.i) M M.s = M.i,5.6 L屬性的自底向上計算,5.6.3 模擬繼承屬性的計算 繼承屬性是某個綜合屬性的一個函數(shù) S aAC C.i = f (A.s) C c C.s = g(C.i) 增加標記非終結(jié)符，把f(A.s)的計算移到對標記非終結(jié)符歸約時進行 S aANC N.i = A.s; C.i = N.s N N.s = f (N.i) C c C.s = g(C.i),5.6 L屬性的自底向上計算,例 數(shù)學(xué)排版語言EQN S B.ps = 10 B S.ht = B.ht B B1.ps = B.ps B1 B2.ps = B.ps B2 B.ht = max(B1.ht, B2.ht ) B B1.ps =B.ps B1 sub B2.ps = shrink(B.ps) B2 B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps ,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.6 L屬性的自底向上計算,5.7 遞歸計算,回顧：語法制導(dǎo)定義的實現(xiàn) 分析樹方法 邊分析邊進行屬性計算，只能完成L屬性計算（忽略規(guī)則的方法） 本節(jié)介紹先分析后計算的方法，不局限于L屬性計算（基于規(guī)則的方法） 為每個非終結(jié)符構(gòu)造一個屬性計算函數(shù)，但是該函數(shù)不含語法分析部分 為非終結(jié)符的不同綜合屬性構(gòu)造不同的函數(shù),5.7 遞歸計算,5.7.1 自左向右遍歷 為B構(gòu)造一個屬性計算函數(shù) S B.ps = 10 B S.ht = B.ht B B1.ps = B.ps B1 B2.ps = B.ps B2 B.ht = max(B1.ht, B2.ht ) B B1.ps =B.ps B1 sub B2.ps = shrink(B.ps) B2 B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps ,5.7 遞歸計算,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結(jié)點n的產(chǎn)生式 of B B1 B2: ps1 = ps; ht1 = B(child(n,1), ps1); ps2 = ps; ht2 = B(child(n,2), ps2); return max(ht1, ht2);,B B1.ps = B.ps B1 B2.ps = B.ps B2 B.ht = max(B1.ht, B2.ht ) ,5.7 遞歸計算,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結(jié)點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 B1 sub B2.ps = shrink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) ,5.7 遞歸計算,function B(n, ps); var ps1, ps2, ht1, ht2; begin c