Constructions of SLR parse tables
Introduction:
An SLR parse table has a DFA as its core. Constructing this DFA from the grammar is similar to constructing a DFA from a regular expression; we first construct an NFA and then convert this into a DFA. Before we construct the NFA, we extend the grammar with a new starting production. Doing this to grammar 3.25.
The next step is to make an NFA for each production. This is done exactly like in section 2.4, treating both terminals and non-terminals as alphabet symbols. The accepting state of each NFA is labelled with the number of the corresponding production. The result is shown in figure 3.26. Note that we have used the optimized construction for e (the empty production).
The NFAs in figure 3.26 make transitions both on terminals and non-terminals. Transitions by terminal correspond to shift actions and transitions on non-terminals correspond to go actions. A go action happens after a reduction, whereby some elements of the stack (corresponding to the right-hand side of a production) are replaced by a nonterminal (corresponding to the left-hand side of that production). However, before we can reduce on a nonterminal, the symbols that form the right hand side must be on the stack. So we prepare for a later transition on a nonterminal by allowing transitions that, eventually, will leave the symbols forming right-hand side of the production on the stack, so we can reduce these to the nonterminal and then make a transition in this.
