《编译原理陈意云课后答案3》由会员分享，可在线阅读，更多相关《编译原理陈意云课后答案3（25页珍藏版）》请在金锄头文库上搜索。
1、编译原理习题课编译原理习题课(3)栾 俊7/26/20242024/7/23.8(a)(a) 消除3.1的左递归(b) 在（a）的基础上构造LL(1)分析表2024/7/33.8(a) (续续)S - (L)|aL - L,S|S只有直接左递归S - (L)|aL - SLL- ,SL|2024/7/43.8(b) (续续)S - (L)|aL - SLL- ,SL| FIRST(S) = (, aFIRST(L) = FIRST(S) = (, aFIRST(L) = , FOLLOW(S) = (FIRST(L)-) + FOLLOW(L) + FOLLOW(L) + $ = , ), $
2、FOLLOW(L) = )FOLLOW(L) = FOLLOW(L) = ),$2024/7/53.8(b) (续续)(),a$SS - (L)S - aLL - SLL - SLLL - L- ,SLL - 2024/7/63.16给出接收文法S - ( L ) | aL - L , S | S的LR(0)活前缀的DFA；并且在此基础上构造SLR(1)分析表.2024/7/73.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
3、2024/7/83.16 (续续)Goto(I0, S) = Goto(I0, () = Goto(I0, a) =I1S - S I3S - aI2S - ( L) L - L , SL - SS - (L) S - a2024/7/93.16 (续续)Goto(I2, L) = Goto(I2, S)=Goto(I2, ()=I2Goto(I2, a)=I3I4S - (L ) L - L , SI5L - S 2024/7/103.16 (续续)Goto(I4, ) = Goto(I4, ,)=I7L - L , SS - (L) S - aI6S - (L ) 2024/7/113.1
4、6 (续续)Goto(I6, S) =Goto(I6, () =I2Goto(I6, a) =I3I8L - L , S 2024/7/123.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 2024/7/133.16 (续续)SLR(1)分析表构造1) 若AaI，且goto(I,a)=J，则actionI,a=s
5、J 2)若A I，则actionI,b = r A,bFollow(A)3)若SS I，则actionI,$ = acc4)若goto(I,B)=K，则GOTOI,B=K5)其它为空白/error2024/7/143.16 (续续)状态actiongoto()a,$SL0s2s311s2s3acc2143r3r3r34s5s65r5r56r2r2r27s2s378r4r42024/7/153.16 (续续)S - ( L ) | aL - L , S | SFOLLOW(S) = $ + FOLLOW(L) = $, ), ,FOLLOW(L) = ), ,2024/7/163.23证明下面文
6、法不是SLR(1)文法S - XX - Ma | bMc | dc | bdaM - d2024/7/173.23 (续续)S - XX - Ma | bMc | dc | bdaM - d存在移进-规约冲突如句子dc，当d进栈后，面临c，此时项目X - d c要求移进，而c在FOLLOW(M)中，因此项目M - d 要求规约2024/7/183.26一个非LR(1)的文法如下：L - MLb | aM - 给出所有有移进-规约冲突的规范LR(1)项目集2024/7/193.26 (续续)拓广文法：L - LL - MLb | aM - I0I0L - L, $L - MLb, $L - a,
7、 $M - , $/a2024/7/203.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 , bb2024/7/213.26 (续续)I0,I2,I5面临a时存在移进-规约冲突2024/7/223.30下面哪个不是LR
8、(1)文法？对非LR(1)文法给出所有冲突的LR(1)项目集S-aAcA-Abb|bS-aAcA-bAb|b2024/7/233.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谢谢！谢谢！25 以上有不当之处，请大家给与批评指正，以上有不当之处，请大家给与批评指正，谢谢大家！谢谢大家！
