资源描述：
《编译原理第二章习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章习题解答1.文法G[S]为：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]的语言是什么？[答案]G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD....=>NDDDD...D=>D......D==================================
13、=============3.已知文法G[S]：S→dAB A→aA
14、a B→ε
15、bB问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？[答案]正规式是daa*b*；相应的正规文法为(由自动机化简来)：G[S]:S→dAA→a
16、aBB→aB
17、a
18、b
19、bCC→bC
20、b也可为(观察得来):G[S]:S→dAA→a
21、aA
22、aBB→bB
23、ε===============================================================================4.已知文法G[Z]：Z->aZb
24、ab写出L(G[Z])的全部元素。[答案]Z=>
25、aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbbL(G[Z])={anbn
26、n>=1}==============================================================================5.给出语言{anbncm
27、n>=1,m>=0}的上下文无关文法。[分析]本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是：A->β,A∈Vn，β∈（Vn∪Vt）*，注意关键问题是保证anbn的成立，即“a与b的个数要相等”，为此，可以用一条形如A->aAb
28、ab的产生式即可解决。[答案
29、]构造上下文无关文法如下：S->AB
30、AA->aAb
31、abB->Bc
32、c[扩展]凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。基本思路是这样的：要求符合anbncm，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而cm做为另一个单位，初步产生式就应写为S->AB，其中A推出anbn，B推出cm。因为m可为0，故上式进一步改写为S->AB
33、A。接下来考虑A,凡是要求两个终结符个数相等的问题，都应写为A->aAb
34、ab形式，对于B就很容易写成B->Bc
35、c了。===================================================
36、===========================6.写一文法，使其语言是偶正整数集合。要求：(1)允许0开头；(2)不允许0开头。[答案](1)允许0开头的偶正整数集合的文法E->NT
37、G
38、SFMT->NT
39、GN->D
40、1
41、3
42、5
43、7
44、9D->0
45、GG->2
46、4
47、6
48、8S->NS
49、εF->1
50、3
51、5
52、7
53、9
54、GM->M0
55、0(2)不允许0开头的偶正整数集合的文法E->NT
56、DT->FT
57、GN->D
58、1
59、3
60、5
61、7
62、9D->2
63、4
64、6
65、8F->N
66、0G->D
67、0==========================================================
68、===================7.已知文法G：E->E+T
69、E-T
70、TT->T*F
71、T/F
72、FF->(E)
73、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+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(
74、F+T)=>i+(i+T)=>i+(i+F)=>i+(i+i)8.为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。〈表达式〉->〈表达式〉〈运算符〉〈表达式〉
75、(〈表达式〉)
76、i〈运算符〉->+
77、-
78、*
79、/[答案]可为句子i+i*i构造两个不同的最右推导:最右推导1 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉i=>〈表达式〉*i=>〈表达式〉〈运算符〉〈表达式〉*i=>〈表达式〉〈运算符〉i *i=>〈表达式〉+i*i=>i+i
