Simple LR parser

From Wikipedia, the free encyclopedia

In computer science, 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 (see LL parser for a definition of follow set). Such a parser can prevent certain shift-reduce and reduce-reduce conflicts (see LR parser) 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.

[edit] 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	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'. 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	s1	r2	3
2		acc
3		r1

[edit] Algorithm

The SLR parsing algorithm

1 Initialize the stack with S
2 Read input symbol
3 While true, do:
3.1 if Action(top(stack), input) = S
         NS <- Goto(top(stack),input)
         push NS
         Read next symbol
3.2 else if Action(top(stack), input) = Rk
         output k
         pop |RHS| of production k from stack
         NS <- Goto(top(stack), LHS_k)
         push NS
3.3 else if Action(top(stack),input) = A
         output valid, return
    else
         output invalid, return