• Introduction
• 1. 1.Introduction
• 2. 2.A Simple Syntax-Directed Translator
• 3. 3.Lexical Analysis
• 4. 4.Syntax Analysis
• 5. 5.Syntax-Directed Translation
• 6. 6.Intermediate-Code Generation
• 7. 7.Run-Time Environments
• 8. 8.Code Generation
• 9. 12.InterProcedural Analysis
• Published with GitBook

# Exercises for Section 8.4

### 8.4.1

Figure 8.10 is a simple matrix-multiplication program.

1. 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.
2. Construct the flow graph for your code from (a).
3. 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

`````` 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)
``````
2. flow graph

3. 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.

1. Translate the program into three-address statements of the type we have been using in this section. Assume integers require 4 bytes.
2. Construct the flow graph for your code from (a).
3. 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

`````` 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)
``````
2. flow graph

3. 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)
``````