编译原理 第2章习题解答

《编译原理 第2章习题解答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章习题解答2.1①该文法定义的是0到9这10个数字{0，1，2，3，4，5，6，7，8，9};②同①;③该文法定义的是{bna2∣n≥0};2.2①因为语言的句子要求由3的整数倍的a组成，所以在构造产生式时，要保证每次产生的a的个数是3。得到文法G[S]：S→aaa

2、Saaa②因为符号串中a、b的个数没有直接关系，所以，将句子分成两部分：an和b2m–1，分别进行构造，然后再合并。可由产生式A→a

3、aA得到an。而由产生式B→b

4、bbB得到b2m–1。由于n≥1，m≥1，所以得到文法G[S]：S→ABA→a

5、aAB→b

6、bbB③因为句子中，a和b的个数一样多，且

7、a全部在句子的前半部分，b全部在句子的后半部分，所以在构造产生式时，可让a和b对称出现。得文法G[S]：S→aSb

8、ab④因为句子中a、b、c的个数没有直接关系，所以分别构造生成an、bm、ck的产生式，然后再合成。可由产生式A→aA

9、e得到an。而由产生式B→bB

10、e得到bm。再由产生式C→cC

11、e得到ck。所以得到文法G[S]：S→ABCA→aA

12、eB→bB

13、eC→cC

14、e⑤文法为G[S]：S→(+

15、–)(ABC

16、2

17、4

18、6

19、8)

20、0C→0

21、2

22、4

23、6

24、8B→BA

25、B0

26、eA→1

27、2

28、3

29、…

30、9⑥能被5整除的整数的末位数必定是0或5。所以只要保证生成的整数末位数

31、字是0或5即可。据此，构造描述能被5整除的整数集合的文法如下：G[S]：S→(+

32、-)A(0

33、5)A→0

34、1

35、2

36、3

37、4

38、5

39、6

40、7

41、8

42、9

43、AA如果还要求整数除0外，均不以0开头，则文法为G[S]：S→(+

44、-)(A(0

45、5)

46、0

47、5)A→AB

48、CB→0

49、C

50、BBC→1

51、2

52、3

53、4

54、5

55、6

56、7

57、8

58、9⑦由于文法的句子aÎ{a,b}+，因此文法的句子可分解为两种情形：以a打头的符号串；以b打头的符号串。于是只要在构造产生式时保证每次产生相同个数的a和b即可。可以构造文法如下。G[S]：S→aSbS

59、bSaS

60、ab

61、ba或G[S]：S→aSb

62、bSa

63、abS

64、Sab

65、

66、baS

67、Sba

68、ab

69、ba2.3略2.40型文法2.5P={S→aD∣eE，D→bF，F→cA，E→dB，A→bC，C→eB，B→d}2.6①3274的最左推导为:NÞNDÞNDDÞNDDDÞDDDDÞ3DDDÞ32DDÞ327DÞ32743274的最右推导为:NÞNDÞN4ÞND4ÞN74ÞND74ÞN274ÞD274Þ3274②65173的最左推导为:NÞNDÞNDDÞNDDDÞNDDDDÞDDDDDÞ6DDDDÞ65DDDÞ651DDÞ6517DÞ6517365173的最右推导为:NÞNDÞN3ÞND3ÞN73ÞND73ÞN173ÞND173ÞN5173ÞD5

70、173Þ651732.7句型+*TP*i(+ET)的短语有*TP、i、+ET、(+ET)、*i(+ET)、+*TP*i(+ET)句型+*TP*i(+ET)的简单短语有*TP、i、+ET句型+*TP*i(+ET)的句柄为*TP2.8①要判别文法是否具有二义性，只要判别文法是否定义有这样的句子：该句子对应着两棵(包括两棵)以上语法树，或者说有两个(包括两个)以上不同的最右(左)推导；或者说在对该句子进行规范归约过程中，其规范句型的句柄不唯一。本题文法是二义性的。因为对于句子abc，存在两个不同的最左推导序列：SÞABÞabBÞabc和SÞABÞaBÞabc②文法是二义性

71、的。因为对于句子123，存在两个不同的最左推导序列：ÞÞ12Þ12Þ134Þ124Þ123和ÞÞ12Þ342Þ142Þ122Þ1232.9①产生式E→E和F→F、G→G是有害产生式，应删去。F，P，G三个非终结符号无法推导出终结符号串，因此，它们对应的产生式为无用产生式，应删去。

72、非终结符号Q无法从识别符号推导出来，因此，Q所对应的产生式也为无用产生式，也应删去。由于删去了F所对应的产生式后，S也无法从识别符号推导出来，故也应删去。压缩后的文法为G[Z]：Z→E+TE→TT→T*i

73、i②使其不含有形如A→B(A、B均为非终结符号)的产生式。将M代入F，然后将改写后的F代入T，最后将改写后的T代入S，于是将文法改为G[S]：S→aFbT

74、Tcb

75、Fa

76、Tb

77、abF

78、c

79、abc

80、cMbF→Tb

81、abF

82、c

83、abcT→Fa

84、Tb

85、abF

86、c

87、abc

88、cMbM→abF

89、c文法中不再有形如A→B(A、B均为非终结符号)的产生式。