资源描述：
《编译原理(第3版)课本习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章高级语言及其语法描述6．（1）L（G6）={0,1,2,......,9}+（2）最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5687．【答案】Ｇ：S→ABC
2、AC
3、CA→1
4、2
5、3
6、4
7、5
8、6
9、7
10、8
11、9B→BB
12、
13、0
14、1
15、2
16、3
17、4
18、5
19、6
20、7
21、8
22、9C→1
23、3
24、5
25、7
26、98．（1）最左推导：E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iE=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=>i*(i+i)最右推导：E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*iE=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*
27、(T+i)=>T*(F+i)=>T*(i+i)=>F*(i+i)=>i*(i+i)E-TTFiEE-TFiFiE+TTFiEE+TFiFiE+TFiET*FiFiT(2)9．证明：该文法存在一个句子iiiei有两棵不同语法分析树，如下所示，因此该文法是二义的。SSeiSiSSiiSeiSiSiSiS→TS
28、TT→(S)
29、()10.【答案】无二义文法为：11.【答案】G1:S→ABA→aAb
30、abB→cB
31、εG2:S→ABA→aA
32、εB→bBc
33、bcG4:S→1S0
34、AA→0A1
35、εG3:S→AAA→aAb
36、ε第3章词法分析7．构造下列正规式相应的D
37、FA：(1)1(0
38、1)*101解：（1）构造NFA：0X152Y0,113411（2）确定化：构造状态转换矩阵如下：重命名：II0I1{X}-{1,5,2}{1,5,2}{5,2}{5,3,2}{5,2}{5,2}{5,3,2}{5,3,2}{5,4,2}{5,3,2}{5,4,2}{5,2}{5,Y,3,2}{5,Y,3,2}{5,4,2}{5,3,2}S010-1123223343425543(3)化简(4)化简之后的状态表分组{0,1,2,3,4}{5}S010-1112232314432考察{0,1,2,3,4}0={2,4}{0,1,2
39、,3,4}1={1,3,5}∴分化为：{0,1,2,3}、{4}、{5}再考察：{0,1,2,3}0={2,4}∴分化为：{0,1,2,}、{3}、{4}、{5}再考察：{0,1,2}0={2}{0,1,2}1={1,3}∴分化为：{0}、{1,2,}、{3}、{4}、{5}(5)画出状态转换图：01210130104101(3)0*10*10*10*解：（1）构造NFA：11X712Y8349561010000（2）确定化：构造状态转换矩阵如下：重命名：II0I1{X,7,1}{7,1}{2,8,3}{7,1}{7,1}{2,8,3}{2,8,3
40、}{8,3}{4,9,5}{8,3}{8,3}{4,9,5}{4,9,5}{9,5}{6,10,Y}{9,5}{9,5}{6,10,Y}{6,10,Y}{10,Y}--{10,Y}{10,Y}--S0101211223433445655667-77-(3)化简如上表所示：{0,1}、{2,3}、{4,5}、{6,7}化简后的状态表为：S0100111222333-（4）最简DFA状态转换图012311100008．（1）（0
41、1）*01（2）∑={0，1，2，3，4，5，6，7，8，9}((1
42、2
43、3
44、4
45、5
46、6
47、7
48、8
49、9）∑*(0
50、5))
51、（0
52、
53、5）（3）1*0((01*0)︱1)*︱0*1((10*1)︱0)*（4）a*b*c*......z*(5)(x0︱)(x1︱)(x2︱)......(x9︱)∑={0,1,.....,9}其中x0∈∑xi∈∑-{x0,......,xi-1}i=1,......,9(6)(x0︱)y0(x1︱)y1(x2︱)y2......(x9︱)y9其中x0∈∑xi∈∑-{x0,......,xi-1}i=1,......,9如果ym≠,则yn=(m=0,......,9)(n=0,1,...,m-1,m+1,...,9)其中y0,...,y9∈{,0,1
54、,...,9}(7)b*(a︱ab)*9．（1）正规式（0
55、1）*（010）（0
56、1）*①NFA:0,10,101X12Y
