From ccaf65bc6331dfb0684876a7475c6474b99125ea Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Sun, 30 Jun 2002 17:33:37 +0000 Subject: [PATCH] * src/state.h, src/state.c (shift_t, SHIFT_SYMBOL, SHIFT_IS_SHIFT) (SHIFT_IS_GOTO, SHIFT_IS_ERROR, SHIFT_DISABLE, SHIFT_IS_DISABLED) (shifts_to): Rename as... (transition_t, TRANSITION_SYMBOL, TRANSITION_IS_TRANSITION) (TRANSITION_IS_GOTO, TRANSITION_IS_ERROR, TRANSITION_DISABLE) (TRANSITION_IS_DISABLED, transitions_to): these. --- ChangeLog | 10 +++++++++ src/LR0.c | 6 ++--- src/conflicts.c | 28 ++++++++++++------------ src/lalr.c | 34 ++++++++++++++-------------- src/lalr.h | 2 +- src/output.c | 10 ++++----- src/print.c | 46 +++++++++++++++++++------------------- src/print_graph.c | 14 ++++++------ src/state.c | 34 ++++++++++++++-------------- src/state.h | 56 ++++++++++++++++++++++++----------------------- 10 files changed, 126 insertions(+), 114 deletions(-) diff --git a/ChangeLog b/ChangeLog index acdcfdb6..014a56cd 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2002-06-30 Akim Demaille + + * src/state.h, src/state.c (shift_t, SHIFT_SYMBOL, SHIFT_IS_SHIFT) + (SHIFT_IS_GOTO, SHIFT_IS_ERROR, SHIFT_DISABLE, SHIFT_IS_DISABLED) + (shifts_to): Rename as... + (transition_t, TRANSITION_SYMBOL, TRANSITION_IS_TRANSITION) + (TRANSITION_IS_GOTO, TRANSITION_IS_ERROR, TRANSITION_DISABLE) + (TRANSITION_IS_DISABLED, transitions_to): these. + + 2002-06-30 Akim Demaille * src/print.c (print_shifts, print_gotos): Merge into... diff --git a/src/LR0.c b/src/LR0.c index 9ce53e06..0d7edff5 100644 --- a/src/LR0.c +++ b/src/LR0.c @@ -240,7 +240,7 @@ get_state (symbol_number_t symbol, size_t core_size, item_number_t *core) | 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. | +| TRANSITIONSET is set up as a vector of state numbers of those states. | `------------------------------------------------------------------*/ static void @@ -336,7 +336,7 @@ set_states (void) reduced to 0. */ state_t *state = this->state; if (!state->shifts) - state_shifts_set (state, 0, 0); + state_transitions_set (state, 0, 0); if (!state->errs) state->errs = errs_new (0); if (!state->reductions) @@ -387,7 +387,7 @@ generate_states (void) /* Create the shifts structures for the shifts to those states, now that the state numbers transitioning to are known. */ - state_shifts_set (state, nshifts, shiftset); + state_transitions_set (state, nshifts, shiftset); /* States are queued when they are created; process them all. */ diff --git a/src/conflicts.c b/src/conflicts.c index aef33e6d..6ad9222b 100644 --- a/src/conflicts.c +++ b/src/conflicts.c @@ -139,13 +139,13 @@ log_resolution (rule_t *rule, int token, static void flush_shift (state_t *state, int token) { - shifts_t *shiftp = state->shifts; + transitions_t *transitions = state->shifts; int i; bitset_reset (lookaheadset, token); - for (i = 0; i < shiftp->nshifts; i++) - if (!SHIFT_IS_DISABLED (shiftp, i) && SHIFT_SYMBOL (shiftp, i) == token) - SHIFT_DISABLE (shiftp, i); + for (i = 0; i < transitions->num; i++) + if (!TRANSITION_IS_DISABLED (transitions, i) && TRANSITION_SYMBOL (transitions, i) == token) + TRANSITION_DISABLE (transitions, i); } @@ -249,17 +249,17 @@ static void set_conflicts (state_t *state) { int i; - shifts_t *shiftp; + transitions_t *transitions; if (state->consistent) return; bitset_zero (lookaheadset); - shiftp = state->shifts; - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) - bitset_set (lookaheadset, SHIFT_SYMBOL (shiftp, i)); + 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)); /* Loop over all rules which require lookahead in this state. First check for shift-reduce conflict, and try to resolve using @@ -308,17 +308,17 @@ count_sr_conflicts (state_t *state) { int i; int src_count = 0; - shifts_t *shiftp = state->shifts; + transitions_t *transitions = state->shifts; - if (!shiftp) + if (!transitions) return 0; bitset_zero (lookaheadset); bitset_zero (shiftset); - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) - bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i)); + 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 (i = 0; i < state->nlookaheads; ++i) bitset_or (lookaheadset, lookaheadset, state->lookaheads[i]); diff --git a/src/lalr.c b/src/lalr.c index 3267172b..dd6a1dc0 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -94,15 +94,15 @@ set_goto_map (void) ngotos = 0; for (state = 0; state < nstates; ++state) { - shifts_t *sp = states[state]->shifts; + transitions_t *sp = states[state]->shifts; int i; - for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) + for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i) { if (ngotos == SHRT_MAX) fatal (_("too many gotos (max %d)"), SHRT_MAX); ngotos++; - goto_map[SHIFT_SYMBOL (sp, i)]++; + goto_map[TRANSITION_SYMBOL (sp, i)]++; } } @@ -127,13 +127,13 @@ set_goto_map (void) for (state = 0; state < nstates; ++state) { - shifts_t *sp = states[state]->shifts; + transitions_t *sp = states[state]->shifts; int i; - for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) + for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i) { - int k = temp_map[SHIFT_SYMBOL (sp, i)]++; + int k = temp_map[TRANSITION_SYMBOL (sp, i)]++; from_state[k] = state; - to_state[k] = sp->shifts[i]; + to_state[k] = sp->states[i]; } } @@ -189,15 +189,15 @@ initialize_F (void) for (i = 0; i < ngotos; i++) { state_number_t stateno = to_state[i]; - shifts_t *sp = states[stateno]->shifts; + transitions_t *sp = states[stateno]->shifts; int j; - for (j = 0; j < sp->nshifts && SHIFT_IS_SHIFT (sp, j); j++) - bitset_set (F[i], SHIFT_SYMBOL (sp, j)); + for (j = 0; j < sp->num && TRANSITION_IS_SHIFT (sp, j); j++) + bitset_set (F[i], TRANSITION_SYMBOL (sp, j)); - for (; j < sp->nshifts; j++) + for (; j < sp->num; j++) { - symbol_number_t symbol = SHIFT_SYMBOL (sp, j); + symbol_number_t symbol = TRANSITION_SYMBOL (sp, j); if (nullable[symbol]) edge[nedges++] = map_goto (stateno, symbol); } @@ -266,7 +266,7 @@ build_relations (void) for (rp = rules[*rulep].rhs; *rp >= 0; rp++) { - state = shifts_to (state->shifts, + state = transitions_to (state->shifts, item_number_as_symbol_number (*rp)); states1[length++] = state->number; } @@ -360,20 +360,20 @@ states_lookaheads_count (void) int k; int nlookaheads = 0; reductions_t *rp = states[i]->reductions; - shifts_t *sp = states[i]->shifts; + transitions_t *sp = states[i]->shifts; /* 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->nreds > 1 - || (rp->nreds == 1 && sp->nshifts && SHIFT_IS_SHIFT (sp, 0))) + || (rp->nreds == 1 && sp->num && TRANSITION_IS_SHIFT (sp, 0))) nlookaheads += rp->nreds; else states[i]->consistent = 1; - for (k = 0; k < sp->nshifts; k++) - if (SHIFT_IS_ERROR (sp, k)) + for (k = 0; k < sp->num; k++) + if (TRANSITION_IS_ERROR (sp, k)) { states[i]->consistent = 0; break; diff --git a/src/lalr.h b/src/lalr.h index da4ab1ae..3bece77c 100644 --- a/src/lalr.h +++ b/src/lalr.h @@ -24,7 +24,7 @@ #include "bitset.h" #include "bitsetv.h" -/* Import the definition of CORE, SHIFTS and REDUCTIONS. */ +/* Import the definition of CORE, TRANSITIONS and REDUCTIONS. */ # include "state.h" /* Import the definition of RULE_T. */ diff --git a/src/output.c b/src/output.c index 6b082f57..b24593fa 100644 --- a/src/output.c +++ b/src/output.c @@ -430,7 +430,7 @@ action_row (state_t *state) int i; rule_number_t default_rule = 0; reductions_t *redp = state->reductions; - shifts_t *shiftp = state->shifts; + transitions_t *transitions = state->shifts; errs_t *errp = state->errs; /* set nonzero to inhibit having any default reduction */ int nodefault = 0; @@ -460,11 +460,11 @@ action_row (state_t *state) /* 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 < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) + for (i = 0; i < transitions->num && TRANSITION_IS_SHIFT (transitions, i); i++) + if (!TRANSITION_IS_DISABLED (transitions, i)) { - symbol_number_t symbol = SHIFT_SYMBOL (shiftp, i); - state_number_t shift_state = shiftp->shifts[i]; + symbol_number_t symbol = TRANSITION_SYMBOL (transitions, i); + state_number_t shift_state = transitions->states[i]; if (actrow[symbol] != 0) conflicted = conflrow[symbol] = 1; diff --git a/src/print.c b/src/print.c index f1dbe12d..c531b04c 100644 --- a/src/print.c +++ b/src/print.c @@ -123,18 +123,18 @@ print_core (FILE *out, state_t *state) `----------------------------------------------------------------*/ static void -print_transitions (state_t *state, FILE *out, bool display_shifts_p) +print_transitions (state_t *state, FILE *out, bool display_transitions_p) { - shifts_t *shiftp = state->shifts; + transitions_t *transitions = state->shifts; size_t width = 0; int i; /* Compute the width of the lookaheads column. */ - for (i = 0; i < shiftp->nshifts; i++) - if (!SHIFT_IS_DISABLED (shiftp, i) - && SHIFT_IS_SHIFT (shiftp, i) == display_shifts_p) + for (i = 0; i < transitions->num; i++) + if (!TRANSITION_IS_DISABLED (transitions, i) + && TRANSITION_IS_SHIFT (transitions, i) == display_transitions_p) { - symbol_t *symbol = symbols[SHIFT_SYMBOL (shiftp, i)]; + symbol_t *symbol = symbols[TRANSITION_SYMBOL (transitions, i)]; max_length (&width, symbol_tag_get (symbol)); } @@ -146,19 +146,19 @@ print_transitions (state_t *state, FILE *out, bool display_shifts_p) width += 2; /* Report lookaheads and shifts. */ - for (i = 0; i < shiftp->nshifts; i++) - if (!SHIFT_IS_DISABLED (shiftp, i) - && SHIFT_IS_SHIFT (shiftp, i) == display_shifts_p) + for (i = 0; i < transitions->num; i++) + if (!TRANSITION_IS_DISABLED (transitions, i) + && TRANSITION_IS_SHIFT (transitions, i) == display_transitions_p) { - symbol_t *symbol = symbols[SHIFT_SYMBOL (shiftp, i)]; + symbol_t *symbol = symbols[TRANSITION_SYMBOL (transitions, i)]; const char *tag = symbol_tag_get (symbol); - state_number_t state1 = shiftp->shifts[i]; + state_number_t state1 = transitions->states[i]; int j; fprintf (out, " %s", tag); for (j = width - strlen (tag); j > 0; --j) fputc (' ', out); - if (display_shifts_p) + if (display_transitions_p) fprintf (out, _("shift, and go to state %d\n"), state1); else fprintf (out, _("go to state %d\n"), state1); @@ -224,15 +224,15 @@ state_default_rule (state_t *state) we shift (S/R conflicts)... */ bitset_zero (shiftset); { - shifts_t *shiftp = state->shifts; - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) + transitions_t *transitions = state->shifts; + 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 default rule. */ - if (SHIFT_IS_ERROR (shiftp, i)) + if (TRANSITION_IS_ERROR (transitions, i)) return NULL; - bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i)); + bitset_set (shiftset, TRANSITION_SYMBOL (transitions, i)); } } @@ -302,7 +302,7 @@ print_reduction (FILE *out, size_t width, static void print_reductions (FILE *out, state_t *state) { - shifts_t *shiftp = state->shifts; + transitions_t *transitions = state->shifts; reductions_t *redp = state->reductions; rule_t *default_rule = NULL; size_t width = 0; @@ -314,9 +314,9 @@ print_reductions (FILE *out, state_t *state) default_rule = state_default_rule (state); bitset_zero (shiftset); - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) - bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i)); + 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)); /* Compute the width of the lookaheads column. */ if (default_rule) @@ -396,9 +396,9 @@ static void print_actions (FILE *out, state_t *state) { reductions_t *redp = state->reductions; - shifts_t *shiftp = state->shifts; + transitions_t *transitions = state->shifts; - if (shiftp->nshifts == 0 && redp->nreds == 0) + if (transitions->num == 0 && redp->nreds == 0) { fputc ('\n', out); if (state->number == final_state->number) diff --git a/src/print_graph.c b/src/print_graph.c index 34e34ee9..8e6cdb3d 100644 --- a/src/print_graph.c +++ b/src/print_graph.c @@ -127,19 +127,19 @@ print_actions (state_t *state, const char *node_name) { int i; - shifts_t *shiftp = state->shifts; + transitions_t *transitions = state->shifts; reductions_t *redp = state->reductions; static char buff[10]; edge_t edge; - if (!shiftp->nshifts && !redp) + if (!transitions->num && !redp) return; - for (i = 0; i < shiftp->nshifts; i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) + for (i = 0; i < transitions->num; i++) + if (!TRANSITION_IS_DISABLED (transitions, i)) { - state_number_t state1 = shiftp->shifts[i]; + state_number_t state1 = transitions->states[i]; symbol_number_t symbol = states[state1]->accessing_symbol; new_edge (&edge); @@ -152,10 +152,10 @@ print_actions (state_t *state, const char *node_name) sprintf (buff, "%d", state1); edge.targetname = buff; /* Shifts are blue, gotos are green, and error is red. */ - if (SHIFT_IS_ERROR (shiftp, i)) + if (TRANSITION_IS_ERROR (transitions, i)) edge.color = red; else - edge.color = SHIFT_IS_SHIFT(shiftp, i) ? blue : green; + edge.color = TRANSITION_IS_SHIFT(transitions, i) ? blue : green; edge.label = symbol_tag_get (symbols[symbol]); output_edge (&edge, fgraph); close_edge (fgraph); diff --git a/src/state.c b/src/state.c index 9f6572b3..a23199e3 100644 --- a/src/state.c +++ b/src/state.c @@ -35,32 +35,32 @@ | Create a new array of N shifts/gotos. | `---------------------------------------*/ -#define SHIFTS_ALLOC(Nshifts) \ - (shifts_t *) xcalloc ((unsigned) (sizeof (shifts_t) \ +#define TRANSITIONS_ALLOC(Nshifts) \ + (transitions_t *) xcalloc ((unsigned) (sizeof (transitions_t) \ + (Nshifts - 1) * sizeof (state_number_t)), 1) -static shifts_t * -shifts_new (int nshifts, state_number_t *shifts) +static transitions_t * +transitions_new (int num, state_number_t *the_states) { - shifts_t *res = SHIFTS_ALLOC (nshifts); - res->nshifts = nshifts; - memcpy (res->shifts, shifts, nshifts * sizeof (shifts[0])); + transitions_t *res = TRANSITIONS_ALLOC (num); + res->num = num; + memcpy (res->states, the_states, num * sizeof (the_states[0])); return res; } -/*-----------------------------------------------------------------. -| Return the state such these SHIFTS contain a shift/goto to it on | -| SYMBOL. Aborts if none found. | -`-----------------------------------------------------------------*/ +/*-------------------------------------------------------------------. +| Return the state such these TRANSITIONS contain a shift/goto to it | +| on SYMBOL. Aborts if none found. | +`-------------------------------------------------------------------*/ state_t * -shifts_to (shifts_t *shifts, symbol_number_t s) +transitions_to (transitions_t *shifts, symbol_number_t s) { int j; - for (j = 0; j < shifts->nshifts; j++) - if (SHIFT_SYMBOL (shifts, j) == s) - return states[shifts->shifts[j]]; + for (j = 0; j < shifts->num; j++) + if (TRANSITION_SYMBOL (shifts, j) == s) + return states[shifts->states[j]]; abort (); } @@ -168,9 +168,9 @@ state_new (symbol_number_t accessing_symbol, `--------------------------*/ void -state_shifts_set (state_t *state, int nshifts, state_number_t *shifts) +state_transitions_set (state_t *state, int nshifts, state_number_t *shifts) { - state->shifts = shifts_new (nshifts, shifts); + state->shifts = transitions_new (nshifts, shifts); } diff --git a/src/state.h b/src/state.h index 08d9fa36..dd13a916 100644 --- a/src/state.h +++ b/src/state.h @@ -97,52 +97,54 @@ typedef short state_number_t; /* Be ready to map a state_number_t to an int. */ # define state_number_as_int(Tok) ((int) (Tok)) -/*---------. -| Shifts. | -`---------*/ +/*--------------. +| Transitions. | +`--------------*/ -typedef struct shifts_s +typedef struct transtion_s { - short nshifts; - state_number_t shifts[1]; -} shifts_t; + short num; + state_number_t states[1]; +} transitions_t; -/* What is the symbol which is shifted by SHIFTS->shifts[Shift]? Can +/* 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. */ -#define SHIFT_SYMBOL(Shifts, Shift) \ - (states[Shifts->shifts[Shift]]->accessing_symbol) +#define TRANSITION_SYMBOL(Transitions, Shift) \ + (states[Transitions->states[Shift]]->accessing_symbol) -/* Is the SHIFTS->shifts[Shift] a real shift? (as opposed to gotos.) */ +/* Is the TRANSITIONS->states[Shift] a real shift? (as opposed to gotos.) */ -#define SHIFT_IS_SHIFT(Shifts, Shift) \ - (ISTOKEN (SHIFT_SYMBOL (Shifts, Shift))) +#define TRANSITION_IS_SHIFT(Transitions, Shift) \ + (ISTOKEN (TRANSITION_SYMBOL (Transitions, Shift))) -/* Is the SHIFTS->shifts[Shift] a goto?. */ +/* Is the TRANSITIONS->states[Shift] a goto?. */ -#define SHIFT_IS_GOTO(Shifts, Shift) \ - (!SHIFT_IS_SHIFT (Shifts, Shift)) +#define TRANSITION_IS_GOTO(Transitions, Shift) \ + (!TRANSITION_IS_SHIFT (Transitions, Shift)) -/* Is the SHIFTS->shifts[Shift] then handling of the error token?. */ +/* Is the TRANSITIONS->states[Shift] then handling of the error token?. */ -#define SHIFT_IS_ERROR(Shifts, Shift) \ - (SHIFT_SYMBOL (Shifts, Shift) == errtoken->number) +#define TRANSITION_IS_ERROR(Transitions, Shift) \ + (TRANSITION_SYMBOL (Transitions, Shift) == errtoken->number) /* When resolving a SR conflicts, if the reduction wins, the shift is disabled. */ -#define SHIFT_DISABLE(Shifts, Shift) \ - (Shifts->shifts[Shift] = 0) +#define TRANSITION_DISABLE(Transitions, Shift) \ + (Transitions->states[Shift] = 0) -#define SHIFT_IS_DISABLED(Shifts, Shift) \ - (Shifts->shifts[Shift] == 0) +#define TRANSITION_IS_DISABLED(Transitions, Shift) \ + (Transitions->states[Shift] == 0) -/* Return the state such these SHIFTS contain a shift/goto to it on +/* Return the state such these TRANSITIONS contain a shift/goto to it on SYMBOL. Aborts if none found. */ struct state_s; -struct state_s *shifts_to PARAMS ((shifts_t *shifts, symbol_number_t s)); +struct state_s *transitions_to PARAMS ((transitions_t *state, + symbol_number_t s)); + /*-------. | Errs. | @@ -178,7 +180,7 @@ typedef struct state_s { state_number_t number; symbol_number_t accessing_symbol; - shifts_t *shifts; + transitions_t *shifts; reductions_t *reductions; errs_t *errs; @@ -214,7 +216,7 @@ state_t *state_new PARAMS ((symbol_number_t accessing_symbol, size_t core_size, item_number_t *core)); /* Set the shifts of STATE. */ -void state_shifts_set PARAMS ((state_t *state, +void state_transitions_set PARAMS ((state_t *state, int nshifts, state_number_t *shifts)); /* Set the reductions of STATE. */ -- 2.45.2