资源描述：
《编译原理及实现课后习题答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*.000x=(aaa)=ε
2、x
3、=0xx=aaaaaa
4、xx
5、=655x=aaaaaaaaaaaaaaa
6、x
7、=15+12nA=A∪A∪….∪A∪…={a,aa,aaa,aaaa,aaaaa…}012nA*=A∪A∪A∪….∪A∪…={ε,a,aa,aaa,aaaa,aaaaa…}2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3xy=abcb
8、xy
9、=4xyz=abcbaab
10、xyz
11、=7333(xy)=(a
12、bcb)=abcbabcbabcb
13、(xy)
14、=122.3设有文法G[S]：S∷=SS*
15、SS+
16、a，写出符号串aa+a*规范推导，并构造语法树。S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*SSS*SS+aaa2.4已知文法G[Z]：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写出全部由此文法描述的只含有四个符号的句子。Z=>U0=>Z10=>U010=>1010Z=>U0=>Z10=>V110=>0110Z=>V1=>Z01=>U001=>1001Z=>V1=>Z01=>V101=>01012.5已知文法G[S]：S∷=ABA∷=aA︱εB∷
17、=bBc︱bc,写出该文法描述的语言。nA∷=aA︱ε描述的语言:{a
18、n>=0}nnB∷=bBc︱bc描述的语言：{bc
19、n>=1}nmmL(G[S])={abc
20、n>=0,m>=1}2.6已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。开始符号：EVt={+,-,*,/,（,）,i}Vn={E,F,T}2.7对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。短语：T+T*F+iT+T*FiiETT*FE+T简单短语：iT*FTE+TF句柄：TTT*Fi2.8设有文
21、法G[S]：S∷=S*S
22、S+S
23、(S)
24、a，该文法是二义性文法吗？SSS*SS+SS+SaaS*Saaaa根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。2.9写一文法，使其语言是奇正整数集合。A::=1
25、3
26、5
27、7
28、9
29、NAN::=0
30、1
31、2
32、3
33、4
34、5
35、6
36、7
37、8
38、92.10给出语言{anbm
39、n,m≥1}的文法。G[S]:S::=ABA::=aA
40、aB::=bB
41、b3.1有正则文法G[Z]：Z::=Ua
42、Vb，U::=Zb
43、b，V::=Za
44、a，画出该文法的状态图，并检查句子abba是否合法。解：该文法的状态图如下：bSUabab
45、VZa句子abba合法。3.2状态图如图3.35所示，S为开始状态，Z为终止状态。写出相应的正则文法以及V，Vn和Vt。aaSAbbZ图3-35状态图解：左线性文法G[Z]:右线性文法G’[S]:Z::=Ab
46、bS::=aA
47、bA::=Aa
48、aA::=aA
49、bV={Z,A,a,b}V={S,A,a,b}Vn={Z,A}Vn={S,A}Vt={a,b}Vt={a,b}3.3构造下列正则表达式相应的NFA：1(1
50、0)*
51、01(1010*
52、1(010)*1)*0解：正则表达式：1(1
53、0)*
54、01、1(1
55、0)*
56、0SZ2、0SZ1(1
57、0)*3、0SZ01εA14、0q0q
58、110,1q2正则表达式：1(1010*
59、1(010)*1)*0100112113ε006810145703.4将图3.36的NFAM确定化aa,b01a图3.36状态图解：abq0={0}{0,1}{1}q1={0,1}{0,1}{1}q2={1}{0}ΦDFA:aaq1q0abbq23.5将图3.37的DFA化简。abb023abaaab1b4b5a图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
60、}q1={2,4}q2={3,5}化简后的DFA：bbaq0q1q2aab4.1对下面文法，设计递归下降分析程序。S→aAS
61、(A),A→Ab
62、c解：首先将左递归去掉，将规则A→Ab
63、c改成A→c{b}非终结符号S的分析程序如下：过程SNNINPUTSYM=’aINPUTSYM=’(’错误’YYINPUTSYM=下一个符号INPUTSYM=下一个符号过程A过程AN过程SINPUTSYM=’)’错误出口YINPUTSYM=下一个符号非终结符号A的分析程序如下：过程ANINPUTSYM=’c’错误YINPUTSYM=下一个符号NI
