COMPUTER SCIENCE TRIPOS Part IB – 2018 – Paper 4
Compiler Construction (TGG)
This question covers a wide variety of topics in the interdisciplinary subject of
Compiler Construction.
(a) What is the difference between lexical analysis and parsing? [2 marks]
(b) Give an example of an ambiguous context-free grammar together with a
demonstration that it is indeed ambiguous. [3 marks]
(c) In the context of functional programming, describe the concept of a closure and
how it is used. [3 marks]
(d) Can any recursive function be transformed into a tail-recursive function? Briefly
explain you answer. [3 marks]
(e) Describe one advantage and one disadvantage for using reference counting as a
technique for memory management. [2 marks]
(f ) For what kinds of programming languages might you employ static links on the
stack? Explain your answer. [3 marks]
(g) Consider an optimisation that replaces any expression of the form
0 × e
with 0, where e is an arbitrary expression. Why might this rule be useful in a
compiler’s optimisation phase? Is it always correct? [4 marks]