编译原理练习四
一、填空题
1．编译过程中，常见的中间语言形式有四元式 、 三元式 、 逆波兰表示和 树形表示。
2、表达式x+yzVa>0Λ(8+z)>3的逆波兰表示为 xy+za0>8z+3>ΛV 。 3、在编译程序中安排中间代码生成的目的是 便于代码优化 和 便于目标程序的移植 。
4、根据所涉及程序的范围，优化可分为局部优化、循环优化 和全局优化三种。
5、编译程序进行数据流分析的目的是为了进行全局优化。
6．局部优化是局限与一个 基本块 范围内的一种优化。
7．基本块内可进行的优化有：删除公共子表达式 、删除无用代码 、合并已知常量等。 8．从词法分析器到中间代码生成与被编译的源代码有关，称之为编译器的 前端， 而目标代码生成主要与目标机有关，称之为编译器的 后端 。 9．编译器通常按需要把寄存器分为三组使用： 可分配寄存器 、保留寄存器 和 零用寄存器 。
10．释放寄存器的总的原则是释放代价最小的寄存器 。
二、选择题
1．表达式-a+b*(-c+d)的逆波兰式是 d 。 a.ab+-cd+-* b.a-b+c-d+* c.a-bc+-d+* d.a-bc-d+*+
2．在编译程序中安排中间代码生成的目的是 b d 。 a. 便于进行存储空间的组织 b. 有利于目标代码的优化 c. 有利于编译程序的移植 d. 有利于目标代码的移植 e. 有利于提高目标代码的质量
3．-a-(b*c/(c-d)+(-b)*a)的逆波兰表示是 c 。 a.abc*cd-b-a*+/-- b.a-bc*cd-b-a*+/- c.a-bc*cd-/b-a*+- d.a-bc*/cd-b-a*+-
4.赋值语句X:=-(a+b)/(c-d)-(a+b*c)的逆波兰表示是 c 。 a.Xab+cd-/-bc*a+-:= b. Xab+/cd-bc*a+--:= c. Xab+-cd-/abc*+-:= d. Xab+cd-/abc*+--:=
5.对任何一个编译程序来说，产生中间代码是 b . a.不可缺少的 b. 不一定必要的
6．逆波兰表达式ab+cd+*所代表的中缀形式的表达式是 b 。 a.a+b+c*d b. (a+b)*(c+d) c. (a+b)*c+d d. a+b*c+d
7.目标代码生成应着重考虑的问题是 a d a. 每个语法成分的语义
b. 目标程序运行所占用的空间 c. 目标程序运行速度
d. 目标代码中需要哪些信息，怎样截取这些信息 e. 如何使生成的目标代码尽可能简短
8．代码优化的主要目标是 a b c 。 a. 如何提高目标程序的运行速度
b. 如何减少目标程序运行所需的空间 c. 如何协调a和b
d. 如何使生成的目标代码尽可能的简短
9．编译程序在优化时 b 用到源程序中的注释 a.可能要 b.不可能
10．在编译程序采用的优化方法中， c d e 是在循环语句范围内进行的。 a. 合并已知常量 b. 删除多余运算 c. 删除归纳变量 d. 强度消弱 e. 代码外提
11．程序基本块是指 d 。 a. 一个子程序
b. 一个仅有一个入口和一个出口的语句 c. 一个没有嵌套的程序段
d. 一组顺序执行的程序段，仅有一个入口和一个出口
12．合并表达式中的常量运算的目的是 c 。 a. 合并常量，使表达式中的常量尽可能少 b. 合并常量，是表达式尽可能简短
c. 将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的
值替换表达式中出现的所以这种常量运算，使得生成的代码指令尽可能少
13．下面的程序段可以进行哪些优化c d e i:=1 j:=10 read k 1: x:=x*i y:=j*i z:=x*y write j i:=i+1
if i<100 goto 1 halt
a.合并已知常量 b.删除多余运算 c.删除归纳变量 d.强度消弱 e.代码外提
三、为什么要使用中间语言形式？ 解答：使用中间语言形式有如下好处：
i. 中间语言与具体机器无关，把与机器特性紧密相关的内容尽可能放到
后端，有利于重定目标，一种中间语言可以为生成多种不同型号目标机上的目标代码服务
ii. 可以对中间语言进行与机器无关的优化，有利于提高目标代码的质量 iii. 使各阶段的开发复杂性降低，有利于编译程序的开发
四、设有表达式A*(B*C-A) B+C*D
(1)写出逆波兰式中间代码 (2)写出三元式中间代码 (3)写出多元式中间代码 (4)画出树
解答：逆波兰表示：ABC*A-*BCD*+ 三元式表示：（1）* B C （2）-（1） A （3）* A （2） （4）* C D （5）+ B （4） （6） （3）（5） 多元式表示：（1）* B C T1 （2）- T1 A T2 （3）* A T2 T3 （4）* C D T4 （5）+ B T4 T5 （6） T3 T5 T6 树表示：
* + A - B * * A C D B C
五、试写出下列语句的四元式中间代码
(1)if x>0 then x:=0 else x:=1 (2)while x>0 do x:=x-1
(3)if x>0 then if x<0 then x:=x+1 else x:=1 else x:=1 (4)while x>0 do while y>0 do begin y:=y-x; x:=x-1 end 解答： (1)
> x 0 t1 FJ 5 t1 / := 0 / x RJ 6 / / := 1 / x (2)
> x 0 t1 FJ 6 t1 / - x 1 t2 := t2 / x RJ 1 / /
(3)(4)略
六、给出从多元式划分基本块的方法 解答：基本块划分算法：
1)求出多元式程序中各个基本块的入口语句： •(1)程序的第一个句句；或者
•(2)能由条件转移语句或无条件转移语句转移到达的语句；或者， •(3)仅跟在条件转移语句后面的语句。
2)对以上求出的每一入口语句，构造其所属的基本块。
3)凡未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句，从而
也是不会被执行的语句，可把他们删除。
七、给出程序流图（以基本块为结点）的一种表示方法。 解答：参考书P328
八、设有语句序列 i:=2;
j:=i*(i+1); k:=2*(i+j)
试写出优化前和优化后的多元式代码。其中变量均为一般整形变量。 解答： 优化前
:= 2 i
+ i 1 t1 * i t1 t2 := t2 j
+ i j t3 * 2 t3 t4 := t4 k 优化后
:= 2 i := 6 j := 24 k
