X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/c801dbf7d9e2c8d41917eb12dff81357378d75cd..55f0c7b1f26afabb7f356343f2650626e09fce51:/src/tables.c diff --git a/src/tables.c b/src/tables.c index b7f773f5..02d10f15 100644 --- a/src/tables.c +++ b/src/tables.c @@ -1,6 +1,7 @@ /* Output the generated parsing program for Bison. - Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002 - Free Software Foundation, Inc. + + Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004, + 2005 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -16,8 +17,8 @@ You should have received a copy of the GNU General Public License along with Bison; see the file COPYING. If not, write to the Free - Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA - 02111-1307, USA. */ + Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. */ #include "system.h" @@ -41,11 +42,21 @@ Of course vector_number_t ought to be wide enough to contain state_number and symbol_number. */ -typedef short vector_number; -#define state_number_to_vector_number(State) \ - ((vector_number) State) -#define symbol_number_to_vector_number(Symbol) \ - ((vector_number) (state_number_as_int (nstates) + Symbol - ntokens)) +typedef int vector_number; + +#if 0 /* Not currently used. */ +static inline vector_number +state_number_to_vector_number (state_number s) +{ + return s; +} +#endif + +static inline vector_number +symbol_number_to_vector_number (symbol_number sym) +{ + return state_number_as_int (nstates) + sym - ntokens; +} int nvectors; @@ -72,11 +83,11 @@ int nvectors; #define BASE_MAXIMUM INT_MAX #define BASE_MINIMUM INT_MIN -static base_number **froms = NULL; -static base_number **tos = NULL; -static unsigned int **conflict_tos = NULL; -static short *tally = NULL; -static base_number *width = NULL; +static base_number **froms; +static base_number **tos; +static unsigned int **conflict_tos; +static int *tally; +static base_number *width; /* For a given state, N = ACTROW[SYMBOL]: @@ -85,15 +96,15 @@ static base_number *width = NULL; If N = MIN, stands for `raise a syntax error'. If N > 0, stands for `shift SYMBOL and go to n'. If N < 0, stands for `reduce -N'. */ -typedef short action_number; -#define ACTION_NUMBER_MINIMUM SHRT_MIN +typedef int action_number; +#define ACTION_NUMBER_MINIMUM INT_MIN -static action_number *actrow = NULL; +static action_number *actrow; /* FROMS and TOS are reordered to be compressed. ORDER[VECTOR] is the new vector number of VECTOR. We skip `empty' vectors (i.e., TALLY[VECTOR] = 0), and call these `entries'. */ -static vector_number *order = NULL; +static vector_number *order; static int nentries; base_number *base = NULL; @@ -103,18 +114,18 @@ base_number *base = NULL; base_number base_ninf = 0; static base_number *pos = NULL; -static unsigned int *conflrow = NULL; -unsigned int *conflict_table = NULL; -unsigned int *conflict_list = NULL; +static unsigned int *conflrow; +unsigned int *conflict_table; +unsigned int *conflict_list; int conflict_list_cnt; static int conflict_list_free; /* TABLE_SIZE is the allocated size of both TABLE and CHECK. We start with more or less the original hard-coded value (which was SHRT_MAX). */ -static size_t table_size = 32768; -base_number *table = NULL; -base_number *check = NULL; +static int table_size = 32768; +base_number *table; +base_number *check; /* The value used in TABLE to denote explicit syntax errors (%nonassoc), a negative infinite. First defaults to ACTION_NUMBER_MININUM, but in order to keep small tables, renumbered as TABLE_ERROR, which @@ -133,9 +144,9 @@ rule_number *yydefact; `----------------------------------------------------------------*/ static void -table_grow (size_t desired) +table_grow (int desired) { - size_t old_size = table_size; + int old_size = table_size; while (table_size <= desired) table_size *= 2; @@ -144,13 +155,15 @@ table_grow (size_t desired) fprintf (stderr, "growing table and check from: %d to %d\n", old_size, table_size); - table = XREALLOC (table, base_number, table_size); - check = XREALLOC (check, base_number, table_size); - conflict_table = XREALLOC (conflict_table, unsigned int, table_size); + table = xnrealloc (table, table_size, sizeof *table); + conflict_table = xnrealloc (conflict_table, table_size, + sizeof *conflict_table); + check = xnrealloc (check, table_size, sizeof *check); for (/* Nothing. */; old_size < table_size; ++old_size) { table[old_size] = 0; + conflict_table[old_size] = 0; check[old_size] = -1; } } @@ -160,7 +173,7 @@ table_grow (size_t desired) /*-------------------------------------------------------------------. | For GLR parsers, for each conflicted token in S, as indicated | -| by non-zero entries in CONFLROW, create a list of possible | +| 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 S. Store the alternative | | reductions followed by a 0 in CONFLICT_LIST, updating | @@ -174,7 +187,7 @@ conflict_row (state *s) int i, j; reductions *reds = s->reductions; - if (! glr_parser) + if (!nondeterministic_parser) return; for (j = 0; j < ntokens; j += 1) @@ -185,7 +198,7 @@ conflict_row (state *s) /* Find all reductions for token J, and record all that do not match ACTROW[J]. */ for (i = 0; i < reds->num; i += 1) - if (bitset_test (reds->lookaheads[i], j) + if (bitset_test (reds->look_ahead_tokens[i], j) && (actrow[j] != rule_number_as_item_number (reds->rules[i]->number))) { @@ -199,6 +212,7 @@ conflict_row (state *s) /* Leave a 0 at the end. */ if (conflict_list_free <= 0) abort (); + conflict_list[conflict_list_cnt] = 0; conflict_list_cnt += 1; conflict_list_free -= 1; } @@ -206,8 +220,8 @@ conflict_row (state *s) /*------------------------------------------------------------------. -| Decide what to do for each type of token if seen as the lookahead | -| token in specified state. The value returned is used as the | +| Decide what to do for each type of token if seen as the | +| look-ahead in specified state. The value returned is used as the | | default action (yydefact) for the state. In addition, ACTROW is | | filled with what to do for each kind of token, index by symbol | | number, with zero meaning do the default action. The value | @@ -215,7 +229,7 @@ conflict_row (state *s) | situation is an error. The parser recognizes this value | | specially. | | | -| This is where conflicts are resolved. The loop over lookahead | +| This is where conflicts are resolved. The loop over look-ahead | | rules considered lower-numbered rules last, and the last rule | | considered that likes a token gets to handle it. | | | @@ -234,28 +248,31 @@ action_row (state *s) transitions *trans = s->transitions; errs *errp = s->errs; /* Set to nonzero to inhibit having any default reduction. */ - int nodefault = 0; - int conflicted = 0; + bool nodefault = false; + bool conflicted = false; for (i = 0; i < ntokens; i++) actrow[i] = conflrow[i] = 0; - if (reds->lookaheads) + if (reds->look_ahead_tokens) { int j; bitset_iterator biter; /* loop over all the rules available here which require - lookahead (in reverse order to give precedence to the first + look-ahead (in reverse order to give precedence to the first rule) */ for (i = reds->num - 1; i >= 0; --i) /* and find each token which the rule finds acceptable to come next */ - BITSET_FOR_EACH (biter, reds->lookaheads[i], j, 0) + BITSET_FOR_EACH (biter, reds->look_ahead_tokens[i], j, 0) { /* and record this rule as the rule to use if that token follows. */ if (actrow[j] != 0) - conflicted = conflrow[j] = 1; + { + conflicted = true; + conflrow[j] = 1; + } actrow[j] = rule_number_as_item_number (reds->rules[i]->number); } } @@ -269,13 +286,16 @@ action_row (state *s) state *shift_state = trans->states[i]; if (actrow[sym] != 0) - conflicted = conflrow[sym] = 1; + { + conflicted = true; + conflrow[sym] = 1; + } actrow[sym] = state_number_as_int (shift_state->number); /* Do not use any default reduction if there is a shift for error */ if (sym == errtoken->number) - nodefault = 1; + nodefault = true; } /* See which tokens are an explicit error in this state (due to @@ -325,7 +345,7 @@ action_row (state *s) int j; for (j = 0; j < ntokens; j++) if (actrow[j] == rule_number_as_item_number (default_rule->number) - && ! (glr_parser && conflrow[j])) + && ! (nondeterministic_parser && conflrow[j])) actrow[j] = 0; } } @@ -355,10 +375,10 @@ save_row (state_number s) { symbol_number i; int count; - base_number *sp = NULL; - base_number *sp1 = NULL; - base_number *sp2 = NULL; - unsigned int *sp3 = NULL; + base_number *sp; + base_number *sp1; + base_number *sp2; + unsigned int *sp3; /* Number of non default actions in S. */ count = 0; @@ -370,12 +390,10 @@ save_row (state_number s) return; /* Allocate non defaulted actions. */ - froms[s] = sp1 = sp = XCALLOC (base_number, count); - tos[s] = sp2 = XCALLOC (base_number, count); - if (glr_parser) - conflict_tos[s] = sp3 = XCALLOC (unsigned int, count); - else - conflict_tos[s] = NULL; + froms[s] = sp = sp1 = xnmalloc (count, sizeof *sp1); + tos[s] = sp2 = xnmalloc (count, sizeof *sp2); + conflict_tos[s] = sp3 = + nondeterministic_parser ? xnmalloc (count, sizeof *sp3) : NULL; /* Store non defaulted actions. */ for (i = 0; i < ntokens; i++) @@ -383,7 +401,7 @@ save_row (state_number s) { *sp1++ = i; *sp2++ = actrow[i]; - if (glr_parser) + if (nondeterministic_parser) *sp3++ = conflrow[i]; } @@ -394,7 +412,7 @@ save_row (state_number s) /*------------------------------------------------------------------. | Figure out the actions for the specified state, indexed by | -| lookahead token type. | +| look-ahead token type. | | | | The YYDEFACT table is output now. The detailed info is saved for | | putting into YYTABLE later. | @@ -407,19 +425,19 @@ token_actions (void) symbol_number j; rule_number r; - int nconflict = glr_parser ? conflicts_total_count () : 0; + int nconflict = nondeterministic_parser ? conflicts_total_count () : 0; - yydefact = XCALLOC (rule_number, nstates); + yydefact = xnmalloc (nstates, sizeof *yydefact); - actrow = XCALLOC (action_number, ntokens); - conflrow = XCALLOC (unsigned int, ntokens); + actrow = xnmalloc (ntokens, sizeof *actrow); + conflrow = xnmalloc (ntokens, sizeof *conflrow); - conflict_list = XCALLOC (unsigned int, 1 + 2 * nconflict); + conflict_list = xnmalloc (1 + 2 * nconflict, sizeof *conflict_list); conflict_list_free = 2 * nconflict; conflict_list_cnt = 1; /* Find the rules which are reduced. */ - if (!glr_parser) + if (!nondeterministic_parser) for (r = 0; r < nrules; ++r) rules[r].useful = false; @@ -432,7 +450,7 @@ token_actions (void) /* Now that the parser was computed, we can find which rules are really reduced, and which are not because of SR or RR conflicts. */ - if (!glr_parser) + if (!nondeterministic_parser) { for (j = 0; j < ntokens; ++j) if (actrow[j] < 0 && actrow[j] != ACTION_NUMBER_MINIMUM) @@ -459,15 +477,15 @@ token_actions (void) static void save_column (symbol_number sym, state_number default_state) { - int i; + goto_number i; base_number *sp; base_number *sp1; base_number *sp2; int count; vector_number symno = symbol_number_to_vector_number (sym); - goto_number begin = goto_map[sym]; - goto_number end = goto_map[sym + 1]; + goto_number begin = goto_map[sym - ntokens]; + goto_number end = goto_map[sym - ntokens + 1]; /* Number of non default GOTO. */ count = 0; @@ -479,8 +497,8 @@ save_column (symbol_number sym, state_number default_state) return; /* Allocate room for non defaulted gotos. */ - froms[symno] = sp1 = sp = XCALLOC (base_number, count); - tos[symno] = sp2 = XCALLOC (base_number, count); + froms[symno] = sp = sp1 = xnmalloc (count, sizeof *sp1); + tos[symno] = sp2 = xnmalloc (count, sizeof *sp2); /* Store the state numbers of the non defaulted gotos. */ for (i = begin; i < end; i++) @@ -500,17 +518,17 @@ save_column (symbol_number sym, state_number default_state) `-------------------------------------------------------------*/ static state_number -default_goto (symbol_number sym, short state_count[]) +default_goto (symbol_number sym, size_t state_count[]) { state_number s; - int i; - goto_number m = goto_map[sym]; - goto_number n = goto_map[sym + 1]; - state_number default_state = (state_number) -1; - int max = 0; + goto_number i; + goto_number m = goto_map[sym - ntokens]; + goto_number n = goto_map[sym - ntokens + 1]; + state_number default_state = -1; + size_t max = 0; if (m == n) - return (state_number) -1; + return -1; for (s = 0; s < nstates; s++) state_count[s] = 0; @@ -542,8 +560,8 @@ static void goto_actions (void) { symbol_number i; - short *state_count = XCALLOC (short, nstates); - yydefgoto = XMALLOC (state_number, nvars); + size_t *state_count = xnmalloc (nstates, sizeof *state_count); + yydefgoto = xnmalloc (nvars, sizeof *yydefgoto); /* For a given nterm I, STATE_COUNT[S] is the number of times there is a GOTO to S on I. */ @@ -607,7 +625,7 @@ matching_state (vector_number vector) int prev; /* If VECTOR is a nterm, return -1. */ - if (i >= (int) nstates) + if (nstates <= i) return -1; t = tally[i]; @@ -657,30 +675,30 @@ pack_vector (vector_number vector) base_number *to = tos[i]; unsigned int *conflict_to = conflict_tos[i]; - if (! t) + if (!t) abort (); for (j = lowzero - from[0]; ; j++) { int k; - int ok = 1; + bool ok = true; - if ((int) table_size <= j) + if (table_size <= j) abort (); for (k = 0; ok && k < t; k++) { loc = j + state_number_as_int (from[k]); - if (loc >= (int) table_size) + if (table_size <= loc) table_grow (loc); if (table[loc] != 0) - ok = 0; + ok = false; } for (k = 0; ok && k < vector; k++) if (pos[k] == j) - ok = 0; + ok = false; if (ok) { @@ -688,7 +706,7 @@ pack_vector (vector_number vector) { loc = j + from[k]; table[loc] = to[k]; - if (glr_parser && conflict_to != NULL) + if (nondeterministic_parser && conflict_to != NULL) conflict_table[loc] = conflict_to[k]; check[loc] = from[k]; } @@ -716,10 +734,10 @@ pack_vector (vector_number vector) `-------------------------------------------------------------*/ static base_number -table_ninf_remap (base_number tab[], size_t size, base_number ninf) +table_ninf_remap (base_number tab[], int size, base_number ninf) { base_number res = 0; - size_t i; + int i; for (i = 0; i < size; i++) if (tab[i] < res && tab[i] != ninf) @@ -739,11 +757,11 @@ pack_table (void) { int i; - base = XCALLOC (base_number, nvectors); - pos = XCALLOC (base_number, nentries); - table = XCALLOC (base_number, table_size); - conflict_table = XCALLOC (unsigned int, table_size); - check = XCALLOC (base_number, table_size); + base = xnmalloc (nvectors, sizeof *base); + pos = xnmalloc (nentries, sizeof *pos); + table = xcalloc (table_size, sizeof *table); + conflict_table = xcalloc (table_size, sizeof *conflict_table); + check = xnmalloc (table_size, sizeof *check); lowzero = 0; high = 0; @@ -751,7 +769,7 @@ pack_table (void) for (i = 0; i < nvectors; i++) base[i] = BASE_MINIMUM; - for (i = 0; i < (int) table_size; i++) + for (i = 0; i < table_size; i++) check[i] = -1; for (i = 0; i < nentries; i++) @@ -792,26 +810,25 @@ tables_generate (void) /* This is a poor way to make sure the sizes are properly correlated. In particular the signedness is not taken into account. But it's not useless. */ - verify (sizes_are_properly_correlated, - (sizeof nstates <= sizeof nvectors - && sizeof nvars <= sizeof nvectors)); + verify (sizeof nstates <= sizeof nvectors + && sizeof nvars <= sizeof nvectors); nvectors = state_number_as_int (nstates) + nvars; - froms = XCALLOC (base_number *, nvectors); - tos = XCALLOC (base_number *, nvectors); - conflict_tos = XCALLOC (unsigned int *, nvectors); - tally = XCALLOC (short, nvectors); - width = XCALLOC (base_number, nvectors); + froms = xcalloc (nvectors, sizeof *froms); + tos = xcalloc (nvectors, sizeof *tos); + conflict_tos = xcalloc (nvectors, sizeof *conflict_tos); + tally = xcalloc (nvectors, sizeof *tally); + width = xnmalloc (nvectors, sizeof *width); token_actions (); goto_actions (); - free (goto_map + ntokens); + free (goto_map); free (from_state); free (to_state); - order = XCALLOC (vector_number, nvectors); + order = xcalloc (nvectors, sizeof *order); sort_actions (); pack_table (); free (order); @@ -823,7 +840,7 @@ tables_generate (void) { free (froms[i]); free (tos[i]); - XFREE (conflict_tos[i]); + free (conflict_tos[i]); } free (froms);