编译原理阶段练习四

1、编译原理练习四一、填空题1.编译过程中，常见的中间语言形式有四元式、三元式、逆波兰表示和树形表小。2、表达式x+y至Va>0A (8+z)>3的逆波兰表示为xy+z Ma0>8z+3>A V 。3、在编译程序中安排中间代码生成的目的是便于代码优化 和 便于目标程序的移植 。4、根据所涉及程序的范围，优化可分为局部优化、循环优化和全局优化三种。5、编译程序进行数据流分析的目的是为了进行全局优化。6 .局部优化是局限与一个基本块 范围内的一种优化。7 .基本块内可进行的优化有：删除公共子表达式、删除无用代码、合并已知8 .从词法分析器到中间代码生成与被编译的源代码有关，称之

2、为编译器的 前端,而目标代码生成主要与目标机有关，称之为编译器的 后端 。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) 的逆波兰表示

3、是 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)的逆波兰表示是 ca.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*db. (a+b)*(c+d)c. (a+b)*c+dd. a+b

4、*c+d7 .目标代码生成应着重考虑的问题是a da.每个语法成分的语义b.目标程序运行所占用的空间c.目标程序运行速度d.目标代码中需要哪些信息，怎样截取这些信息e.如何使生成的目标代码尽可能简短8 .代码优化的主要目标是a b c 。a.如何提高目标程序的运行速度b.如何减少目标程序运行所需的空间c.如何协调a和bd.如何使生成的目标代码尽可能的简短9 .编译程序在优化时 b 用到源程序中的注释a.可能要 b.不可能10 .在编译程序采用的优化方法中，c d e 是在循环语句范围内进行的。a.合并已知常量b.删除多余运算c.删除归纳变量d.强度消弱e.代码外提11 .程序基本块是指.d。a

5、. 一个子程序b. 一个仅有一个入口和一个出口的语句c. 一个没有嵌套的程序段d. 一组顺序执行的程序段，仅有一个入口和一个出口12 .合并表达式中的常量运算的目的是 。a.合并常量，使表达式中的常量尽可能少b.合并常量，是表达式尽可能简短c.将可在编译时刻计算的常量运算在编译时刻计算出来，然后用所计算出来的值替换表达式中出现的所以这种常量运算，使得生成的代码指令尽可能少13 .下面的程序段可以进行哪些优化cdei:=1j:=10 read k1: x:=x*i y:=j*i z:=x*y write j i:=i+1 if i<100 goto 1 halta.合并已知常量b.删除多余

6、运算c.删除归纳变量d.强度消弱e.代码外提三、为什么要使用中间语言形式？解答：使用中间语言形式有如下好处：i. 中间语言与具体机器无关，把与机器特性紧密相关的内容尽可能放到后端，有利于重定目标，一种中间语言可以为生成多种不同型号目标 机上的目标代码服务ii. 可以对中间语言进行与机器无关的优化，有利于提高目标代码的质量iii. 使各阶段的开发复杂性降低，有利于编译程序的开发 四、设有表达式A*(B*C-A) < B+C*D(1)写出逆波兰式中间代码(2)写出三元式中间代码(3)写出多元式中间代码(4)画出树解答：逆波兰表示：ABC*A-*BCD*+二兀式表小：(1)* B C(2)-(

7、1) A(3)* A (2)(4)* C D(5)+ B (4)(6)工(3) (5)多兀式表小：(1)* B C T1(2)-T 1 A T 2(3)* A T 2 T3(4)* C D T 4(5)+ B T 4 T 5(6)三 T 3 T 5 T 6树表小:五、试写出下列语句的四元式中间代码(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

8、begin y:=y-x; x:=x-1 end解答：> x0t1FJ 5 t i /:=0/xRJ 6 /:=1/x> x 0 tFJ 6 t 1 /> x 1 t:=t 2 / xRJ 1 / /(4)略六、给出从多元式划分基本块的方法解答：基本块划分算法：1)求出多元式程序中各个基本块的入口语句：?(1)程序的第一个句句；或者?(2)能由条件转移语句或无条件转移语句转移到达的语句；或者，?(3)仅跟在条件转移语句后面的语句。2)对以上求出的每一入口语句，构造其所属的基本块。从而3)凡未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句,也是不会被执行的语句，可把他们删除。七、给出程序流图(以基本块为结点)的一种表示方法。解答：参考书P3