LR(1) derivation example

Grammar

S -> S ; S
S -> id := E
S -> print ( L )
E -> id
E -> num
E -> E + E
E -> ( S , E )
L -> E
L -> L , E

Input

id := num ; id := id + ( id := num + num , id )

STEP 1

Stack  :

Input  : id := num ; id := id + ( id := num + num , id ) <eof>

Action : shift

STEP 2

Stack  : 
id

Input  : := num ; id := id + ( id := num + num , id ) <eof>

Action : goto

STEP 3

Stack  : 
id

Input  : := num ; id := id + ( id := num + num , id ) <eof>

Action : shift

STEP 4

Stack  : 
id
 
:=

Input  : num ; id := id + ( id := num + num , id ) <eof>

Action : goto

STEP 5

Stack  : 
id
 
:=

Input  : num ; id := id + ( id := num + num , id ) <eof>

Action : shift

STEP 6

Stack  : 
id
 
:=
 
num

Input  : ; id := id + ( id := num + num , id ) <eof>

Action : goto

STEP 7

Stack  : 
id
 
:=
 
num

Input  : ; id := id + ( id := num + num , id ) <eof>

Action : reduce E -> num . {<eof>, +, ;}

STEP 8

Stack  : 
id
 
:=
 
E
└── num

Input  : ; id := id + ( id := num + num , id ) <eof>

Action : goto

STEP 9

Stack  : 
id
 
:=
 
E
└── num

Input  : ; id := id + ( id := num + num , id ) <eof>

Action : reduce S -> id := E . {<eof>, ;}

STEP 10

Stack  : 
S
├── id
├── :=
└── E
    └── num

Input  : ; id := id + ( id := num + num , id ) <eof>

Action : goto

STEP 11

Stack  : 
S
├── id
├── :=
└── E
    └── num

Input  : ; id := id + ( id := num + num , id ) <eof>

Action : shift

STEP 12

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;

Input  : id := id + ( id := num + num , id ) <eof>

Action : goto

STEP 13

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;

Input  : id := id + ( id := num + num , id ) <eof>

Action : shift

STEP 14

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id

Input  : := id + ( id := num + num , id ) <eof>

Action : goto

STEP 15

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id

Input  : := id + ( id := num + num , id ) <eof>

Action : shift

STEP 16

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=

Input  : id + ( id := num + num , id ) <eof>

Action : goto

STEP 17

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=

Input  : id + ( id := num + num , id ) <eof>

Action : shift

STEP 18

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
id

Input  : + ( id := num + num , id ) <eof>

Action : goto

STEP 19

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
id

Input  : + ( id := num + num , id ) <eof>

Action : reduce E -> id . {<eof>, +, ;}

STEP 20

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id

Input  : + ( id := num + num , id ) <eof>

Action : goto

STEP 21

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id

Input  : + ( id := num + num , id ) <eof>

Action : shift

STEP 22

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+

Input  : ( id := num + num , id ) <eof>

Action : goto

STEP 23

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+

Input  : ( id := num + num , id ) <eof>

Action : shift

STEP 24

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(

Input  : id := num + num , id ) <eof>

Action : goto

STEP 25

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(

Input  : id := num + num , id ) <eof>

Action : shift

STEP 26

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id

Input  : := num + num , id ) <eof>

Action : goto

STEP 27

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id

Input  : := num + num , id ) <eof>

Action : shift

STEP 28

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=

Input  : num + num , id ) <eof>

Action : goto

STEP 29

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=

Input  : num + num , id ) <eof>

Action : shift

STEP 30

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
num

Input  : + num , id ) <eof>

Action : goto

STEP 31

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
num

Input  : + num , id ) <eof>

Action : reduce E -> num . {+, ,, ;}

STEP 32

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
E
└── num

Input  : + num , id ) <eof>

Action : goto

STEP 33

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
E
└── num

Input  : + num , id ) <eof>

Action : shift

STEP 34

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
E
└── num
 
+

Input  : num , id ) <eof>

Action : goto

STEP 35

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
E
└── num
 
+

Input  : num , id ) <eof>

Action : shift

STEP 36

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
E
└── num
 
+
 
num

Input  : , id ) <eof>

Action : goto

STEP 37

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
E
└── num
 
+
 
num

Input  : , id ) <eof>

Action : reduce E -> num . {+, ,, ;}

STEP 38

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
E
└── num
 
+
 
E
└── num

Input  : , id ) <eof>

Action : goto

STEP 39

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
E
└── num
 
+
 
E
└── num

Input  : , id ) <eof>

Action : reduce E -> E + E . {+, ,, ;}

STEP 40

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
E
├── E
│   └── num
├── +
└── E
    └── num

Input  : , id ) <eof>

Action : goto

STEP 41

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
id
 
:=
 
E
├── E
│   └── num
├── +
└── E
    └── num

Input  : , id ) <eof>

Action : reduce S -> id := E . {,, ;}

STEP 42

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
S
├── id
├── :=
└── E
    ├── E
    │   └── num
    ├── +
    └── E
        └── num

Input  : , id ) <eof>

Action : goto

STEP 43

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
S
├── id
├── :=
└── E
    ├── E
    │   └── num
    ├── +
    └── E
        └── num

Input  : , id ) <eof>

Action : shift

STEP 44

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
S
├── id
├── :=
└── E
    ├── E
    │   └── num
    ├── +
    └── E
        └── num
 
,

Input  : id ) <eof>

Action : goto

STEP 45

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
S
├── id
├── :=
└── E
    ├── E
    │   └── num
    ├── +
    └── E
        └── num
 
,

Input  : id ) <eof>

Action : shift

