编译原理第七章答案

1、第7章LR分析已知文法LaAd|aAb|&ab#给出分析过程。判断该文法是否是SLR(1)文法，若是构造相应分析表，弁对输入串答案：文法:AAaAd|aAb|&拓广文法为G,增加产生式STA若产生式排序为:0STA1ATaAd2ATaAb3AT由产生式知:First(S)=&,aFirst(A)=,aFollow(S)=#Follow(A)=d,b,#DFA如下图所示:G的LR(0)项目集族及识别活前缀的b：AfxAdA匈IAbAf?aAd人f.&AbAf?A .为归约项R),存在移进-归约冲突，因此所给文法不是=0在I。中：A-.aAd和AaAb为移进项目,LRft?文法*在IQXId中:F

2、ollow(A)na=drb,#n(a所以在I。、12中的移进-归约冲突可以由Follow集解决，所以G是SLR文法。构造的SLR(1)分析表如下:题目1的SLR(1)分析表状态(State)ActionGotoadbftA0S2t3r3r311acc91S2r3r3r333S4Sb4rlrlrl5r2r2r2题IJ1对输入串甜H的分析过程状态栈(stfit亡stack)文法符号栈剩余输入串(input1亡ft)动件(action)二ab#Shiftp26aReduceby:Ab23EaAb执Shift0235paAbReduceby:A-*aAbfl1.=4n分析成功，说明输入串ab是文法的

3、句子。第2题若有定义二进制数的文法如下：STL?L|LLTLB|BBT0|1(1)试为该文法构造LR分析表，弁说明属哪类LR分析表。给出输入串101.110的分析过程。答案：文法：STL.L|LLTLB|BBT0|1拓广文法为G,增加产生式STS若产生式排序为：0STSSTl.lSTLLTLBLTBBT0BT1由产生式知：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如下图所示在I2中:BT.

4、0和BT.1为移进项目，STL.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I2、|8中:Follow(s)n0,1=#n0,1=所以在12、|8中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下:题目2的SLR(1)分析表状态(State)ActionGoto?01SLB0S4S51231acc?2S6S4S5r273r4r4r4r4?4r5r5r5r5?5r6r6r6r6?6S4S583r3r3r3r3?8S4S5rl7题RI2对输入吊101.110A的分析过程状态栈(statestack)文法符号栈剩余输入串(inpu

5、tleft)动作(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