完整word版编译原理试卷及答案word文档良心出品.doc
- 文档编号:14765361
- 上传时间:2023-06-27
- 格式:DOC
- 页数:5
- 大小:237KB
完整word版编译原理试卷及答案word文档良心出品.doc
《完整word版编译原理试卷及答案word文档良心出品.doc》由会员分享,可在线阅读,更多相关《完整word版编译原理试卷及答案word文档良心出品.doc(5页珍藏版)》请在冰点文库上搜索。
装订线
装订线内不要答题
学号
姓名
班级
东北大学秦皇岛分校
课程名称:
编译原理试卷:
(B)答案考试形式:
闭卷
授课专业:
计算机科学与技术考试日期:
年月日试卷:
共2页
题号
一
二
三
四
总分
得分
阅卷人
一、填空题(每空2分,共30分)
1、编译程序的整个过程可以从逻辑上划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等几个阶段,另外还有两个重要的工作是理和出错处理。
表格管
2、规范规约中的可归约串是句柄,算符优先分析中的可归约串是最左素短语。
3、语法分析方法主要可分为自顶向下和自底向上两大类。
4、LR(0)文法的项目集中不会出现移进-归约冲突和归约-归约冲突。
5、数据空间的动态存储分配方式可分为栈式和堆式两种。
6、编译程序是指能将源语言程序翻译成目标语言程序的程序。
7、确定有穷自动机DFA是NFA的一个特例。
8、表达式(a+b)*c的逆波兰表示为ab+c*。
二、选择题(每题2分,共20分)
1、LR语法分析栈中存放的状态是识别B的DFA状态。
A、前缀B、可归前缀C、项目D、句柄
2、D不可能是目标代码。
A、汇编指令代码B、可重定位指令代码
C、绝对机器指令代码D、中间代码
3、一个控制流程图就是具有C的有向图
A、唯一入口结点B、唯一出口结点C、唯一首结点D、唯一尾结点
4、设有文法G[S]:
S→b|bB B→bS ,则该文法所描述的语言是C。
A、L(G)={bi|i≥0}B、L(G)={b2i|i≥0}
C、L(G)={b2i+1|i≥0}D、L(G)={b2i+1|i≥1}
5、把汇编语言程序翻译成机器可执行的目标程序的工作是由B完成的。
A、编译器B、汇编器C、解释器D、预处理器
6、在目标代码生成阶段,符号表用于D。
A、目标代码生成B、语义检查C、语法检查D、预处理器地址分配0
7、规范归约是指B。
A、最左推导的逆过程B、最右推导的逆过程C、规范推导D、最左归约逆过程
8、使用A可以定义一个程序的意义。
A、语义规则B、词法规则C、语法规则D、左结合规则
9、经过编译所得到的目标程序是D。
A、三元式序列B、四元式序列C、间接三元式D、机器语言程序或汇编语言程序
10、在一个基本块内进行的代码优化是B。
A、全局优化B、局部优化C、循环优化D、代码外提
三、简答题(3小题,共30分)
1、已知文法G[S]:
S→Ac|aB
A→ab
B→bc
证明该文法具有二义性(本题6分)
证明:
因为该文法的句型abc存在如下两棵语法树:
所以,该文法具有二义性
装订线
装订线内不要答题
学号
姓名
班级
3、若有文法G[S]:
S→bAbA→(B|aB→Aa)。
构造该文法的简单优先关系矩阵。
(10分)
解:
4、构造正规表达式(a|b)*b的DFA并化简。
(14分)
解:
先构造其NFA如下:
确定化为DFA:
将其最小化如下:
四、综合题(20分)
设有文法G[S]:
S→BA A→BS|d B→aA|bS|c
(1)证明文法G是LL
(1)文法。
(2)构造LL
(1)分析表。
(3)写出句子adccd的分析过程。
解:
(1)
可见,文法G是是LL
(1)文法。
(2)
(3)
备注:
学生不得在试题纸上答题(含填空题、选择题等客观题
一、填空题(每空1分,共20分)
1.编译过程一般分为、、中间代码生成、
和目标代码生成五个阶段。
2.语法分析最常用的两类方法是和分析法。
3.确定的有穷自动机是一个,通常表示为。
4.所谓最右推导是指。
5.语法分析器的任务是。
6.如果一个文法的任何产生式的右部都不含有的非终结符,则这种文法称为文法。
7.进行确定的自上而下语法分析要求语言的文法是无和的。
8.LR分析法是一种的语法分析方法。
9.根据优化对象所涉及的程序范围,代码优化分为、和等。
10.常用的优化技术包括:
、、强度削弱、复写传播、等。
二、是非题(下列各题,你认为正确的,请在题后的括号内打“√”,错的打“×”。
每题2分,共20分)
1.正规文法产生的语言都可以用上下文无关文法来描述。
……………………()
2.仅考虑一个基本块,不能确定一个赋值是否真是无用的。
………………………( )
3.如果一个文法是递归的,则其产生的语言的句子是无穷个。
…………………( )
4.四元式之间的联系是通过符号表实现的。
…………………………………………( )
5.文法的二义性和语言的二义性是两个不同的概念。
…………………………( )
6.一个LL(l)文法一定是无二义的。
………………………………………………()
7.在规范规约中用最左素短语来刻划可归约串。
………………………………()
8.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。
……………()
9.编译程序是对汇编程序的翻译。
……………………………………( )
10.逆波兰法表示的表达式亦称前缀式。
……………………………………………()
三、简答题(每题5分,共15分)
1、简述栈式存储管理策略;2、何谓DAG;3、何谓文法的二义性;
四、给出下述文法对应的正规式(7分)
S→0A|1B
A→1S|1
B→0S|0
五、已知文法G(E):
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
证明E+T*F是该文法的一个句型,并指出该句型的所有短语、直接短语和句柄。
(8分)
六、设有文法G[S]:
SàaBc|bAB
AàaAb|b
Bàb|ε
构造其LL
(1)分析表,并分析符号串baabbb是否是该文法的句子.(10分)
七、设有文法G[E]:
Eà(E)|ε
试判断该文法是否为SLR
(1)文法,若不是,请说明理由;若是请构造SLR
(1)分析表。
(10分)
八、假设可用寄存器为R0和R1,试写出下列四元式序列对应的目标代码。
(10分)
T1=B-C
T2=A*T1
T3=D+1
T4=E-F
T5=T3*T4
参考答案
一、填空题(1X20=20分)
1.词法分析、语法分析、代码优化
2.自上而下、自下而上
3.五元组、DFA=(K,∑,M,S,Z)
4.任何一步都是对中最右非终结符进行替换
5.分析一个文法的句子结构
6.相邻、算符
7.左递归、公共左因子
8.自下而上
9.局部优化、循环优化、局部优化
10.删除公共子表达式、代码外提、变换循环控制条件、合并已知量、删除无用赋值(任选3个)
二、是非题(2X10=20分)
1、×2、√3、√4、×5、√6、√7、×8、√9、×10、×
三、简答题(见书中相应部分)(5X3=15分)
四、解:
首先得正规式方程组:
S=0A+1B
A=1S+1
B=0S+0
求解该方程组得:
S=(01|10)(01|10)*(8分)
五、解(2分)
是文法G[S]的句型。
短语:
E+T*F,T*F(2分)
直接短语:
T*F(2分)
句柄:
T*F(2分)
六、解:
、因为FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}(2分),所以构造文法G[S]的LL
(1)分析表(5)如下:
a
B
c
#
S
aBc
bAB
A
aAb
b
B
b
ε
ε
符号串baabbb是该文法的句子(3分)(分析过程略)。
七(2分)
所以该文法为SLR
(1)文法。
其分析表如下:
(8分)
状态
ACTION
GOTO
(
)
#
E
0
S2
r2
r2
1
1
acc
2
S2
r2
r2
3
3
S4
4
r1
r1
八、目标代码为:
(10分)
LDR0,B
SUBR0,C
LDR1,A
MULR1,R0
LDR0,D
ADDR0,1
STR1,M
LDR1,E
SUBR0,F
MULR0,R1
LDR1,M
DIVR1,R0
STR1,W
-5-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整 word 编译 原理 试卷 答案 文档 良心 出品