Node:Parser States, Next:Reduce/Reduce, Previous:Contextual Precedence, Up:Algorithm
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 look-ahead token is read, the current parser state together with the type of look-ahead token are looked up in a table. This table entry can say, "Shift the look-ahead 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 look-ahead token is erroneous in the current state. This causes error processing to begin (see Error Recovery).