Next: Shift/Reduce Up: Algorithm
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: '(' expr ')'
| term '!'
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
The current look-ahead token is stored in the variable `yychar'.
Note: Special Features for Use in Actions.
automatically generated by info2www