1. Each of the following parts addresses a different aspect of compiling and carries the marks shown.

(a) Explain the constraints on a regular expression grammar compared to a context free language. 6 Marks

(b) Consider the following simple grammar:

E → E + E |
E ∗ E
(E) | x

Is the grammar suitable for SLR parsing? Explain how you worked this out. 13 Marks

(c) Differentiate between precedence and associativity in a grammar and explain their use in constructing a parser. 6 marks

2. These parts address code generation and optimisation.

(a) Outline how peephole optimisations work, using appropriate examples for each form of optimisation. 10 Marks

(b) Consider the following three address code:

1 accum :=  0
2  I :=  1
3  T1 :=  4 * I
4  T2 :=  addr(M) - 4
5  T3 :=  T2[T1]
6  T4 :=  addr(B) - 4
7  T5 :=  T4[T1]
8  T6 :=  T3*T5
9 accum :=  accum + T6
10 I := I + 1
11  if I≤20 goto (3)

Construct its flow graph and perform u-d chain dataflow analysis on it. 10 Marks How does natural loop identification work? Show with a suitable example. 5 Marks