src/LR0.c

   1 /* Generate the nondeterministic finite state machine for bison,
   2    Copyright 1984, 1986, 1989, 2000, 2001  Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  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 "system.h"
  26 #include "getargs.h"
  27 #include "reader.h"
  28 #include "gram.h"
  29 #include "state.h"
  30 #include "complain.h"
  31 #include "closure.h"
  32 #include "LR0.h"
  33 #include "lalr.h"
  34 #include "reduce.h"
  35
  36 int nstates;
  37 int final_state;
  38 static state_t *first_state = NULL;
  39
  40 static state_t *this_state = NULL;
  41 static state_t *last_state = NULL;
  42
  43 static int nshifts;
  44 static short *shift_symbol = NULL;
  45
  46 static short *redset = NULL;
  47 static short *shiftset = NULL;
  48
  49 static short **kernel_base = NULL;
  50 static int *kernel_size = NULL;
  51 static short *kernel_items = NULL;
  52
  53 /* hash table for states, to recognize equivalent ones.  */
  54
  55 #define STATE_HASH_SIZE 1009
  56 static state_t **state_hash = NULL;
  57
  58 \f
  59 static void
  60 allocate_itemsets (void)
  61 {
  62   int i;
  63
  64   /* Count the number of occurrences of all the symbols in RITEMS.
  65      Note that useless productions (hence useless nonterminals) are
  66      browsed too, hence we need to allocate room for _all_ the
  67      symbols.  */
  68   int count = 0;
  69   short *symbol_count = XCALLOC (short, nsyms + nuseless_nonterminals);
  70
  71   for (i = 0; ritem[i]; ++i)
  72     if (ritem[i] > 0)
  73       {
  74         count++;
  75         symbol_count[ritem[i]]++;
  76       }
  77
  78   /* See comments before new_itemsets.  All the vectors of items
  79      live inside KERNEL_ITEMS.  The number of active items after
  80      some symbol cannot be more than the number of times that symbol
  81      appears as an item, which is symbol_count[symbol].
  82      We allocate that much space for each symbol.  */
  83
  84   kernel_base = XCALLOC (short *, nsyms);
  85   if (count)
  86     kernel_items = XCALLOC (short, count);
  87
  88   count = 0;
  89   for (i = 0; i < nsyms; i++)
  90     {
  91       kernel_base[i] = kernel_items + count;
  92       count += symbol_count[i];
  93     }
  94
  95   free (symbol_count);
  96   kernel_size = XCALLOC (int, nsyms);
  97 }
  98
  99
 100 static void
 101 allocate_storage (void)
 102 {
 103   allocate_itemsets ();
 104
 105   shiftset = XCALLOC (short, nsyms);
 106   redset = XCALLOC (short, nrules + 1);
 107   state_hash = XCALLOC (state_t *, STATE_HASH_SIZE);
 108 }
 109
 110
 111 static void
 112 free_storage (void)
 113 {
 114   free (shift_symbol);
 115   free (redset);
 116   free (shiftset);
 117   free (kernel_base);
 118   free (kernel_size);
 119   XFREE (kernel_items);
 120   free (state_hash);
 121 }
 122
 123
 124
 125
 126 /*----------------------------------------------------------------.
 127 | Find which symbols can be shifted in the current state, and for |
 128 | each one record which items would be active after that shift.   |
 129 | Uses the contents of itemset.                                   |
 130 |                                                                 |
 131 | shift_symbol is set to a vector of the symbols that can be      |
 132 | shifted.  For each symbol in the grammar, kernel_base[symbol]   |
 133 | points to a vector of item numbers activated if that symbol is  |
 134 | shifted, and kernel_size[symbol] is their numbers.              |
 135 `----------------------------------------------------------------*/
 136
 137 static void
 138 new_itemsets (void)
 139 {
 140   int i;
 141
 142   if (trace_flag)
 143     fprintf (stderr, "Entering new_itemsets, state = %d\n",
 144              this_state->number);
 145
 146   for (i = 0; i < nsyms; i++)
 147     kernel_size[i] = 0;
 148
 149   shift_symbol = XCALLOC (short, nsyms);
 150   nshifts = 0;
 151
 152   for (i = 0; i < nitemset; ++i)
 153     {
 154       int symbol = ritem[itemset[i]];
 155       if (symbol > 0)
 156         {
 157           if (!kernel_size[symbol])
 158             {
 159               shift_symbol[nshifts] = symbol;
 160               nshifts++;
 161             }
 162
 163           kernel_base[symbol][kernel_size[symbol]] = itemset[i] + 1;
 164           kernel_size[symbol]++;
 165         }
 166     }
 167 }
 168
 169
 170
 171 /*-----------------------------------------------------------------.
 172 | Subroutine of get_state.  Create a new state for those items, if |
 173 | necessary.                                                       |
 174 `-----------------------------------------------------------------*/
 175
 176 static state_t *
 177 new_state (int symbol)
 178 {
 179   state_t *p;
 180
 181   if (trace_flag)
 182     fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",
 183              this_state->number, symbol, tags[symbol]);
 184
 185   if (nstates >= MAXSHORT)
 186     fatal (_("too many states (max %d)"), MAXSHORT);
 187
 188   p = STATE_ALLOC (kernel_size[symbol]);
 189   p->accessing_symbol = symbol;
 190   p->number = nstates;
 191   p->nitems = kernel_size[symbol];
 192
 193   shortcpy (p->items, kernel_base[symbol], kernel_size[symbol]);
 194
 195   last_state->next = p;
 196   last_state = p;
 197   nstates++;
 198
 199   return p;
 200 }
 201
 202
 203 /*--------------------------------------------------------------.
 204 | Find the state number for the state we would get to (from the |
 205 | current state) by shifting symbol.  Create a new state if no  |
 206 | equivalent one exists already.  Used by append_states.        |
 207 `--------------------------------------------------------------*/
 208
 209 static int
 210 get_state (int symbol)
 211 {
 212   int key;
 213   int i;
 214   state_t *sp;
 215
 216   if (trace_flag)
 217     fprintf (stderr, "Entering get_state, state = %d, symbol = %d (%s)\n",
 218              this_state->number, symbol, tags[symbol]);
 219
 220   /* Add up the target state's active item numbers to get a hash key.
 221      */
 222   key = 0;
 223   for (i = 0; i < kernel_size[symbol]; ++i)
 224     key += kernel_base[symbol][i];
 225   key = key % STATE_HASH_SIZE;
 226   sp = state_hash[key];
 227
 228   if (sp)
 229     {
 230       int found = 0;
 231       while (!found)
 232         {
 233           if (sp->nitems == kernel_size[symbol])
 234             {
 235               found = 1;
 236               for (i = 0; i < kernel_size[symbol]; ++i)
 237                 if (kernel_base[symbol][i] != sp->items[i])
 238                   found = 0;
 239             }
 240
 241           if (!found)
 242             {
 243               if (sp->link)
 244                 {
 245                   sp = sp->link;
 246                 }
 247               else              /* bucket exhausted and no match */
 248                 {
 249                   sp = sp->link = new_state (symbol);
 250                   found = 1;
 251                 }
 252             }
 253         }
 254     }
 255   else                          /* bucket is empty */
 256     {
 257       state_hash[key] = sp = new_state (symbol);
 258     }
 259
 260   if (trace_flag)
 261     fprintf (stderr, "Exiting get_state => %d\n", sp->number);
 262
 263   return sp->number;
 264 }
 265
 266 /*------------------------------------------------------------------.
 267 | Use the information computed by new_itemsets to find the state    |
 268 | numbers reached by each shift transition from the current state.  |
 269 |                                                                   |
 270 | shiftset is set up as a vector of state numbers of those states.  |
 271 `------------------------------------------------------------------*/
 272
 273 static void
 274 append_states (void)
 275 {
 276   int i;
 277   int j;
 278   int symbol;
 279
 280   if (trace_flag)
 281     fprintf (stderr, "Entering append_states, state = %d\n",
 282              this_state->number);
 283
 284   /* first sort shift_symbol into increasing order */
 285
 286   for (i = 1; i < nshifts; i++)
 287     {
 288       symbol = shift_symbol[i];
 289       j = i;
 290       while (j > 0 && shift_symbol[j - 1] > symbol)
 291         {
 292           shift_symbol[j] = shift_symbol[j - 1];
 293           j--;
 294         }
 295       shift_symbol[j] = symbol;
 296     }
 297
 298   for (i = 0; i < nshifts; i++)
 299     shiftset[i] = get_state (shift_symbol[i]);
 300 }
 301
 302
 303 static void
 304 new_states (void)
 305 {
 306   first_state = last_state = this_state = STATE_ALLOC (0);
 307   nstates = 1;
 308 }
 309
 310
 311 /*------------------------------------------------------------.
 312 | Save the NSHIFTS of SHIFTSET into the current linked list.  |
 313 `------------------------------------------------------------*/
 314
 315 static void
 316 save_shifts (void)
 317 {
 318   shifts *p = shifts_new (nshifts);
 319   shortcpy (p->shifts, shiftset, nshifts);
 320   this_state->shifts = p;
 321 }
 322
 323
 324 /*------------------------------------------------------------------.
 325 | Subroutine of augment_automaton.  Create the next-to-final state, |
 326 | to which a shift has already been made in the initial state.      |
 327 |                                                                   |
 328 | The task of this state consists in shifting (actually, it's a     |
 329 | goto, but shifts and gotos are both stored in SHIFTS) the start   |
 330 | symbols, hence the name.                                          |
 331 `------------------------------------------------------------------*/
 332
 333 static void
 334 insert_start_shifting_state (void)
 335 {
 336   state_t *statep;
 337   shifts *sp;
 338
 339   statep = STATE_ALLOC (0);
 340   statep->number = nstates++;
 341
 342   /* The distinctive feature of this state from the
 343      eof_shifting_state, is that it is labeled as post-start-symbol
 344      shifting.  I fail to understand why this state, and the
 345      post-start-start can't be merged into one.  But it does fail if
 346      you try. --akim */
 347   statep->accessing_symbol = start_symbol;
 348
 349   last_state->next = statep;
 350   last_state = statep;
 351
 352   /* Make a shift from this state to (what will be) the final state.  */
 353   sp = shifts_new (1);
 354   statep->shifts = sp;
 355   sp->shifts[0] = nstates;
 356 }
 357
 358
 359 /*-----------------------------------------------------------------.
 360 | Subroutine of augment_automaton.  Create the final state, which  |
 361 | shifts `0', the end of file.  The initial state shifts the start |
 362 | symbol, and goes to here.                                        |
 363 `-----------------------------------------------------------------*/
 364
 365 static void
 366 insert_eof_shifting_state (void)
 367 {
 368   state_t *statep;
 369   shifts *sp;
 370
 371   /* Make the final state--the one that follows a shift from the
 372      next-to-final state.
 373      The symbol for that shift is 0 (end-of-file).  */
 374   statep = STATE_ALLOC (0);
 375   statep->number = nstates++;
 376
 377   last_state->next = statep;
 378   last_state = statep;
 379
 380   /* Make the shift from the final state to the termination state.  */
 381   sp = shifts_new (1);
 382   statep->shifts = sp;
 383   sp->shifts[0] = nstates;
 384 }
 385
 386
 387 /*---------------------------------------------------------------.
 388 | Subroutine of augment_automaton.  Create the accepting state.  |
 389 `---------------------------------------------------------------*/
 390
 391 static void
 392 insert_accepting_state (void)
 393 {
 394   state_t *statep;
 395
 396    /* Note that the variable `final_state' refers to what we sometimes
 397       call the termination state.  */
 398   final_state = nstates;
 399
 400   /* Make the termination state.  */
 401   statep = STATE_ALLOC (0);
 402   statep->number = nstates++;
 403   last_state->next = statep;
 404   last_state = statep;
 405 }
 406
 407
 408
 409
 410
 411 /*------------------------------------------------------------------.
 412 | Make sure that the initial state has a shift that accepts the     |
 413 | grammar's start symbol and goes to the next-to-final state, which |
 414 | has a shift going to the final state, which has a shift to the    |
 415 | termination state.  Create such states and shifts if they don't   |
 416 | happen to exist already.                                          |
 417 `------------------------------------------------------------------*/
 418
 419 static void
 420 augment_automaton (void)
 421 {
 422   if (!first_state->shifts->nshifts)
 423     {
 424       /* The first state has no shifts.  Make one shift, from the
 425          initial state to the next-to-final state.  */
 426
 427       shifts *sp = shifts_new (1);
 428       first_state->shifts = sp;
 429       sp->shifts[0] = nstates;
 430
 431       /* Create the next-to-final state, with shift to
 432          what will be the final state.  */
 433       insert_start_shifting_state ();
 434     }
 435   else
 436     {
 437       state_t *statep = first_state->next;
 438       /* The states reached by shifts from FIRST_STATE are numbered
 439          1..(SP->NSHIFTS).  Look for one reached by START_SYMBOL.
 440          This is typical of `start: start ... ;': there is a state
 441          with the item `start: start . ...'.  We want to add a `shift
 442          on EOF to eof-shifting state here.  */
 443       while (statep->accessing_symbol != start_symbol
 444              && statep->number < first_state->shifts->nshifts)
 445         statep = statep->next;
 446
 447       if (statep->accessing_symbol == start_symbol)
 448         {
 449           /* We already have STATEP, a next-to-final state for `start:
 450              start . ...'.  Make sure it has a shift to what will be
 451              the final state.  */
 452           int i;
 453
 454           /* Find the shift of the inital state that leads to STATEP.  */
 455           shifts *sp = statep->shifts;
 456
 457           shifts *sp1 = shifts_new (sp->nshifts + 1);
 458           statep->shifts = sp1;
 459           sp1->shifts[0] = nstates;
 460           for (i = sp->nshifts; i > 0; i--)
 461             sp1->shifts[i] = sp->shifts[i - 1];
 462
 463           XFREE (sp);
 464
 465           insert_eof_shifting_state ();
 466         }
 467       else
 468         {
 469           /* There is no state for `start: start . ...'. */
 470           int i, k;
 471           shifts *sp = first_state->shifts;
 472           shifts *sp1 = NULL;
 473
 474           /* Add one more shift to the initial state, going to the
 475              next-to-final state (yet to be made).  */
 476           sp1 = shifts_new (sp->nshifts + 1);
 477           first_state->shifts = sp1;
 478           /* Stick this shift into the vector at the proper place.  */
 479           statep = first_state->next;
 480           for (k = 0, i = 0; i < sp->nshifts; k++, i++)
 481             {
 482               if (statep->accessing_symbol > start_symbol && i == k)
 483                 sp1->shifts[k++] = nstates;
 484               sp1->shifts[k] = sp->shifts[i];
 485               statep = statep->next;
 486             }
 487           if (i == k)
 488             sp1->shifts[k++] = nstates;
 489
 490           XFREE (sp);
 491
 492           /* Create the next-to-final state, with shift to what will
 493              be the final state.  Corresponds to `start: start . ...'.  */
 494           insert_start_shifting_state ();
 495         }
 496     }
 497
 498   insert_accepting_state ();
 499 }
 500
 501
 502 /*----------------------------------------------------------------.
 503 | Find which rules can be used for reduction transitions from the |
 504 | current state and make a reductions structure for the state to  |
 505 | record their rule numbers.                                      |
 506 `----------------------------------------------------------------*/
 507
 508 static void
 509 save_reductions (void)
 510 {
 511   int count;
 512   int i;
 513
 514   /* Find and count the active items that represent ends of rules. */
 515
 516   count = 0;
 517   for (i = 0; i < nitemset; ++i)
 518     {
 519       int item = ritem[itemset[i]];
 520       if (item < 0)
 521         redset[count++] = -item;
 522     }
 523
 524   /* Make a reductions structure and copy the data into it.  */
 525
 526   if (count)
 527     {
 528       reductions *p = REDUCTIONS_ALLOC (count);
 529       p->nreds = count;
 530       shortcpy (p->rules, redset, count);
 531
 532       this_state->reductions = p;
 533     }
 534 }
 535
 536 \f
 537 /*--------------------.
 538 | Build STATE_TABLE.  |
 539 `--------------------*/
 540
 541 static void
 542 set_state_table (void)
 543 {
 544   state_t *sp;
 545   state_table = XCALLOC (state_t *, nstates);
 546
 547   for (sp = first_state; sp; sp = sp->next)
 548     {
 549       /* Pessimization, but simplification of the code: make sure all
 550          the states have a shifts and errs, even if reduced to 0.  */
 551       if (!sp->shifts)
 552         sp->shifts = shifts_new (0);
 553       if (!sp->errs)
 554         sp->errs = errs_new (0);
 555
 556       state_table[sp->number] = sp;
 557     }
 558 }
 559
 560 /*-------------------------------------------------------------------.
 561 | Compute the nondeterministic finite state machine (see state.h for |
 562 | details) from the grammar.                                         |
 563 `-------------------------------------------------------------------*/
 564
 565 void
 566 generate_states (void)
 567 {
 568   allocate_storage ();
 569   new_closure (nitems);
 570   new_states ();
 571
 572   while (this_state)
 573     {
 574       if (trace_flag)
 575         fprintf (stderr, "Processing state %d (reached by %s)\n",
 576                  this_state->number, tags[this_state->accessing_symbol]);
 577       /* Set up ruleset and itemset for the transitions out of this
 578          state.  ruleset gets a 1 bit for each rule that could reduce
 579          now.  itemset gets a vector of all the items that could be
 580          accepted next.  */
 581       closure (this_state->items, this_state->nitems);
 582       /* record the reductions allowed out of this state */
 583       save_reductions ();
 584       /* find the itemsets of the states that shifts can reach */
 585       new_itemsets ();
 586       /* find or create the core structures for those states */
 587       append_states ();
 588
 589       /* create the shifts structures for the shifts to those states,
 590          now that the state numbers transitioning to are known */
 591       save_shifts ();
 592
 593       /* states are queued when they are created; process them all */
 594       this_state = this_state->next;
 595     }
 596
 597   /* discard various storage */
 598   free_closure ();
 599   free_storage ();
 600
 601   /* set up initial and final states as parser wants them */
 602   augment_automaton ();
 603
 604   /* Set up STATE_TABLE. */
 605   set_state_table ();
 606 }