STEP 46

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
S
├── id
├── :=
└── E
    ├── E
    │   └── num
    ├── +
    └── E
        └── num
 
,
 
id

Input  : ) <eof>

Action : goto

STEP 47

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
S
├── id
├── :=
└── E
    ├── E
    │   └── num
    ├── +
    └── E
        └── num
 
,
 
id

Input  : ) <eof>

Action : reduce E -> id . {), +}

STEP 48

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
S
├── id
├── :=
└── E
    ├── E
    │   └── num
    ├── +
    └── E
        └── num
 
,
 
E
└── id

Input  : ) <eof>

Action : goto

STEP 49

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
S
├── id
├── :=
└── E
    ├── E
    │   └── num
    ├── +
    └── E
        └── num
 
,
 
E
└── id

Input  : ) <eof>

Action : shift

STEP 50

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
S
├── id
├── :=
└── E
    ├── E
    │   └── num
    ├── +
    └── E
        └── num
 
,
 
E
└── id
 
)

Input  : <eof>

Action : goto

STEP 51

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
(
 
S
├── id
├── :=
└── E
    ├── E
    │   └── num
    ├── +
    └── E
        └── num
 
,
 
E
└── id
 
)

Input  : <eof>

Action : reduce E -> ( S , E ) . {<eof>, +, ;}

STEP 52

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
E
├── (
├── S
│   ├── id
│   ├── :=
│   └── E
│       ├── E
│       │   └── num
│       ├── +
│       └── E
│           └── num
├── ,
├── E
│   └── id
└── )

Input  : <eof>

Action : goto

STEP 53

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
└── id
 
+
 
E
├── (
├── S
│   ├── id
│   ├── :=
│   └── E
│       ├── E
│       │   └── num
│       ├── +
│       └── E
│           └── num
├── ,
├── E
│   └── id
└── )

Input  : <eof>

Action : reduce E -> E + E . {<eof>, +, ;}

STEP 54

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
├── E
│   └── id
├── +
└── E
    ├── (
    ├── S
    │   ├── id
    │   ├── :=
    │   └── E
    │       ├── E
    │       │   └── num
    │       ├── +
    │       └── E
    │           └── num
    ├── ,
    ├── E
    │   └── id
    └── )

Input  : <eof>

Action : goto

STEP 55

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
id
 
:=
 
E
├── E
│   └── id
├── +
└── E
    ├── (
    ├── S
    │   ├── id
    │   ├── :=
    │   └── E
    │       ├── E
    │       │   └── num
    │       ├── +
    │       └── E
    │           └── num
    ├── ,
    ├── E
    │   └── id
    └── )

Input  : <eof>

Action : reduce S -> id := E . {<eof>, ;}

STEP 56

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
S
├── id
├── :=
└── E
    ├── E
    │   └── id
    ├── +
    └── E
        ├── (
        ├── S
        │   ├── id
        │   ├── :=
        │   └── E
        │       ├── E
        │       │   └── num
        │       ├── +
        │       └── E
        │           └── num
        ├── ,
        ├── E
        │   └── id
        └── )

Input  : <eof>

Action : goto

STEP 57

Stack  : 
S
├── id
├── :=
└── E
    └── num
 
;
 
S
├── id
├── :=
└── E
    ├── E
    │   └── id
    ├── +
    └── E
        ├── (
        ├── S
        │   ├── id
        │   ├── :=
        │   └── E
        │       ├── E
        │       │   └── num
        │       ├── +
        │       └── E
        │           └── num
        ├── ,
        ├── E
        │   └── id
        └── )

Input  : <eof>

Action : reduce S -> S ; S . {<eof>, ;}

STEP 58

Stack  : 
S
├── S
│   ├── id
│   ├── :=
│   └── E
│       └── num
├── ;
└── S
    ├── id
    ├── :=
    └── E
        ├── E
        │   └── id
        ├── +
        └── E
            ├── (
            ├── S
            │   ├── id
            │   ├── :=
            │   └── E
            │       ├── E
            │       │   └── num
            │       ├── +
            │       └── E
            │           └── num
            ├── ,
            ├── E
            │   └── id
            └── )

Input  : <eof>

Action : accept

S
├── S
│   ├── id
│   ├── :=
│   └── E
│       └── num
├── ;
└── S
    ├── id
    ├── :=
    └── E
        ├── E
        │   └── id
        ├── +
        └── E
            ├── (
            ├── S
            │   ├── id
            │   ├── :=
            │   └── E
            │       ├── E
            │       │   └── num
            │       ├── +
            │       └── E
            │           └── num
            ├── ,
            ├── E
            │   └── id
            └── )

First, Follow, Nullable sets

first    (E) = {(, id, num}
follow   (E) = {), +, ,, ;}
nullable (E) = false

first    (L) = {(, id, num}
follow   (L) = {), ,}
nullable (L) = false

first    (S) = {id, print}
follow   (S) = {,, ;}
nullable (S) = false

first    (() = {(}
follow   (() = {(, id, num, print}
nullable (() = false

first    ()) = {)}
follow   ()) = {), +, ,, ;}
nullable ()) = false

first    (+) = {+}
follow   (+) = {(, id, num}
nullable (+) = false

first    (,) = {,}
follow   (,) = {(, E, id, num}
nullable (,) = false

first    (:=) = {:=}
follow   (:=) = {(, id, num}
nullable (:=) = false

first    (;) = {;}
follow   (;) = {id, print}
nullable (;) = false

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

first    (id) = {id}
follow   (id) = {), +, ,, :=, ;}
nullable (id) = false

first    (num) = {num}
follow   (num) = {), +, ,, ;}
nullable (num) = false

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