编译原理第三章答案

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

1、第3章文法和语言第1题文法G＝({A,B,S},{a,b,c},P,S)其中P为：S→Ac

2、aBA→abB→bc写出L(G[S])的全部元素。答案：L(G[S])={abc}第2题文法G[N]为：N→D

3、NDD→0

4、1

5、2

6、3

7、4

8、5

9、6

10、7

11、8

12、9G[N]的语言是什么？答案:G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD....=>NDDDD...D=>D......D或者：允许0开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案：G[S]:S->S+D

13、S-D

14、DD-

15、>0

16、1

17、2

18、3

19、4

20、5

21、6

22、7

23、8

24、9第4题已知文法G[Z]：Z→aZb

25、ab写出L(G[Z])的全部元素。答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbbL(G[Z])={anbn

26、n>=1}第5题写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头；(2)不允许0打头。答案：(1)允许0开头的偶正整数集合的文法E→NT

27、DT→NT

28、DN→D

29、1

30、3

31、5

32、7

33、9D→0

34、2

35、4

36、6

37、8(2)不允许0开头的偶正整数集合的文法E→NT

38、DT→FT

39、GN→D

40、1

41、3

42、5

43、7

44、9D→2

45、4

46、6

47、8F→N

48、0G→D

49、0第6题

50、已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。（５）i+(i+i)（６）i+i*i第8题文法G[S]为：S→Ac

51、aBA→abB→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc(2)S=>aB=>abc即存在两不同的最右推导。所以，该文法是二义的。或者：第10题文法S→S(S)S

52、ε(1)生成的语言是什么？(2)该文法是二义的吗？说明理由。答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。第11题

53、令文法G[E]为：E→T

54、E+T

55、E-TT→F

56、T*F

57、T/FF→(E)

58、i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。第14题给出生成下述语言的上下文无关文法：（1）{anbnambm

59、n，m>=0}（2）{1n0m1m0n

60、n，m>=0}（3）{WaWr

61、W属于{0

62、a}*，Wr表示W的逆}答案：（１）S→AAA→aAb

63、ε（２）S→1S0

64、AA→0A1

65、ε（３）S→0S0

66、1S1

67、ε第16题给出生成下述语言的三型文法：(1){an

68、n>=0}(2){anbm

69、n,m>=1}(3){anbmck

70、n,m,k>=0}答案：(1)S→aS

71、

72、ε(2)S→aAA→aA

73、BB→bB

74、b(3)A→aA

75、BB→bB

76、CC→cC

77、ε第18题解释下列术语和概念：（１）字母表（２）串、字和句子（３）语言、语法和语义答案：（１）字母表：是一个非空有穷集合。（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。附加题问题1：给出下述文法所对应的正规式：S→

78、0A

79、1BA→1S

80、1B→0S

81、0答案：R=(01

82、10)(01

83、10)*问题2：已知文法G[A]，写出它定义的语言描述G[A]:A→0B

84、1CB→1

85、1A

86、0BBC→0

87、0A

88、1CC答案:G[A]定义的语言由0、1符号串组成，串中0和1的个数相同.问题3：给出语言描述，构造文法.构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案一：G[E]E→E+T

89、TT→T*F

90、FF→(E)

91、a答案二：G[E]E→E+E

92、E*E

93、(E)

94、a问题4：已知文法G[S]:S→dABA→aA

95、aB→ε

96、bB相应的正规式是什么？G[S]能否改写成为等

97、价的正规文法？答案：正规式是daa*b*；相应的正规文法为(由自动机化简来)：G[S]:S→dAA→a

98、aBB→aB

99、a

100、b

101、bCC→bC

102、b也可为(观察得来):G[S]:S→dAA→a

103、aA

104、aBB→bB

105、ε问题5：已知文法G：E→E+T

106、E-T

107、TT→T*F

108、T/F

109、FF→(E)

110、i试给出下述表达式的推导及语法树(1)i;(2)i*i+i(3)i+i*i(4)i+(i+i)答案：(1)E=>T=>F=>i(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i(3)E=>E+T=>T+T=>F+T=>i+

111、T=>i+