编译原理（龙书）：第八章部分题目参考答案

以下题目答案源自编译原理课程作业。

(1) 2+2+1+2=7 (2) 2+2+2+2=8 (3) 2+2+2+2=8 (4) 2+2+2=6 (5) 2+2+2=6 (6) 2+2+1+2=7

(1) 三地址序列与基本块划分： B1 (1) i=2 B2 (2) if i>n goto (7) B3 (3) t1=i4 (4) a[t1]=TRUE (5) i=i+1 (6) goto (2) B4 (7) count=0 (8) s=sqrt(n)(9) i=2 B5 (10) if i>s goto (22) B6 (11) t2=i4 (12) ifFalse a[t2] goto (20) B7 (13) count=count+1 (14) j=2i B8 (15) j=0 B9 (16) t3=j4 (17) a[t3]=FALSE (18) j=j+1 (19) goto (15) B10 (20) i=i+1 (21) goto (10) B11 (22) …

(2) 流图：

(3) 存在的循环有： a) B2 -> B3 -> B3 b) B5 -> B6 -> B10 -> B5 c) B5 -> B6 -> B7 ->B8 -> B10 d) B8 -> B9 -> B8

(1) a设置为不活跃，b设置为活跃，影响所有对数组a的引用 (2) a设置为不活跃，b设置为活跃，影响所有对数组b的引用 (3) a设置为不活跃，b设置为活跃，从后往前的扫描过程中，所有对b的使用都是活跃的 (4) a设置为不活跃，b设置为活跃，从后往前的扫描过程中，所有对a的使用都是不活跃的

假设本题中的数组被定义为int[]或int[n][]

1）

2）

3)

4) 5)

6）

机器代码： LD R1, b LD R2, c MUL R1, R1, R2 R1 R2 R3 a b c x t1 t2 t1 c a b c,R2 x R1 LD R2, a ADD R1, R1, R2 R1 R2 R3 a b c x t1 t2 t2 a a,R2 b c,R2 x R1 ST x, R1 R1 R2 R3 a b c x t1 t2 t2 a a,R2 b c,R2 x R1

2) 机器代码： LD R1,e LD R2,f ADD R1,R1,R2 R1 R2 R3 a b c d e f x t1 t2 t3 t4 t5 t1 f a b c d e f,R2 x R1 LD R2,d MUL R1,R1,R2 R1 R2 R3 a b c d e f x t1 t2 t3 t4 t5 t2 d a b c d,R2 e f x R1 LD R2,b LD R3,c ADD R2,R2,R3 R1 R2 R3 a b c d e f x t1 t2 t3 t4 t5 t2 t3 c a b c,R3 d e f x R1 R2 LD R3,a DIV R2,R3,R2 R1 R2 R3 a b c d e f x t1 t2 t3 t4 t5 t2 t4 a a,R3 b c d e f x R1 R2 SUB R1,R2,R1 R1 R2 R3 a b c d e f x t1 t2 t3 t4 t5 t5 t4 a a,R3 b c d e f x R2 R1 ST x,R1 R1 R2 R3 a b c d e f x t1 t2 t3 t4 t5 t5 t4 a a,R3 b c d e f x R2 R1

3) 机器代码： LD R1,i LD R2,#4 MUL R1,R1,R2 R1 R2 R3 i a[t1] x t1 t2 t3 t1 4 i x R1 LD R1,a(t1) R1 R2 R3 i a[t1] x t1 t2 t3 a[t1],t2 4 i R1 x R1 LD R2,#1 ADD R1,R1,R2 R1 R2 R3 i a[t1] x t1 t2 t3 t3 1 i x R1 ST x,R1 R1 R2 R3 i a[t1] x t1 t2 t3 t3 1 i x R1

4) 机器代码： LD R1,i LD R2,#4 MUL R1,R1,R2 R1 R2 R3 i a[t1] b[t2] c[t1] t1 t2 t3 t1 4 R1 LD R2,c(R1) R1 R2 R3 i a[t1] b[t2] c[t1] t1 t2 t3 t1 c[t1],t2 R2 R1 R2 LD R2,b(R2) R1 R2 R3 i a[t1] b[t2] c[t1] t1 t2 t3 t1 b[t2],t3 R2 R1 R2 ST a(R1),R2 R1 R2 R3 i a[t1] b[t2] c[t1] t1 t2 t3 t1 b[t2],t3 a[t1] R2 R1 R2

