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