SLR Parsing

SLR parser

A Simple LR parser or SLR parser is an LR parser for which the parsing tables are generated as for an LR(0) parser except that it only performs a reduction with a grammar rule A → w if the next symbol on the input stream is in the follow set of A . Such a parser can prevent certain shift-reduce and reduce-reduce conflicts that occur in LR(0) parsers and it can therefore deal with more grammars. However, it still cannot parse all grammars that can be parsed by an LR(1) parser. A grammar that can be parsed by an SLR parser is called a SLR grammar.

Example

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

(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	s2/r2	r2	3
2		acc
3	r1	r1

As can be observed there is a shift-reduce conflict for state 1 and terminal '1'. However, the follow set of E is { $ } so the reduce actions r1 and r2 are only valid in the column for $. The result are the following conflict-less action and goto table:

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