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

第7章 习题

7-1 设有如下的三地址码（四元式）序列：

read N I:=N J:=2

L1 : if I≤J goto L3 L2 : I:=I-J

if I>J goto L2 if I=0 goto L4 J:=J+1 I:=N goto L1

L3 : Print ′YES′

halt

L4 : 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*C

D:=B/C

E:=A+D

F:=2*E G:=B*C H:=G*G F:=H*G

L:=F

M:=L

(2) B:=3 D:=A+C

E:=A*C F:=E+D G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L

分别构造相应的DAG，并根据所得的DAG，重建经优化后的四元式序列。在进行优化时，须分别考虑如下两种情况：

（ⅰ）变量G、L、M在基本块出口之后被引用； （ⅱ）仅变量L在基本块出口之后被引用。

7-4 对于题图7-4所示的控制流程图： (1) 分别求出它们各个结点的必经结点集； (2) 分别求出它们的各个回边； (3) 找出各流程图的全部循环。

234456112356324778(a)8(b)题图7-4657(c)

7-5 对于如下的程序：

I:=1 read J,K L: A:=K*I

B:=J*I C:=A*B write C I:=I+1

if A<100 goto L halt

试对其中的循环进行可能的优化。

第8章 习题答案

7-1 解：划分情况及控制流程如答案图7-1所示：

B1B2read NI:=NJ:=2L1B3B4B5B6L3L2if I≤J gotoL3I:=I-Jif I>J gotoL2if I=0 gotoL4J:=J+1I:=NgotoL1Print ′YES′halt B7L4 Print ′NO′halt 答案图7-1 将四元式序列划分为基本块

7-2 解：

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