资源描述：
《编译原理及实现课后习题答案绝杀版》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、2.1设字母表A={a},符号串x=aaa,写出下列符号串及其长度：xO,xx,X5以及A+和A*.x°=(aaa)°=£Ix°
2、=0xx=aaaaaaIxx
3、=6x=aaaaaaaaaaaaaaaA+=A1UA2U….UAnU•••={a,aa,aaa,aaaa,aaaaa>>e}A*=A°UAlUA2U••••UAnU•••={£,a,aa,aaa,aaaa,aaaaa・・・}2.2令E={a,b,c},又令x=abc,y=b,z=aab,写出如下符号串及它们的长度：xy,xyz,(xy)3xy=abcb
4、xy
5、=4xyz=abcbaabI
6、xyz
7、=7(xy)'二(abeb)3二abebabebabebI(xy)3
8、=122.3设有文法G[S]：S：：=SS*
9、SS+
10、a,写出符号串aa+a*规范推导，并构造语法树。S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*2.4已知文法G[Z]：Z：：=UO
11、VI>U：：=Z111、V：：=Z0
12、0,请写出全部由此文法描述的只含有四个符号的句子。Z=>UO=>Z1O二>U010=>1010Z二〉UO二〉Z10二〉V110二>0110z二〉VI二〉Z01二〉U001二>1001Z=>Vl=>Z01=>V101=>01012.
13、5已知文法G[S]：S：：=ABA：：=aA
14、£B：：=bBc
15、be,写出该文法描述的语言。A：：=aA
16、£描述的语言：{an
17、n>=0}B：：二bBc
18、be描述的语言：{bncn
19、n>=l}L(G[S])={aW
20、n>=0,m>=l}2.6已知文法E：：=T
21、E+T
22、E-T>T：：=F
23、T*F
24、T/F.F：：=(E)
25、i,写出该文法的开始符号.终结符号集合Vt・非终结符号集合Vn。2.8设有文法G[S]：S：：=S*S
26、S+S
27、(S)
28、a,S*SS+Sa开始符号：EVt={+,i}Vn={E,F,T}2.7对2.6题的文法，写出句型T+T*F
29、+i的短语、简单短语以及句柄。短语：T+T*F+iT+T*F••11TT*F简单短语：iT*FT句柄:T根据所给文法推导出句子a+a*a,画出了两棵不同的语法树，所以该文法是二义性文法。2.9写一文法，使其语言是奇正整数集合。A::=1
30、3
31、5
32、7
33、9
34、NAN::=0
35、l
36、2
37、3
38、4
39、5
40、6
41、7
42、8
43、92.10给出语言｛anb叫n,m>l｝的文法。G[S]:S::=ABA::二aA
44、aB::=bB
45、b3.1有正则文法G[Z]:Z::=Ua
46、Vb,U::=Zb
47、b,V::=Za
48、a,画出该文法的状态图，并检查句子abba是否合法。解：该文法的状态
49、图如下：b句子abba合法。右线性文法Vn={S,A}Vt={a,b}3.2状态图如图3.35所示，S为开始状态，Z为终止状态。写岀相应的正则文法以及V,Vn和也。解：左线性文法G[Z]:G，[S]:Z::=Ab
50、bS::=aA
51、bA::=Aa
52、aA::=aA
53、bV={Z,A,a,b}V={S,A,a,b}Vn={Z,A}Vt={a,b}3.3构造下列正则表达式相应的NFA：1(1
54、0)*
55、01(1010*11(010)*1)*0解:正则表达式：1(1
56、0)*
57、0解:aabqO={0}{0,1}{1}ql={0,1}{0,1}{1}q2二⑴{0
58、}eDFA:a.3.5将图3.37的DFA化简。图3.37DFA状态图-解:划分ab{0,1}{1}{2,4}{2,3,4,5}{1,0,3,5}{3,5,2,4}划分ab{0,1}{1}{2,4}{2,4}{0,1}{3,5}{3,5}{3,5}{2,4}q0={0,1}ql={2,4}q2={3,5}化简后的DFA：2.1对下面文法，设计递归下降分析程序。S->aAS
59、(A),A->Ab
60、c解：首先将左递归去掉，将规则A-Ab
61、c改成A->c{b}非终结符号S的分析程序如下：非终结符号A的分析程序如下:4.2设有文法G[Z]：Z：：=（A）
62、,A：：=a
63、Bb,B：：=Aab若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？解：若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。因为规则A：：=a
64、Bb和规则B：：=Aab构成了间接左递归，不满足实现没有回溯的递归下降分析方法的条件（1）（书P67）,且规则A::=a
65、Bb,FIRST（a）={a},FIRST（Bb）二{a},即此规则候选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的条件（2）（书P67）,在分析过程中，将造成回溯。改写文法可避免回溯：将规则B::=Aab代入规则A：
66、：=a
67、Bb得：A：：=a
68、Aabb,再转换成：A：：=a{abb},可避免回溯。4.3若有文法如下，设计递归下降分析程序。＜语句〉一〈语句X赋值语句
