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