X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/05846dae07d2113181fb791fc9c5f9382edc35ce..82f3355eaf8d5988391021262dc9acfa6485c098:/src/tables.c?ds=sidebyside diff --git a/src/tables.c b/src/tables.c index a615204a..ef37fbab 100644 --- a/src/tables.c +++ b/src/tables.c @@ -1,121 +1,66 @@ -/* Output the generated parsing program for bison, - Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002 - Free Software Foundation, Inc. +/* Output the generated parsing program for Bison. + + Copyright (C) 1984, 1986, 1989, 1992, 2000-2006, 2009-2011 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. */ - - -/* The parser tables consist of these tables. - - YYTRANSLATE = vector mapping yylex's token numbers into bison's - token numbers. - - YYTNAME = vector of string-names indexed by bison token number. - - YYTOKNUM = vector of yylex token numbers corresponding to entries - in YYTNAME. - - YYRLINE = vector of line-numbers of all rules. For yydebug - printouts. - - YYRHS = vector of items of all rules. This is exactly what RITEMS - contains. For yydebug and for semantic parser. - - YYPRHS[R] = index in YYRHS of first item for rule R. - - YYR1[R] = symbol number of symbol that rule R derives. - - YYR2[R] = number of symbols composing right hand side of rule R. - - YYSTOS[S] = the symbol number of the symbol that leads to state S. - - YYDEFACT[S] = default rule to reduce with in state s, when YYTABLE - doesn't specify something else to do. Zero means the default is an - error. - - YYDEFGOTO[I] = default state to go to after a reduction of a rule - that generates variable NTOKENS + I, except when YYTABLE specifies - something else to do. + along with this program. If not, see . */ - YYPACT[S] = index in YYTABLE of the portion describing state S. - The lookahead token's type is used to index that portion to find - out what to do. - - If the value in YYTABLE is positive, we shift the token and go to - that state. - - If the value is negative, it is minus a rule number to reduce by. - - If the value is zero, the default action from YYDEFACT[S] is used. - - YYPGOTO[I] = the index in YYTABLE of the portion describing what to - do after reducing a rule that derives variable I + NTOKENS. This - portion is indexed by the parser state number, S, as of before the - text for this nonterminal was read. The value from YYTABLE is the - state to go to if the corresponding value in YYCHECK is S. - - YYTABLE = a vector filled with portions for different uses, found - via YYPACT and YYPGOTO. - - YYCHECK = a vector indexed in parallel with YYTABLE. It indicates, - in a roundabout way, the bounds of the portion you are trying to - examine. - - Suppose that the portion of YYTABLE starts at index P and the index - to be examined within the portion is I. Then if YYCHECK[P+I] != I, - I is outside the bounds of what is actually allocated, and the - default (from YYDEFACT or YYDEFGOTO) should be used. Otherwise, - YYTABLE[P+I] should be used. +#include +#include "system.h" - YYFINAL = the state number of the termination state. YYFLAG = most - negative short int. Used to flag ?? */ +#include +#include -#include "system.h" -#include "bitsetv.h" -#include "quotearg.h" -#include "getargs.h" +#include "complain.h" +#include "conflicts.h" #include "files.h" +#include "getargs.h" #include "gram.h" -#include "complain.h" #include "lalr.h" +#include "muscle-tab.h" #include "reader.h" #include "symtab.h" -#include "conflicts.h" #include "tables.h" -/* Several tables will be indexed both by state and nonterminal - numbers. We call `vector' such a thing (= either a state or a - symbol number. +/* Several tables are indexed both by state and nonterminal numbers. + We call such an index a `vector'; i.e., a vector is either a state + or a nonterminal number. Of course vector_number_t ought to be wide enough to contain - state_number_t and symbol_number_t. */ -typedef short vector_number_t; -#define VECTOR_NUMBER_MAX ((vector_number_t) SHRT_MAX) -#define VECTOR_NUMBER_MIN ((vector_number_t) SHRT_MIN) -#define state_number_to_vector_number(State) \ - ((vector_number_t) State) -#define symbol_number_to_vector_number(Symbol) \ - ((vector_number_t) (state_number_as_int (nstates) + Symbol - ntokens)) + state_number and symbol_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) +{ + return state_number_as_int (nstates) + sym - ntokens; +} int nvectors; -/* FROMS and TOS are indexed by vector_number_t. +/* FROMS and TOS are indexed by vector_number. If VECTOR is a nonterminal, (FROMS[VECTOR], TOS[VECTOR]) form an array of state numbers of the non defaulted GOTO on VECTOR. @@ -128,69 +73,68 @@ int nvectors; (FROMS[VECTOR][SIZE] - FROMS[VECTOR][0] + 1) where SIZE = TALLY[VECTOR]. - FROMS therefore contains symbol_number_t and action_number_t, - TOS state_number_t and action_number_t, + FROMS therefore contains symbol_number and action_number, + TOS state_number and action_number, TALLY sizes, WIDTH differences of FROMS. - Let base_t be the type of FROMS, TOS, and WIDTH. */ -#define BASE_MAX ((base_t) INT_MAX) -#define BASE_MIN ((base_t) INT_MIN) + Let base_number be the type of FROMS, TOS, and WIDTH. */ +#define BASE_MAXIMUM INT_MAX +#define BASE_MINIMUM INT_MIN -static base_t **froms = NULL; -static base_t **tos = NULL; -static unsigned int **conflict_tos = NULL; -static short *tally = NULL; -static base_t *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]: If N = 0, stands for `run the default action'. - If N = MIN, stands for `raise a parse error'. + 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_t; -#define ACTION_MAX ((action_t) SHRT_MAX) -#define ACTION_MIN ((action_t) SHRT_MIN) +typedef int action_number; +#define ACTION_NUMBER_MINIMUM INT_MIN -static action_t *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_t *order = NULL; +static vector_number *order; static int nentries; -base_t *base = NULL; +base_number *base = NULL; /* A distinguished value of BASE, negative infinite. During the - computation equals to BASE_MIN, later mapped to BASE_NINF to + computation equals to BASE_MINIMUM, later mapped to BASE_NINF to keep parser tables small. */ -base_t base_ninf = 0; -static base_t *pos = 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_t *table = NULL; -base_t *check = NULL; -/* The value used in TABLE to denote explicit parse errors - (%nonassoc), a negative infinite. First defaults to ACTION_MIN, +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_MINIMUM, but in order to keep small tables, renumbered as TABLE_ERROR, which is the smallest (non error) value minus 1. */ -base_t table_ninf = 0; +base_number table_ninf = 0; static int lowzero; int high; -state_number_t *yydefgoto; -rule_number_t *yydefact; +state_number *yydefgoto; +rule_number *yydefact; /*----------------------------------------------------------------. | If TABLE (and CHECK) appear to be small to be addressed at | @@ -199,9 +143,9 @@ rule_number_t *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; @@ -210,13 +154,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_t, table_size); - check = XREALLOC (check, base_t, 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; } } @@ -225,22 +171,22 @@ table_grow (size_t desired) /*-------------------------------------------------------------------. -| For GLR parsers, for each conflicted token in STATE, as indicated | -| by non-zero entries in CONFLROW, create a list of possible | +| For GLR parsers, for each conflicted token in S, as indicated | +| 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 STATE. Store the alternative | +| currently recorded for that token in S. Store the alternative | | reductions followed by a 0 in CONFLICT_LIST, updating | | CONFLICT_LIST_CNT, and storing an index to the start of the list | | back into CONFLROW. | `-------------------------------------------------------------------*/ static void -conflict_row (state_t *state) +conflict_row (state *s) { int i, j; - reductions_t *reds = state->reductions; + reductions *reds = s->reductions; - if (! glr_parser) + if (!nondeterministic_parser) return; for (j = 0; j < ntokens; j += 1) @@ -251,18 +197,19 @@ conflict_row (state_t *state) /* 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->lookahead_tokens[i], j) && (actrow[j] != rule_number_as_item_number (reds->rules[i]->number))) { - assert (conflict_list_free > 0); + 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. */ - assert (conflict_list_free > 0); + aver (0 < conflict_list_free); + conflict_list[conflict_list_cnt] = 0; conflict_list_cnt += 1; conflict_list_free -= 1; } @@ -270,13 +217,14 @@ conflict_row (state_t *state) /*------------------------------------------------------------------. -| 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 | +| 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 | -| ACTION_MIN, a very negative number, means this situation is an | -| error. The parser recognizes this value specially. | +| ACTION_NUMBER_MINIMUM, a very negative number, means this | +| situation is an error. The parser recognizes this value | +| specially. | | | | This is where conflicts are resolved. The loop over lookahead | | rules considered lower-numbered rules last, and the last rule | @@ -288,91 +236,109 @@ conflict_row (state_t *state) | that has any such conflicts. | `------------------------------------------------------------------*/ -static rule_t * -action_row (state_t *state) +static rule * +action_row (state *s) { int i; - rule_t *default_rule = NULL; - reductions_t *redp = state->reductions; - transitions_t *transitions = state->transitions; - errs_t *errp = state->errs; + rule *default_reduction = NULL; + reductions *reds = s->reductions; + 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 (redp->lookaheads) + if (reds->lookahead_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 rule) */ - for (i = redp->num - 1; i >= 0; --i) + for (i = reds->num - 1; i >= 0; --i) /* and find each token which the rule finds acceptable to come next */ - BITSET_FOR_EACH (biter, redp->lookaheads[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. */ if (actrow[j] != 0) - conflicted = conflrow[j] = 1; - actrow[j] = rule_number_as_item_number (redp->rules[i]->number); + { + conflicted = true; + conflrow[j] = 1; + } + actrow[j] = rule_number_as_item_number (reds->rules[i]->number); } } /* 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_EACH_SHIFT (transitions, i) + FOR_EACH_SHIFT (trans, i) { - symbol_number_t symbol = TRANSITION_SYMBOL (transitions, i); - state_t *shift_state = transitions->states[i]; + symbol_number sym = TRANSITION_SYMBOL (trans, i); + state *shift_state = trans->states[i]; - if (actrow[symbol] != 0) - conflicted = conflrow[symbol] = 1; - actrow[symbol] = state_number_as_int (shift_state->number); + if (actrow[sym] != 0) + { + 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 (symbol == errtoken->number) - nodefault = 1; + if (sym == errtoken->number) + nodefault = true; } /* See which tokens are an explicit error in this state (due to - %nonassoc). For them, record ACTION_MIN as the action. */ + %nonassoc). For them, record ACTION_NUMBER_MINIMUM as the + action. */ for (i = 0; i < errp->num; i++) { - symbol_t *symbol = errp->symbols[i]; - actrow[symbol->number] = ACTION_MIN; + symbol *sym = errp->symbols[i]; + 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 (redp->num >= 1 && !nodefault) + if (reds->num >= 1 && !nodefault) { - if (state->consistent) - default_rule = redp->rules[0]; + if (s->consistent) + default_reduction = reds->rules[0]; else { int max = 0; - for (i = 0; i < redp->num; i++) + for (i = 0; i < reds->num; i++) { int count = 0; - rule_t *rule = redp->rules[i]; - symbol_number_t j; + rule *r = reds->rules[i]; + symbol_number j; for (j = 0; j < ntokens; j++) - if (actrow[j] == rule_number_as_item_number (rule->number)) + if (actrow[j] == rule_number_as_item_number (r->number)) count++; if (count > max) { max = count; - default_rule = rule; + default_reduction = r; } } @@ -386,43 +352,44 @@ action_row (state_t *state) { int j; for (j = 0; j < ntokens; j++) - if (actrow[j] == rule_number_as_item_number (default_rule->number) - && ! (glr_parser && conflrow[j])) + 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_MIN) + if (actrow[i] == ACTION_NUMBER_MINIMUM) actrow[i] = 0; if (conflicted) - conflict_row (state); + conflict_row (s); - return default_rule; + return default_reduction; } -/*--------------------------------------------. -| Set FROMS, TOS, TALLY and WIDTH for STATE. | -`--------------------------------------------*/ +/*----------------------------------------. +| Set FROMS, TOS, TALLY and WIDTH for S. | +`----------------------------------------*/ static void -save_row (state_number_t state) +save_row (state_number s) { - symbol_number_t i; + symbol_number i; int count; - base_t *sp = NULL; - base_t *sp1 = NULL; - base_t *sp2 = NULL; - unsigned int *sp3 = NULL; + base_number *sp; + base_number *sp1; + base_number *sp2; + unsigned int *sp3; - /* Number of non default actions in STATE. */ + /* Number of non default actions in S. */ count = 0; for (i = 0; i < ntokens; i++) if (actrow[i] != 0) @@ -432,12 +399,10 @@ save_row (state_number_t state) return; /* Allocate non defaulted actions. */ - froms[state] = sp1 = sp = XCALLOC (base_t, count); - tos[state] = sp2 = XCALLOC (base_t, count); - if (glr_parser) - conflict_tos[state] = sp3 = XCALLOC (unsigned int, count); - else - conflict_tos[state] = 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++) @@ -445,12 +410,12 @@ save_row (state_number_t state) { *sp1++ = i; *sp2++ = actrow[i]; - if (glr_parser) + if (nondeterministic_parser) *sp3++ = conflrow[i]; } - tally[state] = count; - width[state] = sp1[-1] - sp[0] + 1; + tally[s] = count; + width[s] = sp1[-1] - sp[0] + 1; } @@ -465,42 +430,42 @@ save_row (state_number_t state) static void token_actions (void) { - state_number_t i; - symbol_number_t j; - rule_number_t r; + state_number i; + 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_t, nstates); + yydefact = xnmalloc (nstates, sizeof *yydefact); - actrow = XCALLOC (action_t, 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; + rules[r].useful = false; for (i = 0; i < nstates; ++i) { - rule_t *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 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_MIN) - rules[item_number_as_rule_number (actrow[j])].useful = TRUE; + if (actrow[j] < 0 && actrow[j] != ACTION_NUMBER_MINIMUM) + rules[item_number_as_rule_number (actrow[j])].useful = true; if (yydefact[i]) - rules[yydefact[i] - 1].useful = TRUE; + rules[yydefact[i] - 1].useful = true; } } @@ -512,24 +477,24 @@ token_actions (void) /*------------------------------------------------------------------. | Compute FROMS[VECTOR], TOS[VECTOR], TALLY[VECTOR], WIDTH[VECTOR], | | i.e., the information related to non defaulted GOTO on the nterm | -| SYMBOL. | +| SYM. | | | -| DEFAULT_STATE is the principal destination on SYMBOL, i.e., the | -| default GOTO destination on SYMBOL. | +| DEFAULT_STATE is the principal destination on SYM, i.e., the | +| default GOTO destination on SYM. | `------------------------------------------------------------------*/ static void -save_column (symbol_number_t symbol, state_number_t default_state) +save_column (symbol_number sym, state_number default_state) { - int i; - base_t *sp; - base_t *sp1; - base_t *sp2; + goto_number i; + base_number *sp; + base_number *sp1; + base_number *sp2; int count; - vector_number_t symno = symbol_number_to_vector_number (symbol); + vector_number symno = symbol_number_to_vector_number (sym); - goto_number_t begin = goto_map[symbol]; - goto_number_t end = goto_map[symbol + 1]; + goto_number begin = goto_map[sym - ntokens]; + goto_number end = goto_map[sym - ntokens + 1]; /* Number of non default GOTO. */ count = 0; @@ -541,8 +506,8 @@ save_column (symbol_number_t symbol, state_number_t default_state) return; /* Allocate room for non defaulted gotos. */ - froms[symno] = sp1 = sp = XCALLOC (base_t, count); - tos[symno] = sp2 = XCALLOC (base_t, 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++) @@ -557,22 +522,22 @@ save_column (symbol_number_t symbol, state_number_t default_state) } -/*----------------------------------------------------------------. -| Return `the' most common destination GOTO on SYMBOL (a nterm). | -`----------------------------------------------------------------*/ +/*-------------------------------------------------------------. +| Return `the' most common destination GOTO on SYM (a nterm). | +`-------------------------------------------------------------*/ -static state_number_t -default_goto (symbol_number_t symbol, short state_count[]) +static state_number +default_goto (symbol_number sym, size_t state_count[]) { - state_number_t s; - int i; - goto_number_t m = goto_map[symbol]; - goto_number_t n = goto_map[symbol + 1]; - state_number_t default_state = (state_number_t) -1; - int max = 0; + state_number s; + 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_t) -1; + return -1; for (s = 0; s < nstates; s++) state_count[s] = 0; @@ -603,15 +568,15 @@ default_goto (symbol_number_t symbol, short state_count[]) static void goto_actions (void) { - symbol_number_t i; - short *state_count = XCALLOC (short, nstates); - yydefgoto = XMALLOC (state_number_t, nvars); + symbol_number i; + 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. */ for (i = ntokens; i < nsyms; ++i) { - state_number_t default_state = default_goto (i, state_count); + state_number default_state = default_goto (i, state_count); save_column (i, default_state); yydefgoto[i - ntokens] = default_state; } @@ -660,24 +625,33 @@ sort_actions (void) In any other case, return -1. */ -static state_number_t -matching_state (vector_number_t vector) +static state_number +matching_state (vector_number vector) { - vector_number_t i = order[vector]; + vector_number i = order[vector]; int t; int w; int prev; /* If VECTOR is a nterm, return -1. */ - if (i >= (int) nstates) + if (nstates <= i) return -1; t = tally[i]; w = width[i]; + /* If VECTOR has GLR conflicts, return -1 */ + if (conflict_tos[i] != NULL) + { + int j; + for (j = 0; j < t; j += 1) + if (conflict_tos[i][j] != 0) + return -1; + } + for (prev = vector - 1; prev >= 0; prev--) { - vector_number_t j = order[prev]; + vector_number j = order[prev]; int k; int match = 1; @@ -687,7 +661,8 @@ matching_state (vector_number_t vector) return -1; for (k = 0; match && k < t; k++) - if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k]) + if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k] + || (conflict_tos[j] != NULL && conflict_tos[j][k] != 0)) match = 0; if (match) @@ -698,37 +673,39 @@ matching_state (vector_number_t vector) } -static base_t -pack_vector (vector_number_t vector) +static base_number +pack_vector (vector_number vector) { - vector_number_t i = order[vector]; + vector_number i = order[vector]; int j; int t = tally[i]; int loc = 0; - base_t *from = froms[i]; - base_t *to = tos[i]; + base_number *from = froms[i]; + base_number *to = tos[i]; unsigned int *conflict_to = conflict_tos[i]; - assert (t); + aver (t != 0); - for (j = lowzero - from[0]; j < (int) table_size; j++) + for (j = lowzero - from[0]; ; j++) { int k; - int ok = 1; + bool ok = true; + + aver (j < table_size); 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) { @@ -736,7 +713,7 @@ pack_vector (vector_number_t 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]; } @@ -747,14 +724,10 @@ pack_vector (vector_number_t vector) if (loc > high) high = loc; - if (j < BASE_MIN || BASE_MAX < j) - fatal ("base_t too small to hold %d\n", j); + aver (BASE_MINIMUM <= j && j <= BASE_MAXIMUM); return j; } } -#define pack_vector_succeeded 0 - assert (pack_vector_succeeded); - return 0; } @@ -766,11 +739,11 @@ pack_vector (vector_number_t vector) | parsers. | `-------------------------------------------------------------*/ -static base_t -table_ninf_remap (base_t tab[], size_t size, base_t ninf) +static base_number +table_ninf_remap (base_number tab[], int size, base_number ninf) { - base_t res = 0; - size_t i; + base_number res = 0; + int i; for (i = 0; i < size; i++) if (tab[i] < res && tab[i] != ninf) @@ -790,40 +763,40 @@ pack_table (void) { int i; - base = XCALLOC (base_t, nvectors); - pos = XCALLOC (base_t, nentries); - table = XCALLOC (base_t, table_size); - conflict_table = XCALLOC (unsigned int, table_size); - check = XCALLOC (base_t, 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; for (i = 0; i < nvectors; i++) - base[i] = BASE_MIN; + 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++) { - state_number_t state = matching_state (i); - base_t place; + state_number s = matching_state (i); + base_number place; - if (state < 0) + if (s < 0) /* A new set of state actions, or a nonterminal. */ place = pack_vector (i); else - /* Action of I were already coded for STATE. */ - place = base[state]; + /* Action of I were already coded for S. */ + place = base[s]; pos[i] = place; base[order[i]] = place; } /* Use the greatest possible negative infinites. */ - base_ninf = table_ninf_remap (base, nvectors, BASE_MIN); - table_ninf = table_ninf_remap (table, high + 1, ACTION_MIN); + base_ninf = table_ninf_remap (base, nvectors, BASE_MINIMUM); + table_ninf = table_ninf_remap (table, high + 1, ACTION_NUMBER_MINIMUM); free (pos); } @@ -840,28 +813,28 @@ tables_generate (void) { int i; - /* That's a poor way to make sure the sizes are properly corelated, - in particular the signedness is not taking into account, but it's - not useless. */ - assert (sizeof (nvectors) >= sizeof (nstates)); - assert (sizeof (nvectors) >= sizeof (nvars)); + /* 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 (sizeof nstates <= sizeof nvectors + && sizeof nvars <= sizeof nvectors); nvectors = state_number_as_int (nstates) + nvars; - froms = XCALLOC (base_t *, nvectors); - tos = XCALLOC (base_t *, nvectors); - conflict_tos = XCALLOC (unsigned int *, nvectors); - tally = XCALLOC (short, nvectors); - width = XCALLOC (base_t, 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 (); - XFREE (goto_map + ntokens); - XFREE (from_state); - XFREE (to_state); + free (goto_map); + free (from_state); + free (to_state); - order = XCALLOC (vector_number_t, nvectors); + order = xcalloc (nvectors, sizeof *order); sort_actions (); pack_table (); free (order); @@ -871,9 +844,9 @@ tables_generate (void) for (i = 0; i < nvectors; i++) { - XFREE (froms[i]); - XFREE (tos[i]); - XFREE (conflict_tos[i]); + free (froms[i]); + free (tos[i]); + free (conflict_tos[i]); } free (froms);