编译原理教程课后习题答案第五章

《编译原理教程课后习题答案第五章》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第五章代码优化5.1完成以下选择题：(1)优化可生成—的目标代码。a.运行时间较短b.占用存储空间较小c.运行时间短但占用内存空间人d.运行吋间短且占用存储空间小(2)下列—优化方法不是针对循环优化进行的。a.强度削弱b.删除归纳变量c.删除多余运算d.代码外提(3)基本块内的优化为oa.代码外提，删除归纳变量b.删除多余运篦，删除无川赋值c.强度削弱，代码外提d.循环展开，循环合并⑷在程序流图中，我们称具冇下述性质—的结点序列为一个循环。a.它们是非连通的且只有一个入口结点b.它们是强连通的但有多个入口结点c.它们是非连通的但有多个入口结

2、点d.它们是强连通的且只有一个入口结点(5)关于必经结点的二元关系，下列叙述中不正确的是—oa.满足自反性b.满足传递性c.满足反対称性d.满足对称性【解答】⑴d(2)c(3)b⑷d(5)d5.2何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行?【解答】优化根据涉及的程序范围可分为三种。(1)局部优化是指局限于基本块范围内的一种优化。一个基本块是指程序中一组顺序执行的语句序列(或四元式序列)，其屮只有一个入口(第一个语句)和一个出口(最后一个语句)。对于一个给定的程序，我们可以把它划分为一系列的基木块，然后在各个基木块范I罚内

3、分别进行优化。通常应用DAG方法进行局部优化。(2)循环优化是指対循环中的代码进行优化。例如，如果在循环语句中某些运算结果不随循坏的重复执行而改变，那么该运算可以提到循坏外，其运算结果仍保持不变，但程序运行的效率却捉高了。循环优化包括代码外捉、强度削弱、删除归纳变量、循环合并和循环展开。5.3将下面程序划分为基木块并作出其程序流图。read(A,B)F=1C=A*AD=B*BifC100gotoL2haltL2:

4、F=F-1gotoLI【解答】先求出四元式程序中各基本块的入口语句，即程序的第一个语句，或者能由条件语句或无条件转移语句转移到的语句，或者条件转移语句的后继语旬。然后对求出的每一入口语句构造其所属的基本块，它是rti该入口语句至下一入口语句(不包括该入口语句)或转移语句(包括该转移语句)或停语句(包括该停语句)之间的语句序列组成的。凡未被纳入某一基本块的语句都从程序中删除。要注意基本块的核心只冇一个入口和一个出口，入口就是其中第一个语句，出口就是其屮最后一个语句。如杲发现某基木块有两个以上的入口或两个以上的出口，则划分基本块有误。程序流图画

5、法是当下述条件⑴和(2)有一个成立时，从结点i有一有向边引到结点j：(1)基木块j在程序中的位置紧跟在基木块i之后，并且基木块i的出口语句不是无条件转移语句goto⑸或停语句。(2)基本块i的出口语句是goto(s)或if...goto(s),并且⑸是基本块j的入口语句。应用上述方法求出本题所给程序的基本块及程序流图见图5・1,图中的有向边、实线是按流图画法⑴画出的，虚线是按流图画法(2)画出的。J：E=B*B巧F=F+2E=E+Fwrite(E)ifE>100gcUoL5.4基木块的DAG如图5・2所示。若：(1)b在该基木块出口处不活跃

6、；(2)b在该基本块岀口处活跃；请分别给出下列代码经过优化Z后的代码:(1)a=b+c(2)b=a-d(3)c=b+c(4)d=a-d图5・2习题5.4的DAG图【解答】(1)当b在出口处不活跃时，生成优化后的代码为a=bO+cOd=a-dOc=d+cO(2)当b在出口活跃吋，纶成优化后的代码为a=bO+cOb=a-dOd=bc二d+cO5.5对于基木块P：S0=2S1=3/SOS2=T-CS3=T+CR=SO/S3H=RS4=3/S1S5=T+CS6=S4/S5H=S6*S2(1)应用DAG对该基本块进行优化；(2)假定只有R、H在基本块

7、出口是活跃的，试写出优化后的四元式序列。【解答】(1)根据DAG图得到优化后的四元式序列为S0=2S4=2Sl=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试画出如下中间代码序列的程序流图，并求出:(1)各结点的必经结点集合D(n)；(2)流图中的回边与循环。J=0L1：1=0if1<8gotoL3L2：A=B+CB=D*CL3：ifB=0gotoL4writeBgotoL5L4：1=1+1ifl<

8、8gotoL2L5：J=J+lifJ<=3gotoLIhalt【解答】(1)各结点的必经结点集分别为D(n0)={n0}D(nl)={n0,nl}D(n2)={n0,nl,n2}