资源描述：
《文法和语言课后习题参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章文法和语言课后习题参考答案1.L(G)={abc}2.L(G[N])是无符号整数。3.G3:E→D+E
2、D-E
3、DD→0
4、1
5、2
6、3
7、4
8、5
9、6
10、7
11、8
12、94.L(G[Z])={anbn
13、n>0}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,
29、…,9},P,S)P:SàPD
30、P0
31、DP->NR
32、NR->QR
33、QDà2
34、4
35、6
36、8N->1
37、2
38、3
39、4
40、5
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)<表达式>=><项>=><因子>=>
59、i(2)<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)(3)<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i(4)<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>=><因子>*<因子>+<因子>=>i*i+i=w(5)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)=>i+(<表达式>+<项>)=>i+(<项>+<项>)=>i+(<因子>+<因子>)=>i+(i+
60、i)(6)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>=>i+<项>*<因子>=>i+<因子>*<因子>=>i+i*i<表达式><项><因子>i<表达式><项><因子>(<表达式>)<项><因子>i<表达式><项><项>*<因子><因子>ii<表达式><表达式>+<项><项><项>*<因子><因子>ii<因子>i<表达式><表达式>+<项><项><因子>i<因子>(<表达式>)<表达式>+<项><项><因子>i<因子>i<表达式><表达式>+<项><项><因子>i<
61、项>*<因子><因子>ii(1)i(2)(i)(3)i*i(4)i*i+i(5)i+(i+i)(6)i+i*i语法树见下图:7.为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。<表达式>::=i
62、(<表达式>)
63、<表达式><运算符><表达式><运算符>::=+
64、-
65、*
66、/解：为句子i+i*i构造的两棵语法树如下：所以，该文法是二义的。<表达式><表达式>+<表达式>i<表达式>*<表达式>ii<表达式><表达式>*<表达式><表达式>+<表达式>iii8.习题1中的文法G[S]是
67、二义的吗？为什么？答：是二义的。因为对于句子abc可以有两种不同的生成树，即：S=>Ac=>abc和S=>aB=>abc11.令文法G[E]为：EàT
68、E+T
69、E-TTàF
70、T*F
71、T/FFà(E)
72、i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：可为E+T*F构造一棵语法树（见下图），所以它是句型。EE+TT*F从语法树中容易看出，E+T*F的短语有：T*F是句型E+T*F的相对于T的短语，也是相对于规则TàT*F的直接短语。E+T*F是句型E+T*F的相对于E的短语。句型E
73、+T*F的句柄（最左直接短语）是T*F。12.下述文法G[E]生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。证明：是G[]的句型，并指出该句型的所有短语、直接短语和句柄。à
74、à
75、àa
76、b
77、cà+
78、-à*
79、/解：(1)计算文法G[E]的语言：由于L(T)={(a
80、b
81、c)((a
82、b
83、c)(*
84、/))n
85、n>=0}所以L(E)={L(T
86、)(L(T)(+
87、-))n
88、n>=0}(2)该文法的一个句子是aab*+,它的语法树是：aab*+(1)证明：是G[]的句型，并指出该句型的所有短语、直接短语和句柄。由于下面的语法树可以生成，所以它是G[]的句型。由于
