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