资源描述：
《编译原理课后习题答案ch3.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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}例题：文法G[S]：(5分)S→aSa
3、AA→bA
4、BB→Bc
5、ε所描述的语言是什么？nmln答案：L（G[S]）={abca，n,m,l≥0}第2题文法G[N]为：N→D
6、NDD→0
7、1
8、2
9、3
10、4
11、5
12、6
13、7
14、8
15、9G[N]的语言是什么？答案:G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD....=>
16、NDDDD...D=>D......D或者：允许0开头的非负整数？盛威网（www.snwei.com）专业的计算机学习网站1《编译原理》课后习题答案第三章第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案：G[S]:S->S+D
17、S-D
18、DD->0
19、1
20、2
21、3
22、4
23、5
24、6
25、7
26、8
27、9第4题已知文法G[Z]：Z→aZb
28、ab写出L(G[Z])的全部元素。答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbbnnL(G[Z])={ab
29、n>=1}第5题写一文法，使其语言是偶正整数
30、的集合。要求：(1)允许0打头；(2)不允许0打头。答案：(1)允许0开头的偶正整数集合的文法E→NT
31、DT→NT
32、DN→D
33、1
34、3
35、5
36、7
37、9D→0
38、2
39、4
40、6
41、8(2)不允许0开头的偶正整数集合的文法E→NT
42、DT→FT
43、GN→D
44、1
45、3
46、5
47、7
48、9D→2
49、4
50、6
51、8F→N
52、0G→D
53、0盛威网（www.snwei.com）专业的计算机学习网站2《编译原理》课后习题答案第三章第6题已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。（５）i+
54、(i+i)（６）i+i*i答案：<表达式>(5)<表达式>=><表达式>＋<项>=><表达式>＋<因子><表达式>+<项>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）<项><因子>=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）<因子>（<表达式>)=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）i=><项>＋（i＋i）<表达式>+<项>=><因子>＋（i＋i）=>i＋（i＋i）<项><因子><因子>ii<表达式>(6)<表达式>=><表达式>＋<项>=><
55、表达式>＋<项>*<因子><表达式>+<项>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i<项>=><项>＋i*i<项>*<因子>=><因子>＋i*i<因子>=>i＋i*i<因子>iii盛威网（www.snwei.com）专业的计算机学习网站3《编译原理》课后习题答案第三章第7题证明下述文法G[〈表达式〉]是二义的。〈表达式〉∷=a
56、(〈表达式〉)
57、〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+
58、-
59、*
60、/答案：可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运
61、算符〉a〈表达式〉*a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a盛威网（www.snwei.com）专业的计算机学习网站4《编译原理》课后习题答案第三章第8题文法G[S]为：S→Ac
62、aBA→abB→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc
63、(2)S=>aB=>abc即存在两不同的最右推导。所以，该文法是二义的。或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。SSaBAcbcab第9题考虑下面上下文无关文法：SS→SS*
64、SS+
65、a(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。(2)G[S]的语言是什么？SS*答案：SS+a(1)此文法生成串aa+a*的最右推导如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*aa(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。盛威网（www.snwei.com）专业的计算机学习
66、网站5《编译原理》课后习题答案第三章第10题文法S→S(S)S
67、ε(1)生成的语言是什么？(2)该文法是二义的吗？说明理由。答案：（１）
