LR(1) derivation example

Grammar

S -> if E then S else S
S -> if E then S
S -> read
E -> x

Input

STEP 1

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

Input  : if x then if x then read else read <eof>

Action : shift

STEP 2

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

Input  : x then if x then read else read <eof>

Action : goto

STEP 3

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

Input  : x then if x then read else read <eof>

Action : shift

STEP 4

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

x

Input  : then if x then read else read <eof>

Action : goto

STEP 5

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

x

<s4> E -> x . {then}

Input  : then if x then read else read <eof>

Action : reduce E -> x . {then}

STEP 6

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

Input  : then if x then read else read <eof>

Action : goto

STEP 7

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

Input  : then if x then read else read <eof>

Action : shift

STEP 8

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

Input  : if x then read else read <eof>

Action : goto

STEP 9

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

Input  : if x then read else read <eof>

Action : shift

STEP 10

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

Input  : x then read else read <eof>

Action : goto

STEP 11

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

Input  : x then read else read <eof>

Action : shift

STEP 12

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

x

Input  : then read else read <eof>

Action : goto

STEP 13

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

x

<s4> E -> x . {then}

Input  : then read else read <eof>

Action : reduce E -> x . {then}

STEP 14

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

E └── x

Input  : then read else read <eof>

Action : goto

STEP 15

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

E └── x

<s9> S -> if E . then S {<eof>, else} S -> if E . then S else S {<eof>, else}

Input  : then read else read <eof>

Action : shift

STEP 16

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

E └── x

<s9> S -> if E . then S {<eof>, else} S -> if E . then S else S {<eof>, else}

then

Input  : read else read <eof>

Action : goto

STEP 17

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

E └── x

<s9> S -> if E . then S {<eof>, else} S -> if E . then S else S {<eof>, else}

then

<s10> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>, else} S -> if E then . S else S {<eof>, else}

Input  : read else read <eof>

Action : shift

STEP 18

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

E └── x

<s9> S -> if E . then S {<eof>, else} S -> if E . then S else S {<eof>, else}

then

<s10> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>, else} S -> if E then . S else S {<eof>, else}

read

Input  : else read <eof>

Action : goto

STEP 19

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

E └── x

<s9> S -> if E . then S {<eof>, else} S -> if E . then S else S {<eof>, else}

then

<s10> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>, else} S -> if E then . S else S {<eof>, else}

read

<s8> S -> read . {<eof>, else}

Input  : else read <eof>

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

STEP 20

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

E └── x

<s9> S -> if E . then S {<eof>, else} S -> if E . then S else S {<eof>, else}

then

<s10> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>, else} S -> if E then . S else S {<eof>, else}

S └── read

Input  : else read <eof>

Action : goto

STEP 21

Stack  :

<s0> S -> . if E then S {<eof>} S -> . if E then S else S {<eof>} S -> . read {<eof>}

if

<s1> E -> . x {then} S -> if . E then S {<eof>} S -> if . E then S else S {<eof>}

E └── x

<s3> S -> if E . then S {<eof>} S -> if E . then S else S {<eof>}

then

<s5> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>} S -> if E then . S else S {<eof>}

if

<s7> E -> . x {then} S -> if . E then S {<eof>, else} S -> if . E then S else S {<eof>, else}

E └── x

<s9> S -> if E . then S {<eof>, else} S -> if E . then S else S {<eof>, else}

then

<s10> S -> . if E then S {<eof>, else} S -> . if E then S else S {<eof>, else} S -> . read {<eof>, else} S -> if E then . S {<eof>, else} S -> if E then . S else S {<eof>, else}

S └── read

<s11> S -> if E then S . {<eof>, else} S -> if E then S . else S {<eof>, else}

Input  : else read <eof>

Action : conflict shift/reduce

First, Follow, Nullable sets

first    (E) = {x}
follow   (E) = {then}
nullable (E) = false

first    (S) = {if, read}
follow   (S) = {else}
nullable (S) = false

first    (else) = {else}
follow   (else) = {if, read}
nullable (else) = false

first    (if) = {if}
follow   (if) = {x}
nullable (if) = false

first    (read) = {read}
follow   (read) = {else}
nullable (read) = false

first    (then) = {then}
follow   (then) = {if, read}
nullable (then) = false

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