Help in understanding *.output file

[Rajasankar K]

Hi,

I am learning to understand the *.output file generated by bison.  I have
copy/pasted a small *.output file in this mail and  I state my understanding
here about the state transitions in bison. Can you please correct me, where
I am wrong. I am not concentrating on the shift/reduce conflict here (and I
understand that applying associativity, %left or %right, will solve it).

Thanks for your help,
Raja.


== START copy/paste of   *.output file ==

State 5 contains 1 shift/reduce conflict.


Grammar

    0 $accept: expr $end

    1 expr: NUMBER
    2     | expr '-' expr


Terminals, with rules where they appear

$end (0) 0
'-' (45) 2
error (256)
NUMBER (258) 1


Nonterminals, with rules where they appear

$accept (5)
    on left: 0
expr (6)
    on left: 1 2, on right: 0 2


state 0

    0 $accept: . expr $end

    NUMBER  shift, and go to state 1

    expr  go to state 2

state 1

    1 expr: NUMBER .

    $default  reduce using rule 1 (expr)


state 2

    0 $accept: expr . $end
    2 expr: expr . '-' expr

    $end  shift, and go to state 3
    '-'   shift, and go to state 4


state 3

    0 $accept: expr $end .

    $default  accept


state 4

    2 expr: expr '-' . expr

    NUMBER  shift, and go to state 1

    expr  go to state 5


state 5

    2 expr: expr . '-' expr
    2     | expr '-' expr .

    '-'  shift, and go to state 4

    '-'       [reduce using rule 2 (expr)]
    $default  reduce using rule 2 (expr)

== END copy/paste of   *.output file ==


My understanding:
============

state 0 and state 1:
-------------------
Bison starts with state 0. On getting a NUMBER token, bison shifts that
terminal to the stack and goes to state 1.
When entering state1 the stack top *will* contain a NUMBER. No sooner than
bison enters state 1, it does a reduction, since only $default is the event
specified. So, NUMBER is popped from the stack and expr is pushed into the
stack. On reduction bison *will always* go back to the state from which it
entered the current state. So, in this case, it has to go back to state 0.
While entering a state, if any of  the events listed matches the stack top,
it will take the given action immediately without waiting for any inputs.
Here, when bison goes back to state 0 from state 1, there are two events
possible. One is NUMBER and another is expr. So, automatically, bison
switches to state 2, since expr is on the top of the stack.

So, just after getting the first NUMBER token, bison traverses the states
as, state 0 -> state 1 -> state 0 -> state 2.


My problem in applying this theory in state 4 and state 5 is:
Bison enters state 4 from state 2 (and from state 5)only. It enters state 5
from state 4 only. So, if there is a reduction in state 5 it will come back
to state 4. But there is no reduction in state 4 to go back to state 2. So,
how will it reach state 3 from state 4 or state 5, for a successful match?