考试科目:《编译原理》第8章至第10章（总分100分） 时间：90分钟
一、选择与填充（30）
1. 四元式之间的联系是通过( )来实现的。
A．指示器 B．临时变量 C．符号表 D．程序变量 2. 优化可生成( )的目标代码。
A. 运行时间较短 B. 运行时间短但占用内存空间大 C. 占用存储空间较小 D. 运行时间短且占用存储空间小 3. 下列( )优化方法不是针对循环优化进行的。
A. 强度削弱 B．删除归纳变量 C．删除多余运算 D．代码外提 4. 在目标代码生成阶段，符号表用于( )。
A．目标代码生成 B．语义检查 C．语法检查 D．地址分配
5．语法分析是依据语言的__________规则进行的，中间代码产生是依据语言的_________规进行的。
6．优化可分为局部优化、_____________和全局优化三种。
二、写出表达式A*(B/C-D)+E/F的逆波兰中间代码。(15)
三、什么是活动记录？它主要由哪些内容构成？(15)
四、试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。(15)
五、文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。 (30)
G[M]: 1) S →VdB 2) V →e 3) V →ε 4) B →a 5) B →Bda 6) B →ε
状态 0 1 2 3 4 5 d r3 S4 r2 r6 r4 ACTION e a S3 S5 1 # acc r6 r4 S 1 GOTO B 6 V 2 6 7 8
S7 r5 S8 r1 r5 附：参考答案：
一、选择与填充（30）
1. 四元式之间的联系是通过( B )来实现的。
A．指示器 B．临时变量 C．符号表 D．程序变量 2. 优化可生成( D )的目标代码。
A. 运行时间较短 B. 运行时间短但占用内存空间大 C. 占用存储空间较小 D. 运行时间短且占用存储空间小 3. 下列( C )优化方法不是针对循环优化进行的。
A. 强度削弱 B．删除归纳变量 C．删除多余运算 D．代码外提 4. 在目标代码生成阶段，符号表用于( D )。
A．目标代码生成 B．语义检查 C．语法检查 D．地址分配
5．语法分析是依据语言的___语法__规则进行的，中间代码产生是依据语言的__语义___规进行的。
6．优化可分为局部优化、____循环优化____和全局优化三种。
二、写出表达式A*(B/C-D)+E/F的逆波兰中间代码。(15)
解： ABC/D-*EF/+
三、什么是活动记录？它主要由哪些内容构成？(15)
解：一个过程的一次执行所需信息的管理，是通过称为活动记录的连续存储块来实现的。活动记录的主要内容有：
(1)临时变量域 存放目标程序临时变量的值；
(2)局部数据域 存放过程本次执行时的局部数据、简单变量及数组内情向量等；
(3)机器状态域 保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等； (4)存取链 为访问其它活动记录中所存放的非局部数据所提供的链地址； (5)控制链 指向主调过程的活动记录；
(6)实参 存放主调过程为被调用过程所提供的实参信息； (7)返回值 为主调过程存放被调过程的返回值
四、试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。(15)
2
解： 该表达式的四元式序列为：
(1) (*, b, c, T1） (2) (+, a, T1, T2) (3) (*, c, b, T3) (4) (+, T3, a, T4) (5) (-, T4, e, T5) (6) (*, b, c, T6) (7) (+, T6, d, T7) (8) (/, T5, T7, T8) (9) (-, T2, T8, T9)
可以对该表达式进行删除公共子表达式的优化。优化后的四元式序列为： (1) (*, b, c, T1）
(2) (+, a, T1, T2) (3) (-, T2, e, T5) (4) (+, T1, d, T7) (5) (/, T5, T7, T8) (6) (-, T2, T8, T9)
五、文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。 (30)
G[M]: 1) S →VdB 2) V →e 3) V →ε 4) B →a 5) B →Bda 6) B →ε
状态 0 1 2 3 4 5 6 7 8 解： 状态栈 S0 S0S2
d r3 S4 r2 r6 r4 S7 r5 符号栈 # #V ACTION e a S3 S5 S8 # acc r6 r4 r1 r5 输入流 dada# dada# 3
S 1 GOTO B 6 动作 r3 S4 V 2 S0S2S4 S0S2S4S5 S0S2S4S6 S0S2S4S6S7 S0S2S4S6S7S8 S0S2S4S6 S0S1
#Vd #Vda #VdB #VdBd #VdBda #VdB #S ada# da# da# a# # # # S5 r4 S7 S8 r5 r1 acc 4
编译原理第3阶段练习题
