X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/427c0dda0c9fb207d8abdd92e3f77f91af9b682d..443594d0c4cfac52344f20724decccfbb63d041f:/src/tables.c diff --git a/src/tables.c b/src/tables.c index 47d9d6af..0ebcd2a1 100644 --- a/src/tables.c +++ b/src/tables.c @@ -1,4 +1,4 @@ -/* Output the generated parsing program for bison, +/* Output the generated parsing program for Bison. Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002 Free Software Foundation, Inc. @@ -20,71 +20,6 @@ 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. - - 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. - - YYFINAL = the state number of the termination state. YYFLAG = most - negative short int. Used to flag ?? */ - #include "system.h" #include "bitsetv.h" #include "quotearg.h" @@ -98,9 +33,9 @@ #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. */ @@ -147,7 +82,7 @@ static base_t *width = NULL; /* 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; @@ -181,7 +116,7 @@ static int conflict_list_free; static size_t table_size = 32768; base_t *table = NULL; base_t *check = NULL; -/* The value used in TABLE to denote explicit parse errors +/* The value used in TABLE to denote explicit syntax errors (%nonassoc), a negative infinite. First defaults to ACTION_MIN, but in order to keep small tables, renumbered as TABLE_ERROR, which is the smallest (non error) value minus 1. */ @@ -212,8 +147,7 @@ table_grow (size_t desired) table = XREALLOC (table, base_t, table_size); check = XREALLOC (check, base_t, table_size); - if (glr_parser) - conflict_table = XREALLOC (conflict_table, unsigned int, table_size); + conflict_table = XREALLOC (conflict_table, unsigned int, table_size); for (/* Nothing. */; old_size < table_size; ++old_size) { @@ -256,14 +190,16 @@ conflict_row (state_t *state) && (actrow[j] != rule_number_as_item_number (reds->rules[i]->number))) { - assert (conflict_list_free > 0); + if (conflict_list_free <= 0) + abort (); 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); + if (conflict_list_free <= 0) + abort (); conflict_list_cnt += 1; conflict_list_free -= 1; } @@ -470,26 +406,21 @@ token_actions (void) symbol_number_t j; rule_number_t r; - int nconflict = conflicts_total_count (); + int nconflict = glr_parser ? conflicts_total_count () : 0; yydefact = XCALLOC (rule_number_t, nstates); actrow = XCALLOC (action_t, ntokens); conflrow = XCALLOC (unsigned int, ntokens); + conflict_list = XCALLOC (unsigned int, 1 + 2 * nconflict); + conflict_list_free = 2 * nconflict; + conflict_list_cnt = 1; + /* Find the rules which are reduced. */ if (!glr_parser) for (r = 0; r < nrules; ++r) - rules[r].useful = FALSE; - - if (glr_parser) - { - conflict_list = XCALLOC (unsigned int, 1 + 2 * nconflict); - conflict_list_free = 2 * nconflict; - conflict_list_cnt = 1; - } - else - conflict_list_free = conflict_list_cnt = 0; + rules[r].useful = false; for (i = 0; i < nstates; ++i) { @@ -504,9 +435,9 @@ token_actions (void) { for (j = 0; j < ntokens; ++j) if (actrow[j] < 0 && actrow[j] != ACTION_MIN) - rules[item_number_as_rule_number (actrow[j])].useful = TRUE; + 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; } } @@ -681,6 +612,15 @@ matching_state (vector_number_t vector) 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]; @@ -693,7 +633,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) @@ -715,13 +656,17 @@ pack_vector (vector_number_t vector) base_t *to = tos[i]; unsigned int *conflict_to = conflict_tos[i]; - assert (t); + if (! t) + abort (); - for (j = lowzero - from[0]; j < (int) table_size; j++) + for (j = lowzero - from[0]; ; j++) { int k; int ok = 1; + if ((int) table_size <= j) + abort (); + for (k = 0; ok && k < t; k++) { loc = j + state_number_as_int (from[k]); @@ -753,14 +698,11 @@ 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); + if (! (BASE_MIN <= j && j <= BASE_MAX)) + abort (); return j; } } -#define pack_vector_succeeded 0 - assert (pack_vector_succeeded); - return 0; } @@ -780,7 +722,7 @@ table_ninf_remap (base_t tab[], size_t size, base_t ninf) for (i = 0; i < size; i++) if (tab[i] < res && tab[i] != ninf) - res = base[i]; + res = tab[i]; --res; @@ -799,8 +741,7 @@ pack_table (void) base = XCALLOC (base_t, nvectors); pos = XCALLOC (base_t, nentries); table = XCALLOC (base_t, table_size); - if (glr_parser) - conflict_table = XCALLOC (unsigned int, table_size); + conflict_table = XCALLOC (unsigned int, table_size); check = XCALLOC (base_t, table_size); lowzero = 0; @@ -847,11 +788,12 @@ 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 (sizes_are_properly_correlated, + (sizeof nstates <= sizeof nvectors + && sizeof nvars <= sizeof nvectors)); nvectors = state_number_as_int (nstates) + nvars; @@ -864,9 +806,9 @@ tables_generate (void) token_actions (); goto_actions (); - XFREE (goto_map + ntokens); - XFREE (from_state); - XFREE (to_state); + free (goto_map + ntokens); + free (from_state); + free (to_state); order = XCALLOC (vector_number_t, nvectors); sort_actions (); @@ -878,8 +820,8 @@ tables_generate (void) for (i = 0; i < nvectors; i++) { - XFREE (froms[i]); - XFREE (tos[i]); + free (froms[i]); + free (tos[i]); XFREE (conflict_tos[i]); }