5) 机器代码： LD R1,i LD R2,bn MUL R1,R1,R2 R1 R2 R3 i bn t1 t1 i i bn,R2 R1 LD R2,#4 MUL R1,R1,R2 R1 R2 R3 i bn t1 t2 4 i bn R1 LD R3,k MUL R2,R2,R3 R1 R2 R3 i bn k t1 t2 t3 t2 t3 k i bn k,R3 R1 R2 ADD R1,R1,R2 R1 R2 R3 i bn k t1 t2 t3 t4 t4 t3 k i bn k,R3 R1 R2 R1 LD R2,b(R1) R1 R2 R3 i bn k t1 t2 t3 t4 t5 t4 b(R1),t5 k i bn k,R3 R1 R2 LD R1,cn MUL R1,R1,R3 R1 R2 R3 i bn cn k t1 t2 t3 t4 t5 t6 t6 t5 k i bn cn k,R3 R2 R1 LD R3,#4 MUL R1,R1,R3 R1 R2 R3 i bn cn k t1 t2 t3 t4 t5 t6 t7 t7 t5 4 i bn cn k R2 R1 LD R3,j MUL R3,R3,4 R1 R2 R3 i j bn cn k t1 t2 t3 t4 t5 t6 t7 t8 t7 t5 t8 i j bn cn k R2 R1 R3 ADD R1,R1,R3 R1 R2 R3 i j bn cn k t1 t2 t3 t4 t5 t6 t7 t8 t9 t9 t5 t8 i j bn cn k R2 R3 R1 LD R1,c(R1) R1 R2 R3 i j bn cn k t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t10 t5 t8 i j bn cn k R2 R3 R1 ST n,R2 R1 R2 R3 i j bn cn k n t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t10 t5 t8 i j bn cn k n R2 R3 R1 LD R2,i LD R3,an MUL R2,R2,R3 MUL R2,R2,#4 LD R3,j MUL R3,R3,#4 ADD R2,R2,R3 LD R3,n ADD R1,R1,R3 ST a(R2),R1 R1 R2 R3 i j bn cn k n t13 t14 t14 t13 n i j bn cn k n,R3 R2 R1 6) 机器代码： LD R1,q LD R2,0(R1) LD R3,p R1 R2 R3 q p t1 t2 t3 t4 q,t1 0(R1),t2 p,t3 q,R1 p,R3 R1 R2 R3 LD R2,#1 MUL R2,R2,#4 R1 R2 R3 q p t1 t2 t3 t4 q,t1 4,t4 p,t3 q,R1 p,R3 R1 R3 R2 ADD R3,R1,R2 R1 R2 R3 q p t1 t2 t3 t4 t5 q,t1 4,t4 t5 q,R1 p R1 R2 R3 ST q,R3 R1 R2 R3 q p t1 t2 t3 t4 t5 q,t1 4,t4 t5 q p R1 R2 R3 LD R1,p ADD R3,R1,R2 ST p,R3 R1 R2 R3 q p t1 t2 t3 t4 t5 t6 p 4,t4 t6 q p R2 R3

机器代码： LD R1,b LD R2,c MUL R1,R1,R2 R1 R2 a b c x t1 t2 t1 c a b c,R2 x R1 LD R2,a ADD R1,R1,R2 R1 R2 a b c x t1 t2 t2 a a,R2 b c x R1 ST x, R1 R1 R2 a b c x t1 t2 t2 a a,R2 b c x R1

2) 两个寄存器不够用，需要做溢出处理 3) 机器代码： LD R1,i LD R2,#4 MUL R1,R1,R2 R1 R2 i a[t1] x t1 t2 t3 t1 4 i x R1 LD R1,a(t1) R1 R2 i a[t1] x t1 t2 t3 a[t1],t2 4 i R1 x R1 LD R2,#1 ADD R1,R1,R2 R1 R2 i a[t1] x t1 t2 t3 t3 1 i x R1 ST x,R1 R1 R2 i a[t1] x t1 t2 t3 t3 1 i x R1

4） 机器代码： LD R1,i LD R2,#4 MUL R1,R1,R2 R1 R2 i a[t1] b[t2] c[t1] t1 t2 t3 t1 4 R1 LD R2,c(R1) R1 R2 i a[t1] b[t2] c[t1] t1 t2 t3 t1 c[t1],t2 R2 R1 R2 LD R2,b(R2) R1 R2 i a[t1] b[t2] c[t1] t1 t2 t3 t1 b[t2],t3 R2 R1 R2 ST a(R1),R2 R1 R2 i a[t1] b[t2] c[t1] t1 t2 t3 t1 b[t2],t3 a[t1] R2 R1 R2

5) 两个寄存器不够用，需要做溢出处理 6) 两个寄存器不够用，需要做溢出处理

(1)

(2) (3)

(1)

(2)

(3)