COMPUTER SCIENCE TRIPOS Part IB – 2022 – Paper 4
Compiler Construction (tgg22)
This question concerns constructing LL(1) parsers from context-free grammars.
(a) Suppose we have a grammar that contains these productions.
S → if E then S else S end
S → if E then S end
Note that these productions have a shared initial segment. Explain how this
prevents us from automatically generating an LL(1) parser directly from this
grammar. [2 marks]
(b) Rewrite the productions from Part (a) so that they could be suitable as input
to an LL(1) parser generator. [4 marks]
(c) Eliminate the shared initial segments from these grammar productions.
A → aAbCeDg
A → aAbCd
B → eDgEf
[5 marks]
(d) Give a general method for eliminating shared initial segments from a grammar.
[5 marks]
(e) Argue carefully that the grammar produced by your method generates the same
language as the original grammar. [4 marks