【正文】 t id1, id2, id3 的分析樹(shù)的依賴圖 D int T , id3 L L L id2 id1 , 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type 依賴圖的構(gòu)造方法 for 分析樹(shù)中每一結(jié)點(diǎn) n do for 結(jié)點(diǎn) n的文法符號(hào)的每一個(gè)屬性 a do 為 a在依賴圖中建立一個(gè)結(jié)點(diǎn)； for 分析樹(shù)中每一個(gè)結(jié)點(diǎn) n do for 結(jié)點(diǎn) n所用產(chǎn)生式對(duì)應(yīng)的每一條 語(yǔ)義規(guī)則 b:＝ f（ c1， c2， … ， ck ) do for i:=1 to k do 從結(jié)點(diǎn) ci到結(jié)點(diǎn) b構(gòu)造一條有向邊； 屬性計(jì)算次序 ? 拓?fù)渑判?是無(wú)環(huán)有向圖的結(jié)點(diǎn)的一種排序 m1, m2, … , mk， 它使得邊只會(huì)從這個(gè)次序中先出現(xiàn)的結(jié)點(diǎn)到后出現(xiàn)的結(jié)點(diǎn) ， 也就是若 mi ?mj是從mi到 mj的邊 ， 那么在此排序中 mi先于 mj。 D int T , id3 L L L id2 id1 , 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type 屬性計(jì)算次序 語(yǔ)義規(guī)則的計(jì)算方法 ? 分析樹(shù)方法：前面介紹的方法。語(yǔ)法分析過(guò)程中完成翻譯有許多優(yōu)點(diǎn)，但也有一些不足： 分的自然層次結(jié)構(gòu)； 2. 語(yǔ)法分析方法限制，對(duì)分析樹(shù)結(jié)點(diǎn)的訪問(wèn)序和翻譯需要的訪問(wèn)序不一致。 返回新建立結(jié)點(diǎn)的指針。 關(guān)于表達(dá)式的有向非循環(huán)圖 ◆ 有向非循環(huán)圖 （ Directed Acyclic Graph， 簡(jiǎn)稱 DAG) 用途： 提取表達(dá)式中的公共子表達(dá)式，以取 得目標(biāo)程序的局部?jī)?yōu)化。我們說(shuō)明如何擴(kuò)展分析器的棧使之能夠保存綜合屬性 ? S屬性定義的翻譯器可以借助 LR分析器的生成器來(lái)實(shí)現(xiàn) S屬性定義的自下而上計(jì)算 將 LR分析器 分析棧中 增加 一個(gè)域來(lái)保存綜合屬性值。 L屬性定義 可用于按深度優(yōu)先順序計(jì)算屬性值。 L屬性定義 ◆定義 一個(gè)語(yǔ)法制導(dǎo)定義是 L屬性定義 ，如果?A→X 1X2…X n?P,其每一個(gè)語(yǔ)義規(guī)則中的每一個(gè)屬性都是一個(gè)綜合屬性，或是 Xj(1?j ? n)的一個(gè)繼承屬性，這個(gè)繼承屬性僅依賴于 1. 產(chǎn)生式中 Xj的左邊符號(hào) X1， X2， …X j1 的屬性； 2． A的繼承屬性。其中屬性與文法符號(hào)相對(duì)應(yīng)，語(yǔ)義規(guī)則或語(yǔ)義動(dòng)作用花括號(hào)｛ ｝括起來(lái)，可被插入到產(chǎn)生式右部的任何合適的位置上。 例：一個(gè)簡(jiǎn)單的翻譯模式 E→TR R→addop T {print()}R 1|ε T→num{print()} 把語(yǔ)義動(dòng)作看成終結(jié)符號(hào)，輸入 95+2,其分析樹(shù)如圖 6. 10，當(dāng)按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問(wèn)的語(yǔ)義動(dòng)作，將輸出 9 5 2 + 它是輸入表達(dá)式 95+2的后綴式 。) R Pt(180。) R 5 Pt(180。) R ? 圖 95+2的帶語(yǔ)義動(dòng)作的分析樹(shù) E→TR R→addop T {print()}R1|ε T→num {print()} 例 數(shù)學(xué)排版語(yǔ)言 EQN 例 數(shù)學(xué)排版語(yǔ)言 EQN E sub 1 .val S ? B B ? B1 B2 B ? B1 sub B2 B ? text E 1 .val 例 數(shù)學(xué)排版語(yǔ)言 EQN 例 數(shù)學(xué)排版語(yǔ)言 EQN E sub 1 .val 產(chǎn) 生 式 語(yǔ) 義 規(guī) 則 S ? B := 10。 := shrink()。 ● 一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊符號(hào)的綜合屬性。 :=2} A ?a { print( } Print() S A a A a Print() :=1。 自頂向下的翻譯 用翻譯模式構(gòu)造自頂向下翻譯。 R ?s= 6 9 – T ?val=5 5 R ?i=4。 Y2 Y1 X (a) 例輸入： XY1Y2 采用左遞歸翻譯模式 A→A 1Y｛ :=g(,)} A→X ｛ :=f()} A A A A ? a=g(g(f(X ?x),Y1 ? y),Y2 ? y) A ? a=g(f(X ? x),Y1 ? y) A? a=f(X ? x) A ε Y2 Y1 X (b) A→X ｛ R?i:=f(X ? x)} R ｛ A. ? a:=R. ? s} R→Y ｛ R1 ? i:=g(R ? i,Y ? y)} R1｛ R ? s:=R1 ? s} R→ε ｛ R ? s:=R ? i} R R R R?i=f(X ? x) R ? i=g(f(X ? x),Y1 ? y) R ?i=g(g(f(X ?x),Y1 ?y),Y2 ?y) 例輸入： XY1Y2 消除左遞歸后翻譯模式 例 左遞歸的消除引起繼承屬性 例 左遞歸的消除引起繼承屬性 產(chǎn) 生 式 語(yǔ) 義 規(guī) 則 E ? E1 + T := mknode( ?+?, , ) E ? T := T ? T1*F := mknode( ?*?, , ) T ? F := F ? (E) := F ? id := mkleaf (id, ) F ? num := mkleaf (num, ) 例 左遞歸的消除引起繼承屬性 E ? T { := } R { := } R ? + T { := mknode ( ?+?, , )} R1 { := } R ? ? { := } T ? F { := } W { := } W ? * F { := mknode ( ?*?, , )} W1 { := } W ? ? { := } 例 左遞歸的消除引起繼承屬性 E ? T { := } T + T + T + … R { := } R ? + T { := mknode ( ?+?, , )} R1 { := } R ? ? { := } T ? F { := } W { := } W ? * F { := mknode ( ?*?, , )} W1 { := } W ? ? { := } 例 左遞歸的消除引起繼承屬性 T id i W * * id num id id num 5 * * 指向符號(hào)表中 a的入口 指向符號(hào)表中 b的入口 i W s i W ? 略去了 E ? TR ? T 部分 預(yù)測(cè)翻譯器的設(shè)計(jì) 把預(yù)測(cè)分析器的構(gòu)造方法推廣到翻譯方案的實(shí)現(xiàn) 產(chǎn)生式 R ? +TR | ? 的分析過(guò)程 procdure R。 var nptr , i1, s1, s : ? syntax_tree_node。 nptr := T。 /* 產(chǎn)生式 R ? ? */ return s end。 L屬性的自下而上計(jì)算 刪除翻譯方案中嵌入的動(dòng)作 E ? T R R ? + T {print (?+?)}R1 | ? T {print (???)}R1 | ? T ? num {print ()} L屬性的自下而上計(jì)算 刪除翻譯方案中嵌入的動(dòng)作 E ? T R R ? + T {print (?+?)}R1 | ? T {print (???)}R1 | ? T ? num {print ()} 在文法中加入產(chǎn)生 ?的 標(biāo)記非終結(jié)符 ，讓每個(gè)嵌入動(dòng)作由不同標(biāo)記非終結(jié)符 M代表，并把該動(dòng)作放在產(chǎn)生式 M ? ?的右端。 S ? aANC := 。 := 。 := disp (, ) N ? ? := shrink() B ? text := ? L屬性的自下而上計(jì)算 產(chǎn) 生 式 代 碼 段 S ? LB := 。 := max(, ) M ? ? := B ? B1 sub NB2 :=。 := 。 := 。 := max(, ) M ? ? := B ? B1 sub NB2 :=。 := 。 := 。 遞 歸 計(jì) 算 回顧：語(yǔ)法制導(dǎo)定義的實(shí)現(xiàn) ? 分析樹(shù)方法。 ? 邊分析邊進(jìn)行屬性計(jì)算 ， 只能完成 L屬性計(jì)算（忽略規(guī)則的方法）。 ? 邊分析邊進(jìn)行屬性計(jì)算 ， 只能完成 L屬性計(jì)算（忽略規(guī)則的方法）。 遞 歸 計(jì) 算 自左向右遍歷 為 B構(gòu)造一個(gè)屬性計(jì)算函數(shù) S ? { := 10 } B { := } B ? { := } B1 { := } B2 { := max(, ) } B ? { := } B1 sub { := shrink() } B2 { := disp (, ) } B ? text { := ? } 遞 歸 計(jì) 算 function B(n, ps)。 ps2 := ps。 var ps1, ps2, ht1, ht2。 ht2 := B(child(n,3), ps2)。 begin case 在結(jié)點(diǎn) n的產(chǎn)生式 of ?B ? text?: return ps? 。 := f () A ? QR := r()。 mi := m(ls)。 rs := R(child(n,2), ri)。 i A s i M s i L s ? ? ? ? ? ? i A s i R s i Q s ? ? ? ? ? ? 遞 歸 計(jì) 算 多次遍歷 S ? E := g()。 := ft (, ) E ? id := 。 t := Et(child(n,1), i)。 begin | begin case 在結(jié)點(diǎn) n的產(chǎn)生式 of | case 在結(jié)點(diǎn) n的產(chǎn)生式 of ?E ? E1 E2?: | ?E ? E1 E2?: s1 := Es(child(n,1))。 return fs(s1, s2)。 | return ft(t1, t2)。 本 章 要 點(diǎn) ? 語(yǔ)義規(guī)則的兩種描述方法：語(yǔ)法制導(dǎo)的定義和翻譯方案 。 ? L屬性的自上而下計(jì)算 （ 邊分析邊計(jì)算 ） 。 S? ? S print (S. num) S ? ( L ) S. num := + 1 S ? a S. num := 0 L ? L1 , S L. num := L1. num + S. num L ? S L. num := 例 題 2 為文法 S ? ( L ) | a L ? L , S | S 寫(xiě)一個(gè)翻譯方案，它輸出每個(gè) a的嵌套深度。 S? ? {S. in := 0 } S S ? {L. in := S. in + 1 } ( L ) {S. out := L. out + 1 } S ? a {S. out := S. in + 1。 ? 去掉表達(dá)式中的冗余括號(hào) ， 保留必要的括號(hào) 。 T. op := times 例 題 4 T ? F T. code := F. code。 ? 分別用 1和 2表示加和乘的優(yōu)先級(jí) ， 用 3表示 id和 (E)的優(yōu)先級(jí) ， 用 0表示左側(cè)或右側(cè)沒(méi)有運(yùn)算對(duì)象的情況 。 E1