编译原理,陈意云,课后答案.ppt

《编译原理,陈意云,课后答案.ppt》由会员分享，可在线阅读，更多相关《编译原理,陈意云,课后答案.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理习题课编译原理习题课(3)栾 俊1/4/20233.8(a)(a)消除3.1的左递归(b)在（a）的基础上构造LL(1)分析表1/4/3.8(a)(续续)S-(L)|aL-L,S|S只有直接左递归S-(L)|aL-SLL-,SL|1/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)=),$1/4/3.8(b)(续续)(),a$SS-(L)

2、S-aLL-SLL-SLLL-L-,SLL-1/4/3.16给出接收文法S-(L)|aL-L,S|S的LR(0)活前缀的DFA；并且在此基础上构造SLR(1)分析表.1/4/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-a1/4/3.16(续续)Goto(I0,S)=Goto(I0,()=Goto(I0,a)=I1S-S I3S-aI2S-(L)L-L,SL-SS-(L)S-a1/4/3.16(续续)Goto(I2,L)=Goto(I2,S)=Goto(I2,()=I2Goto(I2,a)

3、=I3I4S-(L )L-L ,SI5L-S 1/4/3.16(续续)Goto(I4,)=Goto(I4,)=I7L-L,SS-(L)S-aI6S-(L)1/4/3.16(续续)Goto(I6,S)=Goto(I6,()=I2Goto(I6,a)=I3I8L-L,S 1/4/3.16(续续)I8L-L,S I0S-SS-(L)S-aI1S-S I2S-(L)L-L,SL-SS-(L)S-aI3S-aI4S-(L )L-L ,SI6S-(L)S(aLSa(,I7L-L,SS-(L)S-aS(aI5L-S 1/4/3.16(续续)SLR(1)分析表构造1)若AaI，且goto(I,a)=J，则ac

4、tionI,a=sJ 2)若A I，则actionI,b=r A,b Follow(A)3)若SS I，则actionI,$=acc4)若goto(I,B)=K，则GOTOI,B=K5)其它为空白/error1/4/3.16(续续)状态actiongoto()a,$SL0s2s311s2s3acc2143r3r3r34s5s65r5r56r2r2r27s2s378r4r41/4/3.16(续续)S-(L)|aL-L,S|SFOLLOW(S)=$+FOLLOW(L)=$,),FOLLOW(L)=),1/4/3.23证明下面文法不是SLR(1)文法S-XX-Ma|bMc|dc|bdaM-d1/4/

5、3.23(续续)S-XX-Ma|bMc|dc|bdaM-d存在移进-规约冲突如句子dc，当d进栈后，面临c，此时项目X-d c要求移进，而c在FOLLOW(M)中，因此项目M-d 要求规约1/4/3.26一个非LR(1)的文法如下：L-MLb|aM-给出所有有移进-规约冲突的规范LR(1)项目集1/4/3.26(续续)拓广文法：L-LL-MLb|aM-I0I0L-L,$L-MLb,$L-a,$M-,$/a1/4/3.26(续续)I0L-L,$L-MLb,$L-a,$M-,aI1L-L,$LI2L-M Lb,$L-MLb,bL-a,bM-,aMI3L-a,$aI4L-M L b,$LI5L-M

6、Lb,bL-MLb,bL-a,bM-,aMI6L-a,baI7L-M L b,$bI8L-ML b,baLMI9L-ML b,bb1/4/3.26(续续)I0,I2,I5面临a时存在移进-规约冲突1/4/3.30下面哪个不是LR(1)文法？对非LR(1)文法给出所有冲突的LR(1)项目集S-aAcA-Abb|bS-aAcA-bAb|b1/4/3.30(续续)第二个不是LR(1)文法第二个文法在句子的正中心按A-b规约，而只向后看一位是无法判断是否到达句子的中心位置的存在冲突的项目集：S-aAc,$A-bAb,cA-b,cA-bAb,cA-bAb,bA-b,bAA-bAb,cA-b,cA-bAb,bA-b,bbA-bAb,bA-b,bA-bAb,bA-b,bbbb1/4/谢谢！谢谢！