Examples from wikipedia
LL(1)
grammar
S -> F
S -> ( S + F )
F -> a
input
( a + a )
parsing steps
S -> "(" S "+" F ")"
-> ( "F" + F )
-> ( "a" + F )
-> ( a + "a" )
LR(0)
grammar
(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1
input
1 + 1
parsing steps
need to build a parser table and traverse through states.
LR(1)
grammar
S’ -> S S
S -> C C
C -> c C | d
input
cd
parsing steps
large table
LALR
grammar
A -> C x A | ε
B -> x C y | x C
C -> x B x | z
input
xxzxx
parsing steps
traverse large parser table
You may also want to have a look at
- Parsing Simulator tool
- antlr works – >download<
- Parser table generation from ocw mit
- From parsing to code genration ocw mit
- additional examples