Simple LR parser

In computer science, an simple LR or SLR parser will typically have more conflict states than an LALR parser. For real-world computer languages, an SLR parser is usually not adequate, but for student projects in a compiler class it is a good learning tool.

A grammar that has no conflicts reported by an SLR parser generator is an SLR grammar.

Algorithm

The SLR parsing algorithm

Initialize the stack with S
Read input symbol
while (true)
    if Action(top(stack), input) = S
         NS <- Goto(top(stack),input)
         push NS
         Read next symbol
    else if Action(top(stack), input) = Rk
         output k
         pop |RHS| of production k from stack
         NS <- Goto(top(stack), LHS_k)
         push NS
    else if Action(top(stack),input) = A
         output valid, return
    else
         output invalid, return

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'. However, the follow set of E is { $ } so the reduce actions r1 and r2 are only valid in the column for $. The result is the following conflict-less action and goto table:

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

Algorithm

Example

See also