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
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:

See also

Full article ▸

 related documents Binary function Divisor Logical disjunction Lagrange's theorem (group theory) Complement (set theory) Chomsky normal form Lipschitz continuity Greedy algorithm Uncountable set Nash embedding theorem Metrization theorem Ordered field Graded algebra De Moivre's formula Amicable number Kernel (category theory) Parity (mathematics) Goldbach's weak conjecture Topological ring Identity element Regular language Twin prime conjecture Euphoria (programming language) Box-Muller transform Normal subgroup Separated sets PSPACE-complete Logarithmic integral function Magma (algebra) Compiler-compiler