src/LR0.c

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