2000 Paper 4 Question 4 Compiler Construction \

Consider the grammar S -> E E -> T + E E -> T T -> x where S is the starting symbol, is a special token marking end of input and x is a terminal. Explain and find the left, right and follow sets for all non-terminals in the grammar. [5 marks] Suppose that an SLR parser for this grammar is required. One stage on the way to constructing the parsing tables is to create the characteristic finite state machine (sometimes known as the LR(0) states). Do this, explaining your working clearly. You do not need to complete the SLR parsing tables. [10 marks] Now, assuming that the parsing tables have been constructed, show what values will be placed on a stack and comment about internal state while an SLR parser using this grammar processes the input text x+x+x. [5 marks]