Chapter 5
5.1.3 Exercises for Section 5.1
Exercise 5.1.1 : For the SDD of Fig. 5.1, give annotated parse trees for the
following expressions:
a) (3 + 4) * (5 + 6) n.
b) 1 * 2 * 3 * (4 + 5) n.
c) (9 + 8 * (7 + 6) + 5) * 4 n.
Exercise 5.1.2 : Extend the SDD of Fig. 5.4 to handle expressions as in Fig. 5.1.
| 1) | L -> En | L.val = E.val |
| 2) | E -> TE' | E'.inh = T.val E.val = E'.syn |
| 3) | E' -> +TE_1' | E_1'.inh = E'.inh + T.val E'.syn = E_1'.syn |
| 4) | E' -> ε | E'.syn = E'.inh |
| 5) | T -> FT' | T'.inh = F.val T.val = T'.syn |
| 6) | T' -> *FT_1' | T_1'.inh = T'.inh * F.val T'.syn = T_1'.syn |
| 7) | T' -> ε | T'.syn = T'.inh |
| 8) | F -> (E) | F.val = E.val |
| 9) | F -> digit | F.val = digit.lexval |
Exercise 5.1.3 : Repeat Exercise 5.1.1, using your SDD from Exercise 5.1.2.
Exercises for Section 6.1
Exercise 6.1.1 : Construct the DAG for the expression
((x + y) - ((x + y) * (x -y))) + ((x + y) * (x - y))
Exercise 6.1.2 : Construct the DAG and identify the value numbers for the subexpressions of the following expressions, assuming + associates from the left.
a) a + b + (a + b).
b) a + b + a + b.
c) a + a + a + a + a + (a + a + a + a))
a)
| 1 | id | a | |
| 2 | id | b | |
| 3 | + | 1 | 2 |
| 4 | + | 3 | 3 |
b)
| 1 | id | a | |
| 2 | id | b | |
| 3 | + | 1 | 2 |
| 4 | + | 3 | 1 |
| 5 | + | 4 | 2 |
c)
| 1 | id | a | |
| 2 | + | 1 | 1 |
| 3 | + | 2 | 1 |
| 4 | + | 3 | 1 |
| 5 | + | 3 | 4 |
| 6 | + | 2 | 5 |
6.2.5 Exercises for Section 6.2
Exercise 6.2.1 : Translate the arithmetic expression a + -(b + c) into:
a) A syntax tree.
b) Quadruples.
c) Triples.
d) Indirect triples.
a)
b)
| op | arg1 | arg2 | result | |
|---|---|---|---|---|
| 0 | + | b | c | t1 |
| 1 | minus | t1 | t2 | |
| 2 | + | a | t2 | t3 |
c)
| op | arg1 | arg2 | |
|---|---|---|---|
| 0 | + | b | c |
| 1 | minus | (0) | |
| 2 | + | a | (1) |
| instruction | |
|---|---|
| 0 | (0) |
| 1 | (1) |
| 2 | (2) |
Exercise 6.2.2 : Repeat Exercise 6.2.1 for the following assignment statements:
i. a = b[i] + c[j].
ii. a[i] = b*c - b*d.
iii. x = f(y+1) + 2.
iv. x = *p + &y.
1
0) =[] b i t1
1) =[] c j t2
2) + t1 t2 t3
3) = t3 a
0) =[] b i
1) =[] c j
2) + (0) (1)
3) = a (2)
Instructions
( 0）
(1）
(2）
(3）
2
0) * b c t1
1) * b d t2
2) - t1 t2 t3
3) []= a i t4
4) = t3 t4
0) * b c
1) * b d
2) - (0) (1)
3) []= a i
4) = (3) (2)
0)
1)
2)
3)
4)
3
0) + y 1 t1
1) param t1
2) call f 1 t2
3) + t2 2 t3
4) = t3 x
0) + y 1
1) param (0)
2) call f 1
3) + (2) 2
4) = x (3)
0)
1)
2)
3)
4)
Exercise 6.2.3 : Show how to transform a three-address code sequence into one in which each dened variable gets a unique variable name.
3adddress code sequence can be transformed into SSA in which each defines variable gets a unique variable name.
Static single-assignment form (SSA) is an intermediate representation that facilitates certain code optimizations. The all assignments in SSA are to variables with distinct names; hence the term static single-assignment.
6.3.7 Exercises for Section 6.3
Exercise 6.3.1 : Determine the types and relative addresses for the identifers in the following sequence of declarations:
float x;
record { float x; float y; } p;
record { int tag; float x; float y; } q;
S -> {top = new Evn(); offset = 0;}
D
D -> T id; {top.put(id.lexeme, T.type, offset);
offset += T.width}
D1
D -> ε
T -> int {T.type = interget; T.width = 4;}
T -> float {T.type = float; T.width = 8;}
T -> record '{'
{Evn.push(top), top = new Evn();
Stack.push(offset), offset = 0;}
D '}' {T.type = record(top); T.width = offset;
top = Evn.top(); offset = Stack.pop();}
line id type offset Evn
1) x float 0 1
2) x float 0 2
2) y float 8 2
2) p record() 8 1
3) tag int 0 3
3) x float 4 3
3) y float 12 3
3) q record() 24 1
Exercise 6.3.2 : Extend the handling of eld names in Fig. 6.18 to classes and single-inheritance class hierarchies.
a) Give an implementation of class Env that allows linked symbol tables, so that a subclass can either redene a eld name or refer directly to a eld name in a superclass.
b) Give a translation scheme that allocates a contiguous data area for the elds in a class, including inherited elds. Inherited elds must maintain the relative addresses they were assigned in the layout for the superclass.
6.4.5 Exercises for Section 6.4
Exercise 6.4.1 : Add to the translation of Fig. 6.19 rules for the following productions:
a) E ! E1 E2.
b) E ! + E1 (unary plus).
a)
E -> E1 * E2 { E.addr = new Temp();
E.code = E1.code || E2.code ||
gen(E.addr '=' E1.addr '*' E2.addr); }
| +E1 { E.addr = E1.addr;
E.code = E1.code; }
Exercise 6.4.2 : Repeat Exercise 6.4.1 for the incremental translation of Fig. 6.20.
E -> E1 * E2 { E.addr = new Temp();
gen(E.addr '=' E1.addr '*' E2.addr; }
| +E1 { E.addr = E1.addr; }
Exercise 6.4.3 : Use the translation of Fig. 6.22 to translate the following
assignments:
a) x = a[i] + b[j].
b) x = a[i][j] + b[i][j].
! c) x = a[b[i][j]][c[k]].
a)
t_1 = i * awidth
t_2 = a[t_1]
t_3 = j * bwidth
t_4 = b[t_3]
t_5 = t_2 + t_4
x = t_5
b)
t_1 = i * ai_width
t_2 = j * aj_width
t_3 = t_1 + t_2
t_4 = a[t_3]
t_5 = i * bi_width
t_6 = j * bj_width
t_7 = t_5 + t_6
t_8 = b[t_7]
t_9 = t_4 + t_8
x = t_9
Exercise 6.4.4 : Revise the translation of Fig. 6.22 for array references of the
Fortran style, that is, id[E1; E2; : : : ; En] for an n-dimensional array.
a.type = array(i, array(j, w))
a.type.length = i
a.type.elem = array(j, w)
Exercise 6.4.5 : Generalize formula (6.7) to multidimensional arrays, and indicate what values can be stored in the symbol table and used to compute o sets. Consider the following cases:
a) An array A of two dimensions, in row-major form. The rst dimension has indexes running from l1 to h1, and the second dimension has indexes from l2 to h2. The width of a single array element is w.
3. A[i_1]]…[i_k] = base +
(
(i_1 - l_1) * n_2 * … * n_k +
… +
(i_k-1 - l_k-1) * n_k +
(i_k - l_k)
) * w
4. A[i_1]]…[i_k] = base +
(
(i_1 - l_1) +
(i_2 - l_2) * n_1 +
… +
(i_k - l_k) * n_k-1 * n_k-2 * … * n_1
) * w
No comments:
Post a Comment