reduced by a state, attach the lookaheads to the reductions.
* src/state.h (state_t): Remove the `lookaheads',
`lookaheads_rule' member.
(reductions_t): Add a `lookaheads' member.
Use a regular array for the `rules'.
* src/state.c (reductions_new): Initialize the lookaheads member
to 0.
(state_rule_lookaheads_print): Adjust.
* src/state.h, src/state.c (state_reductions_find): New.
* src/conflicts.c (resolve_sr_conflict, set_conflicts)
(count_rr_conflicts): Adjust.
* src/lalr.c (LArule): Remove.
(add_lookback_edge): Adjust.
(state_lookaheads_count): New.
(states_lookaheads_initialize): Merge into...
(initialize_LA): this.
(lalr_free): Adjust.
* src/main.c (main): Don't free nullable and derives too early: it
is used by --verbose.
* src/print.c, src/print_graph.c, src/tables.c: Adjust.
+2002-08-01 Akim Demaille <akim@epita.fr>
+
+ Instead of attaching lookaheads and duplicating the rules being
+ reduced by a state, attach the lookaheads to the reductions.
+
+ * src/state.h (state_t): Remove the `lookaheads',
+ `lookaheads_rule' member.
+ (reductions_t): Add a `lookaheads' member.
+ Use a regular array for the `rules'.
+ * src/state.c (reductions_new): Initialize the lookaheads member
+ to 0.
+ (state_rule_lookaheads_print): Adjust.
+ * src/state.h, src/state.c (state_reductions_find): New.
+ * src/conflicts.c (resolve_sr_conflict, set_conflicts)
+ (count_rr_conflicts): Adjust.
+ * src/lalr.c (LArule): Remove.
+ (add_lookback_edge): Adjust.
+ (state_lookaheads_count): New.
+ (states_lookaheads_initialize): Merge into...
+ (initialize_LA): this.
+ (lalr_free): Adjust.
+ * src/main.c (main): Don't free nullable and derives too early: it
+ is used by --verbose.
+ * src/print.c, src/print_graph.c, src/tables.c: Adjust.
+
2002-08-01 Akim Demaille <akim@epita.fr>
* src/derives.h, src/derives.c (derives): A `rule_t***' instead of
`------------------------------------------------------------------*/
static void
-resolve_sr_conflict (state_t *state, int lookahead,
+resolve_sr_conflict (state_t *state, int ruleno,
symbol_t **errs)
{
symbol_number_t i;
+ reductions_t *reds = state->reductions;
/* Find the rule to reduce by to get precedence of reduction. */
- rule_t *redrule = state->lookaheads_rule[lookahead];
+ rule_t *redrule = reds->rules[ruleno];
int redprec = redrule->prec->prec;
- bitset lookaheads = state->lookaheads[lookahead];
+ bitset lookaheads = reds->lookaheads[ruleno];
int nerrs = 0;
for (i = 0; i < ntokens; i++)
{
int i;
transitions_t *transitions = state->transitions;
+ reductions_t *reds = state->reductions;
if (state->consistent)
return;
/* Loop over all rules which require lookahead in this state. First
check for shift-reduce conflict, and try to resolve using
precedence. */
- for (i = 0; i < state->nlookaheads; ++i)
- if (state->lookaheads_rule[i]->prec
- && state->lookaheads_rule[i]->prec->prec
- && !bitset_disjoint_p (state->lookaheads[i], lookaheadset))
+ for (i = 0; i < reds->num; ++i)
+ if (reds->rules[i]->prec && reds->rules[i]->prec->prec
+ && !bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
{
resolve_sr_conflict (state, i, errs);
break;
/* Loop over all rules which require lookahead in this state. Check
for conflicts not resolved above. */
- for (i = 0; i < state->nlookaheads; ++i)
+ for (i = 0; i < reds->num; ++i)
{
- if (!bitset_disjoint_p (state->lookaheads[i], lookaheadset))
+ if (!bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
conflicts[state->number] = 1;
- bitset_or (lookaheadset, lookaheadset, state->lookaheads[i]);
+ bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);
}
}
int i;
int src_count = 0;
transitions_t *transitions = state->transitions;
+ reductions_t *reds = state->reductions;
if (!transitions)
return 0;
FOR_EACH_SHIFT (transitions, i)
bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i));
- for (i = 0; i < state->nlookaheads; ++i)
- bitset_or (lookaheadset, lookaheadset, state->lookaheads[i]);
+ for (i = 0; i < reds->num; ++i)
+ bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);
bitset_and (lookaheadset, lookaheadset, shiftset);
count_rr_conflicts (state_t *state, int one_per_token)
{
int i;
+ reductions_t *reds = state->reductions;
int rrc_count = 0;
- if (state->nlookaheads < 2)
- return 0;
-
for (i = 0; i < ntokens; i++)
{
int count = 0;
int j;
- for (j = 0; j < state->nlookaheads; ++j)
- if (bitset_test (state->lookaheads[j], i))
+ for (j = 0; j < reds->num; ++j)
+ if (bitset_test (reds->lookaheads[j], i))
count++;
if (count >= 2)
for (i = 0; i < nstates; i++)
{
state_t *s = states[i];
+ reductions_t *reds = s->reductions;
int j;
- for (j = 0; j < s->reductions->num; ++j)
- used_rules[s->reductions->rules[j]->number] = TRUE;
+ for (j = 0; j < reds->num; ++j)
+ used_rules[reds->rules[j]->number] = TRUE;
if (conflicts[i])
{
fprintf (out, _("State %d contains "), i);
} goto_list_t;
-/* LARULE is a vector which records the rules that need lookahead in
- various states. The elements of LARULE that apply to state S are
- those from LOOKAHEADS[S] through LOOKAHEADS[S+1]-1.
-
- If LR is the length of LArule, then a number from 0 to LR-1 can
- specify both a rule and a state where the rule might be applied.
- */
-
-static rule_t **LArule = NULL;
-
/* LA is a LR by NTOKENS matrix of bits. LA[l, i] is 1 if the rule
LArule[l] is applicable in the appropriate state when the next
token is symbol i. If LA[l, i] and LA[l, j] are both 1 for i != j,
-static void
-initialize_LA (void)
-{
- state_number_t i;
- int j;
- rule_t **np;
-
- /* Avoid having to special case 0. */
- if (!nLA)
- nLA = 1;
-
- LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
- LArule = XCALLOC (rule_t *, nLA);
- lookback = XCALLOC (goto_list_t *, nLA);
-
- np = LArule;
- for (i = 0; i < nstates; i++)
- if (!states[i]->consistent)
- for (j = 0; j < states[i]->reductions->num; j++)
- *np++ = states[i]->reductions->rules[j];
-}
-
-
static void
set_goto_map (void)
{
static void
add_lookback_edge (state_t *state, rule_t *rule, int gotono)
{
- int i;
- goto_list_t *sp;
-
- for (i = 0; i < state->nlookaheads; ++i)
- if (state->lookaheads_rule[i] == rule)
- break;
-
- assert (state->lookaheads_rule[i] == rule);
-
- sp = XCALLOC (goto_list_t, 1);
- sp->next = lookback[(state->lookaheads - LA) + i];
+ int r = state_reduction_find (state, rule);
+ goto_list_t *sp = XCALLOC (goto_list_t, 1);
+ sp->next = lookback[(state->reductions->lookaheads - LA) + r];
sp->value = gotono;
- lookback[(state->lookaheads - LA) + i] = sp;
+ lookback[(state->reductions->lookaheads - LA) + r] = sp;
}
}
-/*-------------------------------------------------------------.
-| Count the number of lookaheads required for each state |
-| (NLOOKAHEADS member). Compute the total number of LA, NLA. |
-`-------------------------------------------------------------*/
+/*---------------------------------------------------------------.
+| Count the number of lookaheads required for STATE (NLOOKAHEADS |
+| member). |
+`---------------------------------------------------------------*/
-static void
-states_lookaheads_count (void)
+static int
+state_lookaheads_count (state_t *state)
{
- state_number_t i;
- nLA = 0;
-
- /* Count */
- for (i = 0; i < nstates; i++)
- {
- int k;
- int nlookaheads = 0;
- reductions_t *rp = states[i]->reductions;
- transitions_t *sp = states[i]->transitions;
-
- /* We need a lookahead 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;
- else
- states[i]->consistent = 1;
-
- for (k = 0; k < sp->num; k++)
- if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
- {
- states[i]->consistent = 0;
- break;
- }
+ int k;
+ int nlookaheads = 0;
+ reductions_t *rp = state->reductions;
+ transitions_t *sp = state->transitions;
+
+ /* We need a lookahead 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;
+ else
+ state->consistent = 1;
+
+ for (k = 0; k < sp->num; k++)
+ if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
+ {
+ state->consistent = 0;
+ break;
+ }
- states[i]->nlookaheads = nlookaheads;
- nLA += nlookaheads;
- }
+ return nlookaheads;
}
-/*--------------------------------------.
-| Initializing the lookaheads members. |
-`--------------------------------------*/
+/*----------------------------------------------.
+| Compute LA, NLA, and the lookaheads members. |
+`----------------------------------------------*/
static void
-states_lookaheads_initialize (void)
+initialize_LA (void)
{
state_number_t i;
- bitsetv pLA = LA;
- rule_t **pLArule = LArule;
+ bitsetv pLA;
- /* Initialize the members LOOKAHEADS and LOOKAHEADS_RULE for each
- state. */
+ /* Compute the total number of reductions requiring a lookahead. */
+ nLA = 0;
+ for (i = 0; i < nstates; i++)
+ nLA += state_lookaheads_count (states[i]);
+ /* Avoid having to special case 0. */
+ if (!nLA)
+ nLA = 1;
+
+ pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
+ lookback = XCALLOC (goto_list_t *, nLA);
+
+ /* Initialize the members LOOKAHEADS for each state which reductions
+ require lookaheads. */
for (i = 0; i < nstates; i++)
{
- states[i]->lookaheads = pLA;
- states[i]->lookaheads_rule = pLArule;
- pLA += states[i]->nlookaheads;
- pLArule += states[i]->nlookaheads;
+ int count = state_lookaheads_count (states[i]);
+ if (count)
+ {
+ states[i]->reductions->lookaheads = pLA;
+ pLA += count;
+ }
}
}
fprintf (out, "Lookaheads: BEGIN\n");
for (i = 0; i < nstates; ++i)
{
+ reductions_t *reds = states[i]->reductions;
bitset_iterator iter;
+ int nlookaheads = 0;
+
+ if (reds->lookaheads)
+ for (k = 0; k < reds->num; ++k)
+ if (reds->lookaheads[k])
+ ++nlookaheads;
fprintf (out, "State %d: %d lookaheads\n",
- i, states[i]->nlookaheads);
+ i, nlookaheads);
- for (j = 0; j < states[i]->nlookaheads; ++j)
- BITSET_FOR_EACH (iter, states[i]->lookaheads[j], k, 0)
- {
- fprintf (out, " on %d (%s) -> rule %d\n",
- k, symbols[k]->tag,
- states[i]->lookaheads_rule[j]->number);
- };
+ if (reds->lookaheads)
+ for (j = 0; j < reds->num; ++j)
+ BITSET_FOR_EACH (iter, reds->lookaheads[j], k, 0)
+ {
+ fprintf (out, " on %d (%s) -> rule %d\n",
+ k, symbols[k]->tag,
+ reds->rules[j]->number);
+ };
}
fprintf (out, "Lookaheads: END\n");
}
void
lalr (void)
{
- states_lookaheads_count ();
initialize_LA ();
- states_lookaheads_initialize ();
set_goto_map ();
initialize_F ();
build_relations ();
{
state_number_t s;
for (s = 0; s < nstates; ++s)
- {
- states[s]->lookaheads = NULL;
- states[s]->lookaheads_rule = NULL;
- }
+ states[s]->reductions->lookaheads = NULL;
bitsetv_free (LA);
- free (LArule);
}
lalr ();
timevar_pop (TV_LALR);
- timevar_push (TV_FREE);
- nullable_free ();
- derives_free ();
- timevar_pop (TV_FREE);
-
/* Find and record any conflicts: places where one token of
lookahead is not enough to disambiguate the parsing. In file
conflicts. Also resolve s/r conflicts based on precedence
timevar_pop (TV_PARSER);
timevar_push (TV_FREE);
+ nullable_free ();
+ derives_free ();
tables_free ();
states_free ();
reduce_free ();
bitset_set (shiftset, errp->symbols[i]->number);
}
- for (i = 0; i < state->nlookaheads; ++i)
+ for (i = 0; i < redp->num; ++i)
{
int count = 0;
/* How many non-masked lookaheads are there for this reduction?
*/
- bitset_andn (lookaheadset, state->lookaheads[i], shiftset);
+ bitset_andn (lookaheadset, redp->lookaheads[i], shiftset);
count = bitset_count (lookaheadset);
if (count > cmax)
{
cmax = count;
- default_rule = state->lookaheads_rule[i];
+ default_rule = redp->rules[i];
}
/* 3. And finally, each reduction is possibly masked by previous
reductions (in R/R conflicts, we keep the first reductions).
*/
- bitset_or (shiftset, shiftset, state->lookaheads[i]);
+ bitset_or (shiftset, shiftset, redp->lookaheads[i]);
}
return default_rule;
/* Compute the width of the lookaheads column. */
if (default_rule)
width = strlen (_("$default"));
- for (i = 0; i < ntokens; i++)
- {
- int count = bitset_test (shiftset, i);
- for (j = 0; j < state->nlookaheads; ++j)
- if (bitset_test (state->lookaheads[j], i))
- {
- if (count == 0)
- {
- if (state->lookaheads_rule[j] != default_rule)
+ if (redp->lookaheads)
+ for (i = 0; i < ntokens; i++)
+ {
+ int count = bitset_test (shiftset, i);
+
+ for (j = 0; j < redp->num; ++j)
+ if (bitset_test (redp->lookaheads[j], i))
+ {
+ if (count == 0)
+ {
+ if (redp->rules[j] != default_rule)
+ max_length (&width, symbols[i]->tag);
+ count++;
+ }
+ else
+ {
max_length (&width, symbols[i]->tag);
- count++;
- }
- else
- {
- max_length (&width, symbols[i]->tag);
- }
- }
- }
+ }
+ }
+ }
/* Nothing to report. */
if (!width)
width += 2;
/* Report lookaheads (or $default) and reductions. */
- for (i = 0; i < ntokens; i++)
- {
- int defaulted = 0;
- int count = bitset_test (shiftset, i);
+ if (redp->lookaheads)
+ for (i = 0; i < ntokens; i++)
+ {
+ int defaulted = 0;
+ int count = bitset_test (shiftset, i);
- for (j = 0; j < state->nlookaheads; ++j)
- if (bitset_test (state->lookaheads[j], i))
- {
- if (count == 0)
- {
- if (state->lookaheads_rule[j] != default_rule)
- print_reduction (out, width,
- symbols[i]->tag,
- state->lookaheads_rule[j], TRUE);
- else
- defaulted = 1;
- count++;
- }
- else
- {
- if (defaulted)
+ for (j = 0; j < redp->num; ++j)
+ if (bitset_test (redp->lookaheads[j], i))
+ {
+ if (count == 0)
+ {
+ if (redp->rules[j] != default_rule)
+ print_reduction (out, width,
+ symbols[i]->tag,
+ redp->rules[j], TRUE);
+ else
+ defaulted = 1;
+ count++;
+ }
+ else
+ {
+ if (defaulted)
+ print_reduction (out, width,
+ symbols[i]->tag,
+ default_rule, TRUE);
+ defaulted = 0;
print_reduction (out, width,
symbols[i]->tag,
- default_rule, TRUE);
- defaulted = 0;
- print_reduction (out, width,
- symbols[i]->tag,
- state->lookaheads_rule[j], FALSE);
- }
- }
- }
+ redp->rules[j], FALSE);
+ }
+ }
+ }
if (default_rule)
print_reduction (out, width,
obstack_fgrow1 (oout, " %s", symbols[*sp]->tag);
/* Experimental feature: display the lookaheads. */
- if ((report_flag & report_lookaheads)
- && state->nlookaheads)
+ if (report_flag & report_lookaheads)
{
- int j, k;
- bitset_iterator biter;
- int nlookaheads = 0;
+ /* Find the reduction we are handling. */
+ reductions_t *reds = state->reductions;
+ int redno = state_reduction_find (state, &rules[rule]);
- /* Look for lookaheads corresponding to this rule. */
- for (j = 0; j < state->nlookaheads; ++j)
- BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0)
- if (state->lookaheads_rule[j]->number == rule)
- nlookaheads++;
-
- if (nlookaheads)
+ /* Print them if there are. */
+ if (reds->lookaheads && redno != -1)
{
- obstack_sgrow (oout, " [");
- for (j = 0; j < state->nlookaheads; ++j)
- BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0)
- if (state->lookaheads_rule[j]->number == rule)
- obstack_fgrow2 (oout, "%s%s",
- symbols[k]->tag,
- --nlookaheads ? ", " : "");
+ bitset_iterator biter;
+ int k;
+ int not_first = 0;
+ obstack_sgrow (oout, "[");
+ BITSET_FOR_EACH (biter, reds->lookaheads[redno], k, 0)
+ obstack_fgrow2 (oout, "%s%s",
+ not_first++ ? ", " : "",
+ symbols[k]->tag);
obstack_sgrow (oout, "]");
}
}
| Create a new array of N reductions. |
`-------------------------------------*/
-#define REDUCTIONS_ALLOC(Nreductions) \
- (reductions_t *) xcalloc ((sizeof (reductions_t) \
+#define REDUCTIONS_ALLOC(Nreductions) \
+ (reductions_t *) xcalloc ((sizeof (reductions_t) \
+ (Nreductions - 1) * sizeof (rule_t *)), 1)
static reductions_t *
reductions_t *res = REDUCTIONS_ALLOC (num);
res->num = num;
memcpy (res->rules, reductions, num * sizeof (reductions[0]));
+ res->lookaheads = NULL;
return res;
}
}
+int
+state_reduction_find (state_t *state, rule_t *rule)
+{
+ int i;
+ reductions_t *reds = state->reductions;
+ for (i = 0; i < reds->num; ++i)
+ if (reds->rules[i] == rule)
+ return i;
+ return -1;
+}
+
+
/*------------------------.
| Set the errs of STATE. |
`------------------------*/
void
state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out)
{
- int j, k;
- bitset_iterator biter;
- int nlookaheads = 0;
- /* Count the number of lookaheads corresponding to this rule. */
- for (j = 0; j < state->nlookaheads; ++j)
- BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0)
- if (state->lookaheads_rule[j] == rule)
- nlookaheads++;
+ /* Find the reduction we are handling. */
+ reductions_t *reds = state->reductions;
+ int red = state_reduction_find (state, rule);
/* Print them if there are. */
- if (nlookaheads)
+ if (reds->lookaheads && red != -1)
{
+ bitset_iterator biter;
+ int k;
+ int not_first = 0;
fprintf (out, " [");
- for (j = 0; j < state->nlookaheads; ++j)
- BITSET_FOR_EACH (biter, state->lookaheads[j], k, 0)
- if (state->lookaheads_rule[j] == rule)
- fprintf (out, "%s%s",
- symbols[k]->tag,
- --nlookaheads ? ", " : "");
+ BITSET_FOR_EACH (biter, reds->lookaheads[red], k, 0)
+ fprintf (out, "%s%s",
+ not_first++ ? ", " : "",
+ symbols[k]->tag);
fprintf (out, "]");
}
}
#ifndef STATE_H_
# define STATE_H_
-# include "bitsetv.h"
+# include "bitset.h"
/*-------------------.
typedef struct reductions_s
{
short num;
+ bitset *lookaheads;
rule_t *rules[1];
} reductions_t;
/* Nonzero if no lookahead is needed to decide what to do in state S. */
char consistent;
- /* Used in LALR, not LR(0).
-
- When a state is not consistent (there is an S/R or R/R conflict),
- lookaheads are needed to enable the reductions. NLOOKAHEADS is
- the number of lookahead guarded reductions of the
- LOOKAHEADS_RULE. For each rule LOOKAHEADS_RULE[R], LOOKAHEADS[R]
- is the bitset of the lookaheads enabling this reduction. */
- int nlookaheads;
- bitsetv lookaheads;
- rule_t **lookaheads_rule;
-
/* If some conflicts were solved thanks to precedence/associativity,
a human readable description of the resolution. */
const char *solved_conflicts;
void state_reductions_set PARAMS ((state_t *state,
int num, rule_t **reductions));
+int state_reduction_find PARAMS ((state_t *state, rule_t *rule));
+
/* Set the errs of STATE. */
void state_errs_set PARAMS ((state_t *state,
int num, symbol_t **errs));
conflict_row (state_t *state)
{
int i, j;
+ reductions_t *reds = state->reductions;
if (! glr_parser)
return;
/* Find all reductions for token J, and record all that do not
match ACTROW[J]. */
- for (i = 0; i < state->nlookaheads; i += 1)
- if (bitset_test (state->lookaheads[i], j)
+ for (i = 0; i < reds->num; i += 1)
+ if (bitset_test (reds->lookaheads[i], j)
&& (actrow[j]
- != rule_number_as_item_number (state->lookaheads_rule[i]->number)))
+ != rule_number_as_item_number (reds->rules[i]->number)))
{
assert (conflict_list_free > 0);
- conflict_list[conflict_list_cnt]
- = state->lookaheads_rule[i]->number + 1;
+ conflict_list[conflict_list_cnt] = reds->rules[i]->number + 1;
conflict_list_cnt += 1;
conflict_list_free -= 1;
}
for (i = 0; i < ntokens; i++)
actrow[i] = conflrow[i] = 0;
- if (redp->num >= 1)
+ if (redp->lookaheads)
{
int j;
bitset_iterator biter;
/* loop over all the rules available here which require
- lookahead */
- for (i = state->nlookaheads - 1; i >= 0; --i)
+ lookahead (in reverse order to give precedence to the first
+ rule) */
+ for (i = redp->num - 1; i >= 0; --i)
/* and find each token which the rule finds acceptable
to come next */
- BITSET_FOR_EACH (biter, state->lookaheads[i], j, 0)
+ BITSET_FOR_EACH (biter, redp->lookaheads[i], j, 0)
{
/* and record this rule as the rule to use if that
token follows. */
if (actrow[j] != 0)
conflicted = conflrow[j] = 1;
- actrow[j] = rule_number_as_item_number (state->lookaheads_rule[i]->number);
+ actrow[j] = rule_number_as_item_number (redp->rules[i]->number);
}
}
else
{
int max = 0;
- for (i = 0; i < state->nlookaheads; i++)
+ for (i = 0; i < redp->num; i++)
{
int count = 0;
- rule_t *rule = state->lookaheads_rule[i];
+ rule_t *rule = redp->rules[i];
symbol_number_t j;
for (j = 0; j < ntokens; j++)
projects / bison.git / commitdiff
