COMPUTER SCIENCE TRIPOS Part IB – 2012 – Paper 3
Compiler Construction (DJG)
(a) Define the following terms used when discussing a grammar:
(i) a non-terminal symbol [1 mark]
(ii) an ambiguous grammar [1 mark]
(iii) a production [1 mark]
(iv) a context-free grammar [2 marks]
(v) a regular grammar [2 marks]
(b) The following grammar defines a language where expressions are strings or
integers. A type error arises when an integer is added to a string.
Var -> x | y
Exp -> Var | 0 | 1 | “cat” | “dog” | Exp + Exp
S -> Var := Exp | S S
(i) Give a syntactically-correct sentence of the language that contains a type
error. [1 mark]
(ii) What phase (or pass) of a typical, simple compiler would detect such a type
error? Sketch the fragment of code that actually spots the error.
[3 marks]
(iii) Provide a modified grammar such that type errors are also syntax errors.
[3 marks]
(iv) Why is such a modified grammar generally impractical? [1 mark]
(c) Certain operators, such as logical and, which is commonly denoted with &&
use short-circuit evaluation.
(i) Define short-circuit evaluation. [2 marks]
(ii) Give two reasons why it is useful. [1 mark]
(iii) Describe the problem, and its solution, that arises when a short-circuit
operator is encountered during a simplistic compilation of a syntax tree to
stack machine code. [2 marks