【正文】 4. S→ (EtSeS) 12. S→ (EtS) 20. S→ i=E 28. F→ *Fi 第三章 語法分析 5. S→ (EtSeS) 13. S→ (EtS) 21. E→ +EF 29. F→ *Fi 6. S→ (EtSeS) 14. S→ (EtS) 22. E→ +EF 30. F→ *Fi 7. S→ (EtSeS) 15. S→ (EtS) 23. E→ +EF 31. F→ i 8. S→ (EtSeS) 16. S→ (EtS) 24. E→ +EF 32. F→ i 第三章 語法分析 用 ε _CLOSURE方法構(gòu)造文法 G[S′ ]的 LR(0)項目集規(guī)范族： I0: S′ → S I5: S→ (EtSeS) I13: E→ +EF S→ (EtSeS) S→ (EtS) E→ +EF S→ (EtS) I6: S→ (EtSeS) E→ F S→ i=E S→ (EtSeS) I14: E→ +EF I1: S′ → S S→ (EtS) F→ *Fi 第三章 語法分析 I2: S→ (EtSeS) S→ i=E F→ i S→ (EtS) I7: S→ (EtSeS) I15: E→ +EF E→ +EF I8: S→ (EtSeS) I16: E→ F E→ F I9: S→ (EtS) I17: F→ *Fi I3: S→ (EtSeS) I10: S→ i=E F→ *Fi S→ (EtS) I11: S→ i=E F→ i 第三章 語法分析 I4: S→ (EtSeS) E→ +EF I18: F→ *Fi S→ (EtS) E→ F I19: F→ *Fi S→ (EtSeS) I12: S→ i=E I20: F→ i S→ (EtS) S→ i=E 文法 G[S′ ]的 DFA如圖 313所示 。 第三章 語法分析 )S(iiF*FieiS*(t＋EE＋EF＋FF＝i(S I1： S ′ →S I0： S ′ → S S → ( E t S e S ) S → ( E t S ) S → i ＝ E I2： S →( E t S e S ) S →( E t S ) E → ＋ EF E → F I10： S →i ＝ E I1 1： S →i ＝ E E → ＋ EF E → F I12： S →i ＝ E I3： S →( E t S e S ) S →( E t S ) I16： E →F I1 3： E → ＋ E F E → ＋ EF E → F I1 4： E → ＋ E F F → * F i F → i I1 7： F →* F i F → * F i F → i I15： E→ ＋ E F I2 0： F →i I1 8： F →* F i I1 9： F →* F i I4： S →( E t S e S ) S →( E t S ) S → ( E t S e S ) S → ( E t S ) S → i ＝ E I5： S →( E t S e S ) S →( E t S ) I6： S →( E t S e S ) S → ( E t S e S ) S → ( E t S ) S → i ＝ E I7： S →( E t S e S ) I8： S →( E t S e S ) I9： S →( E t S ) )E圖 313 習(xí)題 DFA 第三章 語法分析 構(gòu)造 SLR(1)分析表必須先求出所有形如 “ A→ α ”的FOLLOW(A)， 即由 FOLLOW集的構(gòu)造方法求得 G[S′ ]的FOLLOW集如下： (1) FOLLOW(S′ )={}； (2) 由 S→ (EtSeS)得 FIRST(′ t′ ) ? FOLLOW(E)，即 FOLLOW(E)={t}； FIRST(′ e′ ) ? FOLLOW(S)， 即 FOLLOW(S)={e}； FIRST(′ ) ′ ) ? FOLLOW(S)， 即 FOLLOW(S)={e,)}； 由 F→ *Fi得 FIRST(′ i′ ) ? FOLLOW(F)， 即 FOLLOW(F)={i}； 由 E→ +EF得 FIRST(′ F′ )/{ε}? FOLLOW(E)，即 FOLLOW(E)={t,i}； 第三章 語法分析 (3) 由 S′ → S得 FOLLOW(S′ ) ? FOLLOW(S)， 即FOLLOW(S)={e,),}； 由 S→ i=E 得 FOLLOW(S) ? FOLLOW(E) ， 即FOLLOW(E)={t,i,e,),}； 由 E→ F 得 FOLLOW(E) ? FOLLOW(F) ， 即FOLLOW(F)={t,i,e,),}。 最后得到 SLR(1)分析表 ， 見表 310。 第三章 語法分析 表 310 習(xí)題 SLR(1)分析表 A CT IO N G O T O 狀態(tài) t + e ( ) * = i S E F 0 s10 1 1 acc 2 s13 3 16 3 s4 4 s2 s10 5 5 s6 s9 6 s2 s10 7 7 s8 8 r1 r1 r1 9 r2 r2 r2 10 s11 11 s13 12 16 12 r3 r3 r3 13 s13 14 16 14 s17 15 15 r4 r4 r4 r4 r4 16 r5 r5 r5 r5 r5 17 s17 s20 18 18 s19 19 r6 r6 r6 r6 r6 20 r7 r7 r7 r7 r7 第三章 語法分析 為二義文法 G[T]構(gòu)造一個 LR分析表 (詳細(xì)說明構(gòu)造方法 )。 其中終結(jié)符 “ ， ” 滿足右結(jié)合性 ， 終結(jié)符 “ ； ” 滿足左結(jié)合性 ， 且 “ ， ” 的優(yōu)先級高于 “ ； ”的優(yōu)先級 。 G[T]: T→ TAT | bTe | a A→ , | 。 【 解答 】 首先將文法 G[T]拓廣為文法 G[S]： (0) S→ T 第三章 語法分析 (1)T→ TAT (2) T→ bTe (3) T→ a (4) A→ ， (5) A→ ； 下面列出 LR(0)的所有項目： 1 ． S→ T 5 ． T→ TAT 9 ． T→ bTe 13． A→ ， 2． S→ T 6 ． T→ TAT 10 ． T→ bTe 14． A→ ， 第三章 語法分析 3． T→ TAT 7 ． T→ bTe 11． T→ a 15． A→ 4． T→ TAT 8 ． T→ bTe 12． T→ a 16． A→ 。 用 ε _CLOSURE方法構(gòu)造文法 G[S]的 LR(0)項目集規(guī)范族 ， 并根據(jù)轉(zhuǎn)換函數(shù) GO構(gòu)造出文法 G[S]的 DFA， 如圖314所示 。 第三章 語法分析 bA，；；，ATbaA，；TTaba I1： T →a I0： S → T T → T A T T → bT e T → a I2： T →b T e T → T A T T → bT e T → a I3： S →T T →T A T A → ， A → ； I5： A→ ， I6： A→ ； I4： T →T A T T → T A T T → bT e T → a I8： T →T A T T →T A T A → ， A → ； I7： T →bT e T →T A T A → ， A → ； I9： T →bT e ；e圖 314 習(xí)題 G[S]的 DFA 第三章 語法分析 已知文法 G[S]為二義文法 ， 故必然存在沖突 。 逐一檢查各狀態(tài) ， 得知 I8存在 “ 移進 ” /“歸約 ” 沖突 (因為T→ TAT要求歸約 ， 而 T→ TAT卻要求移進 )。 在此 ， LR(0)已不能滿足要求 ， 因為 LR(0)分析表中的 ACTION子表在某歸約狀態(tài)下 (即某一行 )的所有欄目全被 “ rj”占滿 ， 但由于存在 “ 移進 ” /“歸約 ” 沖突 ， 即在此狀態(tài)下 ， 有些欄目應(yīng)填為 “ Sj”(即歸約 )。 為了減少沖突 ， 最好采用SLR(1)、 LR(1)或 LALR分析表 。 這里采用 SLR(1)分析表 。