编译原理第七章 习题参考答案

问题1已知语法AaAd|aAb|检查语法是否为SLR(1)语法，配置相应的分析表，并提供输入字符串ab#的分析过程。回答：语法：AaAd|aAb|扩展语法为G ，增加生成s a如果创建的排序为：0 S A1 A aAd2 A aAb3 A 已知的创建方法：First (S)=，aFirst (A)=，aFollow(S)=#Follow(A)=d，b，#如下图所示，显示了G 的LR(0)项目集族和标识活动前缀的DFA在I0中：A 。aAd和A 。给定语法，因为aAb是移动项，而a 对于返回项存在移动-返回冲突不是LR(0)语法。在I0、I2中：follow(a)- a = d，b，# 874 a=f因此，I0，I2中的移动-返回冲突可以用Follow集解决，因此g是SLR(1)语法。配置的SLR(1)分析表如下所示：输入字符串ab#分析流程：问题2如果有定义二进制数的语法：SLL|LLLB|BB0|1(1)配置此语法的LR分析表，并说明它是什么类型的LR分析表。(2)给出了输入字符串101.110的分析过程。回答：语法：SL.L|LLLB|BB0|1扩展语法为G ，增加生成s s如果创建的排序为：0 S S1 S L.L2 S L3 L LB4 L B5 B 06 B 1已知的创建方法：First (S)=0，1First (S)=0，1First (L)=0，1First (B)=0，1Follow(S)=#Follow(S)=#Follow(L)=。0，1，#Follow(B)=。0，1，#下图显示了g 的LR(0)项目集族和标识活动前缀的DFA。在I2中：B .0和B .1用于移动项目，S L .由于返回项目的移动-返回冲突，因此不给出语法LR(0)语法。在I2，I8中：follow(s)- 0，1= # - 0，1 =因此，I2，I8中的移动-返回冲突可以用Follow集解决，因此g是SLR(1)语法。配置的SLR(1)分析表如下所示：输入字符串101.110#分析：问题6语法G=(U，T，S，a，b，c，d，e，P，S)其中p为：SUTa|TbTS|Sc|dUUS|e(1)判断g是否为LR(0)、SLR(1)、LALR(1)或LR(1)，以说明原因。(2)配置相应的分析表。回答：语法：SUTa|TbTS|Sc|dUUS|e扩展语法为g，增加生成的SS。如果创建的排序为：0 S S1 S UTa2 S Tb3 T S4 T Sc5 T d6 U美国7 U e已知的创建方法：First (S)=d，eFirst (S)=d，eFirst (U)=eFirst (T)=d，eFollow(S)=#Follow(S)=a，b，c，d，e，#Follow(U)=d，eFollow(T)=a，b下图显示了g 的LR(0)项目集族和标识活动前缀的DFA。在I1中：S S .要接受项目，t S .要返回项目，T S.c是项目移动，接受-返回和移动-返回冲突，因此给定语法不是LR(0)语法。在I1中：follow(s)-follow(t)= # - a，b=ffollow(t)- c = a，b - c =f在I8中：follow(u)-follow(t)- c = d，e - a，b - c =f因此，I1中的