* src/LR0.c (new_state): Merge into...
(state_list_append): this.
(new_states): Merge into...
(generate_states): here.
(set_states): Don't ensure a proper `errs' state member here, do it...
* src/conflicts.c (conflicts_solve): here.
* src/state.h, src/state.c: Comment changes.
(state_t): Rename member `shifts' as `transitions'.
Adjust all dependencies.
(errs_new): For consistency, also take the values as argument.
(errs_dup): Remove.
(state_errs_set): New.
(state_reductions_set, state_transitions_set): Assert that no
previous value was assigned.
(state_free): New.
(states_free): Use it.
* src/conflicts.c (resolve_sr_conflict): Don't use an `errs_t' as
temporary storage: use `errs' and `nerrs' as elsewhere.
(set_conflicts): Allocate and free this `errs'.
+2002-07-03 Akim Demaille <akim@epita.fr>
+
+ Fix some memory leaks, and fix a bug: state 0 was examined twice.
+
+ * src/LR0.c (new_state): Merge into...
+ (state_list_append): this.
+ (new_states): Merge into...
+ (generate_states): here.
+ (set_states): Don't ensure a proper `errs' state member here, do it...
+ * src/conflicts.c (conflicts_solve): here.
+ * src/state.h, src/state.c: Comment changes.
+ (state_t): Rename member `shifts' as `transitions'.
+ Adjust all dependencies.
+ (errs_new): For consistency, also take the values as argument.
+ (errs_dup): Remove.
+ (state_errs_set): New.
+ (state_reductions_set, state_transitions_set): Assert that no
+ previous value was assigned.
+ (state_free): New.
+ (states_free): Use it.
+ * src/conflicts.c (resolve_sr_conflict): Don't use an `errs_t' as
+ temporary storage: use `errs' and `nerrs' as elsewhere.
+ (set_conflicts): Allocate and free this `errs'.
+
2002-07-02 Akim Demaille <akim@epita.fr>
* lib/libiberty.h: New.
static state_list_t *first_state = NULL;
static state_list_t *last_state = NULL;
-static void
-state_list_append (state_t *state)
+
+/*------------------------------------------------------------------.
+| A state was just discovered from another state. Queue it for |
+| later examination, in order to find its transitions. Return it. |
+`------------------------------------------------------------------*/
+
+static state_t *
+state_list_append (symbol_number_t symbol,
+ size_t core_size, item_number_t *core)
{
state_list_t *node = XMALLOC (state_list_t, 1);
+ state_t *state = state_new (symbol, core_size, core);
+
+ if (trace_flag)
+ fprintf (stderr, "state_list_append (state = %d, symbol = %d (%s))\n",
+ nstates, symbol, symbols[symbol]->tag);
+
+ /* If this is the eoftoken, and this is not the initial state, then
+ this is the final state. */
+ if (symbol == 0 && first_state)
+ final_state = state;
+
node->next = NULL;
node->state = state;
if (last_state)
last_state->next = node;
last_state = node;
+
+ return state;
}
static int nshifts;
-/*-----------------------------------------------------------------.
-| Subroutine of get_state. Create a new state for those items, if |
-| necessary. |
-`-----------------------------------------------------------------*/
-
-static state_t *
-new_state (symbol_number_t symbol, size_t core_size, item_number_t *core)
-{
- state_t *res;
-
- if (trace_flag)
- fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",
- nstates, symbol, symbols[symbol]->tag);
-
- res = state_new (symbol, core_size, core);
- state_hash_insert (res);
-
- /* If this is the eoftoken, and this is not the initial state, then
- this is the final state. */
- if (symbol == 0 && first_state)
- final_state = res;
-
- state_list_append (res);
- return res;
-}
-
-
/*--------------------------------------------------------------.
| Find the state number for the state we would get to (from the |
| current state) by shifting symbol. Create a new state if no |
sp = state_hash_lookup (core_size, core);
if (!sp)
- sp = new_state (symbol, core_size, core);
+ sp = state_list_append (symbol, core_size, core);
if (trace_flag)
fprintf (stderr, "Exiting get_state => %d\n", sp->number);
}
-static void
-new_states (void)
-{
- /* The 0 at the lhs is the index of the item of this initial rule. */
- kernel_base[0][0] = 0;
- kernel_size[0] = 1;
- state_list_append (new_state (0, kernel_size[0], kernel_base[0]));
-}
-
-
-
/*----------------------------------------------------------------.
| Find which rules can be used for reduction transitions from the |
| current state and make a reductions structure for the state to |
state_list_t *this = first_state;
/* Pessimization, but simplification of the code: make sure all
- the states have a shifts, errs, and reductions, even if
- reduced to 0. */
+ the states have valid transitions and reductions members,
+ even if reduced to 0. It is too soon for errs, which are
+ computed later, but set_conflicts. */
state_t *state = this->state;
- if (!state->shifts)
+ if (!state->transitions)
state_transitions_set (state, 0, 0);
- if (!state->errs)
- state->errs = errs_new (0);
if (!state->reductions)
state_reductions_set (state, 0, 0);
state_list_t *list = NULL;
allocate_storage ();
new_closure (nritems);
- new_states ();
+
+ /* Create the initial state. The 0 at the lhs is the index of the
+ item of this initial rule. */
+ kernel_base[0][0] = 0;
+ kernel_size[0] = 1;
+ state_list_append (0, kernel_size[0], kernel_base[0]);
+
list = first_state;
while (list)
static void
flush_shift (state_t *state, int token)
{
- transitions_t *transitions = state->shifts;
+ transitions_t *transitions = state->transitions;
int i;
bitset_reset (lookaheadset, token);
| shift or reduce tables so that there is no longer a conflict. |
| |
| LOOKAHEAD is the number of the lookahead bitset to consider. |
+| |
+| ERRS can be used to store discovered explicit errors. |
`------------------------------------------------------------------*/
static void
-resolve_sr_conflict (state_t *state, int lookahead)
+resolve_sr_conflict (state_t *state, int lookahead,
+ symbol_number_t *errs)
{
symbol_number_t i;
/* Find the rule to reduce by to get precedence of reduction. */
rule_t *redrule = state->lookaheads_rule[lookahead];
int redprec = redrule->prec->prec;
bitset lookaheads = state->lookaheads[lookahead];
- errs_t *errp = errs_new (ntokens + 1);
- errp->num = 0;
+ int nerrs = 0;
for (i = 0; i < ntokens; i++)
if (bitset_test (lookaheads, i)
flush_shift (state, i);
flush_reduce (lookaheads, i);
/* Record an explicit error for this token. */
- errp->symbols[errp->num++] = i;
+ errs[nerrs++] = i;
break;
case undef_assoc:
/* Some tokens have been explicitly made errors. Allocate a
permanent errs structure for this state, to record them. */
- state->errs = errs_dup (errp);
- free (errp);
+ state_errs_set (state, nerrs, errs);
if (obstack_object_size (&solved_conflicts_obstack))
{
}
+/*-------------------------------------------------------------------.
+| Solve the S/R conflicts of STATE using the |
+| precedence/associativity, and flag it inconsistent if it still has |
+| conflicts. ERRS can be used as storage to compute the list of |
+| lookaheads on which this STATE raises a parse error (%nonassoc). |
+`-------------------------------------------------------------------*/
+
static void
-set_conflicts (state_t *state)
+set_conflicts (state_t *state, symbol_number_t *errs)
{
int i;
- transitions_t *transitions;
+ transitions_t *transitions = state->transitions;
if (state->consistent)
return;
bitset_zero (lookaheadset);
- transitions = state->shifts;
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));
&& state->lookaheads_rule[i]->prec->prec
&& !bitset_disjoint_p (state->lookaheads[i], lookaheadset))
{
- resolve_sr_conflict (state, i);
+ resolve_sr_conflict (state, i, errs);
break;
}
}
}
+
+/*----------------------------------------------------------------.
+| Solve all the S/R conflicts using the precedence/associativity, |
+| and flag as inconsistent the states that still have conflicts. |
+`----------------------------------------------------------------*/
+
void
conflicts_solve (void)
{
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);
conflicts = XCALLOC (char, nstates);
shiftset = bitset_create (ntokens, BITSET_FIXED);
obstack_init (&solved_conflicts_obstack);
for (i = 0; i < nstates; i++)
- set_conflicts (states[i]);
+ {
+ set_conflicts (states[i], errs);
+
+ /* For uniformity of the code, make sure all the states have a valid
+ `errs' member. */
+ if (!states[i]->errs)
+ states[i]->errs = errs_new (0, 0);
+ }
+
+ free (errs);
}
{
int i;
int src_count = 0;
- transitions_t *transitions = state->shifts;
+ transitions_t *transitions = state->transitions;
if (!transitions)
return 0;
ngotos = 0;
for (state = 0; state < nstates; ++state)
{
- transitions_t *sp = states[state]->shifts;
+ transitions_t *sp = states[state]->transitions;
int i;
for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
{
for (state = 0; state < nstates; ++state)
{
- transitions_t *sp = states[state]->shifts;
+ transitions_t *sp = states[state]->transitions;
int i;
for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
{
for (i = 0; i < ngotos; i++)
{
state_number_t stateno = to_state[i];
- transitions_t *sp = states[stateno]->shifts;
+ transitions_t *sp = states[stateno]->transitions;
int j;
for (j = 0; j < sp->num && TRANSITION_IS_SHIFT (sp, j); j++)
for (rp = rules[*rulep].rhs; *rp >= 0; rp++)
{
- state = transitions_to (state->shifts,
- item_number_as_symbol_number (*rp));
+ state = transitions_to (state->transitions,
+ item_number_as_symbol_number (*rp));
states1[length++] = state->number;
}
int k;
int nlookaheads = 0;
reductions_t *rp = states[i]->reductions;
- transitions_t *sp = states[i]->shifts;
+ 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
int i;
rule_number_t default_rule = 0;
reductions_t *redp = state->reductions;
- transitions_t *transitions = state->shifts;
+ transitions_t *transitions = state->transitions;
errs_t *errp = state->errs;
/* set nonzero to inhibit having any default reduction */
int nodefault = 0;
static void
print_transitions (state_t *state, FILE *out, bool display_transitions_p)
{
- transitions_t *transitions = state->shifts;
+ transitions_t *transitions = state->transitions;
size_t width = 0;
int i;
we shift (S/R conflicts)... */
bitset_zero (shiftset);
{
- transitions_t *transitions = state->shifts;
+ transitions_t *transitions = state->transitions;
for (i = 0; i < transitions->num && TRANSITION_IS_SHIFT (transitions, i); i++)
if (!TRANSITION_IS_DISABLED (transitions, i))
{
static void
print_reductions (FILE *out, state_t *state)
{
- transitions_t *transitions = state->shifts;
+ transitions_t *transitions = state->transitions;
reductions_t *redp = state->reductions;
rule_t *default_rule = NULL;
size_t width = 0;
print_actions (FILE *out, state_t *state)
{
reductions_t *redp = state->reductions;
- transitions_t *transitions = state->shifts;
+ transitions_t *transitions = state->transitions;
if (transitions->num == 0 && redp->num == 0)
{
{
int i;
- transitions_t *transitions = state->shifts;
+ transitions_t *transitions = state->transitions;
reductions_t *redp = state->reductions;
static char buff[10];
| Create a new array of N errs. |
`-------------------------------*/
-#define ERRS_ALLOC(Nerrs) \
- (errs_t *) xcalloc ((unsigned) (sizeof (errs_t) \
- + (Nerrs - 1) * sizeof (symbol_number_t)), 1)
+#define ERRS_ALLOC(Nerrs) \
+ (errs_t *) xcalloc ((sizeof (errs_t) \
+ + (Nerrs - 1) * sizeof (symbol_number_t)), 1)
errs_t *
-errs_new (int n)
+errs_new (int num, symbol_number_t *tokens)
{
- errs_t *res = ERRS_ALLOC (n);
- res->num = n;
- return res;
-}
-
-
-errs_t *
-errs_dup (errs_t *src)
-{
- errs_t *res = errs_new (src->num);
- memcpy (res->symbols, src->symbols, src->num * sizeof (src->symbols[0]));
+ errs_t *res = ERRS_ALLOC (num);
+ res->num = num;
+ memcpy (res->symbols, tokens, num * sizeof (tokens[0]));
return res;
}
| Create a new array of N reductions. |
`-------------------------------------*/
-#define REDUCTIONS_ALLOC(Nreductions) \
- (reductions_t *) xcalloc ((unsigned) (sizeof (reductions_t) \
- + (Nreductions - 1) * sizeof (rule_number_t)), 1)
+#define REDUCTIONS_ALLOC(Nreductions) \
+ (reductions_t *) xcalloc ((sizeof (reductions_t) \
+ + (Nreductions - 1) * sizeof (rule_number_t)), 1)
static reductions_t *
-reductions_new (int nreductions, short *reductions)
+reductions_new (int num, rule_number_t *reductions)
{
- reductions_t *res = REDUCTIONS_ALLOC (nreductions);
- res->num = nreductions;
- memcpy (res->rules, reductions, nreductions * sizeof (reductions[0]));
+ reductions_t *res = REDUCTIONS_ALLOC (num);
+ res->num = num;
+ memcpy (res->rules, reductions, num * sizeof (reductions[0]));
return res;
}
(state_t *) xcalloc ((unsigned) (sizeof (state_t) \
+ (Nitems - 1) * sizeof (item_number_t)), 1)
-/*------------------------------------------------------------.
-| Create a new state with ACCESSING_SYMBOL, for those items. |
-`------------------------------------------------------------*/
+/*------------------------------------------------------------------.
+| Create a new state with ACCESSING_SYMBOL, for those items. Store |
+| it in the state hash table. |
+`------------------------------------------------------------------*/
state_t *
state_new (symbol_number_t accessing_symbol,
res->nitems = core_size;
memcpy (res->items, core, core_size * sizeof (core[0]));
+ state_hash_insert (res);
+
return res;
}
-/*--------------------------.
-| Set the shifts of STATE. |
-`--------------------------*/
+/*-------------.
+| Free STATE. |
+`-------------*/
+
+static void
+state_free (state_t *state)
+{
+ free (state->transitions);
+ free (state->reductions);
+ free (state->errs);
+ free (state);
+}
+
+
+/*-------------------------------.
+| Set the transitions of STATE. |
+`-------------------------------*/
void
-state_transitions_set (state_t *state, int nshifts, state_number_t *shifts)
+state_transitions_set (state_t *state, int num, state_number_t *transitions)
{
- state->shifts = transitions_new (nshifts, shifts);
+ assert (!state->transitions);
+ state->transitions = transitions_new (num, transitions);
}
`------------------------------*/
void
-state_reductions_set (state_t *state, int nreductions, short *reductions)
+state_reductions_set (state_t *state, int num, rule_number_t *reductions)
{
- state->reductions = reductions_new (nreductions, reductions);
+ assert (!state->reductions);
+ state->reductions = reductions_new (num, reductions);
+}
+
+
+/*------------------------.
+| Set the errs of STATE. |
+`------------------------*/
+
+void
+state_errs_set (state_t *state, int num, symbol_number_t *tokens)
+{
+ assert (!state->errs);
+ state->errs = errs_new (num, tokens);
}
states_free (void)
{
state_number_t i;
-
for (i = 0; i < nstates; ++i)
- {
- free (states[i]->shifts);
- XFREE (states[i]->reductions);
- free (states[i]->errs);
- free (states[i]);
- }
- XFREE (states);
+ state_free (states[i]);
+ free (states);
}
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 transitions are shifts (push the lookahead token
- and read another) 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 transitions are represented in two other lists.
-
- Each shifts structure describes the possible shift transitions out
- of one state, the state whose number is in the number field. The
- shifts structures are linked through next and first_shift points to
- them. Each contains a vector of numbers of the states that shift
- transitions can go to. The accessing_symbol fields of those
- states' cores say what kind of input leads to them.
-
- A shift to state zero should be ignored. Conflict resolution
- deletes shifts by changing them to zero.
+ The two types of actions are shifts/gotos (push the lookahead 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
+ actions are represented in two other lists.
+
+ Each transition_t structure describes the possible transitions out
+ of one state, the state whose number is in the number field. Each
+ contains a vector of numbers of the states that transitions can go
+ to. The accessing_symbol fields of those states' cores say what
+ kind of input leads to them.
+
+ A transition to state zero should be ignored: conflict resolution
+ deletes transitions by having them point to zero.
Each reductions structure describes the possible reductions at the
state whose number is in the number field. The data is a list of
Conflict resolution can decide that certain tokens in certain
states should explicitly be errors (for implementing %nonassoc).
For each state, the tokens that are errors for this reason are
- recorded in an errs structure, which has the state number in its
- number field. The rest of the errs structure is full of token
- numbers.
+ recorded in an errs structure, which holds the token numbers.
- There is at least one shift transition present in state zero. It
+ There is at least one goto transition present in state zero. It
leads to a next-to-final state whose accessing_symbol is the
grammar's start symbol. The next-to-final state has one shift to
the final state, whose accessing_symbol is zero (end of input).
- The final state has one shift, which goes to the termination state
- (whose number is nstates-1). The reason for the extra state at the
- end is to placate the parser's strategy of making all decisions one
- token ahead of its actions. */
+ The final state has one shift, which goes to the termination state.
+ The reason for the extra state at the end is to placate the
+ parser's strategy of making all decisions one token ahead of its
+ actions. */
#ifndef STATE_H_
# define STATE_H_
} transitions_t;
-/* What is the symbol which is shifted by TRANSITIONS->states[Shift]? Can
- be a token (amongst which the error token), or non terminals in
- case of gotos. */
+/* What is the symbol labelling the transition to
+ TRANSITIONS->states[Num]? Can be a token (amongst which the error
+ token), or non terminals in case of gotos. */
-#define TRANSITION_SYMBOL(Transitions, Shift) \
- (states[Transitions->states[Shift]]->accessing_symbol)
+#define TRANSITION_SYMBOL(Transitions, Num) \
+ (states[Transitions->states[Num]]->accessing_symbol)
-/* Is the TRANSITIONS->states[Shift] a real shift? (as opposed to gotos.) */
+/* Is the TRANSITIONS->states[Num] a shift? (as opposed to gotos). */
-#define TRANSITION_IS_SHIFT(Transitions, Shift) \
- (ISTOKEN (TRANSITION_SYMBOL (Transitions, Shift)))
+#define TRANSITION_IS_SHIFT(Transitions, Num) \
+ (ISTOKEN (TRANSITION_SYMBOL (Transitions, Num)))
-/* Is the TRANSITIONS->states[Shift] a goto?. */
+/* Is the TRANSITIONS->states[Num] a goto?. */
-#define TRANSITION_IS_GOTO(Transitions, Shift) \
- (!TRANSITION_IS_SHIFT (Transitions, Shift))
+#define TRANSITION_IS_GOTO(Transitions, Num) \
+ (!TRANSITION_IS_SHIFT (Transitions, Num))
-/* Is the TRANSITIONS->states[Shift] then handling of the error token?. */
+/* Is the TRANSITIONS->states[Num] labelled by the error token? */
-#define TRANSITION_IS_ERROR(Transitions, Shift) \
- (TRANSITION_SYMBOL (Transitions, Shift) == errtoken->number)
+#define TRANSITION_IS_ERROR(Transitions, Num) \
+ (TRANSITION_SYMBOL (Transitions, Num) == errtoken->number)
/* When resolving a SR conflicts, if the reduction wins, the shift is
disabled. */
-#define TRANSITION_DISABLE(Transitions, Shift) \
- (Transitions->states[Shift] = 0)
+#define TRANSITION_DISABLE(Transitions, Num) \
+ (Transitions->states[Num] = 0)
-#define TRANSITION_IS_DISABLED(Transitions, Shift) \
- (Transitions->states[Shift] == 0)
+#define TRANSITION_IS_DISABLED(Transitions, Num) \
+ (Transitions->states[Num] == 0)
/* Return the state such these TRANSITIONS contain a shift/goto to it on
SYMBOL. Aborts if none found. */
symbol_number_t symbols[1];
} errs_t;
-errs_t *errs_new PARAMS ((int n));
-errs_t *errs_dup PARAMS ((errs_t *src));
+errs_t *errs_new PARAMS ((int num, symbol_number_t *tokens));
/*-------------.
{
state_number_t number;
symbol_number_t accessing_symbol;
- transitions_t *shifts;
+ transitions_t *transitions;
reductions_t *reductions;
errs_t *errs;
state_t *state_new PARAMS ((symbol_number_t accessing_symbol,
size_t core_size, item_number_t *core));
-/* Set the shifts of STATE. */
+/* Set the transitions of STATE. */
void state_transitions_set PARAMS ((state_t *state,
- int nshifts, state_number_t *shifts));
+ int num, state_number_t *transitions));
/* Set the reductions of STATE. */
void state_reductions_set PARAMS ((state_t *state,
- int nreductions, short *reductions));
+ int num, rule_number_t *reductions));
+
+/* Set the errs of STATE. */
+void state_errs_set PARAMS ((state_t *state,
+ int num, symbol_number_t *errs));
/* Print on OUT all the lookaheads such that this STATE wants to
reduce this RULE. */
projects / bison.git / commitdiff
