第三章 文法和语言课后习题参考答案
更新时间:2024-05-24 18:50:01 阅读量: 综合文库 文档下载
- 第三章第四幕推荐度:
- 相关推荐
第三章 文法和语言课后习题参考答案
1. L(G)={abc}
2. L(G[N])是无符号整数。 3. G3: E→D+E | D-E | D
D→0|1|2|3|4|5|6|7|8|9 4. L(G[Z])={anbn | n>0}
5. 写一文法,使其语言是偶正整数的集合 要求:
(1) 允许0打头 (2) 不允许0打头 解:
(1) G[S]=({S,P,D,N},{0,1,2,…,9},P,S)
P:
S?PD|D P->NP|N
D?0|2|4|6|8
N->0|1|2|3|4|5|6|7|8|9
(2) G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S)
P:
S?PD|P0|D P->NR|N R->QR|Q D?2|4|6|8
N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|9
6. 已知文法G:
<表达式>::=<项>|<表达式>+<项>|<表达式>-<项> <项>::=<因子>|<项>*<因子>|<项>/<因子> <因子>::=(<表达式>)|i。
试给出下述表达式的推导及语法树。
(1)i; (2)(i) (3)i*i; (4)i*i+i; (5)i+(i+i); (6)i+i*i。
解:
(1) <表达式>=><项>=><因子>=>i
(2) <表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i) (3) <表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i
(4) <表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>
=><因子>*<因子>+<因子>=>i*i+i=w
(5) <表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)
=> i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i) (6) <表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>
=>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i
1
语法树见下图:
(1) i <表达式> <项> <因子> i
(2) (i) <表达式> <项> <因子> ( <表达式> )
<项> <因子> i
(4) i*i+i <表达式>
<表达式> + <项> <项> <项> * <因子> <因子> i
i
<因子> i
(5) i+(i+i) <表达式>
<表达式> + <项> <项> <因子> i
<因子> ( <表达式> ) <表达式> + <项> <项> <因子>
<因子> i
(6) i+i*i <表达式>
<表达式> + <项> <项> <因子> i
<项> * <因子> <因子> i
i
(3) i*i <表达式> <项>
<项> * <因子> <因子> i
i
i
7. 为句子i+i*i构造两棵语法树,从而证明下述文法G[<表达式>]是二义的。 <表达式>::=i|(<表达式>)|<表达式><运算符><表达式> <运算符>::=+|-|*|/
解:为句子i+i*i构造的两棵语法树如下: 所以,该文法是二义的。
<表达式> <表达式>
<表达式> + <表达式> <表达式> * <表达式>
i <表达式> * <表达式> <表达式> + <表达式> i
i i i i
2
8. 习题1中的文法G[S]是二义的吗?为什么? 答:是二义的。因为对于句子abc可以有两种不同的生成树,即:S=>Ac=>abc和S=>aB=>abc 11. 令文法G[E]为: E?T|E+T|E-T T?F|T*F|T/F F?(E)|i
证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。 解:可为E+T*F构造一棵语法树(见下图),所以它是句型。 E
E + T
T * F
从语法树中容易看出,E+T*F的短语有:
T*F是句型E+T*F的相对于T的短语,也是相对于规则T?T*F的直接短语。 E+T*F是句型E+T*F的相对于E的短语。 句型E+T*F的句柄(最左直接短语)是T*F。
12. 下述文法G[E]生成的语言是什么?给出该文法的一个句子,该句子至少含五个终结符,构造该句子的语法树。证明:
(1)计算文法G[E]的语言:
n
由于L(T)={(a|b|c)((a|b|c)(*|/))|n>=0}
n
所以L(E)={L(T)(L(T)(+|-))|n>=0}
(2)该文法的一个句子是aab*+,它的语法树是:
a a
(3) 证明:
句柄。
3
由于下面的语法树可以生成
由于
由于
显然,句型
(1)给出该句子相应的最左、最右推导。 (2)该文法产生式的集合可能有哪些元素? (3)找出该句子所有短语、直接短语、句柄。 解:
(1) 最左推导:S => ABS => aBS => aSBBS => aBBS => abBS => abbS => abbAa => abbaa (2) S—>ABS | Aa |ε A—>a
B—>SBB | b
(3) 首先为了区别句子abbaa中的a和b,把它写成a1b1b2a2a3
该句子的短语有:a1b1b2a2a3,b1b2,a2a3,a1,a2,b1,b2,ε 直接短语有:a1,a2,b1,b2,ε 句柄:a1
14. 给出生成下述语言的上下文无关文法:
nnmm
(1){abab|n,m>=0}
nmmn
(2){1010|n,m>=0}
t*t
(3){WaW|W属于{0|a},W表示W的逆} 解:
(1)所求文法为G[S]=({S,A},{a,b},P,S),其中P为: S?AA A?aAb|ε
(2)所求文法为G[S]=({S,A},{0,1},P,S),其中P为: S?1S0|A
4
A?0A1|ε
*
(3)W属于{0|a}是指W可以的取值为{ε,0,a,00,a0,aa0,00aa,a0a0,…}
t
如果W=aa0a00,则W=00a0aa。
所求文法为G[S]=({S,P,Q},{0,a},P,S),其中P为: S?0S0|aSa|a
nmnm
15. 语言{WaW}和{abcd}是上下文无关的吗?能看出它们反映程序设计语言的什么特性吗?
答:生成语言{WaW}的文法非常简单,如 G[S]: S?WaW
W?aW|bW|ε
可见G[S]是上下文无关的。
nmnm
生成语言{abcd}的文法非常复杂,用上下文无关文法不可能办到,只能用上下文有关
nnmm
文法。这是因为要在ac的中间插入b而同时要在其后面插入d。即a,c相关联,b,d相关联。
这说明对语言的限定越多(特别是语言中的符号前后关联越多),生成它的文法越复杂,甚至于很难找到一个上下文法无关文法。 16.给出生成下述语言的三型文法:
n
(1){a|n>=0}
nm
(2){ab|n,m>=1}
nmk
(3){abc|n,m,k>=0} 解:
(1) 生成的3型文法是:
G[S]:S?aS|ε
(2) 生成的2型文法是:
G[S]: S?AB A?aA|a B?bB|b 生成的3型文法是: G[S]: S?aP P?aP|bD D?bD|ε (3) 生成的2型文法是:
G[S]: S?ABC A?aA|ε B?bB|ε C->cC|ε
生成的3型方法是: G[S]: A?aA|bB|cC|ε B?bB|cC|ε C?cC|ε
17、习题6、习题7和习题7中的文法所描述的语言都是由变量i、+、-、*、/、(和)组成算术表达式,因此它们之间是等价的。
19. 刻画语言的语法有文法、正则式和自动机等方式。
5
6
正在阅读:
第三章 文法和语言课后习题参考答案05-24
园林史复习资料11-01
在安全生产和消防安全工作会议上的发言08-17
【完整版】2022-2025年中国推土机行业新产品进入市场策略制定与04-08
一朝春尽红颜老微小说03-17
人教版八年级语文下册第24课《送东阳马生序》中考集锦205-09
世界著名电影配乐大师介绍05-29
复兴小学优质生源培养实施方案01-10
- 小学生造句大全
- 增压泵投资项目可行性研究报告(模板)
- 高中语文人教版粤教版必修1-5全部文言文知识点归纳
- 两学一做专题民主生活会组织生活会批评与自我批评环节个人发言提
- 管理处环境保洁工作操作标准作业指导书
- 2012六一儿童节活动议程 - 图文
- 移树申请报告
- 《贵州省市政工程计价定额》2016定额说明及计算规则
- 计算机长期没有向WSUS报告状态
- 汉语拼音教学策略研究
- 发展西部领先的航空货运枢纽
- 司法所上半年工作总结4篇
- 如何提高银行服务水平
- 发电厂各级人员岗位职责
- 丰田汽车的外部环境分析
- 2017—2018年最新冀教版四年级数学下册《混合运算》教案精品优质
- 中建八局样板策划 - 图文
- 戚安邦《项目管理学》电子书
- 2015年高级项目经理笔记
- 弯桥的设计要点
- 文法
- 课后
- 习题
- 答案
- 语言
- 参考
- 第三章