LR(1) derivation example

Grammar

S -> V = E
S -> E
E -> V
V -> x
V -> * E

Input

STEP 1

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

Input  : * x = x <eof>

Action : shift

STEP 2

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

*

Input  : x = x <eof>

Action : goto

STEP 3

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

*

<s3> E -> . V {<eof>, =} V -> . * E {<eof>, =} V -> . x {<eof>, =} V -> * . E {<eof>, =}

Input  : x = x <eof>

Action : shift

STEP 4

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

*

<s3> E -> . V {<eof>, =} V -> . * E {<eof>, =} V -> . x {<eof>, =} V -> * . E {<eof>, =}

x

Input  : = x <eof>

Action : goto

STEP 5

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

*

<s3> E -> . V {<eof>, =} V -> . * E {<eof>, =} V -> . x {<eof>, =} V -> * . E {<eof>, =}

x

<s4> V -> x . {<eof>, =}

Input  : = x <eof>

Action : reduce V -> x . {<eof>, =}

STEP 6

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

*

<s3> E -> . V {<eof>, =} V -> . * E {<eof>, =} V -> . x {<eof>, =} V -> * . E {<eof>, =}

V └── x

Input  : = x <eof>

Action : goto

STEP 7

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

*

<s3> E -> . V {<eof>, =} V -> . * E {<eof>, =} V -> . x {<eof>, =} V -> * . E {<eof>, =}

V └── x

<s6> E -> V . {<eof>, =}

Input  : = x <eof>

Action : reduce E -> V . {<eof>, =}

STEP 8

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

*

<s3> E -> . V {<eof>, =} V -> . * E {<eof>, =} V -> . x {<eof>, =} V -> * . E {<eof>, =}

E └── V └── x

Input  : = x <eof>

Action : goto

STEP 9

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

*

<s3> E -> . V {<eof>, =} V -> . * E {<eof>, =} V -> . x {<eof>, =} V -> * . E {<eof>, =}

E └── V └── x

<s5> V -> * E . {<eof>, =}

Input  : = x <eof>

Action : reduce V -> * E . {<eof>, =}

STEP 10

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

V ├── * └── E └── V └── x

Input  : = x <eof>

Action : goto

STEP 11

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

V ├── * └── E └── V └── x

<s2> E -> V . {<eof>} S -> V . = E {<eof>}

Input  : = x <eof>

Action : shift

STEP 12

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

V ├── * └── E └── V └── x

<s2> E -> V . {<eof>} S -> V . = E {<eof>}

=

Input  : x <eof>

Action : goto

STEP 13

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

V ├── * └── E └── V └── x

<s2> E -> V . {<eof>} S -> V . = E {<eof>}

=

<s7> E -> . V {<eof>} S -> V = . E {<eof>} V -> . * E {<eof>} V -> . x {<eof>}

Input  : x <eof>

Action : shift

STEP 14

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

V ├── * └── E └── V └── x

<s2> E -> V . {<eof>} S -> V . = E {<eof>}

=

<s7> E -> . V {<eof>} S -> V = . E {<eof>} V -> . * E {<eof>} V -> . x {<eof>}

x

Input  : <eof>

Action : goto

STEP 15

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

V ├── * └── E └── V └── x

<s2> E -> V . {<eof>} S -> V . = E {<eof>}

=

<s7> E -> . V {<eof>} S -> V = . E {<eof>} V -> . * E {<eof>} V -> . x {<eof>}

x

<s11> V -> x . {<eof>}

Input  : <eof>

Action : reduce V -> x . {<eof>}

STEP 16

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

V ├── * └── E └── V └── x

<s2> E -> V . {<eof>} S -> V . = E {<eof>}

=

<s7> E -> . V {<eof>} S -> V = . E {<eof>} V -> . * E {<eof>} V -> . x {<eof>}

V └── x

Input  : <eof>

Action : goto

STEP 17

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

V ├── * └── E └── V └── x

<s2> E -> V . {<eof>} S -> V . = E {<eof>}

=

<s7> E -> . V {<eof>} S -> V = . E {<eof>} V -> . * E {<eof>} V -> . x {<eof>}

V └── x

<s9> E -> V . {<eof>}

Input  : <eof>

Action : reduce E -> V . {<eof>}

STEP 18

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

V ├── * └── E └── V └── x

<s2> E -> V . {<eof>} S -> V . = E {<eof>}

=

<s7> E -> . V {<eof>} S -> V = . E {<eof>} V -> . * E {<eof>} V -> . x {<eof>}

E └── V └── x

Input  : <eof>

Action : goto

STEP 19

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

V ├── * └── E └── V └── x

<s2> E -> V . {<eof>} S -> V . = E {<eof>}

=

<s7> E -> . V {<eof>} S -> V = . E {<eof>} V -> . * E {<eof>} V -> . x {<eof>}

E └── V └── x

<s8> S -> V = E . {<eof>}

Input  : <eof>

Action : reduce S -> V = E . {<eof>}

STEP 20

Stack  :

<s0> E -> . V {<eof>} S -> . E {<eof>} S -> . V = E {<eof>} V -> . * E {<eof>, =} V -> . x {<eof>, =}

S ├── V │ ├── * │ └── E │ └── V │ └── x ├── = └── E └── V └── x

Input  : <eof>

Action : accept

S
├── V
│   ├── *
│   └── E
│       └── V
│           └── x
├── =
└── E
    └── V
        └── x

First, Follow, Nullable sets

first    (E) = {*, x}
follow   (E) = {=}
nullable (E) = false

first    (S) = {*, x}
follow   (S) = {}
nullable (S) = false

first    (V) = {*, x}
follow   (V) = {=}
nullable (V) = false

first    (*) = {*}
follow   (*) = {*, x}
nullable (*) = false

first    (=) = {=}
follow   (=) = {*, x}
nullable (=) = false

first    (x) = {x}
follow   (x) = {=}
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.