+2004-06-21 Paul Eggert <eggert@cs.ucla.edu>
+
+ * NEWS, TODO, doc/bison.texinfo:
+ Use "look-ahead" instead of "lookahead", to be consistent.
+ * REFERENCES: Fix incorrect reference to DeRemer and Pennello,
+ while we're fixing "look-ahead".
+ * src/conflicts.c (shift_set): Renamed from shiftset.
+ (look_ahead_set): Renamed from lookaheadset.
+ * src/print.c: Likewise.
+ * src/getargs.c (report_args): Add "look-ahead" as the new canonical
+ name for "lookahead".
+ (report_types, usage): Likewise.
+ * src/getargs.h (report_look_ahead_tokens): Renamed from
+ report_lookaheads.
+ * src/lalr.c (compute_look_ahead_tokens): Renamed from
+ compute_lookaheads.
+ (state_look_ahead_tokens_count): Renamed from state_lookaheads_count.
+ (look_ahead_tokens_print): Renamed from lookaheads_print.
+ * src/state.c (state_rule_look_ahead_tokens_print): Renamed from
+ state_rule_lookaheads_print.
+ * src/state.h: Likewise.
+ (reductions.look_ahead_tokens): Renamed from lookaheads.
+ * tests/torture.at (AT_DATA_LOOK_AHEAD_TOKENS_GRAMMAR): Renamed from
+ AT_DATA_LOOKAHEADS_GRAMMAR.
+
2004-06-03 Paul Eggert <eggert@cs.ucla.edu>
* README: Update location of patched M4 distribution.
Bison News
----------
+Changes in version 1.875e:
+
+* The option `--report=lookahead' was changed to `--report=look-ahead'.
+ The old spelling still works, but is not documented and will be removed.
+
Changes in version 1.875d, 2004-05-21:
* Unescaped newlines are no longer allowed in character constants or
produces additional information:
- itemset
complete the core item sets with their closure
- - lookahead
- explicitly associate lookaheads to items
+ - lookahead [changed to `look-ahead' in 1.875e and later]
+ explicitly associate look-ahead tokens to items
- solved
describe shift/reduce conflicts solving.
Bison used to systematically output this information on top of
Also, Bison uses a faster but less space-efficient encoding for the
parse tables (see Corbett's PhD thesis from Berkeley, "Static
Semantics in Compiler Error Recovery", June 1985, Report No. UCB/CSD
-85/251), and more modern technique for generating the lookahead sets.
-(See "Efficient Construction of LALR(1) Lookahead Sets" by F. DeRemer
-and A. Pennello, in ACM TOPLS Vol 4 No 4, October 1982. Their
+85/251), and more modern technique for generating the look-ahead sets.
+(See Frank DeRemer and Thomas Pennello, "Efficient Computation of
+LALR(1) Look-Ahead Sets", ACM Transactions on Programming Languages
+and Systems (TOPLAS) 4, 4 (October 1982), 615-649. Their
technique is the standard one now.)
paul rubin
free software foundation
+[DeRemer-Pennello reference corrected by Paul Eggert <eggert@cs.ucla.edu>,
+ 2004-06-21.]
** GLR
How would Paul like to display the conflicted actions? In particular,
-what when two reductions are possible on a given lookahead, but one is
+what when two reductions are possible on a given look-ahead token, but one is
part of $default. Should we make the two reductions explicit, or just
keep $default? See the following point.
-----
-Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
+Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of GNU Bison.
# b4_lyyerror_args
# ----------------
-# Same as above, but on the lookahead, hence yyllocp instead of yylocp.
+# Same as above, but on the look-ahead, hence yyllocp instead of yylocp.
m4_define([b4_lyyerror_args],
[b4_pure_if([b4_location_if([yyllocp, ])])dnl
m4_ifset([b4_parse_param], [b4_c_args(b4_parse_param), ])])
# b4_lpure_args
# -------------
-# Same as above, but on the lookahead, hence yyllocp instead of yylocp.
+# Same as above, but on the look-ahead, hence yyllocp instead of yylocp.
m4_define([b4_lpure_args],
[b4_pure_if([b4_location_if([, yyllocp])])[]b4_user_args])
# b4_lpure_formals
# ----------------
-# Same as above, but on the lookahead, hence yyllocp instead of yylocp.
+# Same as above, but on the look-ahead, hence yyllocp instead of yylocp.
m4_define([b4_lpure_formals],
[b4_pure_if([b4_location_if([YYLTYPE *yyllocp])])[]b4_user_formals])
/* Recover from a syntax error on YYSTACK, assuming that YYTOKENP,
YYLVALP, and YYLLOCP point to the syntactic category, semantic
- value, and location of the lookahead. */
+ value, and location of the look-ahead. */
static void
yyrecoverSyntaxError (yyGLRStack* yystack,
YYSTYPE* yylvalp, YYLTYPE* yyllocp]b4_user_formals[)
int debug_;
std::ostream &cdebug_;
- /* Lookahead and lookahead in internal form. */
+ /* Look-ahead and look-ahead in internal form. */
int looka_;
int ilooka_;
/* Message. */
std::string message;
- /* Semantic value and location of lookahead token. */
+ /* Semantic value and location of look-ahead token. */
SemanticType value;
LocationType location;
/* Beginning of the last erroneous token popped off. */
/* Backup. */
yybackup:
- /* Try to take a decision without lookahead. */
+ /* Try to take a decision without look-ahead. */
n_ = pact_[state_];
if (n_ == pact_ninf_)
goto yydefault;
- /* Read a lookahead token. */
+ /* Read a look-ahead token. */
if (looka_ == empty_)
{
YYCDEBUG << "Reading a token: ";
if (n_ == final_)
goto yyacceptlab;
- /* Shift the lookahead token. */
+ /* Shift the look-ahead token. */
#if YYDEBUG
YYCDEBUG << "Shifting token " << looka_
<< " (" << name_[ilooka_] << "), ";
error_start_ = location.begin;
if (errstatus_ == 3)
{
- /* If just tried and failed to reuse lookahead token after an
+ /* If just tried and failed to reuse look-ahead token after an
error, discard it. */
/* Return failure if at end of input. */
}
}
- /* Else will try to reuse lookahead token after shifting the error
+ /* Else will try to reuse look-ahead token after shifting the error
token. */
goto yyerrlab1;
# Declare the variables that are global, or local to YYPARSE if
# pure-parser.
m4_define([b4_declare_parser_variables],
-[/* The lookahead symbol. */
+[/* The look-ahead symbol. */
int yychar;
-/* The semantic value of the lookahead symbol. */
+/* The semantic value of the look-ahead symbol. */
YYSTYPE yylval;
/* Number of syntax errors so far. */
int yynerrs;b4_location_if([
-/* Location data for the lookahead symbol. */
+/* Location data for the look-ahead symbol. */
YYLTYPE yylloc;])
])
m4_divert_pop([KILL])dnl# ====================== End of M4 code.
int yyresult;
/* Number of tokens to shift before error messages enabled. */
int yyerrstatus;
- /* Lookahead token as an internal (translated) token number. */
+ /* Look-ahead token as an internal (translated) token number. */
int yytoken = 0;
/* Three stacks and their tools:
yybackup:
/* Do appropriate processing given the current state. */
-/* Read a lookahead token if we need one and don't already have one. */
+/* Read a look-ahead token if we need one and don't already have one. */
/* yyresume: */
- /* First try to decide what to do without reference to lookahead token. */
+ /* First try to decide what to do without reference to look-ahead token. */
yyn = yypact[yystate];
if (yyn == YYPACT_NINF)
goto yydefault;
- /* Not known => get a lookahead token if don't already have one. */
+ /* Not known => get a look-ahead token if don't already have one. */
- /* YYCHAR is either YYEMPTY or YYEOF or a valid lookahead symbol. */
+ /* YYCHAR is either YYEMPTY or YYEOF or a valid look-ahead symbol. */
if (yychar == YYEMPTY)
{
YYDPRINTF ((stderr, "Reading a token: "));
if (yyn == YYFINAL)
YYACCEPT;
- /* Shift the lookahead token. */
+ /* Shift the look-ahead token. */
YYDPRINTF ((stderr, "Shifting token %s, ", yytname[yytoken]));
/* Discard the token being shifted unless it is eof. */
if (yyerrstatus == 3)
{
- /* If just tried and failed to reuse lookahead token after an
+ /* If just tried and failed to reuse look-ahead token after an
error, discard it. */
if (yychar <= YYEOF)
}
}
- /* Else will try to reuse lookahead token after shifting the error
+ /* Else will try to reuse look-ahead token after shifting the error
token. */
goto yyerrlab1;
Bison produces @emph{deterministic} parsers that choose uniquely
when to reduce and which reduction to apply
-based on a summary of the preceding input and on one extra token of lookahead.
+based on a summary of the preceding input and on one extra token of look-ahead.
As a result, normal Bison handles a proper subset of the family of
context-free languages.
Ambiguous grammars, since they have strings with more than one possible
sequence of reductions cannot have deterministic parsers in this sense.
The same is true of languages that require more than one symbol of
-lookahead, since the parser lacks the information necessary to make a
+look-ahead, since the parser lacks the information necessary to make a
decision at the point it must be made in a shift-reduce parser.
Finally, as previously mentioned (@pxref{Mystery Conflicts}),
there are languages where Bison's particular choice of how to
symbol (here, @code{exp}). When the parser returns to this state right
after having reduced a rule that produced an @code{exp}, the control
flow jumps to state 2. If there is no such transition on a nonterminal
-symbol, and the lookahead is a @code{NUM}, then this token is shifted on
+symbol, and the look-ahead is a @code{NUM}, then this token is shifted on
the parse stack, and the control flow jumps to state 1. Any other
-lookahead triggers a syntax error.''
+look-ahead triggers a syntax error.''
@cindex core, item set
@cindex item set core
@cindex kernel, item set
@cindex item set core
Even though the only active rule in state 0 seems to be rule 0, the
-report lists @code{NUM} as a lookahead symbol because @code{NUM} can be
+report lists @code{NUM} as a look-ahead token because @code{NUM} can be
at the beginning of any rule deriving an @code{exp}. By default Bison
reports the so-called @dfn{core} or @dfn{kernel} of the item set, but if
you want to see more detail you can invoke @command{bison} with
@end example
@noindent
-the rule 5, @samp{exp: NUM;}, is completed. Whatever the lookahead
+the rule 5, @samp{exp: NUM;}, is completed. Whatever the look-ahead token
(@samp{$default}), the parser will reduce it. If it was coming from
state 0, then, after this reduction it will return to state 0, and will
jump to state 2 (@samp{exp: go to state 2}).
@noindent
In state 2, the automaton can only shift a symbol. For instance,
-because of the item @samp{exp -> exp . '+' exp}, if the lookahead if
+because of the item @samp{exp -> exp . '+' exp}, if the look-ahead if
@samp{+}, it will be shifted on the parse stack, and the automaton
control will jump to state 4, corresponding to the item @samp{exp -> exp
'+' . exp}. Since there is no default action, any other token than
$default reduce using rule 1 (exp)
@end example
-Indeed, there are two actions associated to the lookahead @samp{/}:
+Indeed, there are two actions associated to the look-ahead @samp{/}:
either shifting (and going to state 7), or reducing rule 1. The
conflict means that either the grammar is ambiguous, or the parser lacks
information to make the right decision. Indeed the grammar is
shifting the next token and going to the corresponding state, or
reducing a single rule. In the other cases, i.e., when shifting
@emph{and} reducing is possible or when @emph{several} reductions are
-possible, the lookahead is required to select the action. State 8 is
-one such state: if the lookahead is @samp{*} or @samp{/} then the action
+possible, the look-ahead is required to select the action. State 8 is
+one such state: if the look-ahead is @samp{*} or @samp{/} then the action
is shifting, otherwise the action is reducing rule 1. In other words,
the first two items, corresponding to rule 1, are not eligible when the
-lookahead is @samp{*}, since we specified that @samp{*} has higher
-precedence that @samp{+}. More generally, some items are eligible only
-with some set of possible lookaheads. When run with
-@option{--report=lookahead}, Bison specifies these lookaheads:
+look-ahead token is @samp{*}, since we specified that @samp{*} has higher
+precedence than @samp{+}. More generally, some items are eligible only
+with some set of possible look-ahead tokens. When run with
+@option{--report=look-ahead}, Bison specifies these look-ahead tokens:
@example
state 8
Description of the grammar, conflicts (resolved and unresolved), and
@acronym{LALR} automaton.
-@item lookahead
+@item look-ahead
Implies @code{state} and augments the description of the automaton with
-each rule's lookahead set.
+each rule's look-ahead set.
@item itemset
Implies @code{state} and augments the description of the automaton with
static char *conflicts = NULL;
struct obstack solved_conflicts_obstack;
-static bitset shiftset;
-static bitset lookaheadset;
+static bitset shift_set;
+static bitset look_ahead_set;
\f
transitions *trans = s->transitions;
int i;
- bitset_reset (lookaheadset, token);
+ bitset_reset (look_ahead_set, token);
for (i = 0; i < trans->num; i++)
if (!TRANSITION_IS_DISABLED (trans, i)
&& TRANSITION_SYMBOL (trans, i) == token)
}
-/*-------------------------------------------------------------------.
-| Turn off the reduce recorded for the specified token for the |
-| specified lookahead. Used when we resolve a shift-reduce conflict |
-| in favor of the shift. |
-`-------------------------------------------------------------------*/
+/*--------------------------------------------------------------------.
+| Turn off the reduce recorded for the specified token for the |
+| specified look-ahead. Used when we resolve a shift-reduce conflict |
+| in favor of the shift. |
+`--------------------------------------------------------------------*/
static void
-flush_reduce (bitset lookaheads, int token)
+flush_reduce (bitset look_ahead_tokens, int token)
{
- bitset_reset (lookaheads, token);
+ bitset_reset (look_ahead_tokens, token);
}
| rule has a precedence. A conflict is resolved by modifying the |
| shift or reduce tables so that there is no longer a conflict. |
| |
-| LOOKAHEAD is the number of the lookahead bitset to consider. |
+| RULENO is the number of the look-ahead bitset to consider. |
| |
| ERRORS can be used to store discovered explicit errors. |
`------------------------------------------------------------------*/
/* Find the rule to reduce by to get precedence of reduction. */
rule *redrule = reds->rules[ruleno];
int redprec = redrule->prec->prec;
- bitset lookaheads = reds->lookaheads[ruleno];
+ bitset look_ahead_tokens = reds->look_ahead_tokens[ruleno];
int nerrs = 0;
for (i = 0; i < ntokens; i++)
- if (bitset_test (lookaheads, i)
- && bitset_test (lookaheadset, i)
+ if (bitset_test (look_ahead_tokens, i)
+ && bitset_test (look_ahead_set, i)
&& symbols[i]->prec)
{
/* Shift-reduce conflict occurs for token number i
else if (symbols[i]->prec > redprec)
{
log_resolution (redrule, i, shift_resolution);
- flush_reduce (lookaheads, i);
+ flush_reduce (look_ahead_tokens, i);
}
else
/* Matching precedence levels.
{
case right_assoc:
log_resolution (redrule, i, right_resolution);
- flush_reduce (lookaheads, i);
+ flush_reduce (look_ahead_tokens, i);
break;
case left_assoc:
case non_assoc:
log_resolution (redrule, i, nonassoc_resolution);
flush_shift (s, i);
- flush_reduce (lookaheads, i);
+ flush_reduce (look_ahead_tokens, i);
/* Record an explicit error for this token. */
errors[nerrs++] = symbols[i];
break;
| Solve the S/R conflicts of state S using the |
| precedence/associativity, and flag it inconsistent if it still has |
| conflicts. ERRORS can be used as storage to compute the list of |
-| lookaheads on which S raises a syntax error (%nonassoc). |
+| look-ahead tokens on which S raises a syntax error (%nonassoc). |
`-------------------------------------------------------------------*/
static void
if (s->consistent)
return;
- bitset_zero (lookaheadset);
+ bitset_zero (look_ahead_set);
FOR_EACH_SHIFT (trans, i)
- bitset_set (lookaheadset, TRANSITION_SYMBOL (trans, i));
+ bitset_set (look_ahead_set, TRANSITION_SYMBOL (trans, i));
- /* Loop over all rules which require lookahead in this state. First
+ /* Loop over all rules which require look-ahead in this state. First
check for shift-reduce conflict, and try to resolve using
precedence. */
for (i = 0; i < reds->num; ++i)
if (reds->rules[i]->prec && reds->rules[i]->prec->prec
- && !bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
+ && !bitset_disjoint_p (reds->look_ahead_tokens[i], look_ahead_set))
resolve_sr_conflict (s, i, errors);
- /* Loop over all rules which require lookahead in this state. Check
+ /* Loop over all rules which require look-ahead in this state. Check
for conflicts not resolved above. */
for (i = 0; i < reds->num; ++i)
{
- if (!bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
+ if (!bitset_disjoint_p (reds->look_ahead_tokens[i], look_ahead_set))
conflicts[s->number] = 1;
- bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);
+ bitset_or (look_ahead_set, look_ahead_set, reds->look_ahead_tokens[i]);
}
}
conflicts_solve (void)
{
state_number i;
- /* List of lookaheads on which we explicitly raise a syntax error. */
+ /* List of look-ahead tokens on which we explicitly raise a syntax error. */
symbol **errors = MALLOC (errors, ntokens + 1);
CALLOC (conflicts, nstates);
- shiftset = bitset_create (ntokens, BITSET_FIXED);
- lookaheadset = bitset_create (ntokens, BITSET_FIXED);
+ shift_set = bitset_create (ntokens, BITSET_FIXED);
+ look_ahead_set = bitset_create (ntokens, BITSET_FIXED);
obstack_init (&solved_conflicts_obstack);
for (i = 0; i < nstates; i++)
if (!trans)
return 0;
- bitset_zero (lookaheadset);
- bitset_zero (shiftset);
+ bitset_zero (look_ahead_set);
+ bitset_zero (shift_set);
FOR_EACH_SHIFT (trans, i)
- bitset_set (shiftset, TRANSITION_SYMBOL (trans, i));
+ bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
for (i = 0; i < reds->num; ++i)
- bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);
+ bitset_or (look_ahead_set, look_ahead_set, reds->look_ahead_tokens[i]);
- bitset_and (lookaheadset, lookaheadset, shiftset);
+ bitset_and (look_ahead_set, look_ahead_set, shift_set);
- src_count = bitset_count (lookaheadset);
+ src_count = bitset_count (look_ahead_set);
return src_count;
}
int count = 0;
int j;
for (j = 0; j < reds->num; ++j)
- if (bitset_test (reds->lookaheads[j], i))
+ if (bitset_test (reds->look_ahead_tokens[j], i))
count++;
if (count >= 2)
/*--------------------------------------------------------.
| Total the number of S/R and R/R conflicts. Unlike the |
| code in conflicts_output, however, count EACH pair of |
-| reductions for the same state and lookahead as one |
+| reductions for the same state and look-ahead as one |
| conflict. |
`--------------------------------------------------------*/
conflicts_free (void)
{
XFREE (conflicts);
- bitset_free (shiftset);
- bitset_free (lookaheadset);
+ bitset_free (shift_set);
+ bitset_free (look_ahead_set);
obstack_free (&solved_conflicts_obstack, NULL);
}
"none",
"state", "states",
"itemset", "itemsets",
- "lookahead", "lookaheads",
+ "look-ahead", "lookahead", "lookaheads",
"solved",
"all",
0
report_none,
report_states, report_states,
report_states | report_itemsets, report_states | report_itemsets,
- report_states | report_lookaheads, report_states | report_lookaheads,
+ report_states | report_look_ahead_tokens,
+ report_states | report_look_ahead_tokens,
+ report_states | report_look_ahead_tokens,
report_states | report_solved_conflicts,
report_all
};
THINGS is a list of comma separated words that can include:\n\
`state' describe the states\n\
`itemset' complete the core item sets with their closure\n\
- `lookahead' explicitly associate lookaheads to items\n\
+ `look-ahead' explicitly associate look-ahead tokens to items\n\
`solved' describe shift/reduce conflicts solving\n\
`all' include all the above information\n\
`none' disable the report\n\
/* Parse command line arguments for bison.
- Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003
+ Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004
Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
report_none = 0,
report_states = 1 << 0,
report_itemsets = 1 << 1,
- report_lookaheads = 1 << 2,
+ report_look_ahead_tokens= 1 << 2,
report_solved_conflicts = 1 << 3,
report_all = ~0
};
/* Compute look-ahead criteria for Bison.
- Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003
+ Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004
Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
/* Compute how to make the finite state machine deterministic; find
- which rules need lookahead in each state, and which lookahead
+ which rules need look-ahead in each state, and which look-ahead
tokens they accept. */
#include "system.h"
{
int ri = state_reduction_find (s, r);
goto_list *sp = MALLOC (sp, 1);
- sp->next = lookback[(s->reductions->lookaheads - LA) + ri];
+ sp->next = lookback[(s->reductions->look_ahead_tokens - LA) + ri];
sp->value = gotono;
- lookback[(s->reductions->lookaheads - LA) + ri] = sp;
+ lookback[(s->reductions->look_ahead_tokens - LA) + ri] = sp;
}
static void
-compute_lookaheads (void)
+compute_look_ahead_tokens (void)
{
size_t i;
goto_list *sp;
}
-/*-----------------------------------------------------------.
-| Count the number of lookaheads required for S (NLOOKAHEADS |
-| member). |
-`-----------------------------------------------------------*/
+/*-----------------------------------------------------.
+| Count the number of look-ahead tokens required for S |
+| (N_LOOK_AHEAD_TOKENS member). |
+`-----------------------------------------------------*/
static int
-state_lookaheads_count (state *s)
+state_look_ahead_tokens_count (state *s)
{
int k;
- int nlookaheads = 0;
+ int n_look_ahead_tokens = 0;
reductions *rp = s->reductions;
transitions *sp = s->transitions;
- /* We need a lookahead either to distinguish different
+ /* We need a look-ahead either to distinguish different
reductions (i.e., there are two or more), or to distinguish a
reduction from a shift. Otherwise, it is straightforward,
and the state is `consistent'. */
if (rp->num > 1
|| (rp->num == 1 && sp->num &&
!TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
- nlookaheads += rp->num;
+ n_look_ahead_tokens += rp->num;
else
s->consistent = 1;
break;
}
- return nlookaheads;
+ return n_look_ahead_tokens;
}
-/*----------------------------------------------.
-| Compute LA, NLA, and the lookaheads members. |
-`----------------------------------------------*/
+/*-----------------------------------------------------.
+| Compute LA, NLA, and the look_ahead_tokens members. |
+`-----------------------------------------------------*/
static void
initialize_LA (void)
state_number i;
bitsetv pLA;
- /* Compute the total number of reductions requiring a lookahead. */
+ /* Compute the total number of reductions requiring a look-ahead. */
nLA = 0;
for (i = 0; i < nstates; i++)
- nLA += state_lookaheads_count (states[i]);
+ nLA += state_look_ahead_tokens_count (states[i]);
/* Avoid having to special case 0. */
if (!nLA)
nLA = 1;
pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
CALLOC (lookback, nLA);
- /* Initialize the members LOOKAHEADS for each state which reductions
- require lookaheads. */
+ /* Initialize the members LOOK_AHEAD_TOKENS for each state whose reductions
+ require look-ahead tokens. */
for (i = 0; i < nstates; i++)
{
- int count = state_lookaheads_count (states[i]);
+ int count = state_look_ahead_tokens_count (states[i]);
if (count)
{
- states[i]->reductions->lookaheads = pLA;
+ states[i]->reductions->look_ahead_tokens = pLA;
pLA += count;
}
}
}
-/*---------------------------------------.
-| Output the lookaheads for each state. |
-`---------------------------------------*/
+/*----------------------------------------------.
+| Output the look-ahead tokens for each state. |
+`----------------------------------------------*/
static void
-lookaheads_print (FILE *out)
+look_ahead_tokens_print (FILE *out)
{
state_number i;
int j, k;
- fprintf (out, "Lookaheads: BEGIN\n");
+ fprintf (out, "Look-ahead tokens: BEGIN\n");
for (i = 0; i < nstates; ++i)
{
reductions *reds = states[i]->reductions;
bitset_iterator iter;
- int nlookaheads = 0;
+ int n_look_ahead_tokens = 0;
- if (reds->lookaheads)
+ if (reds->look_ahead_tokens)
for (k = 0; k < reds->num; ++k)
- if (reds->lookaheads[k])
- ++nlookaheads;
+ if (reds->look_ahead_tokens[k])
+ ++n_look_ahead_tokens;
- fprintf (out, "State %d: %d lookaheads\n",
- i, nlookaheads);
+ fprintf (out, "State %d: %d look-ahead tokens\n",
+ i, n_look_ahead_tokens);
- if (reds->lookaheads)
+ if (reds->look_ahead_tokens)
for (j = 0; j < reds->num; ++j)
- BITSET_FOR_EACH (iter, reds->lookaheads[j], k, 0)
+ BITSET_FOR_EACH (iter, reds->look_ahead_tokens[j], k, 0)
{
fprintf (out, " on %d (%s) -> rule %d\n",
k, symbols[k]->tag,
reds->rules[j]->number);
};
}
- fprintf (out, "Lookaheads: END\n");
+ fprintf (out, "Look-ahead tokens: END\n");
}
void
initialize_F ();
build_relations ();
compute_FOLLOWS ();
- compute_lookaheads ();
+ compute_look_ahead_tokens ();
if (trace_flag & trace_sets)
- lookaheads_print (stderr);
+ look_ahead_tokens_print (stderr);
}
{
state_number s;
for (s = 0; s < nstates; ++s)
- states[s]->reductions->lookaheads = NULL;
+ states[s]->reductions->look_ahead_tokens = NULL;
bitsetv_free (LA);
}
# include "state.h"
/* Compute how to make the finite state machine deterministic; find
- which rules need lookahead in each state, and which lookahead
+ which rules need look-ahead in each state, and which look-ahead
tokens they accept. */
void lalr (void);
-/* Release the information related to lookaheads. Can be performed
+/* Release the information related to look-ahead tokens. Can be performed
once the action tables are computed. */
void lalr_free (void);
/* Top level entry point of Bison.
- Copyright (C) 1984, 1986, 1989, 1992, 1995, 2000, 2001, 2002
+ Copyright (C) 1984, 1986, 1989, 1992, 1995, 2000, 2001, 2002, 2004
Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
timevar_pop (TV_LALR);
/* Find and record any conflicts: places where one token of
- lookahead is not enough to disambiguate the parsing. In file
+ look-ahead is not enough to disambiguate the parsing. In file
conflicts. Also resolve s/r conflicts based on precedence
declarations. */
timevar_push (TV_CONFLICTS);
if (complaint_issued)
goto finish;
- /* Lookaheads are no longer needed. */
+ /* Look-ahead tokens are no longer needed. */
timevar_push (TV_FREE);
lalr_free ();
timevar_pop (TV_FREE);
prepare_actions (void)
{
/* Figure out the actions for the specified state, indexed by
- lookahead token type. */
+ look-ahead token type. */
muscle_insert_rule_number_table ("defact", yydefact,
yydefact[0], 1, nstates);
/* Print information on generated parser, for bison,
- Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003
+ Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004
Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
#include "state.h"
#include "symtab.h"
-static bitset shiftset;
-static bitset lookaheadset;
+static bitset shift_set;
+static bitset look_ahead_set;
#if 0
static void
for (/* Nothing */; *sp >= 0; ++sp)
fprintf (out, " %s", symbols[*sp]->tag);
- /* Display the lookaheads? */
- if (report_flag & report_lookaheads)
- state_rule_lookaheads_print (s, &rules[r], out);
+ /* Display the look-ahead tokens? */
+ if (report_flag & report_look_ahead_tokens)
+ state_rule_look_ahead_tokens_print (s, &rules[r], out);
fputc ('\n', out);
}
size_t width = 0;
int i;
- /* Compute the width of the lookaheads column. */
+ /* Compute the width of the look-ahead token column. */
for (i = 0; i < trans->num; i++)
if (!TRANSITION_IS_DISABLED (trans, i)
&& TRANSITION_IS_SHIFT (trans, i) == display_transitions_p)
fputc ('\n', out);
width += 2;
- /* Report lookaheads and shifts. */
+ /* Report look-ahead tokens and shifts. */
for (i = 0; i < trans->num; i++)
if (!TRANSITION_IS_DISABLED (trans, i)
&& TRANSITION_IS_SHIFT (trans, i) == display_transitions_p)
size_t width = 0;
int i;
- /* Compute the width of the lookaheads column. */
+ /* Compute the width of the look-ahead token column. */
for (i = 0; i < errp->num; ++i)
if (errp->symbols[i])
max_length (&width, errp->symbols[i]->tag);
fputc ('\n', out);
width += 2;
- /* Report lookaheads and errors. */
+ /* Report look-ahead tokens and errors. */
for (i = 0; i < errp->num; ++i)
if (errp->symbols[i])
{
int cmax = 0;
int i;
- /* No need for a lookahead. */
+ /* No need for a look-ahead. */
if (s->consistent)
return reds->rules[0];
- /* 1. Each reduction is possibly masked by the lookaheads on which
+ /* 1. Each reduction is possibly masked by the look-ahead tokens on which
we shift (S/R conflicts)... */
- bitset_zero (shiftset);
+ bitset_zero (shift_set);
{
transitions *trans = s->transitions;
FOR_EACH_SHIFT (trans, i)
default rule. */
if (TRANSITION_IS_ERROR (trans, i))
return NULL;
- bitset_set (shiftset, TRANSITION_SYMBOL (trans, i));
+ bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
}
}
- /* 2. Each reduction is possibly masked by the lookaheads on which
+ /* 2. Each reduction is possibly masked by the look-ahead tokens on which
we raise an error (due to %nonassoc). */
{
errs *errp = s->errs;
for (i = 0; i < errp->num; i++)
if (errp->symbols[i])
- bitset_set (shiftset, errp->symbols[i]->number);
+ bitset_set (shift_set, errp->symbols[i]->number);
}
for (i = 0; i < reds->num; ++i)
{
int count = 0;
- /* How many non-masked lookaheads are there for this reduction?
- */
- bitset_andn (lookaheadset, reds->lookaheads[i], shiftset);
- count = bitset_count (lookaheadset);
+ /* How many non-masked look-ahead tokens are there for this
+ reduction? */
+ bitset_andn (look_ahead_set, reds->look_ahead_tokens[i], shift_set);
+ count = bitset_count (look_ahead_set);
if (count > cmax)
{
/* 3. And finally, each reduction is possibly masked by previous
reductions (in R/R conflicts, we keep the first reductions).
*/
- bitset_or (shiftset, shiftset, reds->lookaheads[i]);
+ bitset_or (shift_set, shift_set, reds->look_ahead_tokens[i]);
}
return default_rule;
}
-/*--------------------------------------------------------------------.
-| Report a reduction of RULE on LOOKAHEADS (which can be `default'). |
-| If not ENABLED, the rule is masked by a shift or a reduce (S/R and |
-| R/R conflicts). |
-`--------------------------------------------------------------------*/
+/*--------------------------------------------------------------------------.
+| Report a reduction of RULE on LOOK_AHEAD_TOKEN (which can be `default'). |
+| If not ENABLED, the rule is masked by a shift or a reduce (S/R and |
+| R/R conflicts). |
+`--------------------------------------------------------------------------*/
static void
print_reduction (FILE *out, size_t width,
- const char *lookahead,
+ const char *look_ahead_token,
rule *r, bool enabled)
{
int j;
- fprintf (out, " %s", lookahead);
- for (j = width - strlen (lookahead); j > 0; --j)
+ fprintf (out, " %s", look_ahead_token);
+ for (j = width - strlen (look_ahead_token); j > 0; --j)
fputc (' ', out);
if (!enabled)
fputc ('[', out);
default_rule = state_default_rule (s);
- bitset_zero (shiftset);
+ bitset_zero (shift_set);
FOR_EACH_SHIFT (trans, i)
- bitset_set (shiftset, TRANSITION_SYMBOL (trans, i));
+ bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
- /* Compute the width of the lookaheads column. */
+ /* Compute the width of the look-ahead token column. */
if (default_rule)
width = strlen (_("$default"));
- if (reds->lookaheads)
+ if (reds->look_ahead_tokens)
for (i = 0; i < ntokens; i++)
{
- bool count = bitset_test (shiftset, i);
+ bool count = bitset_test (shift_set, i);
for (j = 0; j < reds->num; ++j)
- if (bitset_test (reds->lookaheads[j], i))
+ if (bitset_test (reds->look_ahead_tokens[j], i))
{
if (! count)
{
fputc ('\n', out);
width += 2;
- /* Report lookaheads (or $default) and reductions. */
- if (reds->lookaheads)
+ /* Report look-ahead tokens (or $default) and reductions. */
+ if (reds->look_ahead_tokens)
for (i = 0; i < ntokens; i++)
{
bool defaulted = false;
- bool count = bitset_test (shiftset, i);
+ bool count = bitset_test (shift_set, i);
for (j = 0; j < reds->num; ++j)
- if (bitset_test (reds->lookaheads[j], i))
+ if (bitset_test (reds->look_ahead_tokens[j], i))
{
if (! count)
{
if (report_flag & report_itemsets)
new_closure (nritems);
/* Storage for print_reductions. */
- shiftset = bitset_create (ntokens, BITSET_FIXED);
- lookaheadset = bitset_create (ntokens, BITSET_FIXED);
+ shift_set = bitset_create (ntokens, BITSET_FIXED);
+ look_ahead_set = bitset_create (ntokens, BITSET_FIXED);
for (i = 0; i < nstates; i++)
print_state (out, states[i]);
- bitset_free (shiftset);
- bitset_free (lookaheadset);
+ bitset_free (shift_set);
+ bitset_free (look_ahead_set);
if (report_flag & report_itemsets)
free_closure ();
/* Output a VCG description on generated parser, for Bison,
- Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
for (/* Nothing */; *sp >= 0; ++sp)
obstack_fgrow1 (oout, " %s", symbols[*sp]->tag);
- /* Experimental feature: display the lookaheads. */
- if (report_flag & report_lookaheads)
+ /* Experimental feature: display the look-ahead tokens. */
+ if (report_flag & report_look_ahead_tokens)
{
/* Find the reduction we are handling. */
reductions *reds = s->reductions;
int redno = state_reduction_find (s, &rules[r]);
/* Print them if there are. */
- if (reds->lookaheads && redno != -1)
+ if (reds->look_ahead_tokens && redno != -1)
{
bitset_iterator biter;
int k;
char const *sep = "";
obstack_sgrow (oout, "[");
- BITSET_FOR_EACH (biter, reds->lookaheads[redno], k, 0)
+ BITSET_FOR_EACH (biter, reds->look_ahead_tokens[redno], k, 0)
{
obstack_fgrow2 (oout, "%s%s", sep, symbols[k]->tag);
sep = ", ";
size_t rules_size = num * sizeof *reds;
reductions *res = xmalloc (offsetof (reductions, rules) + rules_size);
res->num = num;
- res->lookaheads = NULL;
+ res->look_ahead_tokens = NULL;
memcpy (res->rules, reds, rules_size);
return res;
}
-/*-----------------------------------------------------.
-| Print on OUT all the lookaheads such that S wants to |
-| reduce R. |
-`-----------------------------------------------------*/
+/*---------------------------------------------------.
+| Print on OUT all the look-ahead tokens such that S |
+| wants to reduce R. |
+`---------------------------------------------------*/
void
-state_rule_lookaheads_print (state *s, rule *r, FILE *out)
+state_rule_look_ahead_tokens_print (state *s, rule *r, FILE *out)
{
/* Find the reduction we are handling. */
reductions *reds = s->reductions;
int red = state_reduction_find (s, r);
/* Print them if there are. */
- if (reds->lookaheads && red != -1)
+ if (reds->look_ahead_tokens && red != -1)
{
bitset_iterator biter;
int k;
char const *sep = "";
fprintf (out, " [");
- BITSET_FOR_EACH (biter, reds->lookaheads[red], k, 0)
+ BITSET_FOR_EACH (biter, reds->look_ahead_tokens[red], k, 0)
{
fprintf (out, "%s%s", sep, symbols[k]->tag);
sep = ", ";
Each core contains a vector of NITEMS items which are the indices
in the RITEMS vector of the items that are selected in this state.
- The two types of actions are shifts/gotos (push the lookahead token
+ The two types of actions are shifts/gotos (push the look-ahead token
and read another/goto to the state designated by a nterm) and
reductions (combine the last n things on the stack via a rule,
replace them with the symbol that the rule derives, and leave the
- lookahead token alone). When the states are generated, these
+ look-ahead token alone). When the states are generated, these
actions are represented in two other lists.
Each transition structure describes the possible transitions out
typedef struct
{
short int num;
- bitset *lookaheads;
+ bitset *look_ahead_tokens;
rule *rules[1];
} reductions;
reductions *reductions;
errs *errs;
- /* Nonzero if no lookahead is needed to decide what to do in state S. */
+ /* Nonzero if no look-ahead is needed to decide what to do in state S. */
char consistent;
/* If some conflicts were solved thanks to precedence/associativity,
/* Set the errs of STATE. */
void state_errs_set (state *s, int num, symbol **errors);
-/* Print on OUT all the lookaheads such that this STATE wants to
+/* Print on OUT all the look-ahead tokens such that this STATE wants to
reduce R. */
-void state_rule_lookaheads_print (state *s, rule *r, FILE *out);
+void state_rule_look_ahead_tokens_print (state *s, rule *r, FILE *out);
/* Create/destroy the states hash table. */
void state_hash_new (void);
/* Find all reductions for token J, and record all that do not
match ACTROW[J]. */
for (i = 0; i < reds->num; i += 1)
- if (bitset_test (reds->lookaheads[i], j)
+ if (bitset_test (reds->look_ahead_tokens[i], j)
&& (actrow[j]
!= rule_number_as_item_number (reds->rules[i]->number)))
{
/*------------------------------------------------------------------.
-| Decide what to do for each type of token if seen as the lookahead |
-| token in specified state. The value returned is used as the |
+| Decide what to do for each type of token if seen as the |
+| look-ahead in specified state. The value returned is used as the |
| default action (yydefact) for the state. In addition, ACTROW is |
| filled with what to do for each kind of token, index by symbol |
| number, with zero meaning do the default action. The value |
| situation is an error. The parser recognizes this value |
| specially. |
| |
-| This is where conflicts are resolved. The loop over lookahead |
+| This is where conflicts are resolved. The loop over look-ahead |
| rules considered lower-numbered rules last, and the last rule |
| considered that likes a token gets to handle it. |
| |
for (i = 0; i < ntokens; i++)
actrow[i] = conflrow[i] = 0;
- if (reds->lookaheads)
+ if (reds->look_ahead_tokens)
{
int j;
bitset_iterator biter;
/* loop over all the rules available here which require
- lookahead (in reverse order to give precedence to the first
+ look-ahead (in reverse order to give precedence to the first
rule) */
for (i = reds->num - 1; i >= 0; --i)
/* and find each token which the rule finds acceptable
to come next */
- BITSET_FOR_EACH (biter, reds->lookaheads[i], j, 0)
+ BITSET_FOR_EACH (biter, reds->look_ahead_tokens[i], j, 0)
{
/* and record this rule as the rule to use if that
token follows. */
/*------------------------------------------------------------------.
| Figure out the actions for the specified state, indexed by |
-| lookahead token type. |
+| look-ahead token type. |
| |
| The YYDEFACT table is output now. The detailed info is saved for |
| putting into YYTABLE later. |
/* Prepare the LALR and GLR parser tables.
- Copyright (C) 2002 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2004 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
something else to do.
YYPACT[S] = index in YYTABLE of the portion describing state S.
- The lookahead token's type is used to index that portion to find
+ The look-ahead token's type is used to index that portion to find
out what to do.
If the value in YYTABLE is positive, we shift the token and go to
#
# - test the action associated to `error'
#
-# - check the lookahead that triggers an error is not discarded
-# when we enter error recovery. Below, the lookahead causing the
+# - check the look-ahead that triggers an error is not discarded
+# when we enter error recovery. Below, the look-ahead causing the
# first error is ")", which is needed to recover from the error and
# produce the "0" that triggers the "0 != 1" error.
#
calc: error: 4444 != 1])
# The same, but this time exercising explicitly triggered syntax errors.
-# POSIX says the lookahead causing the error should not be discarded.
+# POSIX says the look-ahead causing the error should not be discarded.
_AT_CHECK_CALC_ERROR([$1], [0], [(!) + (0 0) = 1], [62],
[1.9: syntax error, unexpected "number"
calc: error: 2222 != 1])
# Torturing Bison. -*- Autotest -*-
-# Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+# Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc.
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
-# AT_DATA_LOOKAHEADS_GRAMMAR(FILE-NAME, SIZE)
+# AT_DATA_LOOK_AHEAD_TOKENS_GRAMMAR(FILE-NAME, SIZE)
# -------------------------------------------
# Create FILE-NAME, containing a self checking parser for a grammar
-# requiring SIZE lookaheads.
-m4_define([AT_DATA_LOOKAHEADS_GRAMMAR],
+# requiring SIZE look-ahead tokens.
+m4_define([AT_DATA_LOOK_AHEAD_TOKENS_GRAMMAR],
[AT_DATA([[gengram.pl]],
[[#! /usr/bin/perl -w
])
-## ----------------- ##
-## Many lookaheads. ##
-## ----------------- ##
+## ------------------------ ##
+## Many look-ahead tokens. ##
+## ------------------------ ##
-AT_SETUP([Many lookaheads])
+AT_SETUP([Many look-ahead tokens])
-AT_DATA_LOOKAHEADS_GRAMMAR([input.y], [1000])
+AT_DATA_LOOK_AHEAD_TOKENS_GRAMMAR([input.y], [1000])
# GNU m4 requires about 70 MiB for this test on a 32-bit host.
# Ask for 200 MiB, which should be plenty even on a 64-bit host.
projects / bison.git / commitdiff
