Editing Simple LR parser (section)

== Example ==
A grammar that can be parsed by an SLR parser but not by an LR(0) parser is the following:

: (0) S → E
: (1) E → 1 E
: (2) E → 1

Constructing the action and goto table as is done for LR(0) parsers would give the following item sets and tables:

;Item set 0
: S → • E
: + E → • 1 E
: + E → • 1

;Item set 1
: E → 1 • E
: E → 1 •
: + E → • 1 E
: + E → • 1

;Item set 2
: S → E •

;Item set 3
: E → 1 E •

The action and goto tables:

{| class="wikitable"
|- align="center"
! || colspan="2" |''action''||''goto''
|- align="center"
! ''state''
!1||$||E
|- align="center"
!0
|s1||||2
|- align="center"
!1
|s1/r2||r2||3
|- align="center"
!2
|||acc||
|- align="center"
!3
|r1||r1||
|}

As can be observed there is a shift-reduce conflict for state 1 and terminal '1'. This occurs because, when the action table for an LR(0) parser is created, reduce actions are inserted on a per-row basis. However, by using a follow set, reduce actions can be added with finer granularity. The follow set for this grammar:
{| class="wikitable"
|- align="center"
! symbol
|S||E||1
|- align="center"
! following
|$||$||1,$
|}

A reduce only needs to be added to a particular action column if that action is in the follow set associated with that reduce. This algorithm describes whether a reduce action must be added to an action column:

 function mustBeAdded(reduceAction, action) {
     ruleNumber = reduceAction.value;
     ruleSymbol = rules[ruleNumber].leftHandSide;
     return (action in followSet(ruleSymbol))
 }

for example, {{code|mustBeAdded(r2, "1")}} is false, because the left hand side of rule 2 is "E", and 1 is not in E's follow set.
Contrariwise, {{code|mustBeAdded(r2, "$")}} is true, because "$" is in E's follow set.

By using mustBeAdded on each reduce action in the action table, the result is a conflict-free action table:

{| class="wikitable"
|- align="center"
! || colspan="2" |''action''||''goto''
|- align="center"
! ''state''
!1||$||E
|- align="center"
!0
|s1||||2
|- align="center"
!1
|s1||r2||3
|- align="center"
!2
|||acc||
|- align="center"
!3
|||r1||
|}