编译原理陈意云课后答案.pptx
2023/4/2113.8(a)(a)消除的左递归(b)在（a）的基础上构造LL(1)分析表第1页/共24页2023/4/2123.8(a)(续)S-(L)|aL-L,S|S只有直接左递归S-(L)|aL-SLL-,SL|第2页/共24页2023/4/2133.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)=),$第3页/共24页2023/4/2143.8(b)(续)(),a$SS-(L)S-aLL-SLL-SLLL-L-,SLL-第4页/共24页2023/4/215给出接收文法S-(L)|aL-L,S|S的LR(0)活前缀的DFA；并且在此基础上构造SLR(1)分析表.第5页/共24页2023/4/2163.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第6页/共24页2023/4/2173.16(续)Goto(I0,S)=Goto(I0,()=Goto(I0,a)=I1S-S I3S-aI2S-(L)L-L,SL-SS-(L)S-a第7页/共24页2023/4/2183.16(续)Goto(I2,L)=Goto(I2,S)=Goto(I2,()=I2Goto(I2,a)=I3I4S-(L )L-L ,SI5L-S 第8页/共24页2023/4/2193.16(续)Goto(I4,)=Goto(I4,)=I7L-L,SS-(L)S-aI6S-(L)第9页/共24页2023/4/21103.16(续)Goto(I6,S)=Goto(I6,()=I2Goto(I6,a)=I3I8L-L,S 第10页/共24页2023/4/21113.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 第11页/共24页2023/4/21123.16(续)SLR(1)分析表构造1)若AaI，且goto(I,a)=J，则actionI,a=sJ 2)若A I，则actionI,b=r A,b Follow(A)3)若SS I，则actionI,$=acc4)若goto(I,B)=K，则GOTOI,B=K5)其它为空白/error第12页/共24页2023/4/21133.16(续)状态actiongoto()a,$SL0s2s311s2s3acc2143r3r3r34s5s65r5r56r2r2r27s2s378r4r4第13页/共24页2023/4/21143.16(续)S-(L)|aL-L,S|SFOLLOW(S)=$+FOLLOW(L)=$,),FOLLOW(L)=),第14页/共24页2023/4/2115证明下面文法不是SLR(1)文法S-XX-Ma|bMc|dc|bdaM-d第15页/共24页2023/4/21163.23(续)S-XX-Ma|bMc|dc|bdaM-d存在移进-规约冲突如句子dc，当d进栈后，面临c，此时项目X-d c要求移进，而c在FOLLOW(M)中，因此项目M-d 要求规约第16页/共24页2023/4/2117一个非LR(1)的文法如下：L-MLb|aM-给出所有有移进-规约冲突的规范LR(1)项目集第17页/共24页2023/4/21183.26(续)拓广文法：L-LL-MLb|aM-I0I0L-L,$L-MLb,$L-a,$M-,$/a第18页/共24页2023/4/21193.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 Lb,bL-MLb,bL-a,bM-,aMI6L-a,baI7L-M L b,$bI8L-ML b,baLMI9L-ML b,bb第19页/共24页2023/4/21203.26(续)I0,I2,I5面临a时存在移进-规约冲突第20页/共24页2023/4/2121下面哪个不是LR(1)文法？对非LR(1)文法给出所有冲突的LR(1)项目集S-aAcA-Abb|bS-aAcA-bAb|b第21页/共24页2023/4/21223.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,bbbb第22页/共24页2023/4/2123谢谢！谢谢！第23页/共24页2023/4/2124感谢您的观看！第24页/共24页
