X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/c6f1a33c06db52ed122d0922885602cf37f99941..500bbfcd816776d0ddbf3555fedd41b529c405b3:/src/tables.c?ds=sidebyside diff --git a/src/tables.c b/src/tables.c index 91461b29..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) { @@ -239,6 +173,7 @@ static void conflict_row (state_t *state) { int i, j; + reductions_t *reds = state->reductions; if (! glr_parser) return; @@ -250,20 +185,21 @@ conflict_row (state_t *state) /* Find all reductions for token J, and record all that do not match ACTROW[J]. */ - for (i = 0; i < state->nlookaheads; i += 1) - if (bitset_test (state->lookaheads[i], j) + for (i = 0; i < reds->num; i += 1) + if (bitset_test (reds->lookaheads[i], j) && (actrow[j] - != rule_number_as_item_number (state->lookaheads_rule[i]->number))) + != rule_number_as_item_number (reds->rules[i]->number))) { - assert (conflict_list_free > 0); - conflict_list[conflict_list_cnt] - = state->lookaheads_rule[i]->number + 1; + 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; } @@ -304,22 +240,23 @@ action_row (state_t *state) for (i = 0; i < ntokens; i++) actrow[i] = conflrow[i] = 0; - if (redp->num >= 1) + if (redp->lookaheads) { int j; bitset_iterator biter; /* loop over all the rules available here which require - lookahead */ - for (i = state->nlookaheads - 1; i >= 0; --i) + lookahead (in reverse order to give precedence to the first + rule) */ + for (i = redp->num - 1; i >= 0; --i) /* and find each token which the rule finds acceptable to come next */ - BITSET_FOR_EACH (biter, state->lookaheads[i], j, 0) + BITSET_FOR_EACH (biter, redp->lookaheads[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 (state->lookaheads_rule[i]->number); + actrow[j] = rule_number_as_item_number (redp->rules[i]->number); } } @@ -359,10 +296,10 @@ action_row (state_t *state) else { int max = 0; - for (i = 0; i < state->nlookaheads; i++) + for (i = 0; i < redp->num; i++) { int count = 0; - rule_t *rule = state->lookaheads_rule[i]; + rule_t *rule = redp->rules[i]; symbol_number_t j; for (j = 0; j < ntokens; j++) @@ -393,16 +330,6 @@ action_row (state_t *state) } } - /* Find the rules which are reduced. */ - if (!glr_parser) - { - for (i = 0; i < ntokens; i++) - if (actrow[i] < 0 && actrow[i] != ACTION_MIN) - rules[item_number_as_rule_number (actrow[i])].useful = TRUE; - if (default_rule) - default_rule->useful = TRUE; - } - /* If have no default rule, the default is an error. So replace any action which says "error" with "use default". */ @@ -476,46 +403,43 @@ static void token_actions (void) { state_number_t i; + 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); - /* Now that the parser was computed, we can find which rules are - really reduced, and which are not because of SR or RR conflicts. - */ + 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) { rule_t *default_rule = action_row (states[i]); yydefact[i] = default_rule ? default_rule->number + 1 : 0; save_row (i); - } - if (!glr_parser) - for (r = 0; r < nrules ; ++r) - if (!rules[r].useful) + /* 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) { - LOCATION_PRINT (stderr, rules[r].location); - fprintf (stderr, ": %s: %s: ", - _("warning"), _("rule never reduced because of conflicts")); - rule_print (&rules[r], stderr); + 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 (yydefact[i]) + rules[yydefact[i] - 1].useful = true; } + } free (actrow); free (conflrow); @@ -688,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]; @@ -700,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) @@ -722,17 +656,21 @@ 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]); - if (loc > (int) table_size) + if (loc >= (int) table_size) table_grow (loc); if (table[loc] != 0) @@ -760,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; } @@ -787,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; @@ -806,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; @@ -839,16 +773,6 @@ pack_table (void) base_ninf = table_ninf_remap (base, nvectors, BASE_MIN); table_ninf = table_ninf_remap (table, high + 1, ACTION_MIN); - for (i = 0; i < nvectors; i++) - { - XFREE (froms[i]); - XFREE (tos[i]); - XFREE (conflict_tos[i]); - } - - free (froms); - free (tos); - free (conflict_tos); free (pos); } @@ -862,11 +786,14 @@ pack_table (void) void tables_generate (void) { - /* 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)); + int i; + + /* 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; @@ -877,13 +804,11 @@ tables_generate (void) width = XCALLOC (base_t, nvectors); token_actions (); - bitsetv_free (LA); - free (LArule); 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 (); @@ -892,6 +817,17 @@ tables_generate (void) free (tally); free (width); + + for (i = 0; i < nvectors; i++) + { + free (froms[i]); + free (tos[i]); + XFREE (conflict_tos[i]); + } + + free (froms); + free (tos); + free (conflict_tos); }