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 = MALLOC (node, 1);
  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 = NULL;
  88
  89 static rule **redset = NULL;
  90 static state **shiftset = NULL;
  91
  92 static item_number **kernel_base = NULL;
  93 static int *kernel_size = NULL;
  94 static item_number *kernel_items = NULL;
  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   int count = 0;
 109   short int *symbol_count = CALLOC (symbol_count,
 110                                     nsyms + nuseless_nonterminals);
 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   CALLOC (kernel_base, nsyms);
 126   if (count)
 127     CALLOC (kernel_items, count);
 128
 129   count = 0;
 130   for (i = 0; i < nsyms; i++)
 131     {
 132       kernel_base[i] = kernel_items + count;
 133       count += symbol_count[i];
 134     }
 135
 136   free (symbol_count);
 137   CALLOC (kernel_size, nsyms);
 138 }
 139
 140
 141 static void
 142 allocate_storage (void)
 143 {
 144   allocate_itemsets ();
 145
 146   CALLOC (shiftset, nsyms);
 147   CALLOC (redset, nrules);
 148   state_hash_new ();
 149   CALLOC (shift_symbol, nsyms);
 150 }
 151
 152
 153 static void
 154 free_storage (void)
 155 {
 156   free (shift_symbol);
 157   free (redset);
 158   free (shiftset);
 159   free (kernel_base);
 160   free (kernel_size);
 161   XFREE (kernel_items);
 162   state_hash_free ();
 163 }
 164
 165
 166
 167
 168 /*---------------------------------------------------------------.
 169 | Find which symbols can be shifted in S, and for each one       |
 170 | record which items would be active after that shift.  Uses the |
 171 | contents of itemset.                                           |
 172 |                                                                |
 173 | shift_symbol is set to a vector of the symbols that can be     |
 174 | shifted.  For each symbol in the grammar, kernel_base[symbol]  |
 175 | points to a vector of item numbers activated if that symbol is |
 176 | shifted, and kernel_size[symbol] is their numbers.             |
 177 `---------------------------------------------------------------*/
 178
 179 static void
 180 new_itemsets (state *s)
 181 {
 182   int i;
 183
 184   if (trace_flag & trace_automaton)
 185     fprintf (stderr, "Entering new_itemsets, state = %d\n", s->number);
 186
 187   for (i = 0; i < nsyms; i++)
 188     kernel_size[i] = 0;
 189
 190   nshifts = 0;
 191
 192   for (i = 0; i < nritemset; ++i)
 193     if (ritem[itemset[i]] >= 0)
 194       {
 195         symbol_number sym = item_number_as_symbol_number (ritem[itemset[i]]);
 196         if (!kernel_size[sym])
 197           {
 198             shift_symbol[nshifts] = sym;
 199             nshifts++;
 200           }
 201
 202         kernel_base[sym][kernel_size[sym]] = itemset[i] + 1;
 203         kernel_size[sym]++;
 204       }
 205 }
 206
 207
 208
 209 /*--------------------------------------------------------------.
 210 | Find the state we would get to (from the current state) by    |
 211 | shifting SYM.  Create a new state if no equivalent one exists |
 212 | already.  Used by append_states.                              |
 213 `--------------------------------------------------------------*/
 214
 215 static state *
 216 get_state (symbol_number sym, size_t core_size, item_number *core)
 217 {
 218   state *sp;
 219
 220   if (trace_flag & trace_automaton)
 221     fprintf (stderr, "Entering get_state, symbol = %d (%s)\n",
 222              sym, symbols[sym]->tag);
 223
 224   sp = state_hash_lookup (core_size, core);
 225   if (!sp)
 226     sp = state_list_append (sym, 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 S.               |
 237 |                                                                |
 238 | SHIFTSET is set up as a vector of those states.                |
 239 `---------------------------------------------------------------*/
 240
 241 static void
 242 append_states (state *s)
 243 {
 244   int i;
 245
 246   if (trace_flag & trace_automaton)
 247     fprintf (stderr, "Entering append_states, state = %d\n", s->number);
 248
 249   /* First sort shift_symbol into increasing order.  */
 250
 251   for (i = 1; i < nshifts; i++)
 252     {
 253       symbol_number sym = shift_symbol[i];
 254       int j;
 255       for (j = i; 0 < j && sym < shift_symbol [j - 1]; j--)
 256         shift_symbol[j] = shift_symbol[j - 1];
 257       shift_symbol[j] = sym;
 258     }
 259
 260   for (i = 0; i < nshifts; i++)
 261     {
 262       symbol_number sym = shift_symbol[i];
 263       shiftset[i] = get_state (sym, kernel_size[sym], kernel_base[sym]);
 264     }
 265 }
 266
 267
 268 /*----------------------------------------------------------------.
 269 | Find which rules can be used for reduction transitions from the |
 270 | current state and make a reductions structure for the state to  |
 271 | record their rule numbers.                                      |
 272 `----------------------------------------------------------------*/
 273
 274 static void
 275 save_reductions (state *s)
 276 {
 277   int count = 0;
 278   int i;
 279
 280   /* Find and count the active items that represent ends of rules. */
 281   for (i = 0; i < nritemset; ++i)
 282     {
 283       int item = ritem[itemset[i]];
 284       if (item < 0)
 285         redset[count++] = &rules[item_number_as_rule_number (item)];
 286     }
 287
 288   /* Make a reductions structure and copy the data into it.  */
 289   state_reductions_set (s, count, redset);
 290 }
 291
 292 \f
 293 /*---------------.
 294 | Build STATES.  |
 295 `---------------*/
 296
 297 static void
 298 set_states (void)
 299 {
 300   CALLOC (states, nstates);
 301
 302   while (first_state)
 303     {
 304       state_list *this = first_state;
 305
 306       /* Pessimization, but simplification of the code: make sure all
 307          the states have valid transitions and reductions members,
 308          even if reduced to 0.  It is too soon for errs, which are
 309          computed later, but set_conflicts.  */
 310       state *s = this->state;
 311       if (!s->transitions)
 312         state_transitions_set (s, 0, 0);
 313       if (!s->reductions)
 314         state_reductions_set (s, 0, 0);
 315
 316       states[s->number] = s;
 317
 318       first_state = this->next;
 319       free (this);
 320     }
 321   first_state = NULL;
 322   last_state = NULL;
 323 }
 324
 325
 326 /*-------------------------------------------------------------------.
 327 | Compute the nondeterministic finite state machine (see state.h for |
 328 | details) from the grammar.                                         |
 329 `-------------------------------------------------------------------*/
 330
 331 void
 332 generate_states (void)
 333 {
 334   state_list *list = NULL;
 335   allocate_storage ();
 336   new_closure (nritems);
 337
 338   /* Create the initial state.  The 0 at the lhs is the index of the
 339      item of this initial rule.  */
 340   kernel_base[0][0] = 0;
 341   kernel_size[0] = 1;
 342   state_list_append (0, kernel_size[0], kernel_base[0]);
 343
 344   list = first_state;
 345
 346   while (list)
 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       /* states are queued when they are created; process them all.
 370          */
 371       list = list->next;
 372     }
 373
 374   /* discard various storage */
 375   free_closure ();
 376   free_storage ();
 377
 378   /* Set up STATES. */
 379   set_states ();
 380 }