资源描述：
《第3章 文法和语言》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章文法和语言（习题参考答案）1、文法G=({A,B,S},{a,b,c},P,S),其中P为：S->Ac
2、aBA->abB->bc写出L（G[S]）的全部元素。【解】S=>Ac=>abc或S=>aB=>abc所以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]的语言是什么？【解】N=>ND=>NDD....=>NDDDD...D=>D......DG[N]的语言是V+,其中V={0,1,2,3,4,5,6,7,8,9}或：解:NNDn-1Dn{0,
13、1,3,4,5,6,7,8,9}+∴L(G[N])={0,1,3,4,5,6,7,8,9}+5.写一文法，使其语言是偶正整数的集合要求：(1)允许0打头;(2)不允许0打头解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P:S->PD
14、DP->NP
15、ND->0
16、2
17、4
18、6
19、8N->0
20、1
21、2
22、3
23、4
24、5
25、6
26、7
27、8
28、9(2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)P:S->PD
29、P0
30、DP->NR
31、NR->QR
32、QD->2
33、4
34、6
35、8N->1
36、2
37、3
38、4
39、5
40、
41、6
42、7
43、8
44、9Q->0
45、1
46、2
47、3
48、4
49、5
50、6
51、7
52、8
53、96.已知文法G：<表达式>::=<项>
54、<表达式>+<项>
55、<表达式>-<项><项>::=<因子>
56、<项>*<因子>
57、<项>/<因子><因子>::=(<表达式>)
58、i。试给出下述表达式的推导及语法树。(1)i;(2)(i)(3)i*i;(4)i*i+i;(5)i+(i+i);(6)i+i*i。解：(1)v=<表达式>=><项>=><因子>=>i(2)v=<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)(3)v=<表
59、达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i(4)v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>=><因子>*<因子>+<因子>=>i*i+i(5)v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)=>i+(<表达式>+<项>)=>i+(<项>+<项>)=>i+(<因子>+<因子>)=>i+(i+i)(6)v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>=>i+<项>*
60、<因子>=>i+<因子>*<因子>=>i+i*i语法树见下图（略）7.为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。<表达式>::=i
61、(<表达式>)
62、<表达式><运算符><表达式><运算符>::=+
63、-
64、*
65、/解：为句子i+i*i构造的两棵语法树如下：（略）所以，该文法是二义的。8.习题1中的文法G[S]是二义的吗？为什么？答：是二义的。因为对于句子abc可以有两种不同的生成树，即：S=>Ac=>abc和S=>aB=>abc两棵语法树如下：（略）9.考虑下面上下文无关文法：S→SS*
66、
67、SS+
68、a(1)表明通过此文法如何生成串aa+a*，并为该串构造推导树。(2)该文法生成的语言是什么？【解】(1)S=>SS*=>SS+S*aa+a*该串的推导树如下：(2)该文法生成的语言是只含+、*的算术表达式的逆波兰表示。11.令文法G[E]为：ET
69、E+T
70、E-TTF
71、T*F
72、T/FF(E)
73、i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：可为E+T*F构造一棵语法树（见下图），所以它是句型。从语法树中容易看出，E+T*F的短语有：T*F是句型E+T*F的相对于T的短语，也是相对
74、于规则TT*F的直接短语。E+T*F是句型E+T*F的相对于E的短语。句型E+T*F的句柄（最左直接短语）是T*F。12.下述文法G[E]生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。证明：是G[]的句型，并指出该句型的所有短语、直接短语和句柄。->
75、->
76、->a
77、b
78、c->+
79、-->*
80、/解：(1)计算文法G[E]的语言：由于L(T)={(
81、a
82、b
83、c)((a
84、b
85、c)(*
86、/))n
87、n>=0}所以L(E)={L(T)(L(T)(+
88、-))n
89、n>=0}(2)该文法的一个句子是aab*+,它的语法树是：证明：是G[]的句型，并指出该句型的所有短语、直接短语和句柄。由于下面的语法树可以生成，所以它是G[]的句型
