编译原理（紫龙书）中文第2版习题答案
- 前言
- Exercises for Section 1.1
- Exercises for Section 1.3
- Exercises for Section 1.6
- Exercises for Section 2.2
- Exercises for Section 2.3
- Exercises for Section 2.4
- Exercises for Section 2.6
- Exercises for Section 2.8
- 第2章要点
- Exercises for Section 3.1
- Exercises for Section 3.3
- Exercises for Section 3.4
- Exercises for Section 3.5
- Exercises for Section 3.6
- Exercises for Section 3.7
- Exercises for Section 3.8
- Exercises for Section 3.9
- 第3章要点
- Exercises for Section 4.2
- Exercises for Section 4.3
- Exercises for Section 4.4
- Exercises for Section 4.5
- Exercises for Section 4.6
- Exercises for Section 4.7
- 第4章要点
- Exercises for Section 5.1
- Exercises for Section 5.2
- Exercises for Section 5.3
- Exercises for Section 5.4
- Exercises for Section 5.5
- Exercises for Section 6.1
- Exercises for Section 6.2
- Exercises for Section 6.3
- Exercises for Section 6.4
- Exercises for Section 6.5
- Exercises for Section 6.6
- Exercises for Section 6.7
- Exercises for Section 7.2
- Exercises for Section 7.3
- Exercises for Section 7.4
- Exercises for Section 7.5
- Exercises for Section 7.6
- Exercises for Section 7.7
- Exercises for Section 8.2
- Exercises for Section 8.3
- Exercises for Section 8.4
- Exercises for Section 8.5
- Exercises for Section 12.3
Exercises for Section 8.4
8.4.1
Figure 8.10 is a simple matrix-multiplication program.
- Translate the program into three-address statements of the type we have been using in this section. Assume the matrix entries are numbers that require 8 bytes, and that matrices are stored in row-major order.
- Construct the flow graph for your code from (a).
- Identify the loops in your flow graph from (b).
for (i=O; i<n; i++)
for (j=O; j<n; j++)
c[i][j] = 0.0;
for (i=O; i<n; i++)
for (j=O; j<n; j++)
for (k=O; k<n; k++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];Figure 8.10: A matrix-multiplication algorithm
Answer
-
three-address statements
B1 1) i = 0 B2 2) if i >= n goto(13) B3 3) j = 0 B4 4) if j >= n goto(11) B5 5） t1 = n * i 6) t2 = t1 + j 7) t3 = t2 * 8 8) c[t3] = 0.0 9) j = j + 1 10) goto(4) B6 11) i = i + 1 12) goto(2) B7 13) i = 0 B8 14) if i >= n goto(40) B9 15) j = 0 B10 16) if j >= n goto(38) B11 17) k = 0 B12 18) if k >= n goto(36) B13 19) t4 = n * i 20) t5 = t4 + j 21) t6 = t5 * 8 22) t7 = c[t6] 23) t8 = n * i 24) t9 = t8 + k 25) t10 = t9 * 8 26) t11 = a[t10] 27) t12 = n * k 28) t13 = t12 + j 29) t14 = t13 * 8 30) t15 = b[t14] 31) t16 = t11 * t15 32) t17 = t7 + t16 33) c[t6] = t17 34) k = k + 1 35) goto(18) B14 36) j = j + 1 37) goto(16) B15 38) i = i + 1 39) goto(14) -
flow graph
-
loops
- {B2, B3, B4, B6}
- {B4, B5}
- {B8, B9, B10, B15}
- {B10, B11, B12, B14}
- {B12, B13}
8.4.2
Figure 8.11 is code to count the number of primes from 2 to n, using the sieve method on a suitably large array a. That is, a[i] is TRUE at the end only if there is no prime i^0.5 or less that evenly divides i. We initialize all a[i] to TRUE and then set a[j] to FALSE if we find a divisor of j.
- Translate the program into three-address statements of the type we have been using in this section. Assume integers require 4 bytes.
- Construct the flow graph for your code from (a).
- Identify the loops in your flow graph from (b).
for (i=2; i<=n; i++)
a[i] = TRUE;
count = 0;
s = sqrt(n);
for (i=2; i<=s; i++)
if (a[i]) 1* i has been found to be a prime *1 {
count++ ;
for (j=2*i; j<=n; j = j+i)
a[j] = FALSE; 1* no multiple of i is a prime *1
}Figure 8.11: Code to sieve for primes
Answer
-
three-address statements
B1 1) i = 2 B2 2) if i > n goto(7) B3 3) t1 = i * 4 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 = i * 4 12) ifFalse a[t2] goto(20) B7 13) count = count + 1 14) j = 2 * i B8 15) if j > n goto(20) B9 16) t3 = j * 4 17) a[t3] = FALSE 18） j = j + i 19) goto(15) B10 20) i = i + 1 21) goto(10) -
flow graph
-
loops
- {B2, B3}
- {B5, B6, B10}
- {B5, B6, B7, B8, B10}
- {B8, B9}
Note
1. A demo for algorithm 8.7: Determining the liveness and next-use information foreach statement in a basic block.
init:
three-address statements symbol table
symbol live nextuse
i) a = b + c [a, true, null]
j) t = a + b [b, true, null]
[c, true, null]
[t, true, null]
step1:
Attach to statement j the information currently found in the symbol table
symbol live nextuse
i) a = b + c [a, true, null]
j) t = a + b [t, true, null] [b, true, null]
[a, true, null] [c, true, null]
[b, true, null] [t, true, null]
step2:
In the symbol table, set x.live = false and
x.nextuse = null
symbol live nextuse
i) a = b + c [a, true, null]
j) t = a + b [t, true, null] [b, true, null]
[a, true, null] [c, true, null]
[b, true, null] [t, false, null]
step3:
In the symbol table, set a.live = true, b.live = true and
a.nextuse = j, b.nextuse = j
symbol live nextuse
i) a = b + c [a, true, j ]
j) t = a + b [t, true, null] [b, true, j ]
[a, true, null] [c, true, null]
[b, true, null] [t, false, null]
step4:
symbol live nextuse
i) a = b + c [a, true, j ] [a, true, j ]
[b, true, j ] [b, true, j ]
[c, true, null] [c, true, null]
[t, false, null]
j) t = a + b [t, true, null]
[a, true, null]
[b, true, null]
step5:
symbol live nextuse
i) a = b + c [a, true, j ] [a, false, null]
[b, true, j ] [b, true, j ]
[c, true, null] [c, true, null]
[t, false, null]
j) t = a + b [t, true, null]
[a, true, null]
[b, true, null]
step6:
symbol live nextuse
i) a = b + c [a, true, j ] [a, false, null]
[b, true, j ] [b, true, i ]
[c, true, null] [c, true, i ]
[t, false, null]
j) t = a + b [t, true, null]
[a, true, null]
[b, true, null]
2. Three ways to generate code for "for(i = 0; i < n ; i++)" statement
1) i = 0
2) if i >= n goto(9)
3)
...
7) i = i + 1
8) if i < n goto(3)
9)
1) i = 0
2) goto(8)
3)
...
7) i = i + 1
8) if i < n goto(3)
9)
1) i= 0
2) if i >= n goto(9)
...
7) i = i + 1
8) goto(2)
9)更多可参考 RednaxelaFX 的 对C语义的for循环的基本代码生成模式