Handle-recognising DFAs and LR(0) Parsers

Using these idea, we are ready to construct a handle-recognising DFA. DFA states are sets of items; making a transition in the DFA corresponds to moving the marker one place to the right in an item.

We make things a little easier if we introduce a production rule of the form $S'\, \rightarrow\, S$ to the grammar, where $S$ is the start symbol. Whenever we reduce by this rule, we know that we are finished. (A grammar which has had this rule added is called an augmented grammar).

Since our new start symbol is now $S'$, the "goal" of the parse will be to recognise an $S$ and reduce this to $S'$; this is represented by the $LR(0)$ item: $S'\, \rightarrow\, {}_{\triangle} S$. This item is called the initial item.