src/LR0.c

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