編譯原理第七章答案

1、第7章LR分析已知文法LaAd|aAb|&ab#給出分析過(guò)程。判斷該文法是否是SLR(1)文法，若是構(gòu)造相應(yīng)分析表，弁對(duì)輸入串答案：文法:AAaAd|aAb|&拓廣文法為G,增加產(chǎn)生式STA若產(chǎn)生式排序?yàn)?0STA1ATaAd2ATaAb3AT由產(chǎn)生式知:First(S)=&,aFirst(A)=,aFollow(S)=#Follow(A)=d,b,#DFA如下圖所示:G的LR(0)項(xiàng)目集族及識(shí)別活前綴的b：AfxAdA匈IAbAf?aAd人f.&AbAf?A .為歸約項(xiàng)R),存在移進(jìn)-歸約沖突，因此所給文法不是=0在I。中：A-.aAd和AaAb為移進(jìn)項(xiàng)目,LRft?文法*在IQXId中:F

2、ollow(A)na=drb,#n(a所以在I。、12中的移進(jìn)-歸約沖突可以由Follow集解決，所以G是SLR文法。構(gòu)造的SLR(1)分析表如下:題目1的SLR(1)分析表狀態(tài)(State)ActionGotoadbftA0S2t3r3r311acc91S2r3r3r333S4Sb4rlrlrl5r2r2r2題IJ1對(duì)輸入串甜H的分析過(guò)程狀態(tài)棧(stfit亡stack)文法符號(hào)棧剩余輸入串(input1亡ft)動(dòng)件(action)二ab#Shiftp26aReduceby:Ab23EaAb執(zhí)Shift0235paAbReduceby:A-*aAbfl1.=4n分析成功，說(shuō)明輸入串a(chǎn)b是文法的

3、句子。第2題若有定義二進(jìn)制數(shù)的文法如下：STL?L|LLTLB|BBT0|1(1)試為該文法構(gòu)造LR分析表，弁說(shuō)明屬哪類LR分析表。給出輸入串101.110的分析過(guò)程。答案：文法：STL.L|LLTLB|BBT0|1拓廣文法為G,增加產(chǎn)生式STS若產(chǎn)生式排序?yàn)椋?STSSTl.lSTLLTLBLTBBT0BT1由產(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)目集族及識(shí)別活前綴的DFA如下圖所示在I2中:BT.

4、0和BT.1為移進(jìn)項(xiàng)目，STL.為歸約項(xiàng)目，存在移進(jìn)-歸約沖突，因此所給文法不是LR(0)文法。在I2、|8中:Follow(s)n0,1=#n0,1=所以在12、|8中的移進(jìn)-歸約沖突可以由Follow集解決，所以G是SLR(1)文法。構(gòu)造的SLR(1)分析表如下:題目2的SLR(1)分析表狀態(tài)(State)ActionGoto?01SLB0S4S51231acc?2S6S4S5r273r4r4r4r4?4r5r5r5r5?5r6r6r6r6?6S4S583r3r3r3r3?8S4S5rl7題RI2對(duì)輸入吊101.110A的分析過(guò)程狀態(tài)棧(statestack)文法符號(hào)棧剩余輸入串(inpu

5、tleft)動(dòng)作(action)t?101.110#.ShiftP5?101.110?Reduceby:B-1034B01.110#.Reduceby:SfLBK)2SL01.110#.Shift024?L01.110#.Reduceby:B-0027薦LB1.110#.Reduceby:S?LBK)2ni1.110#?Shift025t?Ll?110#.Reduceby:B-1027i?LB.no#.Reduceby:S?LBK)2?110屯?Shift”26SL.lion.?.ShiftIo265i?L.110#Reduceby:B?1p263CL.B100?deduceby:SB0268*L?L10#Shift02685禮？L10屯deduceby:B?102687r?L.LB00?deduceby:SLB0268f?L.L0#?Shif