Slr Parser Website Links For
Simple 		 

Information About

Slr Parser
  CATEGORIES ABOUT SIMPLE LR PARSER
   
parsing algorithms
   
SHOPPER'S DELIGHT
 
Shop For:  
Department
Price Minimum:
Price Maximum:
      




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



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