src/LR0.c

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