Re: y.output format

[Hans Aberg]

Reply-to: address@hidden

At 10:35 +0200 2002/06/21, Matthew P. Carter 98 wrote:
>What I don't understand is how a NON-terminal can ever be
>the input to the finite state machine.

This is part of the parsing algorithm that Bison is using. Bison is using
LALR, but any bottom-up parsing algorithm works basically the same in this
respect. See for example the book by Aho, Sethi & Ullman, sec 4.7, or
perhaps the online available book <http://www.cs.vu.nl/~dick/PTAPG.html>.

Basically, a parsing state is the set of all possible parsing
configurations (called "items" in Aho et. al.) given a certain input: a set
of rules each with a dot on the right hand side, indicating how far the
lookahead of that rule has proceeded at that point. In n-lookahead parsing
algorithms, one is using at most the next n tokens n in order to determine
the next state. The parsing algorithm is replacing those states with
numbers, which is then what the Bison generated parser is using.

  Hans Aberg