编译原理第4章作业答案

第四章练习4.2.1:考虑上下文无关的语法：s-s | s * | a和字符串aa a*(1)给出这个字符串的最左边的派生S - S S *-南-南*- a S S *- a a S *aa a*(3)给出该字符串的语法分析树练习4.3.1:以下是仅包含符号A和符号B的正则表达式的语法。它使用符号|，表示联合运算，以避免与语法中用作元符号的垂直线混淆：rexpr rexpr rterm | rtermrtermrterm rfactor | rfactorrfactor rfactor * |说明rprimarya | b1)从该语法中提取公共因素2)提取公共因素的转换是否使这种语法适用于自顶向下的解析技术？3)提取公共因子后，在原方法中消除了左递归。4)所获得的语法是否适合自顶向下的语法分析？解决办法1)提取左公共因子后的语法变成rexpr rexpr rterm | rtermrtermrterm rfactor | rfactorrfactor rfactor * |说明rprimarya | b2)不，语法中有左递归，自顶向下技术不适合左递归语法3)消除左递归后的语法 rexpr - rterm rexpr rexpr- rterm rexpr|rterm- rfactor rterm rterm- rfactor rterm|rfactor-r primary rfactor rfactor- *rfactor|rprimary- a | b4)该语法没有左递归，适合自顶向下的语法分析。练习4.4.1:为下面的每种语法设计一个预测分析器，并给出一个预测分析表。可能有必要首先提取左公共因子或消除左递归用于语法。(3)S-S(S)S|(5)S-(L)|a L-L，S|S解决办法(3)(1)消除语法的左递归，得到语法S-S S-(S)SS|用类帕斯卡语言构造的预测分析器；程序S开始s。WHILE(前瞻=()然后开始匹配()；s。match()；结束；否则，如果(向前看=a)然后匹配(a)ELSE错误结束；(2)计算第一组和第二组第一(S)=(，跟随(S)=)，$第一个(S)=(，跟随(S)=)，$(3)构建预测分析表非终端符号传入符号（)$SS-S S-S S-S s -(秒)秒”S-S-(5)(1)消除语法的左递归，得到语法S-(L)|a“左-右”L-，SL|类帕斯卡语言的预测分析器；程序S开始if(前瞻=()然后开始匹配()；l。match()；结束；否则，如果(向前看=a)然后匹配(a)ELSE错误结束；程序1；开始s。WHILE(前瞻=，)；开始匹配(，s。结束；结束；(2)计算第一组和第二组第一(S)=(，a跟随(S)=)，$第一(L)=(，a跟随(L)= ) 第一个(L)=，跟随(L)= ) (3)构建预测分析表非终端符号传入符号（),a$SS-(L)S-aL“左-右”“左-右”l L-左-，左练习4.4.4计算练习4.2.2的第一组和第二组语法3)SS(S)S|5)S(L)|a、LL、S|S解决方案：3)第一(S)=，(跟随(S)=(，)，$ 5)第一(S)=(，a 跟随(S)=)，$ 第一(L)=(，a 跟随(L)=)，练习4.6.2为练习4.2.1中的扩充语法构造SLR项集，计算这些项集的GOTO函数，并给出该语法的语法分析表。这是单反语法吗？SSS |SS*|a解决方案：(1)构造语法的增广语法如下S-SSS-SSSS-SS *S-a(2)构造该语法的LR(0)项集如下I5SS-SS *。I4南南合作。I0S-。Ss。党卫军s。党卫军*s。aI1S-SS-S.SS-S.S* S-。党卫军s。党卫军*s。aI2S-a。I3南南合作。南南合作。*S-S.SS-S.S* S-。党卫军s。党卫军*s。a(3) GOTO功能如下转到(I0，S)=I1转到(I0，a)=I2GOTO(I1，S)=I3 GOTO(I1，a)=I2 GOTO(I1，美元)=accGOTO(I3，S)=I3 GOTO(I3)，=I4 GOTO(I3，*)=I5 GOTO(I3，a)=I2(4)构造语法的语法分析表州行为转到*a$S0S211S2acc32R3R3R3R33第四心音表面抗原-5S234R1R1R1R15R2R2R2R2注意：FOLLOW(S)=FOLLOW(S)=，*，a，$这个语法是单反语法，因为在解析表中没有重复的条目练习4.6.6解释以下语法SSA|A嗜酒者互诫协会它是单反(1)，而不是双反(1)。证据：1)可以获得第一(SA)=第一(A)=a，因此该语法不是L1(1)语法2)用于构造语法的扩充语法的语法分析表如下(1)构造扩充语法S-S南南合作特别助理A-a(2)构造LR(0)项集族I4南南合作。I3A-a .I2特别助理I1S-SS-S.Aa .aI0S-.Ss .SAs .Aa .aGOTO函数如下转到(I0，S)=I1转到(I0，A)=I2转到(I0，a)=I3转到(I1，A)=I4转到(I1，a)=I3转到(I1，美元)=acc构建语法分析表如下(FOLLOW(A)=FOLLOW(S)=a，$)状态行为转到a$SA0S3121S3acc42R2R23R3R34R1R1可以看到该语法分析表中没有重复的条目故该文法是单反(1)文法习题4.7.4说明下面的文法S-Aa|bAc|dc|bdaA-d是LALR(1)的，但不是单反(1)的证明：1 、构造该文法的单反(1)语法分析表构造增广文法S-SS-AaS-bAcS-dcS-bdaA-d构造左后(0)项集族I9S-bAc .I8S-dc .I6S-bA.cI5S-Aa .I2特别助理I1S-SI0S-.Ss .嗜酒者互诫协会s .bAcs .哥伦比亚特区s .bdaa .dI4S-d.c公元1000年.I3S-b.AcS-b.daa .dI10S-bda .I7S-bd.a公元1000年.GOTO函数转到(I0，S)=I1转到(I0，A)=I2转到(I0，b)=I3转到(I0，d)=I4GOTO(I1，$)=acc GOTO(I2，a)=I5 GOTO(I3，A)=I6 GOTO(I3，d)=I7GOTO(I4，c)=I8 GOTO(I6，c)=I9 GOTO(I7，a)=I10构建单反相机语法分析表如下(FOLLOW(A)=a，c)状态行为转到abcd$SA0S3第四心音121acc2表面抗原-53正常人血清中的一种蛋白质成分64R5S8|R55R16S97S10|R5R58R39R210R4可以看到在图中存在二义性的条目，故该文法不是单反(1)文法2、构造该文法的LALR(1)语法分析表构造该增广文法的左后(1)项集族如下I5S-Aa .$I7S-bd.a .美元A-d .cI9S-bAc .$I3S-b.Ac，$S-b.da，$a .d，cI1嘘。美元I0S-.美元s .Aa，$s .bAc，美元s .华盛顿特区美元s .bda，美元a .d，aI6S-bA.c .美元I10S-bda .$I8S-dc .$I2特别助理，美元I4S-d.c .美元A-d，美元项集合并：没有可以合并的项集GOTO函数转到(I0，S)=I1转到(I0，A)=I2转到(I0，b)=I3转到(I0，d)=I4GOTO(I1，$)=acc GOTO(I2，a)=I5 GOTO(I3，A)=I6 GOTO(I3，d)=I7GOTO(I4，c)=I8 GOTO(I6，c)=I9 GOTO(I7，a)=I10构造LALR(1)分析表如下状态行为转到abcd$SA0S3第四心音121acc2表面抗原-53正常人血清中的一种蛋白质成分64R5S8R55R16S97S10R58R39R210R4可见该分析表中不存在二义性的条目，故该文法是LALR(1)文法习题4.7.5说明下面的文法S-Aa|bAc|Bc|bBaA-dB-d是左后(1)的，但不是LALR(1)的证明：1 、构造该文法的左后(1)语法分析表构造该文法的增广文法S-SS-AaS-bAcS-BcS-bBaA-dB-d构造该增广文法的左后(1)项集族如下I10S-Bc .$I12S-bBa .$I2特别助理，美元I0S-.美元s .Aa，$s .bAc，美元s .Bc，美元s .bBa，美元a .d，ab .d，cI6S-Aa .$I1嘘。美元I7S-bA.c .美元I4S-B.c .美元I3S-b.Ac，$S-b.Ba，$a .d，cb .d，aI9A-d .cB-d，aI11S-bAc .$I8S-bB.a。美元I5A-d，aB-d，c项集合并：没有可以合并的