Next: LAC, Previous: LR Table Construction, Up: Tuning LR [Contents][Index]
After parser table construction, Bison identifies the reduction with the largest lookahead set in each parser state. To reduce the size of the parser state, traditional Bison behavior is to remove that lookahead set and to assign that reduction to be the default parser action. Such a reduction is known as a default reduction.
Default reductions affect more than the size of the parser tables. They also affect the behavior of the parser:
yylex invocations.
A consistent state is a state that has only one possible parser
action. If that action is a reduction and is encoded as a default
reduction, then that consistent state is called a defaulted state.
Upon reaching a defaulted state, a Bison-generated parser does not bother to
invoke yylex to fetch the next token before performing the reduction.
In other words, whether default reductions are enabled in consistent states
determines how soon a Bison-generated parser invokes yylex for a
token: immediately when it reaches that token in the input or when it
eventually needs that token as a lookahead to determine the next
parser action. Traditionally, default reductions are enabled, and so the
parser exhibits the latter behavior.
The presence of defaulted states is an important consideration when
designing yylex and the grammar file. That is, if the behavior of
yylex can influence or be influenced by the semantic actions
associated with the reductions in defaulted states, then the delay of the
next yylex invocation until after those reductions is significant.
For example, the semantic actions might pop a scope stack that yylex
uses to determine what token to return. Thus, the delay might be necessary
to ensure that yylex does not look up the next token in a scope that
should already be considered closed.
When the parser fetches a new token by invoking yylex, it checks
whether there is an action for that token in the current parser state. The
parser detects a syntax error if and only if either (1) there is no action
for that token or (2) the action for that token is the error action (due to
the use of %nonassoc). However, if there is a default reduction in
that state (which might or might not be a defaulted state), then it is
impossible for condition 1 to exist. That is, all tokens have an action.
Thus, the parser sometimes fails to detect the syntax error until it reaches
a later state.
While default reductions never cause the parser to accept syntactically
incorrect sentences, the delay of syntax error detection can have unexpected
effects on the behavior of the parser. However, the delay can be caused
anyway by parser state merging and the use of %nonassoc, and it can
be fixed by another Bison feature, LAC. We discuss the effects of delayed
syntax error detection and LAC more in the next section (see LAC).
For canonical LR, the only default reduction that Bison enables by default
is the accept action, which appears only in the accepting state, which has
no other action and is thus a defaulted state. However, the default accept
action does not delay any yylex invocation or syntax error detection
because the accept action ends the parse.
For LALR and IELR, Bison enables default reductions in nearly all states by
default. There are only two exceptions. First, states that have a shift
action on the error token do not have default reductions because
delayed syntax error detection could then prevent the error token
from ever being shifted in that state. However, parser state merging can
cause the same effect anyway, and LAC fixes it in both cases, so future
versions of Bison might drop this exception when LAC is activated. Second,
GLR parsers do not record the default reduction as the action on a lookahead
token for which there is a conflict. The correct action in this case is to
split the parse instead.
To adjust which states have default reductions enabled, use the
%define lr.default-reduction directive.
Specify the kind of states that are permitted to contain default reductions. The accepted values of where are:
most (default for LALR and IELR)
consistent
accepting (default for canonical LR)
Next: LAC, Previous: LR Table Construction, Up: Tuning LR [Contents][Index]