Next: Reduce/Reduce, Previous: Contextual Precedence, Up: Algorithm [Contents][Index]

The function `yyparse`

is implemented using a finite-state machine.
The values pushed on the parser stack are not simply token type codes; they
represent the entire sequence of terminal and nonterminal symbols at or
near the top of the stack. The current state collects all the information
about previous input which is relevant to deciding what to do next.

Each time a lookahead token is read, the current parser state together
with the type of lookahead token are looked up in a table. This table
entry can say, “Shift the lookahead token.” In this case, it also
specifies the new parser state, which is pushed onto the top of the
parser stack. Or it can say, “Reduce using rule number `n`.”
This means that a certain number of tokens or groupings are taken off
the top of the stack, and replaced by one grouping. In other words,
that number of states are popped from the stack, and one new state is
pushed.

There is one other alternative: the table can say that the lookahead token is erroneous in the current state. This causes error processing to begin (see Error Recovery).