編譯原理習(xí)題

1、第1題已知文法A aAd|aAb| 判斷該文法是否是 SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對輸入串a(chǎn)b#合出分析過程。答案：文法：A aAd|aAb| 拓廣文法為G,增加產(chǎn)生式S A若產(chǎn)生式排序為：0 S A1 A aAd2A aAb3 A 由產(chǎn)生式知：First (S ) = ,aFirst (A ) = ,aFollow(S ) = #Follow(A ) = d,b,#G的LR(0)項目集族及識別活前綴的DFA如下圖所示在I 0中：A .aAd和A .aAb為移進(jìn)項目，A .為歸約項目，存在移進(jìn)-歸約沖突，因此所給文法 不是LR(0)文法。在I 0、I 2中：Follow(A) n

2、a= d , b, # n a=所以在I。、丨2中的移進(jìn)-歸約沖突可以由Follow 集解決，所以G是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下：對輸入串a(chǎn)b#的分析過程狀態(tài)棧(state slack)文法符號棧剌険輸入串(input left)功作(呂uticin)0ab#,Shift0 2哺.Reduce by :Ap 2 3b#.Shift0 2 3 5Reduce by :A -*aAbP 1歎第2題若有定義二進(jìn)制數(shù)的文法如下：S L L|LL LB|BB 0|1(1)試為該文法構(gòu)造LR分析表，并說明屬哪類LR分析表 給出輸入串101.110的分析過程。答案：文法：S L.L|L

3、L LB|BB 0|1拓廣文法為G,增加產(chǎn)生式S S若產(chǎn)生式排序為：0 S S1 S L.L2 S L3 L LB4 L B5 B t 06 B t 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)項目集族及識別活前綴的DFA如下圖所示:在I 2中：因此所給文法不B t .0和B t .1為移進(jìn)項目，S t L.為歸約項目，存在移進(jìn)-歸約沖突, 是LR(

4、0)文法。在 12、丨8 中：Follow(s) n 0 , 1= # n 0 ,所以在12、|8中的移進(jìn)-歸約沖突可以由Follow 集解決，所以G是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下：狀態(tài)(State)ActionG01 01徉SLB j0S4S51231acc.2S6S4S5r273r4r4r4r4!4r5r5r5r55r6r6r6r66S4S5837r3r3r3t3-g1S4ssrl7對輸入串101.110#的分析過：狀態(tài)棧state stack)00 50 30 20 2 40 2 70 20 2 50 2 70 20 2 60 2 6 50 2 6 30 2 6 80

5、 2 6 S 50 2 6 8 70 2 6 S0 2840 2 6 8 7U 1文法符號棧岸#L虹0 甘LB ttL#L1*LB#L札虹.1#LB 也L#LL1k.LB#LLKL.LO*L.LB剩余輸入串101.110#.01.110#.,01,110#.01.110# 1.110# 1. 110# 1.110#.110#.110#.110#110# 10#10#10#.0#0#0#井甘#.Shift動柞(setion)by:B-1by:S-LBby:B-0by:SLBby:B一1by:S-LBby:B-1by:S-Bby:B-*1by:S-LBby:BTby:S-L.LReduceRtdu

6、ceReducededuceShiftShiftdeduceduceShiftductdeduceShiftReduceShiftReduceReduceReduceShift第6 題文法 G=(U,T,S,a,b,c,d,e,P,S)其中 P 為：S UTa|TbT S|Sc|dUUS|e(1) 判斷G是LR(O) , SLR(1), LALR還是LR，說明理由(2) 構(gòu)造相應(yīng)的分析表。答案：文法：SUTa|TbTS|Sc|dUUS|e 拓廣文法為 G ，增加產(chǎn)生式 S S 若產(chǎn)生式排序為：O S S1 S UTa2 S Tb3 T S4 T Sc5 T d6 U US7 U e 由產(chǎn)生式知

7、： First (S ) = d,e First (S ) = d,e First (U ) = e First (T ) = d,e Follow(S ) = #Follow(S ) = a,b,c,d,e,#Follow(U ) = d,eFollow(T ) = a,bG的LR(O)項目集族及識別活前綴的DFA如下圖所示:AIt：S-UT,&T-*S.It：Iq：h TbT-iTr:UIs：ETUf US在11中：S t S.為接受項目，T t S.為歸約項目，T tS.c為移進(jìn)項目，存在接受-歸約和移進(jìn)- 歸約沖突，因此所給文法不是LR(0)文法。在I 1中：Follow(S) n Follow(T)= # n a , b=Follow(T) n c= a , b n c=在I 8中：Follow(U) n Follow(T) n c=d,e n a , b n c=所以在I1中的接受-歸約和移進(jìn)-歸約沖突與I 8中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow 集解決，所以G是SLR(1)文法。構(gòu)造的SLR(1)分析表