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 TRANSITIONS_ALLOC(Num)                                          \
  39   (transitions_t *) xcalloc ((sizeof (transitions_t)                    \
  40                                   + (Num - 1) * sizeof (state_t *)), 1)
  41
  42 static transitions_t *
  43 transitions_new (int num, state_t **the_states)
  44 {
  45   transitions_t *res = TRANSITIONS_ALLOC (num);
  46   res->num = num;
  47   memcpy (res->states, the_states, num * sizeof (the_states[0]));
  48   return res;
  49 }
  50
  51
  52 /*-------------------------------------------------------------------.
  53 | Return the state such these TRANSITIONS contain a shift/goto to it |
  54 | on SYMBOL.  Aborts if none found.                                  |
  55 `-------------------------------------------------------------------*/
  56
  57 state_t *
  58 transitions_to (transitions_t *shifts, symbol_number_t s)
  59 {
  60   int j;
  61   for (j = 0; j < shifts->num; j++)
  62     if (TRANSITION_SYMBOL (shifts, j) == s)
  63       return shifts->states[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 ((sizeof (errs_t)                  \
  79                       + (Nerrs - 1) * sizeof (symbol_t *)), 1)
  80
  81
  82 errs_t *
  83 errs_new (int num, symbol_t **tokens)
  84 {
  85   errs_t *res = ERRS_ALLOC (num);
  86   res->num = num;
  87   memcpy (res->symbols, tokens, num * sizeof (tokens[0]));
  88   return res;
  89 }
  90
  91
  92
  93
  94                         /*-------------.
  95                         | Reductions.  |
  96                         `-------------*/
  97
  98
  99 /*-------------------------------------.
 100 | Create a new array of N reductions.  |
 101 `-------------------------------------*/
 102
 103 #define REDUCTIONS_ALLOC(Nreductions)                          \
 104   (reductions_t *) xcalloc ((sizeof (reductions_t)             \
 105                             + (Nreductions - 1) * sizeof (rule_t *)), 1)
 106
 107 static reductions_t *
 108 reductions_new (int num, rule_t **reductions)
 109 {
 110   reductions_t *res = REDUCTIONS_ALLOC (num);
 111   res->num = num;
 112   memcpy (res->rules, reductions, num * sizeof (reductions[0]));
 113   res->lookaheads = NULL;
 114   return res;
 115 }
 116
 117
 118
 119                         /*---------.
 120                         | States.  |
 121                         `---------*/
 122
 123
 124 state_number_t nstates = 0;
 125 /* FINAL_STATE is properly set by new_state when it recognizes its
 126    accessing symbol: $end.  */
 127 state_t *final_state = NULL;
 128
 129 #define STATE_ALLOC(Nitems)                                             \
 130   (state_t *) xcalloc ((sizeof (state_t)                                \
 131                         + (Nitems - 1) * sizeof (item_number_t)), 1)
 132
 133 /*------------------------------------------------------------------.
 134 | Create a new state with ACCESSING_SYMBOL, for those items.  Store |
 135 | it in the state hash table.                                       |
 136 `------------------------------------------------------------------*/
 137
 138 state_t *
 139 state_new (symbol_number_t accessing_symbol,
 140            size_t core_size, item_number_t *core)
 141 {
 142   state_t *res;
 143
 144   if (STATE_NUMBER_MAX <= nstates)
 145     abort ();
 146
 147   res = STATE_ALLOC (core_size);
 148   res->accessing_symbol = accessing_symbol;
 149   res->number = nstates;
 150   ++nstates;
 151   res->solved_conflicts = NULL;
 152
 153   res->nitems = core_size;
 154   memcpy (res->items, core, core_size * sizeof (core[0]));
 155
 156   state_hash_insert (res);
 157
 158   return res;
 159 }
 160
 161
 162 /*-------------.
 163 | Free STATE.  |
 164 `-------------*/
 165
 166 static void
 167 state_free (state_t *state)
 168 {
 169   free (state->transitions);
 170   free (state->reductions);
 171   free (state->errs);
 172   free (state);
 173 }
 174
 175
 176 /*-------------------------------.
 177 | Set the transitions of STATE.  |
 178 `-------------------------------*/
 179
 180 void
 181 state_transitions_set (state_t *state, int num, state_t **transitions)
 182 {
 183   if (state->transitions)
 184     abort ();
 185   state->transitions = transitions_new (num, transitions);
 186 }
 187
 188
 189 /*------------------------------.
 190 | Set the reductions of STATE.  |
 191 `------------------------------*/
 192
 193 void
 194 state_reductions_set (state_t *state, int num, rule_t **reductions)
 195 {
 196   if (state->reductions)
 197     abort ();
 198   state->reductions = reductions_new (num, reductions);
 199 }
 200
 201
 202 int
 203 state_reduction_find (state_t *state, rule_t *rule)
 204 {
 205   int i;
 206   reductions_t *reds = state->reductions;
 207   for (i = 0; i < reds->num; ++i)
 208     if (reds->rules[i] == rule)
 209       return i;
 210   return -1;
 211 }
 212
 213
 214 /*------------------------.
 215 | Set the errs of STATE.  |
 216 `------------------------*/
 217
 218 void
 219 state_errs_set (state_t *state, int num, symbol_t **tokens)
 220 {
 221   if (state->errs)
 222     abort ();
 223   state->errs = errs_new (num, tokens);
 224 }
 225
 226
 227
 228 /*--------------------------------------------------------------.
 229 | Print on OUT all the lookaheads such that this STATE wants to |
 230 | reduce this RULE.                                             |
 231 `--------------------------------------------------------------*/
 232
 233 void
 234 state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out)
 235 {
 236   /* Find the reduction we are handling.  */
 237   reductions_t *reds = state->reductions;
 238   int red = state_reduction_find (state, rule);
 239
 240   /* Print them if there are.  */
 241   if (reds->lookaheads && red != -1)
 242     {
 243       bitset_iterator biter;
 244       int k;
 245       int not_first = 0;
 246       fprintf (out, "  [");
 247       BITSET_FOR_EACH (biter, reds->lookaheads[red], k, 0)
 248         fprintf (out, "%s%s",
 249                  not_first++ ? ", " : "",
 250                  symbols[k]->tag);
 251       fprintf (out, "]");
 252     }
 253 }
 254
 255
 256 /*----------------------.
 257 | A state hash table.  |
 258 `----------------------*/
 259
 260 /* Initial capacity of states hash table.  */
 261 #define HT_INITIAL_CAPACITY 257
 262
 263 static struct hash_table *state_table = NULL;
 264
 265 /* Two states are equal if they have the same core items.  */
 266 static bool
 267 state_compare (const state_t *s1, const state_t *s2)
 268 {
 269   int i;
 270
 271   if (s1->nitems != s2->nitems)
 272     return false;
 273
 274   for (i = 0; i < s1->nitems; ++i)
 275     if (s1->items[i] != s2->items[i])
 276       return false;
 277
 278   return true;
 279 }
 280
 281 static unsigned int
 282 state_hash (const state_t *state, unsigned int tablesize)
 283 {
 284   /* Add up the state's item numbers to get a hash key.  */
 285   int key = 0;
 286   int i;
 287   for (i = 0; i < state->nitems; ++i)
 288     key += state->items[i];
 289   return key % tablesize;
 290 }
 291
 292
 293 /*-------------------------------.
 294 | Create the states hash table.  |
 295 `-------------------------------*/
 296
 297 void
 298 state_hash_new (void)
 299 {
 300   state_table = hash_initialize (HT_INITIAL_CAPACITY,
 301                                  NULL,
 302                                  (Hash_hasher) state_hash,
 303                                  (Hash_comparator) state_compare,
 304                                  (Hash_data_freer) NULL);
 305 }
 306
 307
 308 /*---------------------------------------------.
 309 | Free the states hash table, not the states.  |
 310 `---------------------------------------------*/
 311
 312 void
 313 state_hash_free (void)
 314 {
 315   hash_free (state_table);
 316 }
 317
 318
 319 /*---------------------------------------.
 320 | Insert STATE in the state hash table.  |
 321 `---------------------------------------*/
 322
 323 void
 324 state_hash_insert (state_t *state)
 325 {
 326   hash_insert (state_table, state);
 327 }
 328
 329
 330 /*------------------------------------------------------------------.
 331 | Find the state associated to the CORE, and return it.  If it does |
 332 | not exist yet, return NULL.                                       |
 333 `------------------------------------------------------------------*/
 334
 335 state_t *
 336 state_hash_lookup (size_t core_size, item_number_t *core)
 337 {
 338   state_t *probe = STATE_ALLOC (core_size);
 339   state_t *entry;
 340
 341   probe->nitems = core_size;
 342   memcpy (probe->items, core, core_size * sizeof (core[0]));
 343   entry = hash_lookup (state_table, probe);
 344   free (probe);
 345   return entry;
 346 }
 347
 348 /* All the decorated states, indexed by the state number.  */
 349 state_t **states = NULL;
 350
 351
 352 /*----------------------.
 353 | Free all the states.  |
 354 `----------------------*/
 355
 356 void
 357 states_free (void)
 358 {
 359   state_number_t i;
 360   for (i = 0; i < nstates; ++i)
 361     state_free (states[i]);
 362   free (states);
 363 }