资源描述：
《编译原理2习题答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2.设文法G(S):S→(L)
2、aS
3、aL→L,S
4、S(1)消除左递归和回溯;(2)计算每个非终结符的FIRST和FOLLOW;答：S→(L)
5、aS’S’→S
6、εL→SL’L’→,SL’
7、ε(2)FIRST和FOLLOWFIRST(S)={(,a)FIRST(S’)={,a,ε}FIRST(L)={(,a)FIRST(L’)={,,ε}4.构造正规式相应的NFA:1(0
8、1)*101解1(0
9、1)*101对应的NFA为4.已知文法G[S]为S→aSb
10、Sb
11、b，试证明文法G[S]为二义文法。证明：由文法G[S]：S→aSb
12、Sb
13、b，对句子aabbbb对应的两棵语法树为：1.构造正规式1(1
14、
15、0)*101所描述语言的DFA的状态转换图。解：先构造NFA：确定化：重新命名，令AB为B、AC为C、ABY为D得：所以，可得DFA为：2.对下面的文法G:E→TE'E'→+E
16、εT→FT'T'→T
17、εF→PF'F'→*F'
18、εP→(E)
19、a
20、b
21、^(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。(2)证明这个方法是LL(1)的。(3)构造它的预测分析表。解:(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有:FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^);FIRST(E')={+,ε}FIRST(T')
22、=FIRST(T)＋{ε}={(,a,b,^,ε);FIRST(F')={*,ε};FIRST(P)={(,a,b,^);FOLLOW集合有:FOLLOW(E)={),#};FOLLOW(E')=FOLLOW(E)={),#};FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,},#};//不包含εFOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,},#};FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含εFOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)=
23、{(,a,b,^,+,),#};FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε(2)证明这个方法是LL(1)的。各产生式的SELECT集合有:SELECT(E->TE')=FIRST(T)={(,a,b,^);SELECT(E'->+E)={+};SELECT(E'->ε)=FOLLOW(E/)={},#}SELECT(T->FT')=FIRST(F)={(,a,b,^);SELECT(T'->T)=FIRST(T)={(,a,b,^);SELECT(T'->ε)=FOLLOW(T/)={+,},#};SELECT(F->PF')=
24、FIRST(P)={(,a,b,^);SELECT(F'->*F')={*};SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,),#};SELECT(P->(E))={()SELECT(P->a)={a}SELECT(P->b)={b}SELECT(P->^)={^}可见,相同左部产生式的SELECT集的交集均为空,所以文法G[E]是LL(1)文法。(3)构造它的预测分析表。文法G[E]的预测分析表如下:1.考虑以下的文法：E→(L)
25、aL→L,E
26、E1)为这个文法构造LR(0)项目集规范族s。2)判断这个文法是否是LR(0)文法？若不是，请描述出LR(0)冲突，如果是
27、，则构造LR(0)分析表。3)判断这个文法是否是SLR(1)文法？若是，构造SLR(1)分析表答：拓广文法：(0)E’→E(1)E→(L)(2)E→a(3)L→L,E(4)L→E(I4：E→(L·)L→L·,E)LI2：E→(·L),I6：E→(L)·L→·L,EEL→·E(I7：L→L,·EI8：L→L,E·E→·(L)E→·(L)(E→·aE→·aEI0：E’→·EI5：L→E·E→·(L)AE→·a→·dEI1：E’ →E·aaI3：E→a·a是LR(0)文法,LR(0)分析表为:ACTIONGOTOa(),$EL0S3S211acc2S3S2543r2r2r2r2r24S6S75r4r
28、4r4r4r46r1r1r1r1r17S3S288r3r3r3r3r3非终结符Follow集合E’{$}E{},,$}L{},，}是SLR(1)文法
