# Simple LR parser

 related topics {math, number, function} {style, bgcolor, rowspan} {rate, high, increase} {school, student, university}

An 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
while (true)
if Action(top(stack), input) = S
NS <- Goto(top(stack),input)
push NS
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: