X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/8dd162d3ff10fd7fb6f748a885f8055232691c48..fcd32abd3a4b68ef525d7766dbed1c98465e23b9:/src/tables.c?ds=inline diff --git a/src/tables.c b/src/tables.c index 50dd4535..d1f7e7d9 100644 --- a/src/tables.c +++ b/src/tables.c @@ -1,26 +1,24 @@ /* Output the generated parsing program for Bison. - Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004 - Free Software Foundation, Inc. + Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004, + 2005, 2006, 2009 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. - Bison is free software; you can redistribute it and/or modify it - under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. - Bison is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. 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. */ - + along with this program. If not, see . */ +#include #include "system.h" #include @@ -32,6 +30,7 @@ #include "getargs.h" #include "gram.h" #include "lalr.h" +#include "muscle-tab.h" #include "reader.h" #include "symtab.h" #include "tables.h" @@ -42,13 +41,15 @@ Of course vector_number_t ought to be wide enough to contain state_number and symbol_number. */ -typedef short int vector_number; +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) @@ -81,11 +82,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 int *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]: @@ -94,15 +95,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 int 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; @@ -112,9 +113,9 @@ 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; @@ -122,10 +123,10 @@ static int conflict_list_free; with more or less the original hard-coded value (which was SHRT_MAX). */ static int table_size = 32768; -base_number *table = NULL; -base_number *check = NULL; +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, + (%nonassoc), a negative infinite. First defaults to ACTION_NUMBER_MINIMUM, but in order to keep small tables, renumbered as TABLE_ERROR, which is the smallest (non error) value minus 1. */ base_number table_ninf = 0; @@ -153,13 +154,15 @@ table_grow (int desired) fprintf (stderr, "growing table and check from: %d to %d\n", old_size, table_size); - REALLOC (table, table_size); - REALLOC (check, table_size); - REALLOC (conflict_table, 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; } } @@ -169,7 +172,7 @@ table_grow (int 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 | @@ -194,20 +197,19 @@ 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->look_ahead_tokens[i], j) + if (bitset_test (reds->lookahead_tokens[i], j) && (actrow[j] != rule_number_as_item_number (reds->rules[i]->number))) { - if (conflict_list_free <= 0) - abort (); + aver (0 < conflict_list_free); conflict_list[conflict_list_cnt] = reds->rules[i]->number + 1; conflict_list_cnt += 1; conflict_list_free -= 1; } /* Leave a 0 at the end. */ - if (conflict_list_free <= 0) - abort (); + aver (0 < conflict_list_free); + conflict_list[conflict_list_cnt] = 0; conflict_list_cnt += 1; conflict_list_free -= 1; } @@ -216,7 +218,7 @@ conflict_row (state *s) /*------------------------------------------------------------------. | 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 | +| lookahead 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 | @@ -224,7 +226,7 @@ conflict_row (state *s) | situation is an error. The parser recognizes this value | | specially. | | | -| This is where conflicts are resolved. The loop over look-ahead | +| This is where conflicts are resolved. The loop over lookahead | | rules considered lower-numbered rules last, and the last rule | | considered that likes a token gets to handle it. | | | @@ -238,7 +240,7 @@ static rule * action_row (state *s) { int i; - rule *default_rule = NULL; + rule *default_reduction = NULL; reductions *reds = s->reductions; transitions *trans = s->transitions; errs *errp = s->errs; @@ -249,17 +251,17 @@ action_row (state *s) for (i = 0; i < ntokens; i++) actrow[i] = conflrow[i] = 0; - if (reds->look_ahead_tokens) + if (reds->lookahead_tokens) { int j; bitset_iterator biter; /* loop over all the rules available here which require - look-ahead (in reverse order to give precedence to the first + lookahead (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->look_ahead_tokens[i], j, 0) + BITSET_FOR_EACH (biter, reds->lookahead_tokens[i], j, 0) { /* and record this rule as the rule to use if that token follows. */ @@ -302,13 +304,24 @@ action_row (state *s) actrow[sym->number] = ACTION_NUMBER_MINIMUM; } + /* Turn off default reductions where requested by the user. See + state_lookahead_tokens_count in lalr.c to understand when states are + labeled as consistent. */ + { + char *default_reductions = + muscle_percent_define_get ("lr.default-reductions"); + if (0 != strcmp (default_reductions, "all") && !s->consistent) + nodefault = true; + free (default_reductions); + } + /* Now find the most common reduction and make it the default action for this state. */ if (reds->num >= 1 && !nodefault) { if (s->consistent) - default_rule = reds->rules[0]; + default_reduction = reds->rules[0]; else { int max = 0; @@ -325,7 +338,7 @@ action_row (state *s) if (count > max) { max = count; - default_rule = r; + default_reduction = r; } } @@ -339,17 +352,18 @@ action_row (state *s) { int j; for (j = 0; j < ntokens; j++) - if (actrow[j] == rule_number_as_item_number (default_rule->number) + if (actrow[j] + == rule_number_as_item_number (default_reduction->number) && ! (nondeterministic_parser && conflrow[j])) actrow[j] = 0; } } } - /* If have no default rule, the default is an error. + /* If have no default reduction, the default is an error. So replace any action which says "error" with "use default". */ - if (!default_rule) + if (!default_reduction) for (i = 0; i < ntokens; i++) if (actrow[i] == ACTION_NUMBER_MINIMUM) actrow[i] = 0; @@ -357,7 +371,7 @@ action_row (state *s) if (conflicted) conflict_row (s); - return default_rule; + return default_reduction; } @@ -373,7 +387,7 @@ save_row (state_number s) base_number *sp; base_number *sp1; base_number *sp2; - unsigned int *sp3 IF_LINT (= NULL); + unsigned int *sp3; /* Number of non default actions in S. */ count = 0; @@ -385,9 +399,10 @@ save_row (state_number s) return; /* Allocate non defaulted actions. */ - froms[s] = sp = CALLOC (sp1, count); - tos[s] = CALLOC (sp2, count); - conflict_tos[s] = nondeterministic_parser ? CALLOC (sp3, count) : 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++) @@ -406,7 +421,7 @@ save_row (state_number s) /*------------------------------------------------------------------. | Figure out the actions for the specified state, indexed by | -| look-ahead token type. | +| lookahead token type. | | | | The YYDEFACT table is output now. The detailed info is saved for | | putting into YYTABLE later. | @@ -421,12 +436,12 @@ token_actions (void) int nconflict = nondeterministic_parser ? conflicts_total_count () : 0; - CALLOC (yydefact, nstates); + yydefact = xnmalloc (nstates, sizeof *yydefact); - CALLOC (actrow, ntokens); - CALLOC (conflrow, ntokens); + actrow = xnmalloc (ntokens, sizeof *actrow); + conflrow = xnmalloc (ntokens, sizeof *conflrow); - CALLOC (conflict_list, 1 + 2 * nconflict); + conflict_list = xnmalloc (1 + 2 * nconflict, sizeof *conflict_list); conflict_list_free = 2 * nconflict; conflict_list_cnt = 1; @@ -437,8 +452,8 @@ token_actions (void) for (i = 0; i < nstates; ++i) { - rule *default_rule = action_row (states[i]); - yydefact[i] = default_rule ? default_rule->number + 1 : 0; + rule *default_reduction = action_row (states[i]); + yydefact[i] = default_reduction ? default_reduction->number + 1 : 0; save_row (i); /* Now that the parser was computed, we can find which rules are @@ -471,7 +486,7 @@ 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; @@ -491,8 +506,8 @@ save_column (symbol_number sym, state_number default_state) return; /* Allocate room for non defaulted gotos. */ - froms[symno] = sp = CALLOC (sp1, count); - tos[symno] = CALLOC (sp2, 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++) @@ -512,14 +527,14 @@ save_column (symbol_number sym, state_number default_state) `-------------------------------------------------------------*/ static state_number -default_goto (symbol_number sym, short int state_count[]) +default_goto (symbol_number sym, size_t state_count[]) { state_number s; - int i; + goto_number i; goto_number m = goto_map[sym - ntokens]; goto_number n = goto_map[sym - ntokens + 1]; state_number default_state = -1; - int max = 0; + size_t max = 0; if (m == n) return -1; @@ -554,8 +569,8 @@ static void goto_actions (void) { symbol_number i; - short int *state_count = CALLOC (state_count, nstates); - MALLOC (yydefgoto, 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. */ @@ -669,16 +684,14 @@ pack_vector (vector_number vector) base_number *to = tos[i]; unsigned int *conflict_to = conflict_tos[i]; - if (!t) - abort (); + aver (t != 0); for (j = lowzero - from[0]; ; j++) { int k; bool ok = true; - if (table_size <= j) - abort (); + aver (j < table_size); for (k = 0; ok && k < t; k++) { @@ -711,8 +724,7 @@ pack_vector (vector_number vector) if (loc > high) high = loc; - if (! (BASE_MINIMUM <= j && j <= BASE_MAXIMUM)) - abort (); + aver (BASE_MINIMUM <= j && j <= BASE_MAXIMUM); return j; } } @@ -751,11 +763,11 @@ pack_table (void) { int i; - CALLOC (base, nvectors); - CALLOC (pos, nentries); - CALLOC (table, table_size); - CALLOC (conflict_table, table_size); - CALLOC (check, 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; @@ -804,17 +816,16 @@ 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; - CALLOC (froms, nvectors); - CALLOC (tos, nvectors); - CALLOC (conflict_tos, nvectors); - CALLOC (tally, nvectors); - CALLOC (width, 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 (); @@ -823,7 +834,7 @@ tables_generate (void) free (from_state); free (to_state); - CALLOC (order, nvectors); + order = xcalloc (nvectors, sizeof *order); sort_actions (); pack_table (); free (order); @@ -835,7 +846,7 @@ tables_generate (void) { free (froms[i]); free (tos[i]); - XFREE (conflict_tos[i]); + free (conflict_tos[i]); } free (froms);