长安大学《编译原理》习题4

《长安大学《编译原理》习题4》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、习题4.2.1：考虑上下文无关文法：StSS+

2、SS*

3、q以及串aa+a*1)给出这个串的一个最左推导STSS*TSS+S*TaS+S*taa+s*->aa+a♦2)给出这个串的一个最右推导STss*tSa*->SS+a*tSa+a*->aa+a*3）给出这个串的一颗语法分析树4）这个文法是否是二义性的？证明你的回答不是二义性的，不存在两棵不同的分析树5）描述这个文法生成的语言只含有+和*,操作数均为a的算数表达式的后序遍历习题4.4.3：计算练习4.2.1的文法的FIRST和FOLLOW集合FIRST(S)=aFOLLOW(S)

4、=$a+*习题4.6.5：说明下面的文法：S^AaAbBbBaBtw是LL(1)的，但不是SLR(1)的证明：“ab”和“ba”可以由a或者b决定，故S(1)是LL(1)在SLR中，我们不能分解A或者B,这是一个规约，故S不是SLR(1)习题4.6.6：说明下面文法S^SAA力->a是SLR(1),而不是LL(1)的。证明：可以求得FIRST(SA)=FIRST(A)={a},故该文法不是LL(1)文法构建语法分析表如下(FOLLOW(A)=FOLLOW(S)={a,$})状态ACTIONGOTOA$SA0S3121S3acc

5、42R2R23R3R3故该文法是SLR(1)文法习题4.7・4：说明下面的文法SAabAc

6、de

7、bda力td是LALR(1)的，但不是SLR(1)的构建SLR语法分析表如下(FOLLOW(A)={a,c})状态ACTIONGOTOAbcd$SA0S3S4121acc2S53S764R5S8

8、R55R16S97S10

9、R5R58R39R210R4可以看到在图中存在二义性的条目，故该文法不是SLR(l)文法构造LALR(1)分析表如下状态ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8R55R16S

10、97S10R58R39R210R4可见该分析表中不存在二义性的条目，故该文法是LALR(l)文法习题4.7.5：说明下面的文法St4°

11、bAc

12、Be

13、bBa力tdB->d是LR(1)的，但不是LALR(1)的证明：构造LR(1)分析表如下状态ACTIONGOTOAbCd$SAB0S3S51241acc2S63S9784S105R5R66R17Sil8S129R6R510R311R212R4可见该分析表中不存在二义性的条目，故该文法是LR(1)文法构造LALR(l)语法分析表如下状态ACTIONGOTOabcd$SAB0S3S591

14、241acc2S63S9784S95R5

15、R6R5

16、R66R17S108Sil9R310R211R4可见该语法分析表中存在有二义性的条目，故该文法不是LALR(l)文法