编译原理陈意云 课后答案

编译原理习题课(3),栾俊luanj2020/5/27,2020/5/27,luanj,2,3.8(a),(a)消除3.1的左递归(b)在（a）的基础上构造LL(1)分析表,2020/5/27,luanj,3,3.8(a)(续),S-(L)|aL-L,S|S只有直接左递归S-(L)|aL-SLL-,SL|,2020/5/27,luanj,4,3.8(b)(续),S-(L)|aL-SLL-,SL|FIRST(S)=(,aFIRST(L)=FIRST(S)=(,aFIRST(L)=,FOLLOW(S)=(FIRST(L)-)+FOLLOW(L)+FOLLOW(L)+$=,),$FOLLOW(L)=)FOLLOW(L)=FOLLOW(L)=),$,2020/5/27,luanj,5,3.8(b)(续),2020/5/27,luanj,6,3.16,给出接收文法S-(L)|aL-L,S|S的LR(0)活前缀的DFA；并且在此基础上构造SLR(1)分析表.,2020/5/27,luanj,7,3.16(续),拓展文法：(1)S-S(2)S-(L)(3)S-a(4)L-L,S(5)L-S初态：I0=closureS-S=,I0S-SS-(L)S-a,2020/5/27,luanj,8,3.16(续),Goto(I0,S)=Goto(I0,()=Goto(I0,a)=,I1S-S,I3S-a,I2S-(L)L-L,SL-SS-(L)S-a,2020/5/27,luanj,9,3.16(续),Goto(I2,L)=Goto(I2,S)=Goto(I2,()=I2Goto(I2,a)=I3,I4S-(L)L-L,S,I5L-S,2020/5/27,luanj,10,3.16(续),Goto(I4,)=Goto(I4,)=,I7L-L,SS-(L)S-a,I6S-(L),2020/5/27,luanj,11,3.16(续),Goto(I6,S)=Goto(I6,()=I2Goto(I6,a)=I3,I8L-L,S,2020/5/27,luanj,12,3.16(续),I8L-L,S,I0S-SS-(L)S-a,I1S-S,I2S-(L)L-L,SL-SS-(L)S-a,I3S-a,I4S-(L)L-L,S,I6S-(L),S,(,a,L,S,a,(,(,I7L-L,SS-(L)S-a,S,(,a,I5L-S,2020/5/27,luanj,13,3.16(续),SLR(1)分析表构造1)若AaI，且goto(I,a)=J，则actionI,a=sJ2)若AI，则actionI,b=rA,bFollow(A)3)若SSI，则actionI,$=acc4)若goto(I,B)=K，则GOTOI,B=K5)其它为空白/error,2020/5/27,luanj,14,3.16(续),2020/5/27,luanj,15,3.16(续),S-(L)|aL-L,S|SFOLLOW(S)=$+FOLLOW(L)=$,),FOLLOW(L)=),2020/5/27,luanj,16,3.23,证明下面文法不是SLR(1)文法S-XX-Ma|bMc|dc|bdaM-d,2020/5/27,luanj,17,3.23(续),S-XX-Ma|bMc|dc|bdaM-d存在移进-规约冲突如句子dc，当d进栈后，面临c，此时项目X-dc要求移进，而c在FOLLOW(M)中，因此项目M-d要求规约,2020/5/27,luanj,18,3.26,一个非LR(1)的文法如下：L-MLb|aM-给出所有有移进-规约冲突的规范LR(1)项目集,2020/5/27,luanj,19,3.26(续),拓广文法：L-LL-MLb|aM-I0,I0L-L,$L-MLb,$L-a,$M-,$/a,2020/5/27,luanj,20,3.26(续),2020/5/27,luanj,21,3.26(续),I0,I2,I5面临a时存在移进-规约冲突,2020/5/27,luanj,22,3.30,下面哪个不是LR(1)文法？对非LR(1)文法给出所有冲突的LR(1)项目集S-aAcA-Abb|bS-aAcA-bAb|b,2020