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

编译原理习题课(3)栾俊[e-mail]6/25/20202020/6/[e-mail]23.8(a)•(a)消除3.1的左递归(b)在（a）的基础上构造LL(1)分析表2020/6/[e-mail]33.8(a)(续)•S-(L)|aL-L,S|S•只有直接左递归S-(L)|aL-SL’L’-,SL’|ε2020/6/[e-mail]43.8(b)(续)•S-(L)|aL-SL’L’-,SL’|ε•FIRST(S)={(,a}FIRST(L)=FIRST(S)={(,a}FIRST(L’)={,,ε}•FOLLOW(S)=(FIRST(L’)-{ε})+FOLLOW(L)+FOLLOW(L’)+{$}={,,),$}FOLLOW(L)={)}FOLLOW(L’)=FOLLOW(L)={),$}2020/6/[e-mail]53.8(b)(续)(),a$SS-(L)S-aLL-SL’L-SL’L’L’-εL’-,SL’L’-ε2020/6/[e-mail]63.16•给出接收文法S-(L)|aL-L,S|S的LR(0)活前缀的DFA；并且在此基础上构造SLR(1)分析表.2020/6/[e-mail]73.16(续)•拓展文法：(1)S‘-S(2)S-(L)(3)S-a(4)L-L,S(5)L-S•初态：I0=closure{S’-∙S}=I0S’-∙SS-∙(L)S-∙a2020/6/[e-mail]83.16(续)•Goto(I0,S)=•Goto(I0,()=•Goto(I0,a)=I1S’-S∙I3S-a∙I2S-(∙L)L-∙L,SL-∙SS-∙(L)S-∙a2020/6/[e-mail]93.16(续)•Goto(I2,L)=•Goto(I2,S)=•Goto(I2,()=I2•Goto(I2,a)=I3I4S-(L∙)L-L∙,SI5L-S∙2020/6/[e-mail]103.16(续)•Goto(I4,))=•Goto(I4,,)=I7L-L,∙SS-∙(L)S-∙aI6S-(L)∙2020/6/[e-mail]113.16(续)•Goto(I6,S)=•Goto(I6,()=I2•Goto(I6,a)=I3I8L-L,S∙2020/6/[e-mail]123.16(续)I8L-L,S∙I0S’-∙SS-∙(L)S-∙aI1S’-S∙I2S-(∙L)L-∙L,SL-∙SS-∙(L)S-∙aI3S-a∙I4S-(L∙)L-L∙,SI6S-(L)∙S(aLSa((,I7L-L,∙SS-∙(L)S-∙aS(aI5L-S∙2020/6/[e-mail]133.16(续)•SLR(1)分析表构造1)若A∙a∈I，且goto(I,a)=J，则action[I,a]=sJ2)若A∙∈I，则action[I,b]=rA,b∈Follow(A)3)若S‘S∙∈I，则action[I,$]=acc4)若goto(I,B)=K，则GOTO[I,B]=K5)其它为空白/error2020/6/[e-mail]143.16(续)状态actiongoto()a,$SL0s2s311s2s3acc2143r3r3r34s5s65r5r56r2r2r27s2s378r4r42020/6/[e-mail]153.16(续)•S-(L)|aL-L,S|S•FOLLOW(S)={$}+FOLLOW(L)={$,),,}FOLLOW(L)={),,}2020/6/[e-mail]163.23•证明下面文法不是SLR(1)文法S-XX-Ma|bMc|dc|bdaM-d2020/6/[e-mail]173.23(续)•S-XX-Ma|bMc|dc|bdaM-d•存在移进-规约冲突如句子dc，当d进栈后，面临c，此时项目[X-d∙c]要求移进，而c在FOLLOW(M)中，因此项目[M-d∙]要求规约2020/6/[e-mail]183.26•一个非LR(1)的文法如下：L-MLb|aM-ε给出所有有移进-规约冲突的规范LR(1)项目集2020/6/[e-mail]193.26(续)•拓广文法：L’-LL-MLb|aM-ε•I0I0L’-∙L,$L-∙MLb,$L-∙a,$M-∙,$/a2020/6/[e-mail]203.26(续)I0L’-∙L,$L-∙MLb,$L-∙a,$M-∙,aI1L’-L∙,$LI2L-M∙Lb,$L-∙MLb,bL-∙a,bM-∙,aMI3L-a∙,$aI4L-ML∙b,$LI5L-M∙Lb,bL-∙MLb,bL-∙a,bM-∙,aMI6L-a∙,baI7L-MLb∙,$bI8L-ML∙b,baLMI9L-MLb∙,bb2020/6/[e-mail]213.26(续)•I0,I2,I5面临a时存在移进-规约冲突2020/6/[e-mail]223.30•下面哪个不是LR(1)文法？对非LR(1)文法给出所有冲突的LR(1)项目集S-aAcA-Abb|bS-aAcA-bAb|b2020/6/[e-mail]233.30(续)•第二个不是LR(1)文法第二个文法在句子的正中心按A-b规约，而只向后看一位是无法判断是否到达句子的中心位置的•存在冲突的项目集：S-a∙Ac,$A-∙bAb,cA-∙b,cA-b∙Ab,cA-∙bAb,bA-∙b,bAA-b∙Ab,cA-b∙,cA-∙bAb,bA-∙b,bbA-b∙Ab,bA-b∙,bA-∙bAb,bA-∙b,bbbb谢谢！！