资源描述：
《蒋立源-编译原理第三版第八章-习题与答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第8章习题7-1设有如下的三地址码（四元式）序列：readNI:=NJ:=2L1:ifI≤JgotoL3L2:I:=I-JifI>JgotoL2ifI=0gotoL4J:=J+1I:=NgotoL1L3:Print′YES′haltL4:Print′NO′halt试将它划分为基本块，并作控制流程图。7-2考虑如下的基本块：D:=B*C E:=A+B B:=B*C A:=E+D(1)构造相应的DAG；(2)对于所得的DAG，重建基本块，以得到更有效的四元式序列。7-3对于如下的两个基本块：(1)A:=B*CD:=B/C E:=A+DF:=2*EG:
2、=B*CH:=G*GF:=H*GL:=FM:=L(2)B:=3D:=A+CE:=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L分别构造相应的DAG，并根据所得的DAG，重建经优化后的四元式序列。在进行优化时，须分别考虑如下两种情况：（ⅰ）变量G、L、M在基本块出口之后被引用；（ⅱ）仅变量L在基本块出口之后被引用。7-4对于题图7-4所示的控制流程图：(1)分别求出它们各个结点的必经结点集；(2)分别求出它们的各个回边；(3)找出各流程图的全部循环。7-5对于如下的程序：I:=1readJ,KL:
3、A:=K*IB:=J*IC:=A*BwriteCI:=I+1ifA<100gotoLhalt试对其中的循环进行可能的优化。第8章习题答案7-1解：划分情况及控制流程如答案图7-1所示：答案图7-1将四元式序列划分为基本块7-2解：(1)相应的DAG如答案图7-2所示。答案图7-2DAG(2)优化后的代码为： D:=B*C E:=A+B B:=D A:=E+D7-3解：(1)相应的DAG如答案图7-3-(1)所示。若只有G、L、M在出口之后被引用，则优化后的代码为：G:=B*CH:=G*GL:=H*GM:=L若只有L在出口之后被引用，则代码为：G:
4、=B*CH:=G*GL:=H*G(2)相应的DAG如答案图7-3-(2)所示。若只有G、L、M被引用，则代码为：D:=A+CE:=A*CF:=E+DG:=3*FL:=15+FM:=L若只有L被引用，则代码为：D:=A+CE:=A*CF:=E+DL:=+F157-4解：(a)必经结点集：D2={2}D3={2,3}，D4={2,4}D5={2,4,5}D6={2,4,6}D7={2,4,7}D8={2,4,7,8}回边及相应的循环：7→4：{4,5,6,7}8→2：{2,3,4,5,6,7,8}(b)必经结点集：D1={1}D2={1,2}D3={
5、1,2,3}D4={1,2,3,4}D5={1,2,3,5}D6={1,2,3,6}D7={1,2,7}D8={1,2,7,8}回边及相应循环：7→2：{2,3,4,5,6,7}(c)必经结点集：D1={1}D2={1,2},D3={1,2,3}D4={1,2,4},D5=1,2,5}D6={1,2,3,6},D7={1,2,7}回边及相应循环：5→2：{2，3，4，5}6→6：{6}注意：5→4不是回边。因为4不是5的控制结点。7-5解：(1)划分基本块后的流程图如答案图7-5-(1)所示。(2)削弱运算强度后的流程图如答案图7-5-(2)所示
6、。答案图7-5-(2)削弱运算强度后的流程图(3)消除归纳变量后的流程图如答案图7-5-(3)所示。答案图7-5-(3)消除归纳变量后的流程图
