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_t *) xcalloc ((unsigned) (sizeof (shifts_t)                   \
  40                                   + (Nshifts - 1) * sizeof (state_number_t)), 1)
  41
  42 static shifts_t *
  43 shifts_new (int nshifts, state_number_t *shifts)
  44 {
  45   shifts_t *res = SHIFTS_ALLOC (nshifts);
  46   res->nshifts = nshifts;
  47   memcpy (res->shifts, shifts, nshifts * sizeof (shifts[0]));
  48   return res;
  49 }
  50
  51
  52
  53
  54                         /*--------------------.
  55                         | Error transitions.  |
  56                         `--------------------*/
  57
  58
  59 /*-------------------------------.
  60 | Create a new array of N errs.  |
  61 `-------------------------------*/
  62
  63 #define ERRS_ALLOC(Nerrs)                                               \
  64   (errs_t *) xcalloc ((unsigned) (sizeof (errs_t)                       \
  65                                   + (Nerrs - 1) * sizeof (short)), 1)
  66
  67
  68 errs_t *
  69 errs_new (int n)
  70 {
  71   errs_t *res = ERRS_ALLOC (n);
  72   res->nerrs = n;
  73   return res;
  74 }
  75
  76
  77 errs_t *
  78 errs_dup (errs_t *src)
  79 {
  80   errs_t *res = errs_new (src->nerrs);
  81   memcpy (res->errs, src->errs, src->nerrs * sizeof (src->errs[0]));
  82   return res;
  83 }
  84
  85
  86
  87
  88                         /*-------------.
  89                         | Reductions.  |
  90                         `-------------*/
  91
  92
  93 /*-------------------------------------.
  94 | Create a new array of N reductions.  |
  95 `-------------------------------------*/
  96
  97 #define REDUCTIONS_ALLOC(Nreductions)                                   \
  98   (reductions_t *) xcalloc ((unsigned) (sizeof (reductions_t)           \
  99                                   + (Nreductions - 1) * sizeof (short)), 1)
 100
 101 static reductions_t *
 102 reductions_new (int nreductions, short *reductions)
 103 {
 104   reductions_t *res = REDUCTIONS_ALLOC (nreductions);
 105   res->nreds = nreductions;
 106   memcpy (res->rules, reductions, nreductions * sizeof (reductions[0]));
 107   return res;
 108 }
 109
 110
 111
 112                         /*---------.
 113                         | States.  |
 114                         `---------*/
 115
 116
 117 state_number_t nstates = 0;
 118 /* FINAL_STATE is properly set by new_state when it recognizes its
 119    accessing symbol: EOF.  */
 120 state_t *final_state = NULL;
 121
 122 #define STATE_ALLOC(Nitems)                                             \
 123   (state_t *) xcalloc ((unsigned) (sizeof (state_t)                     \
 124                                   + (Nitems - 1) * sizeof (item_number_t)), 1)
 125
 126 /*------------------------------------------------------------.
 127 | Create a new state with ACCESSING_SYMBOL, for those items.  |
 128 `------------------------------------------------------------*/
 129
 130 state_t *
 131 state_new (symbol_number_t accessing_symbol,
 132            size_t core_size, item_number_t *core)
 133 {
 134   state_t *res;
 135
 136   if (nstates >= STATE_NUMBER_MAX)
 137     fatal (_("too many states (max %d)"), STATE_NUMBER_MAX);
 138
 139   res = STATE_ALLOC (core_size);
 140   res->accessing_symbol = accessing_symbol;
 141   res->number = nstates;
 142   ++nstates;
 143   res->solved_conflicts = NULL;
 144
 145   res->nitems = core_size;
 146   memcpy (res->items, core, core_size * sizeof (core[0]));
 147
 148   return res;
 149 }
 150
 151
 152 /*--------------------------.
 153 | Set the shifts of STATE.  |
 154 `--------------------------*/
 155
 156 void
 157 state_shifts_set (state_t *state, int nshifts, state_number_t *shifts)
 158 {
 159   state->shifts = shifts_new (nshifts, shifts);
 160 }
 161
 162
 163 /*------------------------------.
 164 | Set the reductions of STATE.  |
 165 `------------------------------*/
 166
 167 void
 168 state_reductions_set (state_t *state, int nreductions, short *reductions)
 169 {
 170   state->reductions = reductions_new (nreductions, reductions);
 171 }
 172
 173
 174
 175 /*--------------------------------------------------------------.
 176 | Print on OUT all the lookaheads such that this STATE wants to |
 177 | reduce this RULE.                                             |
 178 `--------------------------------------------------------------*/
 179
 180 void
 181 state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out)
 182 {
 183   int j, k;
 184   int nlookaheads = 0;
 185   /* Count the number of lookaheads corresponding to this rule.  */
 186   for (j = 0; j < state->nlookaheads; ++j)
 187     for (k = 0; k < ntokens; ++k)
 188       if (bitset_test (state->lookaheads[j], k)
 189           && state->lookaheads_rule[j]->number == rule->number)
 190         nlookaheads++;
 191
 192   /* Print them if there are.  */
 193   if (nlookaheads)
 194     {
 195       fprintf (out, "  [");
 196       for (j = 0; j < state->nlookaheads; ++j)
 197         for (k = 0; k < ntokens; ++k)
 198           if (bitset_test (state->lookaheads[j], k)
 199               && state->lookaheads_rule[j]->number == rule->number)
 200             fprintf (out, "%s%s",
 201                      symbol_tag_get (symbols[k]),
 202                      --nlookaheads ? ", " : "");
 203       fprintf (out, "]");
 204     }
 205 }
 206
 207
 208 /*----------------------.
 209 | A state hash table.  |
 210 `----------------------*/
 211
 212 /* Initial capacity of states hash table.  */
 213 #define HT_INITIAL_CAPACITY 257
 214
 215 static struct hash_table *state_table = NULL;
 216
 217 /* Two states are equal if they have the same core items.  */
 218 static bool
 219 state_compare (const state_t *s1, const state_t *s2)
 220 {
 221   int i;
 222
 223   if (s1->nitems != s2->nitems)
 224     return FALSE;
 225
 226   for (i = 0; i < s1->nitems; ++i)
 227     if (s1->items[i] != s2->items[i])
 228       return FALSE;
 229
 230   return TRUE;
 231 }
 232
 233 static unsigned int
 234 state_hash (const state_t *state, unsigned int tablesize)
 235 {
 236   /* Add up the state's item numbers to get a hash key.  */
 237   int key = 0;
 238   int i;
 239   for (i = 0; i < state->nitems; ++i)
 240     key += state->items[i];
 241   return key % tablesize;
 242 }
 243
 244
 245 /*-------------------------------.
 246 | Create the states hash table.  |
 247 `-------------------------------*/
 248
 249 void
 250 state_hash_new (void)
 251 {
 252   state_table = hash_initialize (HT_INITIAL_CAPACITY,
 253                                  NULL,
 254                                  (Hash_hasher) state_hash,
 255                                  (Hash_comparator) state_compare,
 256                                  (Hash_data_freer) NULL);
 257 }
 258
 259
 260 /*---------------------------------------------.
 261 | Free the states hash table, not the states.  |
 262 `---------------------------------------------*/
 263
 264 void
 265 state_hash_free (void)
 266 {
 267   hash_free (state_table);
 268 }
 269
 270
 271 /*---------------------------------------.
 272 | Insert STATE in the state hash table.  |
 273 `---------------------------------------*/
 274
 275 void
 276 state_hash_insert (state_t *state)
 277 {
 278   hash_insert (state_table, state);
 279 }
 280
 281
 282 /*------------------------------------------------------------------.
 283 | Find the state associated to the CORE, and return it.  If it does |
 284 | not exist yet, return NULL.                                       |
 285 `------------------------------------------------------------------*/
 286
 287 state_t *
 288 state_hash_lookup (size_t core_size, item_number_t *core)
 289 {
 290   state_t *probe = STATE_ALLOC (core_size);
 291   state_t *entry;
 292
 293   probe->nitems = core_size;
 294   memcpy (probe->items, core, core_size * sizeof (core[0]));
 295   entry = hash_lookup (state_table, probe);
 296   free (probe);
 297   return entry;
 298 }
 299
 300 /* All the decorated states, indexed by the state number.  */
 301 state_t **states = NULL;
 302
 303
 304 /*----------------------.
 305 | Free all the states.  |
 306 `----------------------*/
 307
 308 void
 309 states_free (void)
 310 {
 311   state_number_t i;
 312
 313   for (i = 0; i < nstates; ++i)
 314     {
 315       free (states[i]->shifts);
 316       XFREE (states[i]->reductions);
 317       free (states[i]->errs);
 318       free (states[i]);
 319     }
 320   XFREE (states);
 321 }