蒋立源-编译原理第三版第八章-习题与答案

)第8章习题7-1设有如下的三地址码（四元式）序列：readNI:=NJ:=2L:ifI≤JgotoL13L:I:=I-J2ifI>JgotoL2$ifI=0gotoLJ:=J+14I:=NgotoL1L:Print′YES′3haltL:Print′NO′4halt|试将它划分为基本块，并作控制流程图。7-2考虑如下的基本块：D:=B*CE:=A+BB:=B*CA:=E+D(1)构造相应的DAG；%(2)对于所得的DAG，重建基本块，以得到更有效的四元式序列。

7-3对于如下的两个基本块：(1)A:=B*CD:=B/CE:=A+DF:=2*EG:=B*C…H:=G*GF:=H*GL:=FM:=L(2)B:=3D:=A+CE:=A*CF:=E+D@G:=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)找出各流程图的全部循环。《1232412345345667567887(a)(b)(c)题图7-47-5对于如下的程序：I:=1readJ,KL:A:=K*IB:=J*IC:=A*B~writeCI:=I+1ifA<100gotoLhalt试对其中的循环进行可能的优化。第8章习题答案{7-1解：划分情况及控制流程如答案图7-1所示：readNI:=NJ:=2B1B2LifI≤JgotoL13LI:=I-JB23ifI>JgotoL2BifI=0gotoL44J:=J+1I:=NB5gotoL1B6LPrint′YES′3haltLPrint′NO′haltB47答案图7-1将四元式序列划分为基本块7-2解：(1)相应的DAG如答案图7-2所示。nDnE5nD33*+*n2n2n1n4n1B0CA0B0C00(a)(b)nA6+nE5nD,BnE5nD,B33+*+*n2n4n1n2n4n1A0B0C0A0B0C0(c)(d):答案图7-2DAG(2)优化后的代码为：D:=B*CE:=A+BB:=DA:=E+D|7-3解：(1)相应的DAG如答案图7-3-(1)所示。nFnF,L,M970**nH8nE5*+nA,G3nD4*/n1n2n6B0C02答案图7-3-(1)若只有G、L、M在出口之后被引用，则优化后的代码为：G:=B*CH:=G*GL:=H*G/M:=L若只有L在出口之后被引用，则代码为：G:=B*CH:=G*GL:=H*G(2)相应的DAG如答案图7-3-(2)所示。nG7nL,M9*+nF,J6+nD,H4nE,I5+*nB1n6nK8n2n33515A0C0答案图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)必经结点集：D={2}2（D={2,3}，3D={2,4}4D={2,4,5}5D={2,4,6}6D={2,4,7}7D={2,4,7,8}8回边及相应的循环：7→4：{4,5,6,7}8→2：{2,3,4,5,6,7,8}(b)必经结点集：D={1}1D={1,2}2'D={1,2,3}3D={1,2,3,4}4D={1,2,3,5}5D={1,2,3,6}6D={1,2,7}7D={1,2,7,8}8回边及相应循环：7→2：{2,3,4,5,6,7}(c)必经结点集：D={1}1D={1,2},2D={1,2,3}3D={1,2,4},4~D=1,2,5}5D={1,2,3,6},6D={1,2,7}7回边及相应循环：5→2：{2，3，4，5}6→6：{6}注意：5→4不是回边。因为4不是5的控制结点。7-5解：(1)划分基本块后的流程图如答案图7-5-(1)所示。

BB(1)I:=11(2)readJ,K(3)A:=K*I2(4)B:=J*I(5)C:=A*B(6)writeC(7)I:=I+1(8)ifI<100gotoLB(9)halt3答案图7-5-(1)划分基本块后的流程图(2)削弱运算强度后的流程图如答案图7-5-(2)所示。(1)I:=1B12(2)readJ,KBB′(3)′T:=K*I1(4)′T:=J*I2(3)A:=T12(4)B:=T2(5)C:=A*B(6)writeC(7)I:=I+1(3)〞T:=T+K11(4)〞T:=T+J22(8)ifI<100gotoB(9)halt2B3答案图7-5-(2)削弱运算强度后的流程图(3)消除归纳变量后的流程图如答案图7-5-(3)所示。(1)I:=1B12(2)readJ,KBB(3)′T:=K*I1(4)′T:=J*I2′(7)′T:=K*10032