LR(0) derivation example

Grammar

Z -> E $
E -> T
E -> E + T
T -> i
T -> ( E )

Input

STEP 1

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

Input  : i + i + i $

Action : shift

STEP 2

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

i

Input  : + i + i $

Action : goto

STEP 3

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

i

<s4> T -> i .

Input  : + i + i $

Action : reduce T -> i .

STEP 4

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

T └── i

Input  : + i + i $

Action : goto

STEP 5

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

T └── i

<s2> E -> T .

Input  : + i + i $

Action : reduce E -> T .

STEP 6

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E └── T └── i

Input  : + i + i $

Action : goto

STEP 7

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E └── T └── i

<s1> E -> E . + T Z -> E . $

Input  : + i + i $

Action : shift

STEP 8

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E └── T └── i

<s1> E -> E . + T Z -> E . $

+

Input  : i + i $

Action : goto

STEP 9

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E └── T └── i

<s1> E -> E . + T Z -> E . $

+

<s7> E -> E + . T T -> . ( E ) T -> . i

Input  : i + i $

Action : shift

STEP 10

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E └── T └── i

<s1> E -> E . + T Z -> E . $

+

<s7> E -> E + . T T -> . ( E ) T -> . i

i

Input  : + i $

Action : goto

STEP 11

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E └── T └── i

<s1> E -> E . + T Z -> E . $

+

<s7> E -> E + . T T -> . ( E ) T -> . i

i

<s4> T -> i .

Input  : + i $

Action : reduce T -> i .

STEP 12

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E └── T └── i

<s1> E -> E . + T Z -> E . $

+

<s7> E -> E + . T T -> . ( E ) T -> . i

T └── i

Input  : + i $

Action : goto

STEP 13

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E └── T └── i

<s1> E -> E . + T Z -> E . $

+

<s7> E -> E + . T T -> . ( E ) T -> . i

T └── i

<s8> E -> E + T .

Input  : + i $

Action : reduce E -> E + T .

STEP 14

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ └── T │ └── i ├── + └── T └── i

Input  : + i $

Action : goto

STEP 15

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ └── T │ └── i ├── + └── T └── i

<s1> E -> E . + T Z -> E . $

Input  : + i $

Action : shift

STEP 16

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ └── T │ └── i ├── + └── T └── i

<s1> E -> E . + T Z -> E . $

+

Input  : i $

Action : goto

STEP 17

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ └── T │ └── i ├── + └── T └── i

<s1> E -> E . + T Z -> E . $

+

<s7> E -> E + . T T -> . ( E ) T -> . i

Input  : i $

Action : shift

STEP 18

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ └── T │ └── i ├── + └── T └── i

<s1> E -> E . + T Z -> E . $

+

<s7> E -> E + . T T -> . ( E ) T -> . i

i

Input  : $

Action : goto

STEP 19

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ └── T │ └── i ├── + └── T └── i

<s1> E -> E . + T Z -> E . $

+

<s7> E -> E + . T T -> . ( E ) T -> . i

i

<s4> T -> i .

Input  : $

Action : reduce T -> i .

STEP 20

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ └── T │ └── i ├── + └── T └── i

<s1> E -> E . + T Z -> E . $

+

<s7> E -> E + . T T -> . ( E ) T -> . i

T └── i

Input  : $

Action : goto

STEP 21

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ └── T │ └── i ├── + └── T └── i

<s1> E -> E . + T Z -> E . $

+

<s7> E -> E + . T T -> . ( E ) T -> . i

T └── i

<s8> E -> E + T .

Input  : $

Action : reduce E -> E + T .

STEP 22

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ ├── E │ │ └── T │ │ └── i │ ├── + │ └── T │ └── i ├── + └── T └── i

Input  : $

Action : goto

STEP 23

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ ├── E │ │ └── T │ │ └── i │ ├── + │ └── T │ └── i ├── + └── T └── i

<s1> E -> E . + T Z -> E . $

Input  : $

Action : shift

STEP 24

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ ├── E │ │ └── T │ │ └── i │ ├── + │ └── T │ └── i ├── + └── T └── i

<s1> E -> E . + T Z -> E . $

$

Input  :

Action : goto

STEP 25

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

E ├── E │ ├── E │ │ └── T │ │ └── i │ ├── + │ └── T │ └── i ├── + └── T └── i

<s1> E -> E . + T Z -> E . $

$

<s9> Z -> E $ .

Input  :

Action : reduce Z -> E $ .

STEP 26

Stack  :

<s0> E -> . E + T E -> . T T -> . ( E ) T -> . i Z -> . E $

Z ├── E │ ├── E │ │ ├── E │ │ │ └── T │ │ │ └── i │ │ ├── + │ │ └── T │ │ └── i │ ├── + │ └── T │ └── i └── $

Input  :

Action : accept

Z
├── E
│   ├── E
│   │   ├── E
│   │   │   └── T
│   │   │       └── i
│   │   ├── +
│   │   └── T
│   │       └── i
│   ├── +
│   └── T
│       └── i
└── $

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.