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