LR(1) derivation example

Grammar

E -> F ^ E
E -> F
F -> a
F -> b
F -> c

Input

STEP 1

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

Input  : a ^ b ^ c <eof>

Action : shift

STEP 2

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

a

Input  : ^ b ^ c <eof>

Action : goto

STEP 3

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

a

<s2> F -> a . {<eof>, ^}

Input  : ^ b ^ c <eof>

Action : reduce F -> a . {<eof>, ^}

STEP 4

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

Input  : ^ b ^ c <eof>

Action : goto

STEP 5

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

Input  : ^ b ^ c <eof>

Action : shift

STEP 6

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

Input  : b ^ c <eof>

Action : goto

STEP 7

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

Input  : b ^ c <eof>

Action : shift

STEP 8

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

b

Input  : ^ c <eof>

Action : goto

STEP 9

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

b

<s3> F -> b . {<eof>, ^}

Input  : ^ c <eof>

Action : reduce F -> b . {<eof>, ^}

STEP 10

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── b

Input  : ^ c <eof>

Action : goto

STEP 11

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── b

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

Input  : ^ c <eof>

Action : shift

STEP 12

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── b

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

Input  : c <eof>

Action : goto

STEP 13

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── b

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

Input  : c <eof>

Action : shift

STEP 14

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── b

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

c

Input  : <eof>

Action : goto

STEP 15

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── b

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

c

<s4> F -> c . {<eof>, ^}

Input  : <eof>

Action : reduce F -> c . {<eof>, ^}

STEP 16

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── b

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── c

Input  : <eof>

Action : goto

STEP 17

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── b

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── c

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

Input  : <eof>

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

STEP 18

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── b

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

E └── F └── c

Input  : <eof>

Action : goto

STEP 19

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── b

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

E └── F └── c

<s6> E -> F ^ E . {<eof>}

Input  : <eof>

Action : reduce E -> F ^ E . {<eof>}

STEP 20

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

E ├── F │ └── b ├── ^ └── E └── F └── c

Input  : <eof>

Action : goto

STEP 21

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

F └── a

<s1> E -> F . {<eof>} E -> F . ^ E {<eof>}

^

<s5> E -> . F {<eof>} E -> . F ^ E {<eof>} E -> F ^ . E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

E ├── F │ └── b ├── ^ └── E └── F └── c

<s6> E -> F ^ E . {<eof>}

Input  : <eof>

Action : reduce E -> F ^ E . {<eof>}

STEP 22

Stack  :

<s0> E -> . F {<eof>} E -> . F ^ E {<eof>} F -> . a {<eof>, ^} F -> . b {<eof>, ^} F -> . c {<eof>, ^}

E ├── F │ └── a ├── ^ └── E ├── F │ └── b ├── ^ └── E └── F └── c

Input  : <eof>

Action : accept

E
├── F
│   └── a
├── ^
└── E
    ├── F
    │   └── b
    ├── ^
    └── E
        └── 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.