LR(1) derivation example
Grammar
E -> a
E -> b
E -> c
E -> E - E
Input
a - b - c
STEP 1
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} |
Input : a - b - c <eof>
Action : shift
STEP 2
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} | a |
Input : - b - c <eof>
Action : goto
STEP 3
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} | a | |
Input : - b - c <eof>
Action : reduce E -> a . {<eof>, -}
STEP 4
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} | E
└── a |
Input : - b - c <eof>
Action : goto
STEP 5
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} | E
└── a | |
Input : - b - c <eof>
Action : shift
STEP 6
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} | E
└── a | | - |
Input : b - c <eof>
Action : goto
STEP 7
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} | E
└── a | | - | E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -}
E -> E - . E {<eof>, -} |
Input : b - c <eof>
Action : shift
STEP 8
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} | E
└── a | | - | E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -}
E -> E - . E {<eof>, -} | b |
Input : - c <eof>
Action : goto
STEP 9
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} | E
└── a | | - | E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -}
E -> E - . E {<eof>, -} | b | |
Input : - c <eof>
Action : reduce E -> b . {<eof>, -}
STEP 10
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} | E
└── a | | - | E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -}
E -> E - . E {<eof>, -} | E
└── b |
Input : - c <eof>
Action : goto
STEP 11
Stack :
E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -} | E
└── a | | - | E -> . E - E {<eof>, -}
E -> . a {<eof>, -}
E -> . b {<eof>, -}
E -> . c {<eof>, -}
E -> E - . E {<eof>, -} | E
└── b | E -> E . - E {<eof>, -}
E -> E - E . {<eof>, -} |
Input : - c <eof>
Action : conflict shift/reduce
First, Follow, Nullable sets
first (E) = {a, b, c}
follow (E) = {-}
nullable (E) = false
first (-) = {-}
follow (-) = {a, b, c}
nullable (-) = false
first (a) = {a}
follow (a) = {-}
nullable (a) = false
first (b) = {b}
follow (b) = {-}
nullable (b) = false
first (c) = {c}
follow (c) = {-}
nullable (c) = false
Automaton
The example on this page is auto-generated with dOvs teaching LR parser generator tool. The tool and the webpage is maintained by Aslan Askarov.
