资源描述：
《编译原理教程课后习题答案——第三章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章语法分析3.1完成下列选择题：(1)文法G：S→xSx
2、y所识别的语言是。a.xyxb.(xyx)*c.xnyxn(n≥0)d.x*yx*(2)如果文法G是无二义的，则它的任何句子α。 a.最左推导和最右推导对应的语法树必定相同b.最左推导和最右推导对应的语法树可能不同c.最左推导和最右推导必定相同d.可能存在两个不同的最左推导，但它们对应的语法树相同(3)采用自上而下分析，必须。a.消除左递a.必有ac归b.消除右递归c.消除回溯d.提取公共左因子(4)设a、b、c是文法的终结符，且满足优先关系ab和b
3、c，则。b.必有cac.必有bad.a～c都不一定成立(5)在规范归约中，用来刻画可归约串。a.直接短语b.句柄c.最左素短语d.素短语(6)若a为终结符，则A→α·aβ为项目。a.归约b.移进c.接受d.待约(7)若项目集Ik含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是。a.LALR文法b.LR(0)文法c.LR(1)文法d.SLR(1)文法(8)同心集合并有可能产生新的冲突。a.归约b.“移进”/“移进”c.“移进”/“归约”d.“归约”/“归约”【
4、解答】(1)c(2)a(3)c(4)d(5)b(6)b(7)d(8)d3.2令文法G[N]为G[N]:N→D
5、NDD→0
6、1
7、2
8、3
9、4
10、5
11、6
12、7
13、8
14、9(1)G[N]的语言L(G[N])是什么?(2)给出句子0127、34和568的最左推导和最右推导。【解答】(1)G[N]的语言L(G[N])是非负整数。(2)最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127NNDN4D
15、434NNDN8ND8N68D685683.3已知文法G[S]为S→aSb
16、Sb
17、b，试证明文法G[S]为二义文法。【解答】由文法G[S]：S→aSb
18、Sb
19、b，对句子aabbbb可对应如图3-1所示的两棵语法树。图3-1句子aabbbb对应的两棵不同语法树因此，文法G[S]为二义文法(对句子abbb也可画出两棵不同语法树)。3.4已知文法G[S]为S→SaS
20、ε，试证明文法G[S]为二义文法。【解答】由文法G[S]：S→SaS
21、ε，句子aa的语法树如图3-2所示。图3-2句子aa对应的两棵不同的语法树由图3-
22、2可知，文法G[S]为二义文法。3.5按指定类型，给出语言的文法。(1)L={aibj
23、j＞i≥0}的上下文无关文法；(2)字母表Σ={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；(3)由相同个数a和b组成句子的无二义文法。【解答】(1)由L={aibj
24、j＞i≥0}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→b型的产生式，用以保证b的个数多于a的个数。因此，所求上下文无关文法G[S]为G[S]：S→aSb
25、Sb
26、b(
27、2)为了构造字母表Σ={a,b}上同时只有奇数个a和奇数个b的所有串集合的正规式，我们画出如图3-3所示的DFA，即由开始符S出发，经过奇数个a到达状态A，或经过奇数个b到达状态B；而由状态A出发，经过奇数个b到达状态C(终态)；同样，由状态B出发经过奇数个a到达终态C。由图3-3可直接得到正规文法G[S]如下：G[S]：S→aA
28、bBA→aS
29、bC
30、bB→bS
31、aC
32、aC→bA
33、aB
34、ε图3-3习题3.5的DFA(3)我们用一个非终结符A代表一个a(即有A→a)，用一个非终结符B代表一个b(即有B→b)；为了
35、保证a和b的个数相同，则在出现一个a时应相应地出现一个B，出现一个b时则相应出现一个A。假定已推导出bA，如果下一步要推导出连续两个b时，则应有bAbbAA。也即为了保证b和A的个数一致，应有A→bAA；同理有B→aBB。此外，为了保证递归地推出所要求的ab串，应有S→aBS和S→bAS。由此得到无二义文法G[S]为G[S]：S→aBS
36、bAS
37、εA→bAA
38、aB→aBB
39、b3.6有文法G[S]:S→aAcB
40、BdA→AaB
41、cB→bScA
42、b(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄；(2)写
43、出句子acabcbbdcc的最左推导过程。【解答】(1)分别画出对应句型aAaBcbbdcc和aAcbBdcc的语法树如图3-4的(a)、(b)所示。图3-4习题3.6的语法树(a)aAaBcbbdcc;(b)aAcbBdcc对树(a)，直接短语有3个：AaB、b和c，而AaB为最左直接短语(即为句柄)。对树(b)，直接短语有两个：Bd和c，而Bd为最左直接短语。能否不画出语法树，而直
