SLR(1) Parsers

$SLR(1)$ stands for $Simple LR(1)$; this is basically a method of adding lookahead to $LR(0)$ parsers as simply as possible.

The technique is based on the following observation:

If we are in a DFA state containing the item: $A\, \rightarrow\, \alpha {}_{\triangle}$ then a possible action will be to reduce by this rule. Doing this reduction would involve:

going from a sentential form that looks like:	$\ldots \alpha {}_{\triangle} \ldots$
to one that looks like:	$\ldots A {}_{\triangle} \ldots$

By looking at examples, we can see that the symbol immediately to the right of the marker in a sentential form should correspond to the next input symbol: we can rephrase this as: the symbol following $A$ should be the next symbol in the input.

Since we already have a method of characterising the set of symbols which can follow a non-terminal in a sentential form, we can formulate the $SLR(1)$ reduction rule:

• Reduce by the rule $A\, \rightarrow\, \alpha$ only if the current state contains $A\, \rightarrow\, \alpha {}_{\triangle}$ and the next input symbol is in $FOLLOW(A)$

This provides a quick and easy way to incorporate lookahead into the parser; however, there are many languages which are not $SLR(1)$.