src/LR0.c

   1 /* Generate the nondeterministic finite state machine for Bison.
   2
   3    Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004, 2005, 2006,
   4    2007, 2009 Free Software Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    This program 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 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.  */
  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 <config.h>
  26 #include "system.h"
  27
  28 #include <bitset.h>
  29 #include <quotearg.h>
  30
  31 #include "LR0.h"
  32 #include "closure.h"
  33 #include "complain.h"
  34 #include "getargs.h"
  35 #include "gram.h"
  36 #include "gram.h"
  37 #include "lalr.h"
  38 #include "reader.h"
  39 #include "reduce.h"
  40 #include "state.h"
  41 #include "symtab.h"
  42
  43 typedef struct state_list
  44 {
  45   struct state_list *next;
  46   state *state;
  47 } state_list;
  48
  49 static state_list *first_state = NULL;
  50 static state_list *last_state = NULL;
  51
  52
  53 /*------------------------------------------------------------------.
  54 | A state was just discovered from another state.  Queue it for     |
  55 | later examination, in order to find its transitions.  Return it.  |
  56 `------------------------------------------------------------------*/
  57
  58 static state *
  59 state_list_append (symbol_number sym, size_t core_size, item_number *core)
  60 {
  61   state_list *node = xmalloc (sizeof *node);
  62   state *s = state_new (sym, core_size, core);
  63
  64   if (trace_flag & trace_automaton)
  65     fprintf (stderr, "state_list_append (state = %d, symbol = %d (%s))\n",
  66              nstates, sym, symbols[sym]->tag);
  67
  68   node->next = NULL;
  69   node->state = s;
  70
  71   if (!first_state)
  72     first_state = node;
  73   if (last_state)
  74     last_state->next = node;
  75   last_state = node;
  76
  77   return s;
  78 }
  79
  80 static int nshifts;
  81 static symbol_number *shift_symbol;
  82
  83 static rule **redset;
  84 static state **shiftset;
  85
  86 static item_number **kernel_base;
  87 static int *kernel_size;
  88 static item_number *kernel_items;
  89
  90 \f
  91 static void
  92 allocate_itemsets (void)
  93 {
  94   symbol_number i;
  95   rule_number r;
  96   item_number *rhsp;
  97
  98   /* Count the number of occurrences of all the symbols in RITEMS.
  99      Note that useless productions (hence useless nonterminals) are
 100      browsed too, hence we need to allocate room for _all_ the
 101      symbols.  */
 102   size_t count = 0;
 103   size_t *symbol_count = xcalloc (nsyms + nuseless_nonterminals,
 104                                   sizeof *symbol_count);
 105
 106   for (r = 0; r < nrules; ++r)
 107     for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
 108       {
 109         count++;
 110         symbol_count[*rhsp]++;
 111       }
 112
 113   /* See comments before new_itemsets.  All the vectors of items
 114      live inside KERNEL_ITEMS.  The number of active items after
 115      some symbol S cannot be more than the number of times that S
 116      appears as an item, which is SYMBOL_COUNT[S].
 117      We allocate that much space for each symbol.  */
 118
 119   kernel_base = xnmalloc (nsyms, sizeof *kernel_base);
 120   kernel_items = xnmalloc (count, sizeof *kernel_items);
 121
 122   count = 0;
 123   for (i = 0; i < nsyms; i++)
 124     {
 125       kernel_base[i] = kernel_items + count;
 126       count += symbol_count[i];
 127     }
 128
 129   free (symbol_count);
 130   kernel_size = xnmalloc (nsyms, sizeof *kernel_size);
 131 }
 132
 133
 134 static void
 135 allocate_storage (void)
 136 {
 137   allocate_itemsets ();
 138
 139   shiftset = xnmalloc (nsyms, sizeof *shiftset);
 140   redset = xnmalloc (nrules, sizeof *redset);
 141   state_hash_new ();
 142   shift_symbol = xnmalloc (nsyms, sizeof *shift_symbol);
 143 }
 144
 145
 146 static void
 147 free_storage (void)
 148 {
 149   free (shift_symbol);
 150   free (redset);
 151   free (shiftset);
 152   free (kernel_base);
 153   free (kernel_size);
 154   free (kernel_items);
 155   state_hash_free ();
 156 }
 157
 158
 159
 160
 161 /*---------------------------------------------------------------.
 162 | Find which symbols can be shifted in S, and for each one       |
 163 | record which items would be active after that shift.  Uses the |
 164 | contents of itemset.                                           |
 165 |                                                                |
 166 | shift_symbol is set to a vector of the symbols that can be     |
 167 | shifted.  For each symbol in the grammar, kernel_base[symbol]  |
 168 | points to a vector of item numbers activated if that symbol is |
 169 | shifted, and kernel_size[symbol] is their numbers.             |
 170 |                                                                |
 171 | itemset is sorted on item index in ritem, which is sorted on   |
 172 | rule number.  Compute each kernel_base[symbol] with the same   |
 173 | sort.                                                          |
 174 `---------------------------------------------------------------*/
 175
 176 static void
 177 new_itemsets (state *s)
 178 {
 179   size_t i;
 180
 181   if (trace_flag & trace_automaton)
 182     fprintf (stderr, "Entering new_itemsets, state = %d\n", s->number);
 183
 184   memset (kernel_size, 0, nsyms * sizeof *kernel_size);
 185
 186   nshifts = 0;
 187
 188   for (i = 0; i < nitemset; ++i)
 189     if (item_number_is_symbol_number (ritem[itemset[i]]))
 190       {
 191         symbol_number sym = item_number_as_symbol_number (ritem[itemset[i]]);
 192         if (!kernel_size[sym])
 193           {
 194             shift_symbol[nshifts] = sym;
 195             nshifts++;
 196           }
 197
 198         kernel_base[sym][kernel_size[sym]] = itemset[i] + 1;
 199         kernel_size[sym]++;
 200       }
 201 }
 202
 203
 204
 205 /*--------------------------------------------------------------.
 206 | Find the state we would get to (from the current state) by    |
 207 | shifting SYM.  Create a new state if no equivalent one exists |
 208 | already.  Used by append_states.                              |
 209 `--------------------------------------------------------------*/
 210
 211 static state *
 212 get_state (symbol_number sym, size_t core_size, item_number *core)
 213 {
 214   state *s;
 215
 216   if (trace_flag & trace_automaton)
 217     fprintf (stderr, "Entering get_state, symbol = %d (%s)\n",
 218              sym, symbols[sym]->tag);
 219
 220   s = state_hash_lookup (core_size, core);
 221   if (!s)
 222     s = state_list_append (sym, core_size, core);
 223
 224   if (trace_flag & trace_automaton)
 225     fprintf (stderr, "Exiting get_state => %d\n", s->number);
 226
 227   return s;
 228 }
 229
 230 /*---------------------------------------------------------------.
 231 | Use the information computed by new_itemsets to find the state |
 232 | numbers reached by each shift transition from S.               |
 233 |                                                                |
 234 | SHIFTSET is set up as a vector of those states.                |
 235 `---------------------------------------------------------------*/
 236
 237 static void
 238 append_states (state *s)
 239 {
 240   int i;
 241
 242   if (trace_flag & trace_automaton)
 243     fprintf (stderr, "Entering append_states, state = %d\n", s->number);
 244
 245   /* First sort shift_symbol into increasing order.  */
 246
 247   for (i = 1; i < nshifts; i++)
 248     {
 249       symbol_number sym = shift_symbol[i];
 250       int j;
 251       for (j = i; 0 < j && sym < shift_symbol[j - 1]; j--)
 252         shift_symbol[j] = shift_symbol[j - 1];
 253       shift_symbol[j] = sym;
 254     }
 255
 256   for (i = 0; i < nshifts; i++)
 257     {
 258       symbol_number sym = shift_symbol[i];
 259       shiftset[i] = get_state (sym, kernel_size[sym], kernel_base[sym]);
 260     }
 261 }
 262
 263
 264 /*----------------------------------------------------------------.
 265 | Find which rules can be used for reduction transitions from the |
 266 | current state and make a reductions structure for the state to  |
 267 | record their rule numbers.                                      |
 268 `----------------------------------------------------------------*/
 269
 270 static void
 271 save_reductions (state *s)
 272 {
 273   int count = 0;
 274   size_t i;
 275
 276   /* Find and count the active items that represent ends of rules. */
 277   for (i = 0; i < nitemset; ++i)
 278     {
 279       item_number item = ritem[itemset[i]];
 280       if (item_number_is_rule_number (item))
 281         {
 282           rule_number r = item_number_as_rule_number (item);
 283           redset[count++] = &rules[r];
 284           if (r == 0)
 285             {
 286               /* This is "reduce 0", i.e., accept. */
 287               aver (!final_state);
 288               final_state = s;
 289             }
 290         }
 291     }
 292
 293   /* Make a reductions structure and copy the data into it.  */
 294   state_reductions_set (s, count, redset);
 295 }
 296
 297 \f
 298 /*---------------.
 299 | Build STATES.  |
 300 `---------------*/
 301
 302 static void
 303 set_states (void)
 304 {
 305   states = xcalloc (nstates, sizeof *states);
 306
 307   while (first_state)
 308     {
 309       state_list *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 *s = this->state;
 316       if (!s->transitions)
 317         state_transitions_set (s, 0, 0);
 318       if (!s->reductions)
 319         state_reductions_set (s, 0, 0);
 320
 321       states[s->number] = s;
 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   item_number initial_core = 0;
 340   state_list *list = NULL;
 341   allocate_storage ();
 342   new_closure (nritems);
 343
 344   /* Create the initial state.  The 0 at the lhs is the index of the
 345      item of this initial rule.  */
 346   state_list_append (0, 1, &initial_core);
 347
 348   /* States are queued when they are created; process them all.  */
 349   for (list = first_state; list; list = list->next)
 350     {
 351       state *s = list->state;
 352       if (trace_flag & trace_automaton)
 353         fprintf (stderr, "Processing state %d (reached by %s)\n",
 354                  s->number,
 355                  symbols[s->accessing_symbol]->tag);
 356       /* Set up itemset for the transitions out of this state.  itemset gets a
 357          vector of all the items that could be accepted next.  */
 358       closure (s->items, s->nitems);
 359       /* Record the reductions allowed out of this state.  */
 360       save_reductions (s);
 361       /* Find the itemsets of the states that shifts can reach.  */
 362       new_itemsets (s);
 363       /* Find or create the core structures for those states.  */
 364       append_states (s);
 365
 366       /* Create the shifts structures for the shifts to those states,
 367          now that the state numbers transitioning to are known.  */
 368       state_transitions_set (s, nshifts, shiftset);
 369     }
 370
 371   /* discard various storage */
 372   free_closure ();
 373   free_storage ();
 374
 375   /* Set up STATES. */
 376   set_states ();
 377 }