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

[edit] 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