Simple LR Parser - Example

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:

	action		goto
state	1	$	E
0	s1		2
1	s1/r2	r2	3
2		acc
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 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:

symbol	S	E	1
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.leftHandSide; return (action in followSet(ruleSymbol)) }

for example, 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, 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:

	action		goto
state	1	$	E
0	s1		2
1	s1	r2	3
2		acc
3		r1