The Bison parser does not always reduce immediately as soon as the last n tokens and groupings match a rule. This is because such a simple strategy is inadequate to handle most languages. Instead, when a reduction is possible, the parser sometimes "looks ahead" at the next token in order to decide what to do.
When a token is read, it is not immediately shifted; first it becomes the look-ahead token, which is not on the stack. Now the parser can perform one or more reductions of tokens and groupings on the stack, while the look-ahead token remains off to the side. When no more reductions should take place, the look-ahead token is shifted onto the stack. This does not mean that all possible reductions have been done; depending on the token type of the look-ahead token, some rules may choose to delay their application.
Here is a simple case where look-ahead is needed. These three rules define expressions which contain binary addition operators and postfix unary factorial operators (`!'), and allow parentheses for grouping.
expr: term '+' expr
| term
;
term: '(' expr ')'
| term '!'
| NUMBER
;
Suppose that the tokens `1 + 2' have been read and shifted; what
should be done? If the following token is `)', then the first three
tokens must be reduced to form an expr. This is the only valid
course, because shifting the `)' would produce a sequence of symbols
term ')', and no rule allows this.
If the following token is `!', then it must be shifted immediately so
that `2 !' can be reduced to make a term. If instead the
parser were to reduce before shifting, `1 + 2' would become an
expr. It would then be impossible to shift the `!' because
doing so would produce on the stack the sequence of symbols expr
'!'. No rule allows that sequence.
The current look-ahead token is stored in the variable yychar.
See section Special Features for Use in Actions.
Go to the first, previous, next, last section, table of contents.