編譯原理第七章習(xí)題參考答案.doc

第1 題已知文法AaAd|aAb|判斷該文法是否是SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對輸入串a(chǎn)b#給出分析過程。答案：文法：AaAd|aAb|拓廣文法為G，增加產(chǎn)生式SA若產(chǎn)生式排序?yàn)椋? S A1 A aAd2 A aAb3 A 由產(chǎn)生式知：First (S ) = ,aFirst (A ) = ,aFollow(S ) = #Follow(A ) = d,b,#G的LR(0)項(xiàng)目集族及識別活前綴的DFA 如下圖所示在I0 中：A .aAd 和A .aAb 為移進(jìn)項(xiàng)目，A .為歸約項(xiàng)目，存在移進(jìn)-歸約沖突，因此所給文法不是LR(0)文法。在I0、I2 中：Follow(A) a= d，b，# a=f所以在I0、I2 中的移進(jìn)-歸約沖突可以由Follow 集解決，所以G 是SLR(1)文法。構(gòu)造的SLR(1)分析表如下：對輸入串a(chǎn)b#的分析過程:第2 題若有定義二進(jìn)制數(shù)的文法如下：SLL|LLLB|BB0|1(1) 試為該文法構(gòu)造LR 分析表，并說明屬哪類LR 分析表。(2) 給出輸入串101.110 的分析過程。答案：文法：SL.L|LLLB|BB0|1拓廣文法為G，增加產(chǎn)生式SS若產(chǎn)生式排序?yàn)椋? S S1 S L.L2 S L3 L LB4 L B5 B 06 B 1由產(chǎn)生式知：First (S ) = 0,1First (S ) = 0,1First (L ) = 0,1First (B ) = 0,1Follow(S ) = #Follow(S ) = #Follow(L ) = .,0,1,#Follow(B ) = .,0,1,#G的LR(0)項(xiàng)目集族及識別活前綴的DFA 如下圖所示：在I2 中：B .0 和 B .1 為移進(jìn)項(xiàng)目，S L.為歸約項(xiàng)目，存在移進(jìn)-歸約沖突，因此所給文法不是LR(0)文法。在I2、I8 中：Follow(s) 0，1= # 0，1=所以在I2 、I8 中的移進(jìn)-歸約沖突可以由Follow 集解決，所以G 是SLR(1)文法。構(gòu)造的SLR(1)分析表如下：對輸入串101.110#的分析過:第6 題文法G=(U,T,S,a,b,c,d,e,P,S)其中P 為：SUTa|TbTS|Sc|dUUS|e(1) 判斷G 是LR(0)，SLR(1)，LALR(1)還是LR(1)，說明理由。(2) 構(gòu)造相應(yīng)的分析表。答案：文法：SUTa|TbTS|Sc|dUUS|e拓廣文法為G，增加產(chǎn)生式SS若產(chǎn)生式排序?yàn)椋? S S1 S UTa2 S Tb3 T S4 T Sc5 T d6 U US7 U e由產(chǎn)生式知：First (S ) = d,eFirst (S ) = d,eFirst (U ) = eFirst (T ) = d,eFollow(S ) = #Follow(S ) = a,b,c,d,e,#Follow(U ) = d,eFollow(T ) = a,bG的LR(0)項(xiàng)目集族及識別活前綴的DFA 如下圖所示：在I1 中：S S.為接受項(xiàng)目，T S. 為歸約項(xiàng)目，T S.c 為移進(jìn)項(xiàng)目，存在接受-歸約和移進(jìn)-歸約沖突，因此所給文法不是LR(0)文法。在I1 中：Follow(S) Follow(T)= # a ，b=fFollow(T) c= a ，b c=f在I8 中：Follow(U) Follow(T) c=d,e a ，b c=f所以在I1 中的