Next: Reduce/Reduce Conflicts, Previous: Context-Dependent Precedence, Up: The Bison Parser Algorithm [Contents][Index]

The function `yyparse`

is implemented using a finite-state machine.
The values pushed on the parser stack are not simply token kind 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 kind 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).