Compiler Construction
It is desired to obtain an unambiguous context-free grammar G0 which generates
the same strings as the following grammar G with start symbol S.
S -> E
E -> ( E ) | [ E ] | E * E | a | b | c
( E ) -> ( + E )
[ E ] -> [ – E ]
Define a suitable G0
or explain why G already satisfies the criterion. [6 marks]
Write a context-free (Type 2) grammar which describes floating-point numbers of
the form [±]dd∗
[.d∗
][e[±]dd∗
] where d stands for decimal digit and d
∗
stands for zero
or more decimal digits. [· · ·] means that the enclosed item is optionally present in
the floating-point number. [7 marks]
Sketch a recursive descent parser for the following grammar H with start symbol S.
You should assume the existence of a routine lex() which sets variable token to
one of ‘1’, ‘2’, ‘(’, ‘)’, ‘-’ or eof.
P -> 1 | 2 | (E)
E -> P | E – P
S -> E eof
[7 marks]