- 1、本文档共7页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
编译原理期中测试答案
三、单项选择题(每题3分,共15分)
1.设有文法G[S]:S→(AS)|(b)
A→(SaA)|(a)
该文法的句型(((b)a(a))(b))有C个直接短语。
A.1B.2C.3D.4
2.如果一个文法满足D,则称该文法是二义性文法。
(1)文法的某一个句子存在两个(包括两个)以上的语法树
(2)文法的某一个句子存在两个(包括两个)以上的最左推导
(3)文法的某一个句子存在两个(包括两个)以上的最右推导
(4)在进行归约时,文法的某些规范句型的句柄不唯一
上述描述中的所有正确描述有:
A.(1)B.(1)(2)C.(1)(2)(3)D.(1)(2)(3)(4)
3.构造一个不带回溯的自顶向下语法分析器,要求文法满足
E。
A.对每个形如A→x1|x2|…|xn的产生式,要求FIRST(xi)与
FIRST(xj)的交集为空集(i≠j)
B.对每个形如A→x1|x2|…|xn的产生式,若xi*ε,则要求
FIRST(xj)与FOLLOW(A)的交集为空集(i≠j)
C.不含左递归
D.A和B同时满足
E.A、B和C同时满足
4、给定文法A→bA|cc,下列符号串中,是该文法的句子的是
C。
①cc②bcbc③bcbcc④bccbcc⑤bbbcc
A①B.①③④⑤C.①⑤D.①④⑤
5、若一个句型中出现了某一产生式的右部,则此右部B是该
句型的句柄。
A.一定B.不一定C.一定不D.无法判断
四、简述题(每题5分,共20分)
1、写一上下文无关文法,它能产生语言nm。
L{a#b|n,m0}
S→A#B
A→Aa|
B→Bb|
2、将文法G[S]改写为等价的G′[S],使G′[S]不含左递归和左公共因子。
G[S]:S→bSAe|bA
A→Ab|d
答:文法G[S]改写为等价的不含左递归和左公共因子的
G'[S]S→bB
B→SAe|A
A→dA'
A'→bA'|ε
3、什么是文法的二义性?下面的文法是二义的吗?为什么?
G[S]:S→AB|ABDA→aB→CD|DC→cD→d
答:如果一个文法存在某个句子对应两棵不同的语法树,则该文法是二义
的。
是,句子acd有两个完全不同的语法树。
4、设文法G[A]:A→[B
B→X]|BA
X→Xa|Xb|a|b
试求出文法G[A]产生的语言对应的正则式。
解:X→X(a|b)|a|bX→(a|b)(a|b)*代入B→X]|BA
B→(a|b)(a|b)*]|BAB→(a|b)(a|b)*]A*代入
A→[(a|b)(a|b)*]
文档评论(0)