src/LR0.c

   1 /* Generate the nondeterministic finite state machine for Bison.
   2
   3    Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002 Free Software
   4    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 *symbol_count = CALLOC (symbol_count, nsyms + nuseless_nonterminals);
 110
 111   for (r = 0; r < nrules; ++r)
 112     for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
 113       {
 114         count++;
 115         symbol_count[*rhsp]++;
 116       }
 117
 118   /* See comments before new_itemsets.  All the vectors of items
 119      live inside KERNEL_ITEMS.  The number of active items after
 120      some symbol S cannot be more than the number of times that S
 121      appears as an item, which is SYMBOL_COUNT[S].
 122      We allocate that much space for each symbol.  */
 123
 124   CALLOC (kernel_base, nsyms);
 125   if (count)
 126     CALLOC (kernel_items, count);
 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   CALLOC (kernel_size, nsyms);
 137 }
 138
 139
 140 static void
 141 allocate_storage (void)
 142 {
 143   allocate_itemsets ();
 144
 145   CALLOC (shiftset, nsyms);
 146   CALLOC (redset, nrules);
 147   state_hash_new ();
 148   CALLOC (shift_symbol, nsyms);
 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   XFREE (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   int i;
 182
 183   if (trace_flag & trace_automaton)
 184     fprintf (stderr, "Entering new_itemsets, state = %d\n", s->number);
 185
 186   for (i = 0; i < nsyms; i++)
 187     kernel_size[i] = 0;
 188
 189   nshifts = 0;
 190
 191   for (i = 0; i < nritemset; ++i)
 192     if (ritem[itemset[i]] >= 0)
 193       {
 194         symbol_number sym = item_number_as_symbol_number (ritem[itemset[i]]);
 195         if (!kernel_size[sym])
 196           {
 197             shift_symbol[nshifts] = sym;
 198             nshifts++;
 199           }
 200
 201         kernel_base[sym][kernel_size[sym]] = itemset[i] + 1;
 202         kernel_size[sym]++;
 203       }
 204 }
 205
 206
 207
 208 /*--------------------------------------------------------------.
 209 | Find the state we would get to (from the current state) by    |
 210 | shifting SYM.  Create a new state if no equivalent one exists |
 211 | already.  Used by append_states.                              |
 212 `--------------------------------------------------------------*/
 213
 214 static state *
 215 get_state (symbol_number sym, size_t core_size, item_number *core)
 216 {
 217   state *sp;
 218
 219   if (trace_flag & trace_automaton)
 220     fprintf (stderr, "Entering get_state, symbol = %d (%s)\n",
 221              sym, symbols[sym]->tag);
 222
 223   sp = state_hash_lookup (core_size, core);
 224   if (!sp)
 225     sp = state_list_append (sym, core_size, core);
 226
 227   if (trace_flag & trace_automaton)
 228     fprintf (stderr, "Exiting get_state => %d\n", sp->number);
 229
 230   return sp;
 231 }
 232
 233 /*---------------------------------------------------------------.
 234 | Use the information computed by new_itemsets to find the state |
 235 | numbers reached by each shift transition from S.               |
 236 |                                                                |
 237 | SHIFTSET is set up as a vector of those states.                |
 238 `---------------------------------------------------------------*/
 239
 240 static void
 241 append_states (state *s)
 242 {
 243   int i;
 244
 245   if (trace_flag & trace_automaton)
 246     fprintf (stderr, "Entering append_states, state = %d\n", s->number);
 247
 248   /* First sort shift_symbol into increasing order.  */
 249
 250   for (i = 1; i < nshifts; i++)
 251     {
 252       symbol_number sym = shift_symbol[i];
 253       int j;
 254       for (j = i; 0 < j && sym < shift_symbol [j - 1]; j--)
 255         shift_symbol[j] = shift_symbol[j - 1];
 256       shift_symbol[j] = sym;
 257     }
 258
 259   for (i = 0; i < nshifts; i++)
 260     {
 261       symbol_number sym = shift_symbol[i];
 262       shiftset[i] = get_state (sym, kernel_size[sym], kernel_base[sym]);
 263     }
 264 }
 265
 266
 267 /*----------------------------------------------------------------.
 268 | Find which rules can be used for reduction transitions from the |
 269 | current state and make a reductions structure for the state to  |
 270 | record their rule numbers.                                      |
 271 `----------------------------------------------------------------*/
 272
 273 static void
 274 save_reductions (state *s)
 275 {
 276   int count = 0;
 277   int i;
 278
 279   /* Find and count the active items that represent ends of rules. */
 280   for (i = 0; i < nritemset; ++i)
 281     {
 282       int item = ritem[itemset[i]];
 283       if (item < 0)
 284         redset[count++] = &rules[item_number_as_rule_number (item)];
 285     }
 286
 287   /* Make a reductions structure and copy the data into it.  */
 288   state_reductions_set (s, count, redset);
 289 }
 290
 291 \f
 292 /*---------------.
 293 | Build STATES.  |
 294 `---------------*/
 295
 296 static void
 297 set_states (void)
 298 {
 299   CALLOC (states, nstates);
 300
 301   while (first_state)
 302     {
 303       state_list *this = first_state;
 304
 305       /* Pessimization, but simplification of the code: make sure all
 306          the states have valid transitions and reductions members,
 307          even if reduced to 0.  It is too soon for errs, which are
 308          computed later, but set_conflicts.  */
 309       state *s = this->state;
 310       if (!s->transitions)
 311         state_transitions_set (s, 0, 0);
 312       if (!s->reductions)
 313         state_reductions_set (s, 0, 0);
 314
 315       states[s->number] = s;
 316
 317       first_state = this->next;
 318       free (this);
 319     }
 320   first_state = NULL;
 321   last_state = NULL;
 322 }
 323
 324
 325 /*-------------------------------------------------------------------.
 326 | Compute the nondeterministic finite state machine (see state.h for |
 327 | details) from the grammar.                                         |
 328 `-------------------------------------------------------------------*/
 329
 330 void
 331 generate_states (void)
 332 {
 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   kernel_base[0][0] = 0;
 340   kernel_size[0] = 1;
 341   state_list_append (0, kernel_size[0], kernel_base[0]);
 342
 343   list = first_state;
 344
 345   while (list)
 346     {
 347       state *s = list->state;
 348       if (trace_flag & trace_automaton)
 349         fprintf (stderr, "Processing state %d (reached by %s)\n",
 350                  s->number,
 351                  symbols[s->accessing_symbol]->tag);
 352       /* Set up ruleset and itemset for the transitions out of this
 353          state.  ruleset gets a 1 bit for each rule that could reduce
 354          now.  itemset gets a vector of all the items that could be
 355          accepted next.  */
 356       closure (s->items, s->nitems);
 357       /* Record the reductions allowed out of this state.  */
 358       save_reductions (s);
 359       /* Find the itemsets of the states that shifts can reach.  */
 360       new_itemsets (s);
 361       /* Find or create the core structures for those states.  */
 362       append_states (s);
 363
 364       /* Create the shifts structures for the shifts to those states,
 365          now that the state numbers transitioning to are known.  */
 366       state_transitions_set (s, nshifts, shiftset);
 367
 368       /* states are queued when they are created; process them all.
 369          */
 370       list = list->next;
 371     }
 372
 373   /* discard various storage */
 374   free_closure ();
 375   free_storage ();
 376
 377   /* Set up STATES. */
 378   set_states ();
 379 }