【正文】 分析后計算的方法，不局限于 L屬性計算（基于規(guī)則的方法）。 遞 歸 計 算 回顧：語法制導(dǎo)定義的實現(xiàn) ? 分析樹方法。 ? 邊分析邊進行屬性計算 ， 只能完成 L屬性計算（忽略規(guī)則的方法）。 ? 本節(jié)介紹 先分析后計算的方法，不局限于 L屬性計算（基于規(guī)則的方法）。 – 為每個非終結(jié)符構(gòu)造一個屬性計算函數(shù)，但是該函數(shù)不含語法分析部分 。 遞 歸 計 算 回顧：語法制導(dǎo)定義的實現(xiàn) ? 分析樹方法。 ? 邊分析邊進行屬性計算 ， 只能完成 L屬性計算（忽略規(guī)則的方法）。 ? 本節(jié)介紹 先分析后計算的方法，不局限于 L屬性計算（基于規(guī)則的方法）。 – 為每個非終結(jié)符構(gòu)造一個屬性計算函數(shù)，但是該函數(shù)不含語法分析部分 。 – 為非終結(jié)符的不同綜合屬性構(gòu)造不同的函數(shù)。 遞 歸 計 算 自左向右遍歷 為 B構(gòu)造一個屬性計算函數(shù) S ? { := 10 } B { := } B ? { := } B1 { := } B2 { := max(, ) } B ? { := } B1 sub { := shrink() } B2 { := disp (, ) } B ? text { := ? } 遞 歸 計 算 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 { := } B2 { := max(, ) } 遞 歸 計 算 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 sub { := shrink()} B2{ := disp (, ) } 遞 歸 計 算 function B(n, ps)。 var ps1, ps2, ht1, ht2。 begin case 在結(jié)點 n的產(chǎn)生式 of ?B ? text?: return ps? 。 default: error end B ? text { := ? } 遞 歸 計 算 其它遍歷方法 按所需次序訪問結(jié)點的子結(jié)點，可用于非L屬性定義。 A ? LM := l()。 := m()。 := f () A ? QR := r()。 := q()。 := f () i A s i M s i L s ? ? ? ? ? ? i A s i R s i Q s ? ? ? ? ? ? 遞 歸 計 算 ?A ? LM?: /* 從左到右的次序 */ li := l(ai)。 ls := L(child(n,1), li)。 mi := m(ls)。 ms := M(child(n,2), mi)。 return f (ms)。 i A s i M s i L s ? ? ? ? ? ? i A s i R s i Q s ? ? ? ? ? ? 遞 歸 計 算 ‘ A ? QR?: /* 從右到左的次序 */ ri := r(ai)。 rs := R(child(n,2), ri)。 qi := q(rs)。 qs := Q(child(n,1), qi)。 return f (qs)。 i A s i M s i L s ? ? ? ? ? ? i A s i R s i Q s ? ? ? ? ? ? 遞 歸 計 算 多次遍歷 S ? E := g()。 := E ? E1E2 := fs(, )。 := fi1()。 := fi2()。 := ft (, ) E ? id := 。 := h() S r i E s t ? ? ? ? ? ? ? ? i E1 s t i E s t i E2 s t ? ? ? ? ? i E s t id s ? ? ? ? 遞 歸 計 算 綜合屬性 t不可能和 s在同一遍掃描中完成計算 i E s t ? S r i E s t id s ? ? ? i E s t id s ? ? ? 遞 歸 計 算 function Sr(n)。 begin s := Es(child(n,1))。 i := g(s)。 t := Et(child(n,1), i)。 return t end。 遞 歸 計 算 function Es(n)。 | function Et(n, i)。 begin | begin case 在結(jié)點 n的產(chǎn)生式 of | case 在結(jié)點 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 。 | return ft(t1, t2)。 default: | ?E ? id?: error | return h(i)。 end | default: end。 | error | end | end。 本 章 要 點 ? 語義規(guī)則的兩種描述方法：語法制導(dǎo)的定義和翻譯方案 。 ? 設(shè)計簡單問題的語法制導(dǎo)定義和翻譯方案 ， 這是本章的重點和難點 。 ? 語義規(guī)則的三種計算方法：分析樹方法 、 基于規(guī)則的方法和忽略規(guī)則的方法 。 ? S屬性的自下而上計算 （ 邊分析邊計算 ） 。 ? L屬性的自上而下計算 （ 邊分析邊計算 ） 。 ? L屬性的自下而上計算 （ 邊分析邊計算 ） 。 ? 遞歸計算 （ 先分析后計算 ） 。 例 題 1 為文法 S ? ( L ) | a L ? L , S | S 寫一個語法制導(dǎo)定義，它輸出括號的對數(shù)。 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 寫一個翻譯方案，它輸出每個 a的嵌套深度。例如，對于 ( a , ( a , a) )， 輸出的結(jié)果是 1 2 2。 S? ? {S. depth := 0 } S S ? {L. depth := S. depth + 1 } ( L ) S ? a {print (S. depth) } L ? {L1. depth := L. depth }L1 , {S. depth := L. depth }S L ? {S. depth := L. depth }S 例 題 3 為文法 S ? ( L ) | a L ? L , S | S 寫一個翻譯方案，它打印出每個 a在句子中是第幾個字符。例如，當(dāng)句子是 ( a , ( a , ( a , a ) , (a) ) )時，打印的結(jié)果是 2 5 8 10 14。 S? ? {S. in := 0 } S S ? {L. in := S. in + 1 } ( L ) {S. out := L. out + 1 } S ? a {S. out := S. in + 1。 print (S. out) } L ? {L1. in := L. in }L1 , {S. in := L1. out + 1 } S {L. out := S. out } L ? {S. in := L. in }S {L. out := S. out } 例 題 4 給出把中綴表達式翻譯成沒有冗余括號的中綴表達式的語法制導(dǎo)定義 。 例如 ， 因為 ?和 ?是左結(jié)合 ， ((a ? (b + c )) ? (d ))可以重寫成 a ? (b + c ) ? d。 ? 先把表達式的括號都去掉 ， 然后在必要的地方再加括號 。 ? 去掉表達式中的冗余括號 ， 保留必要的括號 。 例 題 4 第一種方法 S? ? E print ( E. code ) E ? E1 + T if T. op = plus then :=||“+”||“(”||||“)” else E. code := E1. code || “+” || T. code。 E. op := plus E ? T E. code := T. code。 E. op := T. op 例 題 4 T ? T1 ? F if (F. op = plus) or (F. op = times) then if T1. op := plus then T. code := “(” || T1. code || “)” || “?” || “(” || F. code || “)” else T. code := T1. code || “?” || “(” || F. code || “)” else if T1. op := plus then T. code := “(” || T1. code || “)” || “?” || F. code else T. code := T1. code || “?” || F. code。 T. op := times 例 題 4 T ? F T. code := F. code。 T. op := F. op F ? id F. code := id. lexeme。 F. op := id F ? ( E ) F. code := E. code。 F. op := E. op 例 題 4 第二種方法 ? 給 E， T和 F兩個繼承屬性 left_op和 right_op 分別表示左右兩個運算對象的主算符的優(yōu)先級 ? 給它們一個綜合屬性 self_op表示自身主算符的優(yōu)先級 ? 再給一個綜合屬性 code表示沒有冗余括號的代碼 。 ? 分別用 1和 2表示加和乘的優(yōu)先級 ， 用 3表示 id和 (E)的優(yōu)先級 ， 用 0表示左側(cè)或右側(cè)沒有運算對象的情況 。 例 題 4 S? ? E E. left_op := 0。 E. right_op := 0。 print ( E. code ) E ? E1 + T E1. left_op := E. left_op。 E1