【文章內(nèi)容簡介】 . . .. . 學(xué)習(xí)好幫手4) A’ aA’ |ξ將 4）代入 2）1) S aS’2) S’aA’b 3) S’a 4) S’b5) AaA ’6) A’ aA’ |ξ對 2）3)提取左公因子1) SaS’2) S’aS’’3) S’’A’b|ξ4) S’b5) AaA ’6) A’ aA’ |ξ刪除多余產(chǎn)生式 5）1) SaS’2) S’aS’’3) S’’A’b|ξ4) S’b5) A’ aA’ |ξ第六章1S ? a | ∧ | ( T )T ? T , S | S解：(1) 增加輔助產(chǎn)生式 S’?＃S＃求 FIRSTVT 集FIRSTVT（S’ ）＝ {}FIRSTVT（S）＝ {a ∧ ( }＝ { a ∧ ( }FIRSTVT (T) ＝ {,} ∪ FIRSTVT( S ) = { , a ∧ ( }求 LASTVT 集LASTVT（S’ ）＝ { }LASTVT（S）＝ { a ∧ )}LASTVT (T) ＝ { , a ∧ )}(2)算符優(yōu)先關(guān)系表a ∧ ( ) , a ∧ ( = ) , =. . . .. . 學(xué)習(xí)好幫手因為任意兩終結(jié)符之間至多只有一種優(yōu)先關(guān)系成立，所以是算符優(yōu)先文法 (3) a ∧ ( ) , F 1 1 1 1 1 1g 1 1 1 1 1 1f 2 2 1 3 2 1g 2 2 2 1 2 1f 3 3 1 3 3 1g 4 4 4 1 2 1f 3 3 1 3 3 1g 4 4 4 1 2 1(4) 棧 優(yōu)先關(guān)系 當(dāng)前符號 剩余輸入串 移進(jìn)或規(guī)約＃ ( a,a) 移進(jìn)＃( a ,a) 移進(jìn) (a , a) 規(guī)約＃(T , a) 移進(jìn)＃(T， a ) 移進(jìn)＃(T,a ) 規(guī)約＃(T,T ) 規(guī)約＃(T = ) 移進(jìn)＃(T) ＃ 規(guī)約＃T = ＃ 接受4. 擴(kuò)展后的文法S’?S S?S。G S?G G?G(T) G?H H?a H?(S)T?T+S T?S（1）FIRSTVT(S)={。}∪FIRSTVT(G) = {。 , a , ( }FIRSTVT(G)={ ( }∪FIRSTVT(H) = {a , ( }FIRSTCT(H)={a , ( }FIRSTVT(T) = {+} ∪FIRSTVT(S) = {+ , 。 , a , ( }LASTVT(S) = {。} ∪LASTVT(G) = { 。 , a , )}LASTVT(G) = { )} ∪ LASTVT(H) = { a , )}LASTVT(H) = {a, )}LASTVT(T) = {+ } ∪LASTVT(S) = {+ , 。 , a , ) }構(gòu)造算符優(yōu)先關(guān)系表。 ( ) a + . . . .. . 學(xué)習(xí)好幫手； ( ＝ ) a + ＝因為任意兩終結(jié)符之間至多只有一種優(yōu)先關(guān)系成立，所以是算符優(yōu)先文法（2） 句型 a(T+S)。H。(S)的短語有：a(T+S)。H。(S) a(T+S)。H a(T+S) a T+S (S) H 直接短語有: a T+S H (S)句柄： a素短語：a T+S (S) 最左素短語：a(3)分析 a；（a＋a） 棧 優(yōu)先關(guān)系 當(dāng)前符號 剩余輸入串 移進(jìn)或規(guī)約＃＃a＃T＃T；＃T；（＃T；（a＃T；（T＃T；（T＋＃T；（T＋a＃T；（T＋T＃T；（T＃T；（T）＃T；T＃T＝＝a；；（a＋＋a）））＃＃＃；（a＋a）＃（a＋a）＃（a＋a）＃a＋a）＃＋a）＃a）＃a）＃）＃＃＃＃移進(jìn)規(guī)約移進(jìn)移進(jìn)移進(jìn)規(guī)約移進(jìn)移進(jìn)規(guī)約規(guī)約移進(jìn)規(guī)約規(guī)約接受分析 a；（a＋a）棧 優(yōu)先關(guān)系 當(dāng)前符號 剩余輸入串 移進(jìn)或規(guī)約＃＃（＃（a＃（T＃（T＋＃（T＋a＃（T＋T＃（T＃（T）＃T＝＝(a＋＋a）））＃＃a＋a）＃＋a）＃a）＃ a）＃）＃＃＃＃移進(jìn)移進(jìn)規(guī)約移進(jìn)移進(jìn)規(guī)約規(guī)約移進(jìn)規(guī)約接受. . . .. . 學(xué)習(xí)好幫手（4）不能用最右推導(dǎo)推導(dǎo)出上面的兩個句子。第七章已知文法： A → aAd|aAb|ξ判斷該文法是否是 SLR（1）文法，若是構(gòu)造相應(yīng)分析表，并對輸入串 ab給出分析過程。解：(0) A’→ A(1) A → aAd(2) A → aAb(3) A → ξ構(gòu)造該文法的活前綴 DFA：由上圖可知該文法是 SLR（1）文法。構(gòu)造 SLR（1）的分析表：ACTION GOTO狀態(tài)a d b A0 S2 R3 R3 R3 11 acc2 S2 R3 R3 R3 33 S4 S54 R1 R1 R15 R2 R2 R2輸入串 ab的分析過程：步驟 狀態(tài)棧 符號棧 輸入串 ACTION GOTO1 0 ab S22 02 a b R3 33 023 aA b S54 0235 aAb R2 15 01 A acc考慮文法：S →AS|b A→SA|a(1) 列出這個文法的所有 LR（0）項目I0： A’ →A A →aAdA →aAbA →I2：A →aAdA →aAbA →aAdA →aAbA →a I3： A →aAdA →aAbA I4： A →aAdI5：A →aAbdbI1：A’ →AAFollow(A)∩{a}=∮a. . . .. . 學(xué)習(xí)好幫手(2) 按（1）列出的項目構(gòu)造識別這個文法活前綴的 NFA，把這個 NFA確定化為 DFA，說明這個 DFA的所有狀態(tài)全體構(gòu)成這個文法的 LR（0）規(guī)范族。(3) 這個文法是 SLR的嗎？若是，構(gòu)造出它的 SLR分析表。(4) 這個文法是 LALR或 LR（1）的嗎？解：（0）S’→S (1)S→AS (2)S→b (3)A→SA (4)A→a (1)列出所有 LR（0）項目： S’→S S→b A→a S’→ S S→b A→a S →AS A→SA S →AS A→SA S →AS A→SA (3)構(gòu)造該文法的活前綴 NFA：I0：S’→SS →ASS →bA →SAA →aI1：S’→ SA →SAA →SAA →aS →ASS →bS I3：A →SAS →ASS →ASS →bA →SAA →aI5：S →ASA →SAA →SAA →aS →ASS →bI2：S →ASS →ASS →bA →SAA →aI4：A →SAA →SAA →aS →ASS →bI6：S →bI7：A →aAASA ASASA SSbabbbbaaaaab由上可知：I 1 I3 I5 中存在著移進(jìn)和歸約沖突在 I1中含項目：S’→ S 歸約項 Follow(S’)={}A →a 移進(jìn)項 Follow(S’)∩{a}=∮S →b 移進(jìn)項 Follow(S’)∩=∮在 I3中含項目：A →SA 歸約項 Follow(A)={a,b}S →b 移進(jìn)項 Follow(A) ∩ ≠∮A →a 移進(jìn)項 Follow(A) ∩ {a}≠∮在 I5中含項目：S →AS 歸約項 Follow(S)={,a,b}A →a 移進(jìn)項 Follow(S) ∩ {a}≠∮. . . .. . 學(xué)習(xí)好幫手S →b 移進(jìn)項 Follow(S) ∩ ≠∮由此可知，II5 的移進(jìn)與歸約沖突不能解決，所以這個文法不是 SLR（1）文法。（4）做 LR（1）項目集規(guī)范族 由上可知該文法不是 LR（1）文法，也不是 LALR（1）文法。一個類 ALGOL的文法如下：Program→Block Program →Compound StatementBlock→Block head。 Compound Tail Block head→begin dBlock head→Block head。d Compound Tail →S end Compound Tail →S。 Compound Tail Compound Statement→begin Compound Tail 試構(gòu)造其 LR（0）分析表。I1： S’→ S , A →SA ,a/bA →SA ,a/bA →a ,a/bS →AS ,a/bS →b ,a/bI0： S’→S ，S →AS ，a/b/S →b ,a/b/A →SA ,a/bA →a ,a/bI2：S →AS ,a/b/S →AS ,a/b/S →b ,a/b/A →SA ,a/bA →a ,a/bI3：S →b ,a/b/I4：A →a ,a/b/I5：(I 1A)A →SA ,a/bS →AS ,a/b