+2002-07-25 Akim Demaille <akim@epita.fr>
+
+ Stop storing rules from 1 to nrules + 1.
+
+ * src/LR0.c, src/closure.c, src/derives.c, src/gram.c, src/lalr.c
+ * src/nullable.c, src/output.c, src/print.c, src/reader.c
+ * src/reduce.c: Allocate and free from &rules[0], not &rules[1].
+ Iterate from 0 to nrules.
+ Use rule_number_as_item_number and item_number_as_rule_number.
+ Adjust to `derive' now containing possibly 0.
+ * src/gram.h (rule_number_as_item_number, item_number_as_rule_number):
+ Handle the `- 1' part in rule numbers from/to item numbers.
+ * src/conflicts.c (log_resolution): Fix the message which reversed
+ shift and reduce.
+ * src/output.c (action_row): Initialize default_rule to -1.
+ (token_actions): Adjust.
+ * tests/sets.at (Nullable, Firsts): Fix the previously bogus
+ expected output.
+ * tests/conflicts.at (Resolved SR Conflicts): Likewise.
+
2002-07-25 Akim Demaille <akim@epita.fr>
* data/c.m4 (b4_c_function, b4_c_ansi_args, b4_c_ansi_arg)
int count = 0;
short *symbol_count = XCALLOC (short, nsyms + nuseless_nonterminals);
- for (r = 1; r < nrules + 1; ++r)
+ for (r = 0; r < nrules; ++r)
for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
{
count++;
allocate_itemsets ();
shiftset = XCALLOC (state_number_t, nsyms);
- redset = XCALLOC (short, nrules + 1);
+ redset = XCALLOC (short, nrules);
state_hash_new ();
shift_symbol = XCALLOC (symbol_number_t, nsyms);
}
| Use the information computed by new_itemsets to find the state |
| numbers reached by each shift transition from STATE. |
| |
-| TRANSITIONSET is set up as a vector of state numbers of those states. |
+| SHIFTSET is set up as a vector of state numbers of those states. |
`------------------------------------------------------------------*/
static void
{
int item = ritem[itemset[i]];
if (item < 0)
- redset[count++] = -item;
+ redset[count++] = item_number_as_rule_number (item);
}
/* Make a reductions structure and copy the data into it. */
symbol_number_t i, j;
rule_number_t k;
- fderives = bitsetv_create (nvars, nrules + 1, BITSET_FIXED);
+ fderives = bitsetv_create (nvars, nrules, BITSET_FIXED);
set_firsts ();
for (i = ntokens; i < nsyms; ++i)
for (j = ntokens; j < nsyms; ++j)
if (bitset_test (FIRSTS (i), j - ntokens))
- for (k = 0; derives[j][k] > 0; ++k)
+ for (k = 0; derives[j][k] >= 0; ++k)
bitset_set (FDERIVES (i), derives[j][k]);
if (trace_flag)
{
itemset = XCALLOC (item_number_t, n);
- ruleset = bitset_create (nrules + 1, BITSET_FIXED);
+ ruleset = bitset_create (nrules, BITSET_FIXED);
set_fderives ();
}
switch (resolution)
{
case shift_resolution:
- case left_resolution:
+ case right_resolution:
obstack_fgrow2 (&solved_conflicts_obstack,
_("\
Conflict between rule %d and token %s resolved as shift"),
symbols[token]->tag);
break;
case reduce_resolution:
- case right_resolution:
+ case left_resolution:
obstack_fgrow2 (&solved_conflicts_obstack,
_("\
Conflict between rule %d and token %s resolved as reduce"),
{
rule_number_t *rp;
fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
- for (rp = derives[i]; *rp > 0; rp++)
+ for (rp = derives[i]; *rp >= 0; rp++)
{
- fprintf (stderr, "\t\t%3d ", *rp - 1);
+ fprintf (stderr, "\t\t%3d ", *rp);
rule_rhs_print (&rules[*rp], stderr);
}
}
set_derives (void)
{
symbol_number_t i;
- rule_number_t r;
+ int r;
rule_number_t *q;
/* DSET[NTERM] -- A linked list of the numbers of the rules whose
/* DELTS[RULE] -- There are NRULES rule number to attach to nterms.
Instead of performing NRULES allocations for each, have an array
indexed by rule numbers. */
- rule_list_t *delts = XCALLOC (rule_list_t, nrules + 1);
+ rule_list_t *delts = XCALLOC (rule_list_t, nrules);
- for (r = nrules; r > 0; r--)
+ for (r = nrules - 1; r >= 0; --r)
{
symbol_number_t lhs = rules[r].lhs->number;
rule_list_t *p = &delts[r];
void
rule_lhs_print (rule_t *rule, symbol_t *previous_lhs, FILE *out)
{
- fprintf (out, " %3d ", rule->number - 1);
+ fprintf (out, " %3d ", rule->number);
if (previous_lhs != rule->lhs)
{
fprintf (out, "%s:", rule->lhs->tag);
if (ritem[i] >= 0)
fprintf (out, " %s", symbols[ritem[i]]->tag);
else
- fprintf (out, " (rule %d)\n", -ritem[i] - 1);
+ fprintf (out, " (rule %d)\n", item_number_as_rule_number (ritem[i]));
fputs ("\n\n", out);
}
int max = 0;
rule_number_t r;
- for (r = 1; r < nrules + 1; ++r)
+ for (r = 0; r < nrules; ++r)
{
int length = rule_rhs_length (&rules[r]);
if (length > max)
void
grammar_rules_print (FILE *out)
{
- grammar_rules_partial_print (out, _("Grammar"), 1, nrules + 1);
+ grammar_rules_partial_print (out, _("Grammar"), 0, nrules);
}
{
rule_number_t i;
fprintf (out, "Num (Prec, Assoc, Useful, Ritem Range) Lhs -> Rhs (Ritem range) [Num]\n");
- for (i = 1; i < nrules + nuseless_productions + 1; i++)
+ for (i = 0; i < nrules + nuseless_productions; i++)
{
rule_t *rule = &rules[i];
item_number_t *r = NULL;
for (r = rule->rhs; *r >= 0; ++r)
++rhs_count;
fprintf (out, "%3d (%2d, %2d, %2d, %2d-%2d) %2d ->",
- i - 1,
+ i,
rule->prec ? rule->prec->prec : 0,
rule->prec ? rule->prec->assoc : 0,
rule->useful,
/* Dumped the RHS. */
for (r = rule->rhs; *r >= 0; r++)
fprintf (out, " %3d", *r);
- fprintf (out, " [%d]\n", -(*r) - 1);
+ fprintf (out, " [%d]\n", item_number_as_rule_number (*r));
}
}
fprintf (out, "\n\n");
fprintf (out, "Rules interpreted\n-----------------\n\n");
{
rule_number_t r;
- for (r = 1; r < nrules + nuseless_productions + 1; r++)
+ for (r = 0; r < nrules + nuseless_productions; r++)
{
fprintf (out, "%-5d ", r);
rule_print (&rules[r], out);
grammar_free (void)
{
XFREE (ritem);
- free (rules + 1);
+ free (rules);
XFREE (token_translations);
/* Free the symbol table data structure. */
symbols_free ();
/* There is weird relationship between OT1H item_number_t and OTOH
symbol_number_t and rule_number_t: we store the latter in
item_number_t. symbol_number_t are stored as are, while
- the negation of rule_number_t are stored.
+ the negation of (rule_number_t + 1) are stored.
Therefore, an symbol_number_t must be a valid item_number_t, and we
sometimes have to perform the converse transformation. */
# define RULE_NUMBER_MAX ((rule_number_t) SHRT_MAX)
extern rule_number_t nrules;
# define int_of_rule_number(RNum) ((int) (RNum))
-# define rule_number_as_item_number(RNum) ((item_number_t) (- RNum))
-# define item_number_as_rule_number(INum) ((rule_number_t) (- INum))
+# define rule_number_as_item_number(RNum) ((item_number_t) (- RNum - 1))
+# define item_number_as_rule_number(INum) ((rule_number_t) (- INum - 1))
/*--------.
symbol_number_t symbol1 = states[to_state[i]]->accessing_symbol;
rule_number_t *rulep;
- for (rulep = derives[symbol1]; *rulep > 0; rulep++)
+ for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
{
int done;
int length = 1;
{
fprintf (out, " on %d (%s) -> rule %d\n",
k, symbols[k]->tag,
- states[i]->lookaheads_rule[j]->number - 1);
+ states[i]->lookaheads_rule[j]->number);
};
}
fprintf (out, "Lookaheads: END\n");
rule_list_t *p;
symbol_number_t *squeue = XCALLOC (symbol_number_t, nvars);
- short *rcount = XCALLOC (short, nrules + 1);
+ short *rcount = XCALLOC (short, nrules);
/* RITEM contains all the rules, including useless productions.
Hence we must allocate room for useless nonterminals too. */
rule_list_t **rsets = XCALLOC (rule_list_t *, nvars) - ntokens;
s1 = s2 = squeue;
p = relts;
- for (ruleno = 1; ruleno < nrules + 1; ++ruleno)
+ for (ruleno = 0; ruleno < nrules; ++ruleno)
if (rules[ruleno].useful)
{
rule_t *rule = &rules[ruleno];
rule_number_t r;
unsigned int i = 0;
item_number_t *rhs = XMALLOC (item_number_t, nritems);
- unsigned int *prhs = XMALLOC (unsigned int, nrules + 1);
- unsigned int *rline = XMALLOC (unsigned int, nrules + 1);
- symbol_number_t *r1 = XMALLOC (symbol_number_t, nrules + 1);
- unsigned int *r2 = XMALLOC (unsigned int, nrules + 1);
- short *dprec = XMALLOC (short, nrules + 1);
- short *merger = XMALLOC (short, nrules + 1);
-
- for (r = 1; r < nrules + 1; ++r)
+ unsigned int *prhs = XMALLOC (unsigned int, nrules);
+ unsigned int *rline = XMALLOC (unsigned int, nrules);
+ symbol_number_t *r1 = XMALLOC (symbol_number_t, nrules);
+ unsigned int *r2 = XMALLOC (unsigned int, nrules);
+ short *dprec = XMALLOC (short, nrules);
+ short *merger = XMALLOC (short, nrules);
+
+ for (r = 0; r < nrules; ++r)
{
item_number_t *rhsp = NULL;
/* Index of rule R in RHS. */
assert (i == nritems);
muscle_insert_item_number_table ("rhs", rhs, ritem[0], 1, nritems);
- muscle_insert_unsigned_int_table ("prhs", prhs, 0, 1, nrules + 1);
- muscle_insert_unsigned_int_table ("rline", rline, 0, 1, nrules + 1);
- muscle_insert_symbol_number_table ("r1", r1, 0, 1, nrules + 1);
- muscle_insert_unsigned_int_table ("r2", r2, 0, 1, nrules + 1);
- muscle_insert_short_table ("dprec", dprec, 0, 1, nrules + 1);
- muscle_insert_short_table ("merger", merger, 0, 1, nrules + 1);
+ muscle_insert_unsigned_int_table ("prhs", prhs, 0, 0, nrules);
+ muscle_insert_unsigned_int_table ("rline", rline, 0, 0, nrules);
+ muscle_insert_symbol_number_table ("r1", r1, 0, 0, nrules);
+ muscle_insert_unsigned_int_table ("r2", r2, 0, 0, nrules);
+ muscle_insert_short_table ("dprec", dprec, 0, 0, nrules);
+ muscle_insert_short_table ("merger", merger, 0, 0, nrules);
free (rhs);
free (prhs);
| by non-zero entries in CONFLROW, create a list of possible |
| reductions that are alternatives to the shift or reduction |
| currently recorded for that token in STATE. Store the alternative |
-| reductions followed by a 0 in conflict_list, updating |
-| conflict_list_cnt, and storing an index to the start of the list |
+| reductions followed by a 0 in CONFLICT_LIST, updating |
+| CONFLICT_LIST_CNT, and storing an index to the start of the list |
| back into CONFLROW. |
`-------------------------------------------------------------------*/
{
assert (conflict_list_free > 0);
conflict_list[conflict_list_cnt]
- = state->lookaheads_rule[i]->number;
+ = state->lookaheads_rule[i]->number + 1;
conflict_list_cnt += 1;
conflict_list_free -= 1;
}
| considered that likes a token gets to handle it. |
| |
| For GLR parsers, also sets CONFLROW[SYM] to an index into |
-| conflict_list iff there is an unresolved conflict (s/r or r/r) |
+| CONFLICT_LIST iff there is an unresolved conflict (s/r or r/r) |
| with symbol SYM. The default reduction is not used for a symbol |
| that has any such conflicts. |
`------------------------------------------------------------------*/
action_row (state_t *state)
{
int i;
- rule_number_t default_rule = 0;
+ rule_number_t default_rule = -1;
reductions_t *redp = state->reductions;
transitions_t *transitions = state->transitions;
errs_t *errp = state->errs;
/* If have no default rule, the default is an error.
So replace any action which says "error" with "use default". */
- if (default_rule == 0)
+ if (default_rule == -1)
for (i = 0; i < ntokens; i++)
if (actrow[i] == ACTION_MIN)
actrow[i] = 0;
for (i = 0; i < nstates; ++i)
{
- yydefact[i] = action_row (states[i]);
+ yydefact[i] = action_row (states[i]) + 1;
save_row (i);
}
rule_number_t r;
fputs ("m4_define([b4_actions], \n[[", out);
- for (r = 1; r < nrules + 1; ++r)
+ for (r = 0; r < nrules; ++r)
if (rules[r].action)
{
- fprintf (out, " case %d:\n", r);
+ fprintf (out, " case %d:\n", r + 1);
if (!no_lines_flag)
fprintf (out, muscle_find ("linef"),
while (*sp >= 0)
sp++;
- rule = -(*sp);
+ rule = item_number_as_rule_number (*sp);
rule_lhs_print (&rules[rule], previous_lhs, out);
previous_lhs = rules[rule].lhs;
if (!enabled)
fputc ('[', out);
fprintf (out, _("reduce using rule %d (%s)"),
- rule->number - 1, rule->lhs->tag);
+ rule->number, rule->lhs->tag);
if (!enabled)
fputc (']', out);
fputc ('\n', out);
END_TEST (50);
sprintf (buffer, " (%d)", i);
- for (r = 1; r < nrules + 1; r++)
+ for (r = 0; r < nrules; r++)
for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
if (item_number_as_symbol_number (*rhsp) == token_translations[i])
{
END_TEST (65);
- sprintf (buffer + strlen (buffer), " %d", r - 1);
+ sprintf (buffer + strlen (buffer), " %d", r);
break;
}
fprintf (out, "%s\n", buffer);
rule_number_t r;
const char *tag = symbols[i]->tag;
- for (r = 1; r < nrules + 1; r++)
+ for (r = 0; r < nrules; r++)
{
item_number_t *rhsp;
if (rules[r].lhs->number == i)
END_TEST (50);
sprintf (buffer + strlen (buffer), _(" on left:"));
- for (r = 1; r < nrules + 1; r++)
+ for (r = 0; r < nrules; r++)
{
END_TEST (65);
if (rules[r].lhs->number == i)
- sprintf (buffer + strlen (buffer), " %d", r - 1);
+ sprintf (buffer + strlen (buffer), " %d", r);
}
}
sprintf (buffer + strlen (buffer), ",");
END_TEST (50);
sprintf (buffer + strlen (buffer), _(" on right:"));
- for (r = 1; r < nrules + 1; r++)
+ for (r = 0; r < nrules; r++)
{
item_number_t *rhsp;
for (rhsp = rules[r].rhs; *rhsp >= 0; rhsp++)
if (item_number_as_symbol_number (*rhsp) == i)
{
END_TEST (65);
- sprintf (buffer + strlen (buffer), " %d", r - 1);
+ sprintf (buffer + strlen (buffer), " %d", r);
break;
}
}
packgram (void)
{
unsigned int itemno = 0;
- rule_number_t ruleno = 1;
+ rule_number_t ruleno = 0;
symbol_list_t *p = grammar;
ritem = XCALLOC (item_number_t, nritems);
- rules = XCALLOC (rule_t, nrules) - 1;
+ rules = XCALLOC (rule_t, nrules);
while (p)
{
rules[ruleno].precsym = ruleprec;
rules[ruleno].prec = ruleprec;
}
- ritem[itemno++] = -ruleno;
+ ritem[itemno++] = rule_number_as_item_number (ruleno);
++ruleno;
if (p)
while (1)
{
bitset_copy (Np, N);
- for (r = 1; r < nrules + 1; r++)
+ for (r = 0; r < nrules; r++)
if (!bitset_test (P, r)
&& useful_production (r, N))
{
user can know. */
Vp = bitset_create (nsyms, BITSET_FIXED);
- Pp = bitset_create (nrules + 1, BITSET_FIXED);
+ Pp = bitset_create (nrules, BITSET_FIXED);
/* If the start symbol isn't useful, then nothing will be useful. */
if (bitset_test (N, axiom->number - ntokens))
{
rule_number_t r;
bitset_copy (Vp, V);
- for (r = 1; r < nrules + 1; r++)
+ for (r = 0; r < nrules; r++)
{
if (!bitset_test (Pp, r)
&& bitset_test (P, r)
/* A token that was used in %prec should not be warned about. */
{
- rule_number_t i;
- for (i = 1; i < nrules + 1; i++)
- if (rules[i].precsym != 0)
- bitset_set (V1, rules[i].precsym->number);
+ rule_number_t r;
+ for (r = 0; r < nrules; ++r)
+ if (rules[r].precsym != 0)
+ bitset_set (V1, rules[r].precsym->number);
}
}
/* Report and flag useless productions. */
{
rule_number_t r;
- for (r = 1; r < nrules + 1; r++)
+ for (r = 0; r < nrules; r++)
{
rules[r].useful = bitset_test (P, r);
if (!rules[r].useful)
/* Map the nonterminals to their new index: useful first, useless
afterwards. Kept for later report. */
{
- int useful = 1;
- int useless = nrules + 1 - nuseless_productions;
- rule_t *rules_sorted = XMALLOC (rule_t, nrules + 1) - 1;
+ int useful = 0;
+ int useless = nrules - nuseless_productions;
+ rule_t *rules_sorted = XMALLOC (rule_t, nrules);
rule_number_t r;
- for (r = 1; r < nrules + 1; ++r)
+ for (r = 0; r < nrules; ++r)
rules_sorted[rules[r].useful ? useful++ : useless++] = rules[r];
- free (rules + 1);
+ free (rules);
rules = rules_sorted;
/* Renumber the rules markers in RITEMS. */
- for (r = 1; r < nrules + 1; ++r)
+ for (r = 0; r < nrules; ++r)
{
item_number_t *rhsp = rules[r].rhs;
for (/* Nothing. */; *rhsp >= 0; ++rhsp)
{
int r;
int length;
- for (r = nrules + 1; r < nrules + 1 + nuseless_productions; ++r)
+ for (r = nrules; r < nrules + nuseless_productions; ++r)
{
length = rule_rhs_length (&rules[r]);
nritems -= length + 1;
{
rule_number_t r;
- for (r = 1; r < nrules + 1; ++r)
+ for (r = 0; r < nrules; ++r)
{
item_number_t *rhsp;
for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
if (nuseless_productions > 0)
grammar_rules_partial_print (out, _("Useless rules"),
- nrules + 1,
- nuseless_productions + nrules + 1);
+ nrules,
+ nrules + nuseless_productions);
}
\f
/* Allocate the global sets used to compute the reduced grammar */
N = bitset_create (nvars, BITSET_FIXED);
- P = bitset_create (nrules + 1, BITSET_FIXED);
+ P = bitset_create (nrules, BITSET_FIXED);
V = bitset_create (nsyms, BITSET_FIXED);
V1 = bitset_create (nsyms, BITSET_FIXED);
1 | exp OP exp . [$, OP]
$default reduce using rule 1 (exp)
- Conflict between rule 2 and token OP resolved as shift (%left OP).
+ Conflict between rule 1 and token OP resolved as reduce (%left OP).
]])
AT_CLEANUP
e
FDERIVES
$axiom derives
- 1 e $
- 2 'e'
- 3 /* empty */
+ 0 e $
+ 1 'e'
+ 2 /* empty */
e derives
- 2 'e'
- 3 /* empty */
+ 1 'e'
+ 2 /* empty */
]])
AT_CLEANUP
exp
FDERIVES
$axiom derives
- 1 exp $
- 2 exp '<' exp
- 3 exp '>' exp
- 4 exp '+' exp
- 5 exp '-' exp
- 6 exp '^' exp
- 7 exp '=' exp
- 8 "exp"
+ 0 exp $
+ 1 exp '<' exp
+ 2 exp '>' exp
+ 3 exp '+' exp
+ 4 exp '-' exp
+ 5 exp '^' exp
+ 6 exp '=' exp
+ 7 "exp"
exp derives
- 2 exp '<' exp
- 3 exp '>' exp
- 4 exp '+' exp
- 5 exp '-' exp
- 6 exp '^' exp
- 7 exp '=' exp
- 8 "exp"
+ 1 exp '<' exp
+ 2 exp '>' exp
+ 3 exp '+' exp
+ 4 exp '-' exp
+ 5 exp '^' exp
+ 6 exp '=' exp
+ 7 "exp"
]])
AT_CLEANUP
projects / bison.git / commitdiff
