state_number_t.
(errs_t): symbol_t*, not symbol_number_t.
(reductions_t): rule_t*, not rule_number_t.
(FOR_EACH_SHIFT): New.
* src/LR0.c, src/conflicts.c, src/lalr.c, src/output.c
* src/print.c, src/print_graph.c: Adjust.
+2002-07-29 Akim Demaille <akim@epita.fr>
+
+ * src/state.h, src/state.c (transitions_t): Holds state_t*'s, not
+ state_number_t.
+ (errs_t): symbol_t*, not symbol_number_t.
+ (reductions_t): rule_t*, not rule_number_t.
+ (FOR_EACH_SHIFT): New.
+ * src/LR0.c, src/conflicts.c, src/lalr.c, src/output.c
+ * src/print.c, src/print_graph.c: Adjust.
+
2002-07-29 Akim Demaille <akim@epita.fr>
Use $accept and $end, as BYacc and BTYacc do, instead of $axiom and $.
static int nshifts;
static symbol_number_t *shift_symbol = NULL;
-static short *redset = NULL;
-static state_number_t *shiftset = NULL;
+static rule_t **redset = NULL;
+static state_t **shiftset = NULL;
static item_number_t **kernel_base = NULL;
static int *kernel_size = NULL;
{
allocate_itemsets ();
- shiftset = XCALLOC (state_number_t, nsyms);
- redset = XCALLOC (short, nrules);
+ shiftset = XCALLOC (state_t *, nsyms);
+ redset = XCALLOC (rule_t *, nrules);
state_hash_new ();
shift_symbol = XCALLOC (symbol_number_t, nsyms);
}
-/*--------------------------------------------------------------.
-| Find the state number for the state we would get to (from the |
-| current state) by shifting symbol. Create a new state if no |
-| equivalent one exists already. Used by append_states. |
-`--------------------------------------------------------------*/
+/*-----------------------------------------------------------------.
+| Find the state we would get to (from the current state) by |
+| shifting SYMBOL. Create a new state if no equivalent one exists |
+| already. Used by append_states. |
+`-----------------------------------------------------------------*/
-static state_number_t
+static state_t *
get_state (symbol_number_t symbol, size_t core_size, item_number_t *core)
{
state_t *sp;
if (trace_flag)
fprintf (stderr, "Exiting get_state => %d\n", sp->number);
- return sp->number;
+ return sp;
}
-/*------------------------------------------------------------------.
-| Use the information computed by new_itemsets to find the state |
-| numbers reached by each shift transition from STATE. |
-| |
-| SHIFTSET is set up as a vector of state numbers of those states. |
-`------------------------------------------------------------------*/
+/*---------------------------------------------------------------.
+| Use the information computed by new_itemsets to find the state |
+| numbers reached by each shift transition from STATE. |
+| |
+| SHIFTSET is set up as a vector of those states. |
+`---------------------------------------------------------------*/
static void
append_states (state_t *state)
{
int item = ritem[itemset[i]];
if (item < 0)
- redset[count++] = item_number_as_rule_number (item);
+ redset[count++] = &rules[item_number_as_rule_number (item)];
}
/* Make a reductions structure and copy the data into it. */
static void
resolve_sr_conflict (state_t *state, int lookahead,
- symbol_number_t *errs)
+ symbol_t **errs)
{
symbol_number_t i;
/* Find the rule to reduce by to get precedence of reduction. */
flush_shift (state, i);
flush_reduce (lookaheads, i);
/* Record an explicit error for this token. */
- errs[nerrs++] = i;
+ errs[nerrs++] = symbols[i];
break;
case undef_assoc:
`-------------------------------------------------------------------*/
static void
-set_conflicts (state_t *state, symbol_number_t *errs)
+set_conflicts (state_t *state, symbol_t **errs)
{
int i;
transitions_t *transitions = state->transitions;
bitset_zero (lookaheadset);
- for (i = 0; i < transitions->num && TRANSITION_IS_SHIFT (transitions, i); i++)
- if (!TRANSITION_IS_DISABLED (transitions, i))
- bitset_set (lookaheadset, TRANSITION_SYMBOL (transitions, i));
+ FOR_EACH_SHIFT (transitions, i)
+ bitset_set (lookaheadset, TRANSITION_SYMBOL (transitions, i));
/* Loop over all rules which require lookahead in this state. First
check for shift-reduce conflict, and try to resolve using
{
state_number_t i;
/* List of lookaheads on which we explicitly raise a parse error. */
- symbol_number_t *errs = XMALLOC (symbol_number_t, ntokens + 1);
+ symbol_t **errs = XMALLOC (symbol_t *, ntokens + 1);
conflicts = XCALLOC (char, nstates);
shiftset = bitset_create (ntokens, BITSET_FIXED);
bitset_zero (lookaheadset);
bitset_zero (shiftset);
- for (i = 0; i < transitions->num && TRANSITION_IS_SHIFT (transitions, i); i++)
- if (!TRANSITION_IS_DISABLED (transitions, i))
- bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i));
+ 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]);
conflicts_output (FILE *out)
{
bool printed_sth = FALSE;
+ bool *used_rules = XCALLOC (bool, nrules);
state_number_t i;
for (i = 0; i < nstates; i++)
- if (conflicts[i])
- {
- fprintf (out, _("State %d contains "), i);
- fputs (conflict_report (count_sr_conflicts (states[i]),
- count_rr_conflicts (states[i], TRUE)), out);
- printed_sth = TRUE;
- }
+ {
+ state_t *s = states[i];
+ int j;
+ for (j = 0; j < s->reductions->num; ++j)
+ used_rules[s->reductions->rules[j]->number] = TRUE;
+ if (conflicts[i])
+ {
+ fprintf (out, _("State %d contains "), i);
+ fputs (conflict_report (count_sr_conflicts (s),
+ count_rr_conflicts (s, TRUE)), out);
+ printed_sth = TRUE;
+ }
+ }
if (printed_sth)
fputs ("\n\n", out);
+
+ for (i = 0; i < nstates; i++)
+ {
+ state_t *s = states[i];
+ reductions_t *r = s->reductions;
+ int j;
+ for (j = 0; j < r->num; ++j)
+ if (!used_rules[r->rules[j]->number])
+ {
+ LOCATION_PRINT (stderr, r->rules[j]->location);
+ fprintf (stderr, ": %s: %s: ",
+ _("warning"),
+ _("rule never reduced because of conflicts"));
+ rule_print (r->rules[j], stderr);
+ }
+ }
+ free (used_rules);
}
/*--------------------------------------------------------.
for (i = 0; i < nstates; i++)
if (!states[i]->consistent)
for (j = 0; j < states[i]->reductions->num; j++)
- *np++ = &rules[states[i]->reductions->rules[j]];
+ *np++ = states[i]->reductions->rules[j];
}
{
int k = temp_map[TRANSITION_SYMBOL (sp, i)]++;
from_state[k] = state;
- to_state[k] = sp->states[i];
+ to_state[k] = sp->states[i]->number;
}
}
transitions_t *sp = states[stateno]->transitions;
int j;
- for (j = 0; j < sp->num && TRANSITION_IS_SHIFT (sp, j); j++)
+ FOR_EACH_SHIFT (sp, j)
bitset_set (F[i], TRANSITION_SYMBOL (sp, j));
for (; j < sp->num; j++)
reduction from a shift. Otherwise, it is straightforward,
and the state is `consistent'. */
if (rp->num > 1
- || (rp->num == 1 && sp->num && TRANSITION_IS_SHIFT (sp, 0)))
+ || (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_ERROR (sp, k))
+ if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
{
states[i]->consistent = 0;
break;
#include "conflicts.h"
#include "print_graph.h"
#include "muscle_tab.h"
+#include <malloc.h>
+#include <sys/times.h>
/* The name this program was run with, for messages. */
char *program_name;
+static void
+stage (const char *title)
+{
+ struct mallinfo minfo = mallinfo ();
+ struct tms tinfo;
+ times (&tinfo);
+ fprintf (stderr, "STAGE: %30s: %9d (%9d): %ldu %lds\n",
+ title,
+ minfo.uordblks, minfo.arena,
+ tinfo.tms_utime, tinfo.tms_stime);
+}
+
int
main (int argc, char *argv[])
{
muscle_init ();
+ stage ("initialized muscles");
+
/* Read the input. Copy some parts of it to FGUARD, FACTION, FTABLE
and FATTRS. In file reader.c. The other parts are recorded in
the grammar; see gram.h. */
reader ();
+
+ stage ("reader");
+
if (complain_message_count)
exit (1);
/* Find useless nonterminals and productions and reduce the grammar. */
reduce_grammar ();
+ stage ("reduced grammar");
+
/* Record other info about the grammar. In files derives and
nullable. */
set_derives ();
See state.h for more info. */
generate_states ();
+ stage ("generated states");
/* make it deterministic. In file lalr. */
lalr ();
+ stage ("lalred");
/* 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
conflicts_solve ();
conflicts_print ();
+ stage ("solved conflicts");
/* Output file names. */
compute_output_file_names ();
if (report_flag)
print_results ();
+ stage ("printed results");
/* Stop if there were errors, to avoid trashing previous output
files. */
if (complain_message_count)
/* Output the tables and the parser to ftable. In file output. */
output ();
+ stage ("made output");
states_free ();
+ stage ("freed states");
reduce_free ();
+ stage ("freed reduce");
conflicts_free ();
+ stage ("freed conflicts");
free_nullable ();
+ stage ("freed nullable");
free_derives ();
+ stage ("freed derives");
grammar_free ();
+ stage ("freed grammar");
/* The scanner memory cannot be released right after parsing, as it
contains things such as user actions, prologue, epilogue etc. */
scanner_free ();
+ stage ("freed scanner");
muscle_free ();
+ stage ("freed muscles");
/* If using alloca.c, flush the alloca'ed memory for the benefit of
people running Bison as a library in IDEs. */
#if C_ALLOCA
- alloca (0);
+ alloca (0);
#endif
- if (trace_flag)
- bitset_stats_dump (stderr);
+ if (trace_flag)
+ bitset_stats_dump (stderr);
return complain_message_count ? EXIT_FAILURE : EXIT_SUCCESS;
}
| that has any such conflicts. |
`------------------------------------------------------------------*/
-static rule_number_t
+static rule_t *
action_row (state_t *state)
{
int i;
- rule_number_t default_rule = -1;
+ rule_t *default_rule = NULL;
reductions_t *redp = state->reductions;
transitions_t *transitions = state->transitions;
errs_t *errp = state->errs;
- /* set nonzero to inhibit having any default reduction */
+ /* Set to nonzero to inhibit having any default reduction. */
int nodefault = 0;
int conflicted = 0;
/* Now see which tokens are allowed for shifts in this state. For
them, record the shift as the thing to do. So shift is preferred
to reduce. */
- for (i = 0; i < transitions->num && TRANSITION_IS_SHIFT (transitions, i); i++)
- if (!TRANSITION_IS_DISABLED (transitions, i))
- {
- symbol_number_t symbol = TRANSITION_SYMBOL (transitions, i);
- state_number_t shift_state = transitions->states[i];
+ FOR_EACH_SHIFT (transitions, i)
+ {
+ symbol_number_t symbol = TRANSITION_SYMBOL (transitions, i);
+ state_t *shift_state = transitions->states[i];
- if (actrow[symbol] != 0)
- conflicted = conflrow[symbol] = 1;
- actrow[symbol] = state_number_as_int (shift_state);
+ if (actrow[symbol] != 0)
+ conflicted = conflrow[symbol] = 1;
+ actrow[symbol] = state_number_as_int (shift_state->number);
- /* Do not use any default reduction if there is a shift for
- error */
- if (symbol == errtoken->number)
- nodefault = 1;
- }
+ /* Do not use any default reduction if there is a shift for
+ error */
+ if (symbol == errtoken->number)
+ nodefault = 1;
+ }
/* See which tokens are an explicit error in this state (due to
%nonassoc). For them, record ACTION_MIN as the action. */
for (i = 0; i < errp->num; i++)
{
- symbol_number_t symbol = errp->symbols[i];
- actrow[symbol] = ACTION_MIN;
+ symbol_t *symbol = errp->symbols[i];
+ actrow[symbol->number] = ACTION_MIN;
}
/* Now find the most common reduction and make it the default action
for (i = 0; i < state->nlookaheads; i++)
{
int count = 0;
- rule_number_t rule = state->lookaheads_rule[i]->number;
+ rule_t *rule = state->lookaheads_rule[i];
symbol_number_t j;
for (j = 0; j < ntokens; j++)
- if (actrow[j] == rule_number_as_item_number (rule))
+ if (actrow[j] == rule_number_as_item_number (rule->number))
count++;
if (count > max)
{
int j;
for (j = 0; j < ntokens; j++)
- if (actrow[j] == rule_number_as_item_number (default_rule)
+ if (actrow[j] == rule_number_as_item_number (default_rule->number)
&& ! (glr_parser && conflrow[j]))
actrow[j] = 0;
}
/* If have no default rule, the default is an error.
So replace any action which says "error" with "use default". */
- if (default_rule == -1)
+ if (!default_rule)
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]) + 1;
+ rule_t *default_rule = action_row (states[i]);
+ yydefact[i] = default_rule ? default_rule->number + 1 : 0;
save_row (i);
}
{
symbol_t *symbol = symbols[TRANSITION_SYMBOL (transitions, i)];
const char *tag = symbol->tag;
- state_number_t state1 = transitions->states[i];
+ state_t *state1 = transitions->states[i];
int j;
fprintf (out, " %s", tag);
for (j = width - strlen (tag); j > 0; --j)
fputc (' ', out);
if (display_transitions_p)
- fprintf (out, _("shift, and go to state %d\n"), state1);
+ fprintf (out, _("shift, and go to state %d\n"), state1->number);
else
- fprintf (out, _("go to state %d\n"), state1);
+ fprintf (out, _("go to state %d\n"), state1->number);
}
}
/* Compute the width of the lookaheads column. */
for (i = 0; i < errp->num; ++i)
if (errp->symbols[i])
- max_length (&width, symbols[errp->symbols[i]]->tag);
+ max_length (&width, errp->symbols[i]->tag);
/* Nothing to report. */
if (!width)
for (i = 0; i < errp->num; ++i)
if (errp->symbols[i])
{
- const char *tag = symbols[errp->symbols[i]]->tag;
+ const char *tag = errp->symbols[i]->tag;
int j;
fprintf (out, " %s", tag);
for (j = width - strlen (tag); j > 0; --j)
/* No need for a lookahead. */
if (state->consistent)
- return &rules[redp->rules[0]];
+ return redp->rules[0];
/* 1. Each reduction is possibly masked by the lookaheads on which
we shift (S/R conflicts)... */
bitset_zero (shiftset);
{
transitions_t *transitions = state->transitions;
- for (i = 0; i < transitions->num && TRANSITION_IS_SHIFT (transitions, i); i++)
- if (!TRANSITION_IS_DISABLED (transitions, i))
- {
- /* If this state has a shift for the error token, don't use a
+ FOR_EACH_SHIFT (transitions, i)
+ {
+ /* If this state has a shift for the error token, don't use a
default rule. */
- if (TRANSITION_IS_ERROR (transitions, i))
- return NULL;
- bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i));
- }
+ if (TRANSITION_IS_ERROR (transitions, i))
+ return NULL;
+ bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i));
+ }
}
/* 2. Each reduction is possibly masked by the lookaheads on which
errs_t *errp = state->errs;
for (i = 0; i < errp->num; i++)
if (errp->symbols[i])
- bitset_set (shiftset, errp->symbols[i]);
+ bitset_set (shiftset, errp->symbols[i]->number);
}
for (i = 0; i < state->nlookaheads; ++i)
default_rule = state_default_rule (state);
bitset_zero (shiftset);
- for (i = 0; i < transitions->num && TRANSITION_IS_SHIFT (transitions, i); i++)
- if (!TRANSITION_IS_DISABLED (transitions, i))
- bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i));
+ FOR_EACH_SHIFT (transitions, i)
+ bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i));
/* Compute the width of the lookaheads column. */
if (default_rule)
for (i = 0; i < transitions->num; i++)
if (!TRANSITION_IS_DISABLED (transitions, i))
{
- state_number_t state1 = transitions->states[i];
- symbol_number_t symbol = states[state1]->accessing_symbol;
+ state_t *state1 = transitions->states[i];
+ symbol_number_t symbol = state1->accessing_symbol;
new_edge (&edge);
- if (state->number > state1)
+ if (state->number > state1->number)
edge.type = back_edge;
open_edge (&edge, fgraph);
/* The edge source is the current node. */
edge.sourcename = node_name;
- sprintf (buff, "%d", state1);
+ sprintf (buff, "%d", state1->number);
edge.targetname = buff;
/* Shifts are blue, gotos are green, and error is red. */
if (TRANSITION_IS_ERROR (transitions, i))
| Create a new array of N shifts/gotos. |
`---------------------------------------*/
-#define TRANSITIONS_ALLOC(Num) \
- (transitions_t *) xcalloc ((sizeof (transitions_t) \
- + (Num - 1) * sizeof (state_number_t)), 1)
+#define TRANSITIONS_ALLOC(Num) \
+ (transitions_t *) xcalloc ((sizeof (transitions_t) \
+ + (Num - 1) * sizeof (state_t *)), 1)
static transitions_t *
-transitions_new (int num, state_number_t *the_states)
+transitions_new (int num, state_t **the_states)
{
transitions_t *res = TRANSITIONS_ALLOC (num);
res->num = num;
int j;
for (j = 0; j < shifts->num; j++)
if (TRANSITION_SYMBOL (shifts, j) == s)
- return states[shifts->states[j]];
+ return shifts->states[j];
abort ();
}
#define ERRS_ALLOC(Nerrs) \
(errs_t *) xcalloc ((sizeof (errs_t) \
- + (Nerrs - 1) * sizeof (symbol_number_t)), 1)
+ + (Nerrs - 1) * sizeof (symbol_t *)), 1)
errs_t *
-errs_new (int num, symbol_number_t *tokens)
+errs_new (int num, symbol_t **tokens)
{
errs_t *res = ERRS_ALLOC (num);
res->num = num;
#define REDUCTIONS_ALLOC(Nreductions) \
(reductions_t *) xcalloc ((sizeof (reductions_t) \
- + (Nreductions - 1) * sizeof (rule_number_t)), 1)
+ + (Nreductions - 1) * sizeof (rule_t *)), 1)
static reductions_t *
-reductions_new (int num, rule_number_t *reductions)
+reductions_new (int num, rule_t **reductions)
{
reductions_t *res = REDUCTIONS_ALLOC (num);
res->num = num;
state_t *final_state = NULL;
#define STATE_ALLOC(Nitems) \
- (state_t *) xcalloc ((unsigned) (sizeof (state_t) \
- + (Nitems - 1) * sizeof (item_number_t)), 1)
+ (state_t *) xcalloc ((sizeof (state_t) \
+ + (Nitems - 1) * sizeof (item_number_t)), 1)
/*------------------------------------------------------------------.
| Create a new state with ACCESSING_SYMBOL, for those items. Store |
`-------------------------------*/
void
-state_transitions_set (state_t *state, int num, state_number_t *transitions)
+state_transitions_set (state_t *state, int num, state_t **transitions)
{
assert (!state->transitions);
state->transitions = transitions_new (num, transitions);
`------------------------------*/
void
-state_reductions_set (state_t *state, int num, rule_number_t *reductions)
+state_reductions_set (state_t *state, int num, rule_t **reductions)
{
assert (!state->reductions);
state->reductions = reductions_new (num, reductions);
`------------------------*/
void
-state_errs_set (state_t *state, int num, symbol_number_t *tokens)
+state_errs_set (state_t *state, int num, symbol_t **tokens)
{
assert (!state->errs);
state->errs = errs_new (num, tokens);
/* Be ready to map a state_number_t to an int. */
# define state_number_as_int(Tok) ((int) (Tok))
+
+typedef struct state_s state_t;
+
/*--------------.
| Transitions. |
`--------------*/
typedef struct transtion_s
{
short num;
- state_number_t states[1];
+ state_t *states[1];
} transitions_t;
token), or non terminals in case of gotos. */
#define TRANSITION_SYMBOL(Transitions, Num) \
- (states[Transitions->states[Num]]->accessing_symbol)
+ (Transitions->states[Num]->accessing_symbol)
/* Is the TRANSITIONS->states[Num] a shift? (as opposed to gotos). */
disabled. */
#define TRANSITION_DISABLE(Transitions, Num) \
- (Transitions->states[Num] = 0)
+ (Transitions->states[Num] = NULL)
#define TRANSITION_IS_DISABLED(Transitions, Num) \
- (Transitions->states[Num] == 0)
+ (Transitions->states[Num] == NULL)
+
+
+/* Iterate over each transition over a token (shifts). */
+#define FOR_EACH_SHIFT(Transitions, Iter) \
+ for (Iter = 0; \
+ Iter < Transitions->num \
+ && (TRANSITION_IS_DISABLED (Transitions, Iter) \
+ || TRANSITION_IS_SHIFT (Transitions, Iter)); \
+ ++Iter) \
+ if (!TRANSITION_IS_DISABLED (Transitions, Iter))
+
/* Return the state such these TRANSITIONS contain a shift/goto to it on
SYMBOL. Aborts if none found. */
typedef struct errs_s
{
short num;
- symbol_number_t symbols[1];
+ symbol_t *symbols[1];
} errs_t;
-errs_t *errs_new PARAMS ((int num, symbol_number_t *tokens));
+errs_t *errs_new PARAMS ((int num, symbol_t **tokens));
/*-------------.
typedef struct reductions_s
{
short num;
- rule_number_t rules[1];
+ rule_t *rules[1];
} reductions_t;
-/*----------.
-| State_t. |
-`----------*/
+/*---------.
+| States. |
+`---------*/
-typedef struct state_s
+struct state_s
{
state_number_t number;
symbol_number_t accessing_symbol;
*/
unsigned short nitems;
item_number_t items[1];
-} state_t;
+};
extern state_number_t nstates;
extern state_t *final_state;
/* Set the transitions of STATE. */
void state_transitions_set PARAMS ((state_t *state,
- int num, state_number_t *transitions));
+ int num, state_t **transitions));
/* Set the reductions of STATE. */
void state_reductions_set PARAMS ((state_t *state,
- int num, rule_number_t *reductions));
+ int num, rule_t **reductions));
/* Set the errs of STATE. */
void state_errs_set PARAMS ((state_t *state,
- int num, symbol_number_t *errs));
+ int num, symbol_t **errs));
/* Print on OUT all the lookaheads such that this STATE wants to
reduce this RULE. */
projects / bison.git / commitdiff
