LR(1) derivation example
Grammar
E -> E - F
E -> F
F -> a
F -> b
F -> c
Input
a - b - c
STEP 1
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} |
Input : a - b - c <eof>
Action : shift
STEP 2
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | a |
Input : - b - c <eof>
Action : goto
STEP 3
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | a | |
Input : - b - c <eof>
Action : reduce F -> a . {<eof>, -}
STEP 4
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | F
└── a |
Input : - b - c <eof>
Action : goto
STEP 5
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | F
└── a | |
Input : - b - c <eof>
Action : reduce E -> F . {<eof>, -}
STEP 6
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
└── F
└── a |
Input : - b - c <eof>
Action : goto
STEP 7
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
└── F
└── a | |
Input : - b - c <eof>
Action : shift
STEP 8
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
└── F
└── a | | - |
Input : b - c <eof>
Action : goto
STEP 9
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
└── F
└── a | | - | E -> E - . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} |
Input : b - c <eof>
Action : shift
STEP 10
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
└── F
└── a | | - | E -> E - . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | b |
Input : - c <eof>
Action : goto
STEP 11
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
└── F
└── a | | - | E -> E - . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | b | |
Input : - c <eof>
Action : reduce F -> b . {<eof>, -}
STEP 12
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
└── F
└── a | | - | E -> E - . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | F
└── b |
Input : - c <eof>
Action : goto
STEP 13
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
└── F
└── a | | - | E -> E - . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | F
└── b | |
Input : - c <eof>
Action : reduce E -> E - F . {<eof>, -}
STEP 14
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
├── E
│ └── F
│ └── a
├── -
└── F
└── b |
Input : - c <eof>
Action : goto
STEP 15
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
├── E
│ └── F
│ └── a
├── -
└── F
└── b | |
Input : - c <eof>
Action : shift
STEP 16
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
├── E
│ └── F
│ └── a
├── -
└── F
└── b | | - |
Input : c <eof>
Action : goto
STEP 17
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
├── E
│ └── F
│ └── a
├── -
└── F
└── b | | - | E -> E - . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} |
Input : c <eof>
Action : shift
STEP 18
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
├── E
│ └── F
│ └── a
├── -
└── F
└── b | | - | E -> E - . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | c |
Input : <eof>
Action : goto
STEP 19
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
├── E
│ └── F
│ └── a
├── -
└── F
└── b | | - | E -> E - . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | c | |
Input : <eof>
Action : reduce F -> c . {<eof>, -}
STEP 20
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
├── E
│ └── F
│ └── a
├── -
└── F
└── b | | - | E -> E - . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | F
└── c |
Input : <eof>
Action : goto
STEP 21
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
├── E
│ └── F
│ └── a
├── -
└── F
└── b | | - | E -> E - . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | F
└── c | |
Input : <eof>
Action : reduce E -> E - F . {<eof>, -}
STEP 22
Stack :
E -> . E - F {<eof>, -}
E -> . F {<eof>, -}
F -> . a {<eof>, -}
F -> . b {<eof>, -}
F -> . c {<eof>, -} | E
├── E
│ ├── E
│ │ └── F
│ │ └── a
│ ├── -
│ └── F
│ └── b
├── -
└── F
└── c |
Input : <eof>
Action : accept
E
├── E
│ ├── E
│ │ └── F
│ │ └── a
│ ├── -
│ └── F
│ └── b
├── -
└── F
└── c
First, Follow, Nullable sets
first (E) = {a, b, c}
follow (E) = {-}
nullable (E) = false
first (F) = {a, b, c}
follow (F) = {-}
nullable (F) = 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.
