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

第8章习题7-1设有如下的三地址码（四元式）序列：readNI:=NJ:=2L1:ifI≤JgotoL3L2:I:=I-JifIJgotoL2ifI=0gotoL4J:=J+1I:=NgotoL1L3:Print′YES′haltL4:Print′NO′halt试将它划分为基本块，并作控制流程图。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*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)找出各流程图的全部循环。345678212345678(a)(b)1234576(c)题图7-47-5对于如下的程序：I:=1readJ,KL:A:=K*IB:=J*IC:=A*BwriteCI:=I+1ifA100gotoLhalt试对其中的循环进行可能的优化。第8章习题答案7-1解：划分情况及控制流程如答案图7-1所示：L1ifI≤JgotoL3L2I:=I-JifIJgotoL2ifI=0gotoL4L3Print′YES′haltB1B2B6readNI:=NJ:=2J:=J+1I:=NgotoL1L4Print′NO′haltB7B3B4B5答案图7-1将四元式序列划分为基本块7-2解：(1)相应的DAG如答案图7-2所示。n1n2B0C0n3*Dn4,BA0n5+En6+An1n2B0C0n3*Dn4,BA0n5+En1n2B0C0n3*Dn4A0n5+En1n2B0C0n3*D(a)(b)(c)(d)答案图7-2DAG(2)优化后的代码为：D:=B*CE:=A+BB:=DA:=E+D7-3解：(1)相应的DAG如答案图7-3-(1)所示。答案图7-3-(1)n2B0C0*A,Gn4/DEn62H+F,L,Mn7*n3*n5*F0n9n8n1若只有G、L、M在出口之后被引用，则优化后的代码为：G:=B*CH:=G*GL:=H*GM:=L若只有L在出口之后被引用，则代码为：G:=B*CH:=G*GL:=H*G(2)相应的DAG如答案图7-3-(2)所示。答案图7-3-(2)n3A0C0+D,Hn5*E,IF,Jn63+Gn9n4n6*L,Mn7n2n1Bn8515K+若只有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={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)所示。(1)I:=1(2)readJ,K(9)haltB1B2B3(3)A:=K*I(4)B:=J*I(5)C:=A*B(6)writeC(7)I:=I+1(8)ifI100gotoL答案图7-5-(1)划分基本块后的流程图(2)削弱运算强度后的流程图如答案图7-5-(2)所示。(1)I:=1(2)readJ,K(9)haltB1B2B3(3)A:=T1(4)B:=T2(5)C:=A*B(6)writeC(7)I:=I+1(3)〞T1:=T1+K(4)〞T2:=T2+J(8)ifI100gotoB2(3)′T1:=K*I(4)′T2:=J*IB2′答案图7-5-(2)削弱运算强度后的流程图(3)消除归纳变量后的流程图如答案图7-5-(3)所示。(1)I:=1(2)readJ,K(9)haltB1B2B3(3)A:=T1(4)B:=T2(5)C:=A*B(6)writeC(3)〞T1:=T1+K(4)〞T2:=T2+J(8)ifAT3gotoB2(3)′T1:=K*I(4)′T2:=J*I(7)′T3:=K*100B2′答案图7-5-(3)消除归纳变量后的流程图