Look-Ahead
Previous: <Algorithm=>Algorithm> * Next: <Shift\/Reduce=>ShiftRedue> * Up: <Algorithm=>Algorithm>

#Wrap on
{fH3}Look-Ahead Tokens{f}

The Bison parser does {fEmphasis}not{f} always reduce immediately as soon as the
last {fStrong}n{f} 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
{fUnderline}look-ahead token{f}, 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 ({fEmphasis}!{f}), and allow parentheses for grouping.

#Wrap off
#fCode
expr:     term '+' expr
        | term
        ;

term:     '(' expr ')'
        | term '!'
        | NUMBER
        ;
#f
#Wrap on

Suppose that the tokens {fEmphasis}1 + 2{f} have been read and shifted; what
should be done?  If the following token is {fEmphasis}){f}, then the first three
tokens must be reduced to form an {fCode}expr{f}.  This is the only valid
course, because shifting the {fEmphasis}){f} would produce a sequence of symbols
{fCode}term ')'{f}, and no rule allows this.

If the following token is {fEmphasis}!{f}, then it must be shifted immediately so
that {fEmphasis}2 !{f} can be reduced to make a {fCode}term{f}.  If instead the
parser were to reduce before shifting, {fEmphasis}1 + 2{f} would become an
{fCode}expr{f}.  It would then be impossible to shift the {fEmphasis}!{f} because
doing so would produce on the stack the sequence of symbols {fCode}expr
'!'{f}.  No rule allows that sequence.

The current look-ahead token is stored in the variable {fCode}yychar{f}.
\*Note <Action Features=>ActionFeat>: Special Features for Use in Actions.

