《编译原理教程课后习题答案第五章》由会员分享，可在线阅读，更多相关《编译原理教程课后习题答案第五章（13页珍藏版）》请在装配图网上搜索。
1、第五章代码优化5.1 完成以下选择题：(1) 优化可生成 的目标代码。a. 运行时间较短b. 占用存储空间较小c. 运行时间短但占用内存空间大d. 运行时间短且占用存储空间小(2) 下列 优化方法不是针对循环优化进行的。a.强度削弱b. 删除归纳变量c. 删除多余运算d. 代码外提(3) 基本块内的优化为 。a. 代码外提，删除归纳变量b. 删除多余运算，删除无用赋值c. 强度削弱，代码外提d. 循环展开，循环合并(4) 在程序流图中，我们称具有下述性质的结点序列为一个循环。a. 它们是非连通的且只有一个入口结点b. 它们是强连通的但有多个入口结点c. 它们是非连通的但有多个入口结点d. 它们
2、是强连通的且只有一个入口结点(5) 关 于必经结点的二元关系，下列叙述中不正确的是 。a. 满足自反性b. 满足传递性c. 满足反对称性d. 满足对称性【解答】(1) d C (3) b d (5) d5.2 何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行？【解答】 优化根据涉及的程序范围可分为三种。(1) 局部优化是指局限于基本块范围内的一种优化。 一个基本块是指程序中一组顺序执行的语句序列 (或四元式序列 ) ，其中只有一个入口 (第一个语句 )和一个出口 (最后一个语句) 。对于一个给定的程序，我们可以把它划分为一系列的基本块，然后在各个基本块范围内分别进行优化。通常应用
3、DAGT法进行局部优化。(2) 循环优化是指对循环中的代码进行优化。例如，如果在循环语句中某些运算结果不随循环的重复执行而改变， 那么该运算可以提到循环外，其运算结果仍保持不变，但程序运行的效率却提高了。 循环优化包括代码外提、强度削弱、删除归纳变量、循环合并和循环展开。5.3 将下面程序划分为基本块并作出其程序流图。read(A,B)F=1C=A*AD=B*Bif C100 goto L2 halt L2:F=F-1goto L1【解答】先求出四元式程序中各基本块的入口语句，即程序的第一个语句，或者能由条件语句或无条件转移语句转移到的语句，或者条件转移语句的后继语句。然后对求出的每一入口语句
4、构造其所属的基本块，它是由该入口语句至下一入口语句(不包括该入口语句)或转移语句(包括该转移语句)或停语句(包括该停语句)之间的语句序列组成的。凡未被纳入某一基本块的语句都从程序中删除。要注意基本块的核心只有一个入口和一个出口，入口就是其中第一个语句，出口就是其中最后一个语句。如果发现某基本块有两个以上的入口或两个以上的出口，则划分基本块有误。 程序流图画法是当下述条件(1)和(2)有一个成立时，从结点i有一有向边引到结点j：(1)基本块j在程序中的位置紧跟在基本块i之后，弁且基本块i的出口语句不是无条件转移语句goto(s)或停语句。(2)基本块i的出口语句是 goto(s)或if ? ?
5、? got(s),弁且(S)是基本块j的入口语句。应用上述方法求出本题所给程序的基本块及程序流图见图5-1 ,图中的有向边、实线是按流图画法(1)画出的，虚线是按流图画法(2)画出的。ead(A,B)F = 1C = A*A0 = B*BifC 100 go)L5.4 基本块的DA改口图5-2所示。若：(1) b在该基本块出口处不活跃；(2) b在该基本块出口处活跃；请分别给出下列代码经过优化之后的代码(1) a=b+c b=a-d(3) c=b+c d=a-d图5-2习题5.4的DAGS【解答】 (1)当b在出口处不活跃时，生成优化后的代码为a=b0+c0 d=a-d0 c=d+c0(2)当
6、b在出口活跃时，生成优化后的代码为a=b0+c0 b=a-d0d=bc=d+c05.5 对于基本块P:S0=2S 仁 3/S0S2=T-CS3=T+CR=S0/ S3H=RS4=3/ S1S5=T+CS6=S4/ S5H=S6*S2应用DAG寸该基本块进行优化；根(2)假定只有R H在基本块出口是活跃的，试写出优化后的四元式序列。【解答】据DAGS得到优化后的四元式序列为S0=2S4=2S1 = 1.5S2=T-CS3=T+CS5=S3R=2/S3S6=RH=S6*S2(2)若只有R、H在基本块出口是活跃的，优化后的四元式序列为S2=T-CS3=T+CR=2/ S3H=R*S25.6 试画出如
7、下中间代码序列的程序流图，弁求出(1)各结点的必经结点集合D(n)；(2)流图中的回边与循环。J=OL1 : I=Oif I 8 goto L3L2: A=B+CB=D*CL3 : if B =0 goto L4Write Bgoto L5 L4 : I= 1 + 1if I8 goto L2L5 : J= J+1if J n,且该通路不经过 d,从而d2应属于M ,这与d2 G L矛盾。所以不可能存在上 述结点di,也即d是循环的唯一入口结点。至此，我们已经满足了循环的定义：循环是程序流图中具有唯一入口结点的强连通子图，也即，L是包含回边n-d的循环，d是循环的唯一入口结点。5.8 对下面四
8、元式代码序列：A=Oi = iLi:B=J+iC=B+IA=C+Aif I=i00 goto L2 I=I+igoto LiL2: Write Ahalt画出其控制流程图；【解答】(1)在构造程序的基本块的基础上画出该程序的流图，如图(2)求出循环弁进行循环的代码外提和强度削弱优化。5-5所示。BiL,: B = J+ 1B2C A if IB + I C + A =100 gotg1=1+1 B3 goto L1L/ write AhaltB4图5-6习题5.8中代码外提后的程序流图 我们知道，强度削弱不仅可对乘法运算进行，也可对加法运算进行。由于本题中的四元式程序不存在乘法运算，所以只能进
9、行加法运算的强度削弱。从图5-5中可以看到，B2中的C=B+I ,变量B因代码外提其定值点已在循环之外，故相当于常数。而另一加数I值由B3中的1 = 1 + 1决定，即每循环一次I值增1；也即每循环一次，B2中的C=B+I其C值增量与B3中的I相同，即常数1。因此，我们可以对 C进行强度削弱，即将 外提 B2中的四元式C=B+I 到前置结点B2 中，同时在B3中I=I+1之后给C增加一个常量1。进行强度削弱后的结果如图5-7所示。5.9 某程序流图如图5-8所示。(1)给出该流图中的循环;(2)指出循环不变运算；(3)指出哪些循环不变运算可以外图5-8习题5.9的程序流图【解答】 流图中的循环
10、为B2,B3,B4 o(2) B3中的i=2是循环不变运算。(3)循环不变运算外提的条件是：该不变运算所在的结点是循环所有出口结点的必经结点； 当把循环不变运算 A=B OP C(B或OP C可以没有)外提时，要求循环中其他地方不再有A的定值点； 当把循环不变运算 A=B op C外提时，要求循环中 A的所有引用点都是而且仅 仅是这 个定值所能到达的。由于i=2所在的结点不是循环所有出口结点的必经结点，故不能外提。5.10 一程序流图如图5-9所示，试分别对其进行代码外提、强度削弱和删除归纳变量等优 化。i = 1BiLi:if i M goto LFlB2j = 1B3B4B6I if j
11、N goto3LL2：F TT = =i*Ni = i + 1T2 =T+ jgoto L 1T3 =addr(A)-CT4 =i*NT5 =l+ jT6 =addr(B)-CT7 =TgT3T2 = T j = j + 1 goto L 2【解答】由图5-9可知，B5B4与B6 B2为流图的有向边，从而有D(B5)= B1 , BZ B3, B4, B5D(B6)= B1 , BZ B3, B4, B6故有B4 DOM B5和B2 DOM B6,因此BgB4和B B2为何边(其余都不是回 边)，即分别组 成了循环B4 , B5、B2 , B3 , B4 , B5 , B6。对循环B4 , B5、B2 , B3 , B4 , B5 , B6进行代码外提、强度削弱和删除归纳变量等优化后，其优化后的程序流图如图5-10所示。i = 1 BiT3= addr(A)T6= addr(B)T 1 = i*NT4 = i*NR = M*Nif T i R gotoT 5 ? 1 +B3Q j + f T 2+if T 2 R goto B 6T7= 口 5T5= T + 1T3T 2 = TT2 = T + 1 goto B 4T；=+ N b6goto B 2B7图5-10习题5.10中优化后的程序流图
编译原理教程课后习题答案第五章
