COMPUTER SCIENCE TRIPOS Part IB – 2021 – Paper 4
Compiler Construction (tgg22)
(a) Show that the following grammar for the language of balanced parenthesis is
ambiguous.
S → 
| (S)
| SS
[5 marks]
(b) An arithmetic expression such as x ∗ ((z ∗ u) + y) can be represented without
parenthesis in postfix notation as xzu ∗ y + ∗. This representation is ideal for
evaluation using a stack machine.
Below is a simple grammar for postfix expressions:
S → i
| SS+
| SS∗
The terminal i represents the lexical class of identifiers. Here is a DFA for the
LR(0) items of this grammar.
2 :
13 : S–>.i
11 : S–>.SS*
10 : S–>S.S*
7 : S–>.SS+
6 : S–>S.S+
1 : S’–>S.
1 :
12 : S–>i.
i
3 :
13 : S–>.i
11 : S–>.SS*
10 : S–>S.S*
9 : S–>SS.*
7 : S–>.SS+
6 : S–>S.S+
5 : S–>SS.+
S
0 :
13 : S–>.i
11 : S–>.SS*
7 : S–>.SS+
0 : S’–>.S
S
i
i
S
4 :
4 : S–>SS+.
+
5 :
8 : S–>SS*.
*
(i) Using the DFA, construct the SLR(1) ACT ION and GOT O tables for this
grammar. Explain your work. [6 marks]
(ii) Show a trace of a parsing of w = iii ∗ i + ∗. Justify every step. [9 marks]