LR(1) derivation example
Grammar
E -> T
E -> E + T
T -> i
T -> ( E )
T -> i [ E ]
Input
i [ i ]
STEP 1
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} |
Input : i [ i ] <eof>
Action : shift
STEP 2
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i |
Input : [ i ] <eof>
Action : goto
STEP 3
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} |
Input : [ i ] <eof>
Action : shift
STEP 4
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} | [ |
Input : i ] <eof>
Action : goto
STEP 5
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} | [ | E -> . E + T {+, ]}
E -> . T {+, ]}
T -> . ( E ) {+, ]}
T -> . i {+, ]}
T -> . i [ E ] {+, ]}
T -> i [ . E ] {<eof>, +} |
Input : i ] <eof>
Action : shift
STEP 6
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} | [ | E -> . E + T {+, ]}
E -> . T {+, ]}
T -> . ( E ) {+, ]}
T -> . i {+, ]}
T -> . i [ E ] {+, ]}
T -> i [ . E ] {<eof>, +} | i |
Input : ] <eof>
Action : goto
STEP 7
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} | [ | E -> . E + T {+, ]}
E -> . T {+, ]}
T -> . ( E ) {+, ]}
T -> . i {+, ]}
T -> . i [ E ] {+, ]}
T -> i [ . E ] {<eof>, +} | i | T -> i . {+, ]}
T -> i . [ E ] {+, ]} |
Input : ] <eof>
Action : reduce T -> i . {+, ]}
STEP 8
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} | [ | E -> . E + T {+, ]}
E -> . T {+, ]}
T -> . ( E ) {+, ]}
T -> . i {+, ]}
T -> . i [ E ] {+, ]}
T -> i [ . E ] {<eof>, +} | T
└── i |
Input : ] <eof>
Action : goto
STEP 9
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} | [ | E -> . E + T {+, ]}
E -> . T {+, ]}
T -> . ( E ) {+, ]}
T -> . i {+, ]}
T -> . i [ E ] {+, ]}
T -> i [ . E ] {<eof>, +} | T
└── i | |
Input : ] <eof>
Action : reduce E -> T . {+, ]}
STEP 10
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} | [ | E -> . E + T {+, ]}
E -> . T {+, ]}
T -> . ( E ) {+, ]}
T -> . i {+, ]}
T -> . i [ E ] {+, ]}
T -> i [ . E ] {<eof>, +} | E
└── T
└── i |
Input : ] <eof>
Action : goto
STEP 11
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} | [ | E -> . E + T {+, ]}
E -> . T {+, ]}
T -> . ( E ) {+, ]}
T -> . i {+, ]}
T -> . i [ E ] {+, ]}
T -> i [ . E ] {<eof>, +} | E
└── T
└── i | E -> E . + T {+, ]}
T -> i [ E . ] {<eof>, +} |
Input : ] <eof>
Action : shift
STEP 12
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} | [ | E -> . E + T {+, ]}
E -> . T {+, ]}
T -> . ( E ) {+, ]}
T -> . i {+, ]}
T -> . i [ E ] {+, ]}
T -> i [ . E ] {<eof>, +} | E
└── T
└── i | E -> E . + T {+, ]}
T -> i [ E . ] {<eof>, +} | ] |
Input : <eof>
Action : goto
STEP 13
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | i | T -> i . {<eof>, +}
T -> i . [ E ] {<eof>, +} | [ | E -> . E + T {+, ]}
E -> . T {+, ]}
T -> . ( E ) {+, ]}
T -> . i {+, ]}
T -> . i [ E ] {+, ]}
T -> i [ . E ] {<eof>, +} | E
└── T
└── i | E -> E . + T {+, ]}
T -> i [ E . ] {<eof>, +} | ] | T -> i [ E ] . {<eof>, +} |
Input : <eof>
Action : reduce T -> i [ E ] . {<eof>, +}
STEP 14
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | T
├── i
├── [
├── E
│ └── T
│ └── i
└── ] |
Input : <eof>
Action : goto
STEP 15
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | T
├── i
├── [
├── E
│ └── T
│ └── i
└── ] | |
Input : <eof>
Action : reduce E -> T . {<eof>, +}
STEP 16
Stack :
E -> . E + T {<eof>, +}
E -> . T {<eof>, +}
T -> . ( E ) {<eof>, +}
T -> . i {<eof>, +}
T -> . i [ E ] {<eof>, +} | E
└── T
├── i
├── [
├── E
│ └── T
│ └── i
└── ] |
Input : <eof>
Action : accept
E
└── T
├── i
├── [
├── E
│ └── T
│ └── i
└── ]
First, Follow, Nullable sets
first (E) = {(, i}
follow (E) = {), +, ]}
nullable (E) = false
first (T) = {(, i}
follow (T) = {), +, ]}
nullable (T) = false
first (() = {(}
follow (() = {(, i}
nullable (() = false
first ()) = {)}
follow ()) = {), +, ]}
nullable ()) = false
first (+) = {+}
follow (+) = {(, i}
nullable (+) = false
first ([) = {[}
follow ([) = {(, i}
nullable ([) = false
first (]) = {]}
follow (]) = {), +, ]}
nullable (]) = false
first (i) = {i}
follow (i) = {), +, [, ]}
nullable (i) = 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.
