《编译原理作业解析(13) (1)》由会员分享，可在线阅读，更多相关《编译原理作业解析(13) (1)（11页珍藏版）》请在金锄头文库上搜索。
1、1,编译原理作业辅导 第四章语法分析,第十一次作业P146 22、24(1)(2),24. 给定文法： EEE+ | EE* | a （1）构造它的LR(0)项目集规范族；在上述文法中引入新的开始符号E,并将E作为第0个规则r1:E=EE+ r2: E=EE* r3: E=a 则基本LR(0)项目集为： E=E E=E E=EE+ E=EE+ E=EE+ E=EE+ E=EE* E=EE* E=EE* E=EE* E=a E=a,第十一次作业P146 22、24(1)(2),第十一次作业P146 22、24(1)(2),2)在I1中存在“移进E-a”和“归约：E-E”冲突，因此该文法不是LR(
2、0)文法，但有FOLLOW(E)=#a=，而该动作冲突可用SLR(1)方法解决，该文法是SLR(1)文法，其分析表如下：,第十二次作业P146 24(3)(4) 26 30,26. 对如下文法G： SS(S) S 构造LR(1)项目规范集以及LR(1)分析表，并用分析器给出()的分析过程。,引入开始符号S。则拓广文法：S-S，S-S(S)，S-。其中r1: S-S(S) r2: S-,第十二次作业P146 24(3)(4) 26 30,LR(1)分析表如下所示：,第十二次作业P146 24(3)(4) 26 30,分析符号串（）,第十二次作业P146 24(3)(4) 26 30,P148 3
3、0. 给出如下文法： G1S: SaSbS | aS | c G2S: SaAa | aBb Ax Bx G3S: SaAa | aBb| bAb Ax Bx G4S: SaAa | aBb| bAb| bBa Ax Bx 1)证明二义性文法G1S不是LR(0)文法； 2)证明G2S是SLR(1)文法但不是LR(0)文法； 3)证明G3S是LR(1)文法但不是SLR(1)文法； 4)证明G4S是LR(1)文法但不是LALR文法。,1)证明：构造其LR(0)项目集： I0: S-S S-aSbS S-aS S-c I1: S-aSbS S-aS S-c S-aSbS S-aS I2: S-aSb
4、S S-aS 因为I2中出现了“移进-归约”冲突，因此不是LR(0)文法；,第十二次作业P146 24(3)(4) 26 30,2)证明：构造其LR(0)项目集： I0: S-S S-aAa S-aBb I1: S-S I2: S-aAa S-aBb A-x B-x I3: S-aAa I4: S-aBb I5: A-x B-x I6: S-aAa I7: S-aBb 由于I5中出现了“归约-规约”冲突，因此G2S不是LR(0)文法； FOLLOW(A)=aFOLLOW(B)=b= ACTIONi, a=“用产生式A-x进行归约”；ACTIONi, b=“用产生式B-x进行归约”；,第十二次作
5、业P146 24(3)(4) 26 30,3)证明：构造其LR(1)项目集： I0: S-S, # S-aAa, # S-aBb, # S-bAb, # I1: S-S, # I2: S-aAa, # A-x, a S-aBb, # B-x, b I3: S-bAb, # A-x, b I4: A-x, a B-x, b （其余从略）此时由I4可知存在“归约-归约”冲突，且FOLLOW(A)=a,bFOLLOW(B)=b 故该文法不是SLR(1)文法，但有ACTIONi, a=“用产生式A-x进行归约”，ACTIONi, b=“用产生式B-x进行归约”，所以是LR(1)文法。,4)证明：构造其
6、LR(1)项目规范集： I0: S-S, # S-aAa, # S-aBb, # S-bAb, # S-bBa, # I1: S-S, # I2: S-aAa, # S-aBb, # A-x, a B-x, b I3: S- bAb, # S-bBa, # A-x, b B-x, a I4: S-aAa, # I5: S-aBb, # I6: A-x, a B-x, b I7: S-bAb, # I8: S-bBa, # I9: A-x, b B-x, a I10: S-aAa, # I11: S-aBb, # I12: S-bAb, # I13: S-bBa, # 对于I6与I9并不存在“归约-归约”冲突，于LR(1)文法相符； 然合并同心集I6和I9，得：A-x, a/b B-x, a/b 出现了“归约-归约”冲突，故该文法并非LALR文法。,
