CS3 Compiler techniques June 1995

1. (a) Consider the following fragment of a grammar. By generating parser tables, using the SLR technique, decide whether it is SLR. Terminal symbols are shown in bold face, non-terminals in italics.

S → L=R
S → R
L → ∗R
L → id
R → L

9 marks

(b) Using the same example explain the concept of lookahead in LALR parsing. 8 marks

(c) Explain the structure of a compiler in terms of its phases. How do the needs of:

i. portable compilers; ii. high level optimising compilers;

affect this structure? 8 marks 2. (a) Using the fragment of three address code below, show how a flow graph can

be obtained and how a loop can be identified. All statements use the same notation as that used throughout the lectures. 10 marks

(1) RES := 0
(2) I := 1
(3) T_{1} := 4 ∗ I
(4) T_{2} := addr(A) − 4
(5) T_{3} := T_{2}[T_{1}]
(6) T_{4} := addr(B) − 4
(7) T_{5} := T_{4}[T_{1}]
(8) T_{6} := T_{3} ∗ T_{5}
(9) RES := RES + T_{6}
(10) I := I + 1
(11) if I ≤ 20 goto (3)

(b) Using the flow graph obtained above or another suitable example, explain the optimisations known as:

i. code motion from loops; 5 marks ii. strength reduction; 5 marks iii. induction variable elimination; 5 marks 3. Consider the example of three address code below. All statements use the same

notation as that used throughout the lectures.

(1) S_{1} := 2 ∗ L
(2) S_{2} := addr(K) − 2
(3) S_{3} := S_{2}[S_{1}]
(4) S_{4} := 2 ∗ L
(5) S_{5} := addr(J) − 2
(6) S_{6} := S_{5}[S_{4}]
(7) S_{7} := S_{3} ∗ S_{6}
(8) S_{8} := T OT + S_{6}
(9) T OT := S_{8}
(10) S_{9} := L + 1
(11) L := S_{9}
(12) if L ≤ 10 goto (1)

(a) Show how adirected acyclic graph or DAG is constructed for this code. 15 marks

(b) Explain how DAG construction identifies common sub-expressions, using any examples in the code given above. 5 marks

(c) What optimisations might result and what assumptions underly them? 5 marks