资源描述：
《编译原理第三章答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3章文法和语言第1题文法G＝({A,B,S},{a,b,c},P,S)其中P为：S→Ac
2、aBA→abB→bc写出L(G[S])的全部元素。答案：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或者：允许0开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案：G[S]:S->S+D
13、S-D
14、DD->0
15、1
16、2
17、3
18、4
19、5
20、6
21、
22、7
23、8
24、9第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题写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头；(2)不允许0打头。答案：(1)允许0开头的偶正整数集合的文法E→NT
27、DT→NT
28、DN→D
29、1
30、3
31、5
32、7
33、9D→0
34、2
35、4
36、6
37、8(2)不允许0开头的偶正整数集合的文法E→NT
38、DT→FT
39、GN→D
40、1
41、3
42、5
43、7
44、9D→2
45、4
46、6
47、8F→N
48、0G→D
49、0第6题已知文法G：<表达式>::=<项>｜<表达式>＋<项><
50、项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。（５）i+(i+i)（６）i+i*i答案：(5)<表达式>=><表达式>＋<项>=><表达式>＋<因子>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）=><项>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）(6)<表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子>=><表达式>＋<项>*i=>
51、<表达式>＋<因子>*i=><表达式>＋i*i=><项>＋i*i=><因子>＋i*i=>i＋i*i<表达式><表达式>+<项><因子><表达式><表达式>+<项><因子>i<项><因子>i<项><因子>i（)<表达式><表达式>+<项><项>*<因子><因子>i<项><因子>ii第7题证明下述文法G[〈表达式〉]是二义的。〈表达式〉∷=a
52、(〈表达式〉)
53、〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+
54、-
55、*
56、/答案：可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉a〈表达式〉*a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运
57、算符〉a*a〈表达式〉+a*aa+a*a最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a第8题文法G[S]为：S→Ac
58、aBA→abB→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc(2)S=>aB=>abc即存在两不同的最右推导。所以，该文法是二义的。或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。第9题考虑下面上下文无关文法：S→SS*
59、SS+
60、a(1)表明通过
61、此文法如何生成串aa+a*，并为该串构造语法树。(2)G[S]的语言是什么？答案：(1)此文法生成串aa+a*的最右推导如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。SAcabSaBbcSSS*SS+aaa第10题文法S→S(S)S
62、ε(1)生成的语言是什么？(2)该文法是二义的吗？说明理由。答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。第11题令文法G[E]为：E→T
63、E+T
64、E-TT→F
65、T*F
66、T/FF→(E)
67、i证明E+T*F是它的一个句型，指出这个句型的所有短
68、语、直接短语和句柄。答案：此句型对应语法树如右，故为此文法一个句型。或者：因为存在推导序列:E=>E+T=>E+T*F，所以E+T*F句型此句型相对于E的短语有:E+T*F；相对于T的短语有T*F直接短语为：T*F句柄为：T*F第13题一个上下文无关文法生成句子abbaa的推导树如下：(1)给出串abbaa最左推导、最右推导。(2)该文法的产生式集合P可能有哪些元素？(3)找出该句子的所有短语、直接短语、句柄
