编译原理试卷及答案.doc

装 订 线
装 订 线 内 不 要 答 题
学 号

姓 名

班 级

东 北 大 学 秦 皇 岛 分 校

课程名称： 编译原理 试卷： (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→bAb A→（B|a B→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分)
LD R0,B
SUB R0,C
LD R1,A
MUL R1,R0
LD R0,D
ADD R0,1
ST R1,M
LD R1,E
SUB R0,F
MUL R0,R1
LD R1,M
DIV R1,R0
ST R1,W

- 5 -