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