【正文】 S ? .aSSb S ? .aSSS S ? .c I6: S ? aSSb. I7: S ? aSSS. I0 I1 S c I3 a I2 S I4 start S I5 b I6 a c a a c c S I7 50 證明下面文法是 SLR(1)文法 , 并構(gòu)造其 SLR分析表 . E ? E + T (1) F ? F* (5) E ? T (2) F ? a (6) T ? T F (3) F ? b (7) T ? F (4) I0: E’ ? .E E ? .E+T E ? .T T ? .TF T ? .F F ? .F* F ? .a F ? .b I1: E’ ? E. E ? E.+T I2: E ? T. T ? F ? .F* F ? .a F ? .b I3: T ? F. F ? F.* I4: F ? a. I5: F ? b. I6: E ? E+.T T ? .TF T ? .F F ? .F* F ? .a F ? .b I7: T ? TF. F ? F.* I8: F ? F*. I9: E ? E+T. T ? F ? .F* F ? .a F ? .b action goto + * a b $ E T F 0 s4 s5 1 2 3 1 s6 acc 2 r2 s4 s5 r2 7 3 r4 s8 r4 r4 r4 4 r6 r6 r6 r6 r6 5 r7 r7 r7 r7 r7 6 s4 s5 9 3 7 r3 s8 r3 r3 r3 8 r5 r5 r5 r5 r5 9 r1 s4 s5 r1 7 Follow(E) = {+, $} Follow(T) = {+, $, a, b} Follow(E) = {+, $, *, a, b} 51 證明每一個(gè) LL(1)文法都是 LR(1)文法 . 52 證明下面文法是 LL(1)的但不是 SLR(1)文法 . S ? A a A b | B b B a A ? ? B ? ? First(AaAb)={a} First(BbBa)= First(AaAb) ? First(BbBa) = ? ?文法是 LL(1)的 . 構(gòu)造 SLR(1)項(xiàng)目集 : I0: S’ ? .S S ? .AaAb S ? .BbBa A ? . B ? . Follow(A) = Follow(B) = {a, b} 存在歸約 歸約沖突 , ?該文法不 是 SLR(1)文法 . 53 證明任何一個(gè) LR(1)文法都是無二義文法 . 54 證明任何 SLR(1)文法都是 LR(1)文法 . 假設(shè)文法 G是 SLR(1)文法 , 則 對(duì)于文法的狀態(tài) i: 對(duì)于 A??.X?, X?VT, , X?Follow(B), i中沒有項(xiàng)目 B??. 對(duì)于 A??.和 B? ?., Follow(A) ? Follow(B) = ? 構(gòu)造 G的 LR(1)項(xiàng)目集 , 若 G是 LR(1)文法 , 則項(xiàng)目集 i必須滿足條件 : (1)對(duì)于 [A??.X?, a], X?VT, , X?Follow(B), i中沒有項(xiàng)目 [B??., X]. (顯然成立 ) (2)沒有 [A??., a]和 [B? ?.,a]的兩個(gè)項(xiàng)目 . 由 closure(I)的構(gòu)造 {[A??.B?,a], [B?.?, First(?a)]}可得知 , 項(xiàng)目 A??.?的向前搜索符號(hào) ?Follow(A) 對(duì)于一個(gè)項(xiàng)目集中的不同歸約項(xiàng)目 [A?? A,], [ B??3.,搜索符 A] 搜索符 A ?搜索符 A = ? 不存在歸約 歸約沖突 , 所以條件 (2)成立 . 55 為下面的文法構(gòu)造它的 LR(1)項(xiàng)目集規(guī)范族 ,并判斷它是否為 LR(1)文法 ? 若是 ,構(gòu)造它的分析表 . S ? E S’ ? S S ? E (1) E ? E + T | T E ? E + T (2) E ? T (3) T ? ( E ) | a T ? ( E ) (4) T ? a (5) I0: S’ ? .S $ S ? .E $ E ? .E+T $/+ E ? .T $/+ T ? .(E) $/+ T ? .a $/+ I1: S’ ? S. $ I2: S ? E. $ E ? E.+T $/+ I3: E ? T. $/+ I4: T ? (.E) $/+ E ? .E+T )/+ E ? .T )/+ T ? .(E) )/+ T ? .a )/+ I5: T ?a. $/+ I6: E ? E+.T $/+ T ? .(E) $/+ T ? .a $/+ I7: T ? (E.) $/+ E ? E.+T )/+ I8: E ? T. )/+ I9: T ? (.E) )/+ E ? .E+T )/+ E ? .T )/+ T ? .(E) )/+ T ? .a )/+ I10:T ? a. )/+ I11:E ? E+T. $/+ I12: T ? (E). $/+ I13:E ? E+.T )/+ T ? .(E) )/+ T ? .a )/+ I14: T ? (E.) )/+ E ? E.+T )/+ I15: E ? E+T. )/+ I16: T ? (E). )/+ LR(1)項(xiàng)目集規(guī)范族 : 56 action goto + ( ) a $ S E T 0 s4 s5 1 2 3 1 acc 2 s6 r1 3 r3 r3 4 s9 s10 7 8 5 r5 r5 6 s4 s5 11 7 s13 s12 8 r3 r3 9 s9 s5 14 8 10 r5 r5 11 r2 r2 12 r4 r4 13 s9 s10 15 14s13 s16 15r2 r2 16r4 r4 LR(1) 分析表 : 57 LALR(1)分析表 : action goto + ( ) a $ S E T 0 s4 9 s5 10 1 2 3 8 1 acc 2 s6 13 r1 3 8 r3 r3 r3 4 9 s4 9 s5 10 7 14 3 8 5 10 r5 r5 r5 6 13 s4 9 s5 10 11 15 7 14 s6 13 s12 16 11 15 r2 r2 r2 12 16 r4 r4 r4 LALR(1)分析表不存在沖突 , 所以該文法是 LALR(1)文法 . 58 證明文法 G[S]: S ? aAd S ?bBd S ? aBe S ? bAe A ? c B ?c 是 LR(1)文法 , 但不是 LALR(1)文法 . 59 對(duì)于輸入的表達(dá)式 (4*7+1)*2, 根據(jù)表 一棵帶注釋的分析樹 . L =58 n =58 =29 * =2 =29 =2 ( =29 ) =28 + =1 =28 =1 =4 * =7 =1 =4 =7 =4（ lex表示是從詞法分析來的） 60 試根據(jù) (a) 表 ， 和 (b) 圖 來建立表達(dá)式 ((a)+(b))的分析樹和語(yǔ)法樹 . (a) E T