src/LR0.c

   1 /* Generate the nondeterministic finite state machine for bison,
   2    Copyright 1984, 1986, 1989, 2000, 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 /* See comments in state.h for the data structures that represent it.
  23    The entry point is generate_states.  */
  24
  25 #include "system.h"
  26 #include "bitset.h"
  27 #include "symtab.h"
  28 #include "getargs.h"
  29 #include "reader.h"
  30 #include "gram.h"
  31 #include "state.h"
  32 #include "complain.h"
  33 #include "closure.h"
  34 #include "LR0.h"
  35 #include "lalr.h"
  36 #include "reduce.h"
  37
  38 unsigned int nstates = 0;
  39 /* Initialize the final state to -1, otherwise, it might be set to 0
  40    by default, and since we don't compute the reductions of the final
  41    state, we end up not computing the reductions of the initial state,
  42    which is of course needed.
  43
  44    FINAL_STATE is properly set by new_state when it recognizes the
  45    accessing symbol: EOF.  */
  46 int final_state = -1;
  47 static state_t *first_state = NULL;
  48
  49 static state_t *this_state = NULL;
  50 static state_t *last_state = NULL;
  51
  52 static int nshifts;
  53 static short *shift_symbol = NULL;
  54
  55 static short *redset = NULL;
  56 static short *shiftset = NULL;
  57
  58 static short **kernel_base = NULL;
  59 static int *kernel_size = NULL;
  60 static short *kernel_items = NULL;
  61
  62 /* hash table for states, to recognize equivalent ones.  */
  63
  64 #define STATE_HASH_SIZE 1009
  65 static state_t **state_hash = NULL;
  66
  67 \f
  68 static void
  69 allocate_itemsets (void)
  70 {
  71   int i, r;
  72   short *rhsp;
  73
  74   /* Count the number of occurrences of all the symbols in RITEMS.
  75      Note that useless productions (hence useless nonterminals) are
  76      browsed too, hence we need to allocate room for _all_ the
  77      symbols.  */
  78   int count = 0;
  79   short *symbol_count = XCALLOC (short, nsyms + nuseless_nonterminals);
  80
  81   for (r = 1; r < nrules + 1; ++r)
  82     for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
  83       {
  84         count++;
  85         symbol_count[*rhsp]++;
  86       }
  87
  88   /* See comments before new_itemsets.  All the vectors of items
  89      live inside KERNEL_ITEMS.  The number of active items after
  90      some symbol cannot be more than the number of times that symbol
  91      appears as an item, which is symbol_count[symbol].
  92      We allocate that much space for each symbol.  */
  93
  94   kernel_base = XCALLOC (short *, nsyms);
  95   if (count)
  96     kernel_items = XCALLOC (short, count);
  97
  98   count = 0;
  99   for (i = 0; i < nsyms; i++)
 100     {
 101       kernel_base[i] = kernel_items + count;
 102       count += symbol_count[i];
 103     }
 104
 105   free (symbol_count);
 106   kernel_size = XCALLOC (int, nsyms);
 107 }
 108
 109
 110 static void
 111 allocate_storage (void)
 112 {
 113   allocate_itemsets ();
 114
 115   shiftset = XCALLOC (short, nsyms);
 116   redset = XCALLOC (short, nrules + 1);
 117   state_hash = XCALLOC (state_t *, STATE_HASH_SIZE);
 118   shift_symbol = XCALLOC (short, nsyms);
 119 }
 120
 121
 122 static void
 123 free_storage (void)
 124 {
 125   free (shift_symbol);
 126   free (redset);
 127   free (shiftset);
 128   free (kernel_base);
 129   free (kernel_size);
 130   XFREE (kernel_items);
 131   free (state_hash);
 132 }
 133
 134
 135
 136
 137 /*----------------------------------------------------------------.
 138 | Find which symbols can be shifted in the current state, and for |
 139 | each one record which items would be active after that shift.   |
 140 | Uses the contents of itemset.                                   |
 141 |                                                                 |
 142 | shift_symbol is set to a vector of the symbols that can be      |
 143 | shifted.  For each symbol in the grammar, kernel_base[symbol]   |
 144 | points to a vector of item numbers activated if that symbol is  |
 145 | shifted, and kernel_size[symbol] is their numbers.              |
 146 `----------------------------------------------------------------*/
 147
 148 static void
 149 new_itemsets (void)
 150 {
 151   int i;
 152
 153   if (trace_flag)
 154     fprintf (stderr, "Entering new_itemsets, state = %d\n",
 155              this_state->number);
 156
 157   for (i = 0; i < nsyms; i++)
 158     kernel_size[i] = 0;
 159
 160   nshifts = 0;
 161
 162   for (i = 0; i < nitemset; ++i)
 163     {
 164       int symbol = ritem[itemset[i]];
 165       if (symbol >= 0)
 166         {
 167           if (!kernel_size[symbol])
 168             {
 169               shift_symbol[nshifts] = symbol;
 170               nshifts++;
 171             }
 172
 173           kernel_base[symbol][kernel_size[symbol]] = itemset[i] + 1;
 174           kernel_size[symbol]++;
 175         }
 176     }
 177 }
 178
 179
 180
 181 /*-----------------------------------------------------------------.
 182 | Subroutine of get_state.  Create a new state for those items, if |
 183 | necessary.                                                       |
 184 `-----------------------------------------------------------------*/
 185
 186 static state_t *
 187 new_state (int symbol)
 188 {
 189   state_t *p;
 190
 191   if (trace_flag)
 192     fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",
 193              nstates, symbol, symbols[symbol]->tag);
 194
 195   if (nstates >= MAXSHORT)
 196     fatal (_("too many states (max %d)"), MAXSHORT);
 197
 198   p = STATE_ALLOC (kernel_size[symbol]);
 199   p->accessing_symbol = symbol;
 200   p->number = nstates;
 201   p->nitems = kernel_size[symbol];
 202
 203   shortcpy (p->items, kernel_base[symbol], kernel_size[symbol]);
 204
 205   /* If this is the eoftoken, and this is not the initial state, then
 206      this is the final state.  */
 207   if (symbol == 0 && first_state)
 208     final_state = p->number;
 209
 210   if (!first_state)
 211     first_state = p;
 212   if (last_state)
 213     last_state->next = p;
 214   last_state = p;
 215
 216   nstates++;
 217
 218   return p;
 219 }
 220
 221
 222 /*--------------------------------------------------------------.
 223 | Find the state number for the state we would get to (from the |
 224 | current state) by shifting symbol.  Create a new state if no  |
 225 | equivalent one exists already.  Used by append_states.        |
 226 `--------------------------------------------------------------*/
 227
 228 static int
 229 get_state (int symbol)
 230 {
 231   int key;
 232   int i;
 233   state_t *sp;
 234
 235   if (trace_flag)
 236     fprintf (stderr, "Entering get_state, state = %d, symbol = %d (%s)\n",
 237              this_state->number, symbol, symbols[symbol]->tag);
 238
 239   /* Add up the target state's active item numbers to get a hash key.
 240      */
 241   key = 0;
 242   for (i = 0; i < kernel_size[symbol]; ++i)
 243     key += kernel_base[symbol][i];
 244   key = key % STATE_HASH_SIZE;
 245   sp = state_hash[key];
 246
 247   if (sp)
 248     {
 249       int found = 0;
 250       while (!found)
 251         {
 252           if (sp->nitems == kernel_size[symbol])
 253             {
 254               found = 1;
 255               for (i = 0; i < kernel_size[symbol]; ++i)
 256                 if (kernel_base[symbol][i] != sp->items[i])
 257                   found = 0;
 258             }
 259
 260           if (!found)
 261             {
 262               if (sp->link)
 263                 {
 264                   sp = sp->link;
 265                 }
 266               else              /* bucket exhausted and no match */
 267                 {
 268                   sp = sp->link = new_state (symbol);
 269                   found = 1;
 270                 }
 271             }
 272         }
 273     }
 274   else                          /* bucket is empty */
 275     {
 276       state_hash[key] = sp = new_state (symbol);
 277     }
 278
 279   if (trace_flag)
 280     fprintf (stderr, "Exiting get_state => %d\n", sp->number);
 281
 282   return sp->number;
 283 }
 284
 285 /*------------------------------------------------------------------.
 286 | Use the information computed by new_itemsets to find the state    |
 287 | numbers reached by each shift transition from the current state.  |
 288 |                                                                   |
 289 | shiftset is set up as a vector of state numbers of those states.  |
 290 `------------------------------------------------------------------*/
 291
 292 static void
 293 append_states (void)
 294 {
 295   int i;
 296   int j;
 297   int symbol;
 298
 299   if (trace_flag)
 300     fprintf (stderr, "Entering append_states, state = %d\n",
 301              this_state->number);
 302
 303   /* first sort shift_symbol into increasing order */
 304
 305   for (i = 1; i < nshifts; i++)
 306     {
 307       symbol = shift_symbol[i];
 308       j = i;
 309       while (j > 0 && shift_symbol[j - 1] > symbol)
 310         {
 311           shift_symbol[j] = shift_symbol[j - 1];
 312           j--;
 313         }
 314       shift_symbol[j] = symbol;
 315     }
 316
 317   for (i = 0; i < nshifts; i++)
 318     shiftset[i] = get_state (shift_symbol[i]);
 319 }
 320
 321
 322 static void
 323 new_states (void)
 324 {
 325   /* The 0 at the lhs is the index of the item of this initial rule.  */
 326   kernel_base[0][0] = 0;
 327   kernel_size[0] = 1;
 328   this_state = new_state (0);
 329 }
 330
 331
 332 /*------------------------------------------------------------.
 333 | Save the NSHIFTS of SHIFTSET into the current linked list.  |
 334 `------------------------------------------------------------*/
 335
 336 static void
 337 save_shifts (void)
 338 {
 339   shifts *p = shifts_new (nshifts);
 340   shortcpy (p->shifts, shiftset, nshifts);
 341   this_state->shifts = p;
 342 }
 343
 344
 345 /*----------------------------------------------------------------.
 346 | Find which rules can be used for reduction transitions from the |
 347 | current state and make a reductions structure for the state to  |
 348 | record their rule numbers.                                      |
 349 `----------------------------------------------------------------*/
 350
 351 static void
 352 save_reductions (void)
 353 {
 354   int count = 0;
 355   int i;
 356
 357   /* If this is the final state, we want it to have no reductions at
 358      all, although it has one for `START_SYMBOL EOF .'.  */
 359   if (this_state->number == final_state)
 360     return;
 361
 362   /* Find and count the active items that represent ends of rules. */
 363   for (i = 0; i < nitemset; ++i)
 364     {
 365       int item = ritem[itemset[i]];
 366       if (item < 0)
 367         redset[count++] = -item;
 368     }
 369
 370   /* Make a reductions structure and copy the data into it.  */
 371   this_state->reductions = reductions_new (count);
 372   shortcpy (this_state->reductions->rules, redset, count);
 373 }
 374
 375 \f
 376 /*---------------.
 377 | Build STATES.  |
 378 `---------------*/
 379
 380 static void
 381 set_states (void)
 382 {
 383   state_t *sp;
 384   states = XCALLOC (state_t *, nstates);
 385
 386   for (sp = first_state; sp; sp = sp->next)
 387     {
 388       /* Pessimization, but simplification of the code: make sure all
 389          the states have a shifts, errs, and reductions, even if
 390          reduced to 0.  */
 391       if (!sp->shifts)
 392         sp->shifts = shifts_new (0);
 393       if (!sp->errs)
 394         sp->errs = errs_new (0);
 395       if (!sp->reductions)
 396         sp->reductions = reductions_new (0);
 397
 398       states[sp->number] = sp;
 399     }
 400 }
 401
 402 /*-------------------------------------------------------------------.
 403 | Compute the nondeterministic finite state machine (see state.h for |
 404 | details) from the grammar.                                         |
 405 `-------------------------------------------------------------------*/
 406
 407 void
 408 generate_states (void)
 409 {
 410   allocate_storage ();
 411   new_closure (nritems);
 412   new_states ();
 413
 414   while (this_state)
 415     {
 416       if (trace_flag)
 417         fprintf (stderr, "Processing state %d (reached by %s)\n",
 418                  this_state->number,
 419                  symbols[this_state->accessing_symbol]->tag);
 420       /* Set up ruleset and itemset for the transitions out of this
 421          state.  ruleset gets a 1 bit for each rule that could reduce
 422          now.  itemset gets a vector of all the items that could be
 423          accepted next.  */
 424       closure (this_state->items, this_state->nitems);
 425       /* record the reductions allowed out of this state */
 426       save_reductions ();
 427       /* find the itemsets of the states that shifts can reach */
 428       new_itemsets ();
 429       /* find or create the core structures for those states */
 430       append_states ();
 431
 432       /* create the shifts structures for the shifts to those states,
 433          now that the state numbers transitioning to are known */
 434       save_shifts ();
 435
 436       /* states are queued when they are created; process them all */
 437       this_state = this_state->next;
 438     }
 439
 440   /* discard various storage */
 441   free_closure ();
 442   free_storage ();
 443
 444   /* Set up STATES. */
 445   set_states ();
 446 }