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