编译原理与实践教程(黄贤英王柯柯编著)习题集答案解析

编译原理与实践教程(黄贤英王柯柯编著)习题集答案解析

ID:47373954

大小:1.04 MB

页数:36页

时间:2019-07-20

编译原理与实践教程(黄贤英王柯柯编著)习题集答案解析_第1页
编译原理与实践教程(黄贤英王柯柯编著)习题集答案解析_第2页
编译原理与实践教程(黄贤英王柯柯编著)习题集答案解析_第3页
编译原理与实践教程(黄贤英王柯柯编著)习题集答案解析_第4页
编译原理与实践教程(黄贤英王柯柯编著)习题集答案解析_第5页
资源描述:

《编译原理与实践教程(黄贤英王柯柯编著)习题集答案解析》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第2章参考答案:1,2,3:解答:略!4.解答: A:① B:③ C:① D:② 5.解答:用E表示<表达式>,T表示<项>,F表示<因子>,上述文法可以写为:E→T

2、E+TT→F

3、T*FF→(E)

4、i最左推导:E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T=>i+i+F=>i+i+iE=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i最右推导:E=>E+T=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i=>F+

5、i+i=>i+i+iE=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*ii+i+i和i+i*i的语法树如下图所示。i+i+i、i+i*i的语法树6.解答:(1)终结符号为:{or,and,not,(,),true,false}非终结符号为:{bexpr,bterm,bfactor}开始符号为:bexpr(2)句子not(trueorfalse)的语法树为:7.解答:(1)把anbnci分成anbn和ci两部分,分别由两个非终结符号生成,因此,生成此文法的产生式为:S→ABA→a

6、Ab

7、abB→cB

8、e(2)令S为开始符号,产生的w中a的个数恰好比b多一个,令E为一个非终结符号,产生含相同个数的a和b的所有串,则产生式如下:S→aE

9、Ea

10、bSS

11、SbS

12、SSbE→aEbE

13、bEaE

14、e(3)设文法开始符号为S,产生的w中满足

15、a

16、≤

17、b

18、≤2

19、a

20、。因此,可想到S有如下的产生式(其中B产生1到2个b):S→aSBS

21、BSaSB→b

22、bb(4)解法一:S→〈奇数头〉〈整数〉〈奇数尾〉     

23、〈奇数头〉〈奇数尾〉     

24、〈奇数尾〉 〈奇数尾〉→1

25、3

26、5

27、7

28、9 〈奇数头〉→2

29、4

30、6

31、8

32、〈奇数尾〉 〈

33、整数〉→〈整数〉〈数字〉

34、〈数字〉 〈数字〉→0

35、〈奇数头〉解法二:文法G=({S,A,B,C,D},{0,1,2,3,4,5,6,7,8,9},P,S)S→AB

36、BA→AC

37、DB→1

38、3

39、5

40、7

41、9D→2

42、4

43、6

44、8

45、BC→0

46、D(5)文法G=({N,S,N,M,D},{0,1,2,3,4,5,6,7,8,9},S,P)S→N0

47、N5N→MD

48、eM→1

49、2

50、3

51、4

52、5

53、6

54、7

55、8

56、9D→D0

57、DM

58、e(6)G[S]:S→aSa

59、bSb

60、cSc

61、a

62、b

63、c

64、e8.解答:(1)句子abab有如下两个不同的最左推导:S=>aSbS=>ab

65、S=>abaSbS=>ababS=>abab  S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab  所以此文法是二义性的。(2)句子abab的两个相应的最右推导:  S=>aSbS=>aSbaSbS=>aSbaSb=>aSbab=>abab  S=>aSbS=>aSb=>abSaSb=>abSab=>abab(3)句子abab的两棵分析树:(a)(b)(4)此文法产生的语言是:在{a,b}上由相同个数的a和b组成的字符串。9,10:解答:略!第3章习题解答:1.解答:(1)  √  (2) √  (3)  ×

66、(4)  ×  (5) √  (6)√2.[分析]   有限自动机分为确定有限自动机和非确定有限自动机。确定有限自动机的确定性表现在映射d:Q×VT-->q是单值函数,也就是说,对任何状态q∈Q和输入字符串a∈VT,d(q,a)唯一确定下一个状态。显然,本题给出的是一个确定的有限自动机,它的状态转换图是C中的②。    它所接受的语言可以用正则表达式表示为00(0

67、1)*,表示的含义为由两个0开始的后跟任意个(包含0个)0或1组成的符号串的集合。2.解答:A:④  B:③  C:②  D:②  E:④3,4.解答:略!5.解答:6.解

68、答:(1)(0

69、1)*01(2)((1

70、2

71、…

72、9)(0

73、1

74、2

75、…

76、9)*

77、e)(0

78、5)(3)(0

79、1)*(011)(0

80、1)*(4)1*

81、1*0(0

82、10)*(1

83、e)(5)a*b*c*…z*(6)(0

84、10*1)*1(7)(00

85、11)*((01

86、10)(00

87、11)*(01

88、10)(00

89、11)*)*(8)[分析]设S是符合要求的串,

90、S

91、=2k+1(k≥0)。则S→S10

92、S21,

93、S1

94、=2k(k>0),

95、S2

96、=2k(k≥0)。且S1是{0,1}上的串,含有奇数个0和奇数个1。 S2是{0,1}上的串,含有偶数个0和偶

97、数个1。考虑有一个自动机M1接受S1,那么自动机M1如下:和L(M1)等价的正规式,即S1为:((00

98、11)

99、(01

100、10)(00

101、11)*(01

102、10))*(01

103、10)(00

104、11)*类似的考虑有一个自动机M2接受

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。