编译原理实践与应用习题的参考答案.doc

《编译原理实践与应用习题的参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、附录部分习题参考答案第1章参考答案：1，2，3，4，5，6，7解答：略！第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

5、=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i=>F+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)把anbnc

6、i分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S→ABA→aAb

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、〈奇数尾〉     

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

26、3

27、5

28、7

29、9 〈奇数头〉→2

30、4

31、6

32、8

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]

59、：S→aSa

60、bSb

61、cSc

62、a

63、b

64、c

65、e8.解答：(1)句子abab有如下两个不同的最左推导：S=>aSbS=>abS=>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)此文法产生的语言是：在

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

67、1)*，表示的含义为由两个0

68、开始的后跟任意个（包含0个）0或1组成的符号串的集合。2.解答：A:④  B:③  C:②  D:②  E:④3，4．解答：略！5．解答：6．解答：(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→S1

92、0

93、S21，

94、S1

95、=2k(k>0），

96、S2

97、=2k(k≥0）。且S1是{0,1}上的串，含有奇数个0和奇数个1。 S2是{0,1}上的串，含有偶数个0和偶数个1。考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规式，即S1为：((00

98、11)

99、(01

100、10)(00

101、11)*(01