src/state.c

   1 /* Type definitions for nondeterministic finite state machine for bison,
   2    Copyright (C) 2001, 2002  Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21
  22 #include "system.h"
  23 #include "hash.h"
  24 #include "complain.h"
  25 #include "gram.h"
  26 #include "state.h"
  27
  28
  29                         /*-------------------.
  30                         | Shifts and Gotos.  |
  31                         `-------------------*/
  32
  33
  34 /*---------------------------------------.
  35 | Create a new array of N shifts/gotos.  |
  36 `---------------------------------------*/
  37
  38 #define SHIFTS_ALLOC(Nshifts)                                           \
  39   (shifts *) xcalloc ((unsigned) (sizeof (shifts)                       \
  40                                   + (Nshifts - 1) * sizeof (short)), 1)
  41
  42 shifts *
  43 shifts_new (int n)
  44 {
  45   shifts *res = SHIFTS_ALLOC (n);
  46   res->nshifts = n;
  47   return res;
  48 }
  49
  50
  51
  52
  53                         /*--------------------.
  54                         | Error transitions.  |
  55                         `--------------------*/
  56
  57
  58 /*-------------------------------.
  59 | Create a new array of N errs.  |
  60 `-------------------------------*/
  61
  62 #define ERRS_ALLOC(Nerrs)                                               \
  63   (errs *) xcalloc ((unsigned) (sizeof (errs)                           \
  64                                   + (Nerrs - 1) * sizeof (short)), 1)
  65
  66
  67 errs *
  68 errs_new (int n)
  69 {
  70   errs *res = ERRS_ALLOC (n);
  71   res->nerrs = n;
  72   return res;
  73 }
  74
  75
  76 errs *
  77 errs_dup (errs *src)
  78 {
  79   errs *res = errs_new (src->nerrs);
  80   memcpy (res->errs, src->errs, src->nerrs * sizeof (src->errs[0]));
  81   return res;
  82 }
  83
  84
  85
  86
  87                         /*-------------.
  88                         | Reductions.  |
  89                         `-------------*/
  90
  91
  92 /*-------------------------------------.
  93 | Create a new array of N reductions.  |
  94 `-------------------------------------*/
  95
  96 #define REDUCTIONS_ALLOC(Nreductions)                                   \
  97   (reductions *) xcalloc ((unsigned) (sizeof (reductions)               \
  98                                   + (Nreductions - 1) * sizeof (short)), 1)
  99
 100 reductions *
 101 reductions_new (int n)
 102 {
 103   reductions *res = REDUCTIONS_ALLOC (n);
 104   res->nreds = n;
 105   return res;
 106 }
 107
 108
 109
 110                         /*---------.
 111                         | States.  |
 112                         `---------*/
 113
 114
 115 state_number_t nstates = 0;
 116 /* FINAL_STATE is properly set by new_state when it recognizes its
 117    accessing symbol: EOF.  */
 118 state_t *final_state = NULL;
 119
 120 #define STATE_ALLOC(Nitems)                                             \
 121   (state_t *) xcalloc ((unsigned) (sizeof (state_t)                     \
 122                                   + (Nitems - 1) * sizeof (item_number_t)), 1)
 123
 124 /*------------------------------------------------------------.
 125 | Create a new state with ACCESSING_SYMBOL, for those items.  |
 126 `------------------------------------------------------------*/
 127
 128 state_t *
 129 state_new (symbol_number_t accessing_symbol,
 130            size_t core_size, item_number_t *core)
 131 {
 132   state_t *res;
 133
 134   if (nstates >= STATE_NUMBER_MAX)
 135     fatal (_("too many states (max %d)"), STATE_NUMBER_MAX);
 136
 137   res = STATE_ALLOC (core_size);
 138   res->accessing_symbol = accessing_symbol;
 139   res->number = nstates;
 140   ++nstates;
 141   res->solved_conflicts = NULL;
 142
 143   res->nitems = core_size;
 144   memcpy (res->items, core, core_size * sizeof (core[0]));
 145
 146   return res;
 147 }
 148
 149
 150 /*--------------------------------------------------------------.
 151 | Print on OUT all the lookaheads such that this STATE wants to |
 152 | reduce this RULE.                                             |
 153 `--------------------------------------------------------------*/
 154
 155 void
 156 state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out)
 157 {
 158   int j, k;
 159   int nlookaheads = 0;
 160   /* Count the number of lookaheads corresponding to this rule.  */
 161   for (j = 0; j < state->nlookaheads; ++j)
 162     for (k = 0; k < ntokens; ++k)
 163       if (bitset_test (state->lookaheads[j], k)
 164           && state->lookaheads_rule[j]->number == rule->number)
 165         nlookaheads++;
 166
 167   /* Print them if there are.  */
 168   if (nlookaheads)
 169     {
 170       fprintf (out, "  [");
 171       for (j = 0; j < state->nlookaheads; ++j)
 172         for (k = 0; k < ntokens; ++k)
 173           if (bitset_test (state->lookaheads[j], k)
 174               && state->lookaheads_rule[j]->number == rule->number)
 175             fprintf (out, "%s%s",
 176                      symbol_tag_get (symbols[k]),
 177                      --nlookaheads ? ", " : "");
 178       fprintf (out, "]");
 179     }
 180 }
 181
 182
 183 /*----------------------.
 184 | A state hash table.  |
 185 `----------------------*/
 186
 187 /* Initial capacity of states hash table.  */
 188 #define HT_INITIAL_CAPACITY 257
 189
 190 static struct hash_table *state_table = NULL;
 191
 192 /* Two states are equal if they have the same core items.  */
 193 static bool
 194 state_compare (const state_t *s1, const state_t *s2)
 195 {
 196   int i;
 197
 198   if (s1->nitems != s2->nitems)
 199     return FALSE;
 200
 201   for (i = 0; i < s1->nitems; ++i)
 202     if (s1->items[i] != s2->items[i])
 203       return FALSE;
 204
 205   return TRUE;
 206 }
 207
 208 static unsigned int
 209 state_hash (const state_t *state, unsigned int tablesize)
 210 {
 211   /* Add up the state's item numbers to get a hash key.  */
 212   int key = 0;
 213   int i;
 214   for (i = 0; i < state->nitems; ++i)
 215     key += state->items[i];
 216   return key % tablesize;
 217 }
 218
 219
 220 /*-------------------------------.
 221 | Create the states hash table.  |
 222 `-------------------------------*/
 223
 224 void
 225 state_hash_new (void)
 226 {
 227   state_table = hash_initialize (HT_INITIAL_CAPACITY,
 228                                  NULL,
 229                                  (Hash_hasher) state_hash,
 230                                  (Hash_comparator) state_compare,
 231                                  (Hash_data_freer) NULL);
 232 }
 233
 234
 235 /*---------------------------------------------.
 236 | Free the states hash table, not the states.  |
 237 `---------------------------------------------*/
 238
 239 void
 240 state_hash_free (void)
 241 {
 242   hash_free (state_table);
 243 }
 244
 245
 246 /*---------------------------------------.
 247 | Insert STATE in the state hash table.  |
 248 `---------------------------------------*/
 249
 250 void
 251 state_hash_insert (state_t *state)
 252 {
 253   hash_insert (state_table, state);
 254 }
 255
 256
 257 /*------------------------------------------------------------------.
 258 | Find the state associated to the CORE, and return it.  If it does |
 259 | not exist yet, return NULL.                                       |
 260 `------------------------------------------------------------------*/
 261
 262 state_t *
 263 state_hash_lookup (size_t core_size, item_number_t *core)
 264 {
 265   state_t *probe = STATE_ALLOC (core_size);
 266   state_t *entry;
 267
 268   probe->nitems = core_size;
 269   memcpy (probe->items, core, core_size * sizeof (core[0]));
 270   entry = hash_lookup (state_table, probe);
 271   free (probe);
 272   return entry;
 273 }
 274
 275 /* All the decorated states, indexed by the state number.  */
 276 state_t **states = NULL;
 277
 278
 279 /*----------------------.
 280 | Free all the states.  |
 281 `----------------------*/
 282
 283 void
 284 states_free (void)
 285 {
 286   state_number_t i;
 287
 288   for (i = 0; i < nstates; ++i)
 289     {
 290       free (states[i]->shifts);
 291       XFREE (states[i]->reductions);
 292       free (states[i]->errs);
 293       free (states[i]);
 294     }
 295   XFREE (states);
 296 }