编译原理第7章 习题与答案

n3D*n1n2B0C0(a)n5En3D, B+*n4n1n2A0B0C0(c)答案图7-2 DAG(2) 优化后的代码为： D:=B*C 7-3 解：

(1) 相应的DAG如答案图7-3-(1)所示。

n5En3D+*n4n1n2A0B0C0(b)n6A+n5En3D, B+*n4n1n2A0B0C0(d)

E:=A+B B:=D A:=E+D

n9F, L, M*n8*H+n3A, G*n1B0n4D/n2C0答案图7-3-(1)n5En7F0*n62

若只有G、L、M在出口之后被引用，则优化后的代码为：

G:=B*C H:=G*G L:=H*G M:=L

若只有L在出口之后被引用，则代码为：

G:=B*C H:=G*G L:=H*G

(2) 相应的DAG如答案图7-3-(2)所示。

n7G*n9L, M+n6F, J+n4D, H+n1B3n65n8K15n2A0答案图7-3-(2)n5E, I*n3C0 若只有G、L、M被引用，则代码为：

D:=A+C E:=A*C F:=E+D G:=3*F L:=15+F M:=L

若只有L被引用，则代码为：

D:=A+C E:=A*C F:=E+D L:=+F15

7-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)所示。