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