- 1、本文档共8页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
编译原理复习例题
一 选择题
1.编译的各阶段工作都涉及 b 。
[A]词法分析 [B]表格管理 [C]语法分析 [D]语义分析
2. d 型文法也称为正规文法。
[A] 0 [B] 1 [C] 2 [D] 3
3. d 文法不是LL(1)的。
[A]递归 [B]右递归 [C]2型 [D]含有公共左因子的
4.文法E→E+E|E*E|i的句子i*i+i*i有 c 棵不同的语法树。
[A] 1 [B] 3 [C] 5 [D] 7
5.文法 S→aaS|abc 定义的语言是 c 。
[A]{a2kbc|k0} [B]{akbc|k0}
[C]{a2k-1bc|k0} [D]{akakbc|k0}
6.若B为非终结符,则 A→?.B? 为 d 。
[A]移进项目 [B]归约项目 [C]接受项目 [D]待约项目
7.同心集合并可能会产生新的 d 冲突。
[A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约
8.代码优化时所依据的是 c 。
[A]语法规则 [B]词法规则
[C]等价变换规则 [D]语义规则
9.表达式a-(-b)*c的逆波兰表示(@为单目减)为 b 。
[A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-*
10.过程的DISPLAY表是用于存取过程的 A 。
[A]非局部变量 [B]嵌套层次 [C]返回地址 [D]入口地址
二 填空题
1.词法分析阶段的任务式从左到右扫描 源程序 ,从而逐个识别 单词 。
2.对于文法G[E]:E→T|E+T T→F|T*F F→P^F|P
P→(E)|i,句型T+T*F+i的句柄是 T 。
3.最右推导的逆过程称为 最左规约 ,也称为 规范推导 。
4.符号表的每一项是由名字栏和 信息栏 两个栏目组成。在目标代码生成阶段,符号表是 内存分配 的依据。
三 判断题(认为正确的填“T”,错的填“F”)
【 T 】1.同心集的合并有可能产生“归约/归约”冲突。
【 T 】2.一个文法所有句子的集合构成该文法定义的语言。
【 F 】3.非终结符可以有综合属性,但不能有继承属性。
【 T 】4.逆波兰表示法表示表达式时无需使用括号。
【 F 】5.一个有穷自动机有且只有一个终态。
【 F 】6.若过程p第k次被调用,则p的DISPLAY表中就有k+1个元素。
四 解答题
1.给定文法G和句型(T+F)*i+T,
G: E→E+T | T T→T*F | F F→(E) | i
(1)画出句型的语法树;
(2)写出句型的全部短语、简单短语和句柄。
解:(略)
2.设有文法G:S→S+S|S*S|i|(S)。
(1)对于输入串i+i*i 给出一个最左推导;
(2)该文法是否是二义性文法?请证明你的结论。
解:(1)i+i*i的最左推导:
S = S+S = i+S = i+S*S = i+i*S = i+i*i
(2)该文法是二义性的。因为对于句子i+i*i可以画出两棵语法树(语法树略)。
3.给出语言{ambmcn|m≥1,n≥0}的上下文无关文法(2型)。
解: G: S→AB|A
A→aAb|ab
B→cB|c
4.给出语言{akbmcn|k,m,n≥1}的正规文法(3型)。
解: G: A→aA|aB
B→bB|bC
C→cC|c
5.将文法G改写成等价的正规文法(3型)。
G: S→dAB
A→aA|a
B→bB|b
解: G: S→dA
A→aA|aB
B→bB|b
6.构造一文法产生任意长的a,b串,使得
|a|≤|b|≤2|a|
其中,“|a|”和“|b|”分别表示串中的字符a和b的个数。
解:b的个数在a的个数和其2倍之间,串的结构形如aSBS和BSaS,其中B为1或2个b。故得文法
G: S→aSBS|BSaS|ε
B→b|bb
7.设有字母表{a,b}上的正规式R=(ab|a)*。
(1)构造R的相应有限自动机;
解:
(2)构造R的相应确定有限自动机;
解:将(1)所得的非确定有限自动机确定化
ε
a
b
-0
1
1
3
12
2
1
+3
a
b
-+013
123
+123
123
13
+13
123
(3)构造R的相应最小确定有
文档评论(0)