Compiler Construction
Describe what is meant by a phrase structured grammar and a context free grammar.
[3 marks]
Describe an algorithm to calculate the set LT (P) of all terminal symbols that can
start a string derived from the non-terminal P using one or more productions of a
given context free grammar. Illustrate your answer by calculating LT sets for the
following grammar:
S -> U V
V -> + U V | 
U -> X W
W -> * X W | 
X -> ( S ) | n [6 marks]
Describe an algorithm to calculate the set FOLLOW(P) of terminal and non-terminal
symbols for a given context free grammar, where
*
FOLLOW(P) = { X | S => … P X … }
i.e. all symbols that can follow P in a sentential form derived from the sentence
symbol S. Illustrate your answer by calculating the FOLLOW sets for the grammar
given above. [6 marks]
Outline possible ways in which the space used by the Action and Goto matrices of
an SLR(1) parser can be reduced. [5 marks]