GNU Info

(bison.info)Look-Ahead

---

Next: Shift/Reduce Up: Algorithm

---

Enter node , (file) or (file)node

Look-Ahead Tokens
=================

   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'.
Note: Special Features for Use in Actions.