COMPUTER SCIENCE TRIPOS Part IB – 2016 – Paper 3
Compiler Construction (TGG)
Consider writing a compiler for a simple language of expressions given by the following
grammar,
e ::= n (integer)
| ? (read integer input from user)
| e + e (addition)
| e − e (subtraction)
| e ∗ e (multiplication)
| (e, e) (pair)
| fst e (first projection)
| snd e (second projection)
(a) Describe the tasks that should be carried in implementing a front end for this
language and any difficulties that might be encountered. [5 marks]
(b) Suppose that the target virtual machine is stack-oriented and that the stack
elements are integer values, and addresses can be stored as integers. Explain
which other features are required in such a virtual machine. Invent a simple
language of instructions for such a machine and show how it would be used to
implement each of the expressions. [10 marks]
(c) Suppose that the following rules are proposed as possible optimizations to be
implemented in your compiler.
expression simplifies to expression
(fst e, snd e) → e
fst (e1, e2) → e1
snd (e1, e2) → e2
Describe how you could implement these rules so that the simplifications are
made only when the program’s semantics is correctly preserved. [5 marks