src/LR0.c

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