X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/c95f5dadd6d891431805234e47eff21e708f4ded..c98b5143b071e351bdb820565681890046a6b45a:/src/tables.c diff --git a/src/tables.c b/src/tables.c index ad850f4d..f06cba86 100644 --- a/src/tables.c +++ b/src/tables.c @@ -1,6 +1,6 @@ /* Output the generated parsing program for Bison. - Copyright (C) 1984, 1986, 1989, 1992, 2000-2006, 2009-2012 Free + Copyright (C) 1984, 1986, 1989, 1992, 2000-2006, 2009-2013 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -35,7 +35,7 @@ #include "tables.h" /* 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 + 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 @@ -90,18 +90,18 @@ 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 syntax error'. - If N > 0, stands for `shift SYMBOL and go to n'. - If N < 0, stands for `reduce -N'. */ + If N = 0, stands for 'run the default action'. + 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 int action_number; #define ACTION_NUMBER_MINIMUM INT_MIN 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'. */ + new vector number of VECTOR. We skip 'empty' vectors (i.e., + TALLY[VECTOR] = 0), and call these 'entries'. */ static vector_number *order; static int nentries; @@ -395,7 +395,7 @@ save_row (state_number s) base_number *sp1 = froms[s] = xnmalloc (count, sizeof *sp1); base_number *sp2 = tos[s] = xnmalloc (count, sizeof *sp2); unsigned int *sp3 = conflict_tos[s] = - nondeterministic_parser ? xnmalloc (count, sizeof *sp3) : NULL;; + nondeterministic_parser ? xnmalloc (count, sizeof *sp3) : NULL; /* Store non defaulted actions. */ for (i = 0; i < ntokens; i++) @@ -424,10 +424,6 @@ save_row (state_number s) static void token_actions (void) { - state_number i; - symbol_number j; - rule_number r; - int nconflict = nondeterministic_parser ? conflicts_total_count () : 0; yydefact = xnmalloc (nstates, sizeof *yydefact); @@ -441,28 +437,34 @@ token_actions (void) /* Find the rules which are reduced. */ if (!nondeterministic_parser) - for (r = 0; r < nrules; ++r) - rules[r].useful = false; - - for (i = 0; i < nstates; ++i) { - 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 (!nondeterministic_parser) - { - for (j = 0; j < ntokens; ++j) - 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; - } + rule_number r; + for (r = 0; r < nrules; ++r) + rules[r].useful = false; } + { + state_number i; + for (i = 0; i < nstates; ++i) + { + 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 (!nondeterministic_parser) + { + symbol_number j; + for (j = 0; j < ntokens; ++j) + 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; + } + } + } free (actrow); free (conflrow); } @@ -511,37 +513,38 @@ save_column (symbol_number sym, state_number default_state) } -/*-------------------------------------------------------------. -| Return `the' most common destination GOTO on SYM (a nterm). | -`-------------------------------------------------------------*/ +/*----------------------------------------------------------------. +| The default state for SYM: the state which is 'the' most common | +| GOTO destination on SYM (an nterm). | +`----------------------------------------------------------------*/ static state_number default_goto (symbol_number sym, size_t state_count[]) { - 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 -1; + goto_number begin = goto_map[sym - ntokens]; + goto_number end = goto_map[sym - ntokens + 1]; + state_number res = -1; - for (s = 0; s < nstates; s++) - state_count[s] = 0; + if (begin != end) + { + size_t max = 0; + goto_number i; + state_number s; - for (i = m; i < n; i++) - state_count[to_state[i]]++; + for (s = 0; s < nstates; s++) + state_count[s] = 0; - for (s = 0; s < nstates; s++) - if (state_count[s] > max) - { - max = state_count[s]; - default_state = s; - } + for (i = begin; i < end; i++) + state_count[to_state[i]]++; - return default_state; + for (s = 0; s < nstates; s++) + if (max < state_count[s]) + { + max = state_count[s]; + res = s; + } + } + return res; } @@ -618,47 +621,43 @@ static state_number matching_state (vector_number vector) { vector_number i = order[vector]; - size_t t; - int w; - int prev; - /* If VECTOR is a nterm, return -1. */ - if (nstates <= i) - return -1; - - t = tally[i]; - w = width[i]; - - /* If VECTOR has GLR conflicts, return -1 */ - if (conflict_tos[i] != NULL) + if (i < nstates) { - int j; - for (j = 0; j < t; j += 1) - if (conflict_tos[i][j] != 0) - return -1; - } + size_t t = tally[i]; + int w = width[i]; + int prev; - for (prev = vector - 1; prev >= 0; prev--) - { - vector_number j = order[prev]; - int k; - int match = 1; - - /* Given how ORDER was computed, if the WIDTH or TALLY is - different, there cannot be a matching state. */ - if (width[j] != w || tally[j] != t) - return -1; - - for (k = 0; match && k < t; 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) - return j; - } + /* 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; 0 <= prev; prev--) + { + vector_number j = order[prev]; + /* Given how ORDER was computed, if the WIDTH or TALLY is + different, there cannot be a matching state. */ + if (width[j] != w || tally[j] != t) + return -1; + else + { + bool match = true; + int k; + for (k = 0; match && k < t; k++) + if (tos[j][k] != tos[i][k] + || froms[j][k] != froms[i][k] + || (conflict_tos[j] != NULL && conflict_tos[j][k] != 0)) + match = false; + if (match) + return j; + } + } + } return -1; }