src/LR0.c

   1 /* Generate the nondeterministic finite state machine for bison,
   2    Copyright (C) 1984, 1986, 1989 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 "alloc.h"
  27 #include "gram.h"
  28 #include "state.h"
  29 #include "complain.h"
  30 #include "closure.h"
  31
  32 extern char *nullable;
  33 extern short *itemset;
  34 extern short *itemsetend;
  35
  36
  37 int nstates;
  38 int final_state;
  39 core *first_state;
  40 shifts *first_shift;
  41 reductions *first_reduction;
  42
  43 extern void generate_states PARAMS ((void));
  44
  45 static core *this_state;
  46 static core *last_state;
  47 static shifts *last_shift;
  48 static reductions *last_reduction;
  49
  50 static int nshifts;
  51 static short *shift_symbol;
  52
  53 static short *redset;
  54 static short *shiftset;
  55
  56 static short **kernel_base;
  57 static short **kernel_end;
  58 static short *kernel_items;
  59
  60 /* hash table for states, to recognize equivalent ones.  */
  61
  62 #define STATE_TABLE_SIZE        1009
  63 static core **state_table;
  64
  65 \f
  66 static void
  67 allocate_itemsets (void)
  68 {
  69   short *itemp;
  70   int symbol;
  71   int i;
  72   int count;
  73   short *symbol_count;
  74
  75   count = 0;
  76   symbol_count = NEW2 (nsyms, short);
  77
  78   itemp = ritem;
  79   symbol = *itemp++;
  80   while (symbol)
  81     {
  82       if (symbol > 0)
  83         {
  84           count++;
  85           symbol_count[symbol]++;
  86         }
  87       symbol = *itemp++;
  88     }
  89
  90   /* See comments before new_itemsets.  All the vectors of items
  91      live inside KERNEL_ITEMS.  The number of active items after
  92      some symbol cannot be more than the number of times that symbol
  93      appears as an item, which is symbol_count[symbol].
  94      We allocate that much space for each symbol.  */
  95
  96   kernel_base = NEW2 (nsyms, short *);
  97   kernel_items = NEW2 (count, short);
  98
  99   count = 0;
 100   for (i = 0; i < nsyms; i++)
 101     {
 102       kernel_base[i] = kernel_items + count;
 103       count += symbol_count[i];
 104     }
 105
 106   shift_symbol = symbol_count;
 107   kernel_end = NEW2 (nsyms, short *);
 108 }
 109
 110
 111 static void
 112 allocate_storage (void)
 113 {
 114   allocate_itemsets ();
 115
 116   shiftset = NEW2 (nsyms, short);
 117   redset = NEW2 (nrules + 1, short);
 118   state_table = NEW2 (STATE_TABLE_SIZE, core *);
 119 }
 120
 121
 122 static void
 123 free_storage (void)
 124 {
 125   FREE (shift_symbol);
 126   FREE (redset);
 127   FREE (shiftset);
 128   FREE (kernel_base);
 129   FREE (kernel_end);
 130   FREE (kernel_items);
 131   FREE (state_table);
 132 }
 133
 134
 135
 136
 137 /*----------------------------------------------------------------.
 138 | Find which symbols can be shifted in the current state, and for |
 139 | each one record which items would be active after that shift.   |
 140 | Uses the contents of itemset.                                   |
 141 |                                                                 |
 142 | shift_symbol is set to a vector of the symbols that can be      |
 143 | shifted.  For each symbol in the grammar, kernel_base[symbol]   |
 144 | points to a vector of item numbers activated if that symbol is  |
 145 | shifted, and kernel_end[symbol] points after the end of that    |
 146 | vector.                                                         |
 147 `----------------------------------------------------------------*/
 148
 149 static void
 150 new_itemsets (void)
 151 {
 152   int i;
 153   int shiftcount;
 154   short *isp;
 155   short *ksp;
 156   int symbol;
 157
 158 #if TRACE
 159   fprintf (stderr, "Entering new_itemsets\n");
 160 #endif
 161
 162   for (i = 0; i < nsyms; i++)
 163     kernel_end[i] = NULL;
 164
 165   shiftcount = 0;
 166
 167   isp = itemset;
 168
 169   while (isp < itemsetend)
 170     {
 171       i = *isp++;
 172       symbol = ritem[i];
 173       if (symbol > 0)
 174         {
 175           ksp = kernel_end[symbol];
 176
 177           if (!ksp)
 178             {
 179               shift_symbol[shiftcount++] = symbol;
 180               ksp = kernel_base[symbol];
 181             }
 182
 183           *ksp++ = i + 1;
 184           kernel_end[symbol] = ksp;
 185         }
 186     }
 187
 188   nshifts = shiftcount;
 189 }
 190
 191
 192
 193 /*-----------------------------------------------------------------.
 194 | Subroutine of get_state.  Create a new state for those items, if |
 195 | necessary.                                                       |
 196 `-----------------------------------------------------------------*/
 197
 198 static core *
 199 new_state (int symbol)
 200 {
 201   int n;
 202   core *p;
 203   short *isp1;
 204   short *isp2;
 205   short *iend;
 206
 207 #if TRACE
 208   fprintf (stderr, "Entering new_state, symbol = %d\n", symbol);
 209 #endif
 210
 211   if (nstates >= MAXSHORT)
 212     fatal (_("too many states (max %d)"), MAXSHORT);
 213
 214   isp1 = kernel_base[symbol];
 215   iend = kernel_end[symbol];
 216   n = iend - isp1;
 217
 218   p =
 219     (core *) xmalloc ((unsigned) (sizeof (core) + (n - 1) * sizeof (short)));
 220   p->accessing_symbol = symbol;
 221   p->number = nstates;
 222   p->nitems = n;
 223
 224   isp2 = p->items;
 225   while (isp1 < iend)
 226     *isp2++ = *isp1++;
 227
 228   last_state->next = p;
 229   last_state = p;
 230
 231   nstates++;
 232
 233   return p;
 234 }
 235
 236
 237 /*--------------------------------------------------------------.
 238 | Find the state number for the state we would get to (from the |
 239 | current state) by shifting symbol.  Create a new state if no  |
 240 | equivalent one exists already.  Used by append_states.         |
 241 `--------------------------------------------------------------*/
 242
 243 static int
 244 get_state (int symbol)
 245 {
 246   int key;
 247   short *isp1;
 248   short *isp2;
 249   short *iend;
 250   core *sp;
 251   int found;
 252
 253   int n;
 254
 255 #if TRACE
 256   fprintf (stderr, "Entering get_state, symbol = %d\n", symbol);
 257 #endif
 258
 259   isp1 = kernel_base[symbol];
 260   iend = kernel_end[symbol];
 261   n = iend - isp1;
 262
 263   /* add up the target state's active item numbers to get a hash key */
 264   key = 0;
 265   while (isp1 < iend)
 266     key += *isp1++;
 267
 268   key = key % STATE_TABLE_SIZE;
 269
 270   sp = state_table[key];
 271
 272   if (sp)
 273     {
 274       found = 0;
 275       while (!found)
 276         {
 277           if (sp->nitems == n)
 278             {
 279               found = 1;
 280               isp1 = kernel_base[symbol];
 281               isp2 = sp->items;
 282
 283               while (found && isp1 < iend)
 284                 {
 285                   if (*isp1++ != *isp2++)
 286                     found = 0;
 287                 }
 288             }
 289
 290           if (!found)
 291             {
 292               if (sp->link)
 293                 {
 294                   sp = sp->link;
 295                 }
 296               else              /* bucket exhausted and no match */
 297                 {
 298                   sp = sp->link = new_state (symbol);
 299                   found = 1;
 300                 }
 301             }
 302         }
 303     }
 304   else                          /* bucket is empty */
 305     {
 306       state_table[key] = sp = new_state (symbol);
 307     }
 308
 309   return sp->number;
 310 }
 311
 312 /*------------------------------------------------------------------.
 313 | Use the information computed by new_itemsets to find the state    |
 314 | numbers reached by each shift transition from the current state.  |
 315 |                                                                   |
 316 | shiftset is set up as a vector of state numbers of those states.  |
 317 `------------------------------------------------------------------*/
 318
 319 static void
 320 append_states (void)
 321 {
 322   int i;
 323   int j;
 324   int symbol;
 325
 326 #if TRACE
 327   fprintf (stderr, "Entering append_states\n");
 328 #endif
 329
 330   /* first sort shift_symbol into increasing order */
 331
 332   for (i = 1; i < nshifts; i++)
 333     {
 334       symbol = shift_symbol[i];
 335       j = i;
 336       while (j > 0 && shift_symbol[j - 1] > symbol)
 337         {
 338           shift_symbol[j] = shift_symbol[j - 1];
 339           j--;
 340         }
 341       shift_symbol[j] = symbol;
 342     }
 343
 344   for (i = 0; i < nshifts; i++)
 345     {
 346       symbol = shift_symbol[i];
 347       shiftset[i] = get_state (symbol);
 348     }
 349 }
 350
 351
 352 static void
 353 new_states (void)
 354 {
 355   core *p;
 356
 357   p = (core *) xmalloc ((unsigned) (sizeof (core) - sizeof (short)));
 358   first_state = last_state = this_state = p;
 359   nstates = 1;
 360 }
 361
 362
 363 static void
 364 save_shifts (void)
 365 {
 366   shifts *p;
 367   short *sp1;
 368   short *sp2;
 369   short *send;
 370
 371   p = (shifts *) xmalloc ((unsigned) (sizeof (shifts) +
 372                                       (nshifts - 1) * sizeof (short)));
 373
 374   p->number = this_state->number;
 375   p->nshifts = nshifts;
 376
 377   sp1 = shiftset;
 378   sp2 = p->shifts;
 379   send = shiftset + nshifts;
 380
 381   while (sp1 < send)
 382     *sp2++ = *sp1++;
 383
 384   if (last_shift)
 385     {
 386       last_shift->next = p;
 387       last_shift = p;
 388     }
 389   else
 390     {
 391       first_shift = p;
 392       last_shift = p;
 393     }
 394 }
 395
 396
 397 /*------------------------------------------------------------------.
 398 | Subroutine of augment_automaton.  Create the next-to-final state, |
 399 | to which a shift has already been made in the initial state.      |
 400 `------------------------------------------------------------------*/
 401
 402 static void
 403 insert_start_shift (void)
 404 {
 405   core *statep;
 406   shifts *sp;
 407
 408   statep = (core *) xmalloc ((unsigned) (sizeof (core) - sizeof (short)));
 409   statep->number = nstates;
 410   statep->accessing_symbol = start_symbol;
 411
 412   last_state->next = statep;
 413   last_state = statep;
 414
 415   /* Make a shift from this state to (what will be) the final state.  */
 416   sp = NEW (shifts);
 417   sp->number = nstates++;
 418   sp->nshifts = 1;
 419   sp->shifts[0] = nstates;
 420
 421   last_shift->next = sp;
 422   last_shift = sp;
 423 }
 424
 425
 426 /*------------------------------------------------------------------.
 427 | Make sure that the initial state has a shift that accepts the     |
 428 | grammar's start symbol and goes to the next-to-final state, which |
 429 | has a shift going to the final state, which has a shift to the    |
 430 | termination state.  Create such states and shifts if they don't   |
 431 | happen to exist already.                                          |
 432 `------------------------------------------------------------------*/
 433
 434 static void
 435 augment_automaton (void)
 436 {
 437   int i;
 438   int k;
 439   core *statep;
 440   shifts *sp;
 441   shifts *sp2;
 442   shifts *sp1 = NULL;
 443
 444   sp = first_shift;
 445
 446   if (sp)
 447     {
 448       if (sp->number == 0)
 449         {
 450           k = sp->nshifts;
 451           statep = first_state->next;
 452
 453           /* The states reached by shifts from first_state are numbered 1...K.
 454              Look for one reached by start_symbol.  */
 455           while (statep->accessing_symbol < start_symbol
 456                  && statep->number < k)
 457             statep = statep->next;
 458
 459           if (statep->accessing_symbol == start_symbol)
 460             {
 461               /* We already have a next-to-final state.
 462                  Make sure it has a shift to what will be the final state.  */
 463               k = statep->number;
 464
 465               while (sp && sp->number < k)
 466                 {
 467                   sp1 = sp;
 468                   sp = sp->next;
 469                 }
 470
 471               if (sp && sp->number == k)
 472                 {
 473                   sp2 = (shifts *) xmalloc ((unsigned) (sizeof (shifts)
 474                                                         +
 475                                                         sp->nshifts *
 476                                                         sizeof (short)));
 477                   sp2->number = k;
 478                   sp2->nshifts = sp->nshifts + 1;
 479                   sp2->shifts[0] = nstates;
 480                   for (i = sp->nshifts; i > 0; i--)
 481                     sp2->shifts[i] = sp->shifts[i - 1];
 482
 483                   /* Patch sp2 into the chain of shifts in place of sp,
 484                      following sp1.  */
 485                   sp2->next = sp->next;
 486                   sp1->next = sp2;
 487                   if (sp == last_shift)
 488                     last_shift = sp2;
 489                   FREE (sp);
 490                 }
 491               else
 492                 {
 493                   sp2 = NEW (shifts);
 494                   sp2->number = k;
 495                   sp2->nshifts = 1;
 496                   sp2->shifts[0] = nstates;
 497
 498                   /* Patch sp2 into the chain of shifts between sp1 and sp.  */
 499                   sp2->next = sp;
 500                   sp1->next = sp2;
 501                   if (sp == 0)
 502                     last_shift = sp2;
 503                 }
 504             }
 505           else
 506             {
 507               /* There is no next-to-final state as yet.  */
 508               /* Add one more shift in first_shift,
 509                  going to the next-to-final state (yet to be made).  */
 510               sp = first_shift;
 511
 512               sp2 = (shifts *) xmalloc (sizeof (shifts)
 513                                         + sp->nshifts * sizeof (short));
 514               sp2->nshifts = sp->nshifts + 1;
 515
 516               /* Stick this shift into the vector at the proper place.  */
 517               statep = first_state->next;
 518               for (k = 0, i = 0; i < sp->nshifts; k++, i++)
 519                 {
 520                   if (statep->accessing_symbol > start_symbol && i == k)
 521                     sp2->shifts[k++] = nstates;
 522                   sp2->shifts[k] = sp->shifts[i];
 523                   statep = statep->next;
 524                 }
 525               if (i == k)
 526                 sp2->shifts[k++] = nstates;
 527
 528               /* Patch sp2 into the chain of shifts
 529                  in place of sp, at the beginning.  */
 530               sp2->next = sp->next;
 531               first_shift = sp2;
 532               if (last_shift == sp)
 533                 last_shift = sp2;
 534
 535               FREE (sp);
 536
 537               /* Create the next-to-final state, with shift to
 538                  what will be the final state.  */
 539               insert_start_shift ();
 540             }
 541         }
 542       else
 543         {
 544           /* The initial state didn't even have any shifts.
 545              Give it one shift, to the next-to-final state.  */
 546           sp = NEW (shifts);
 547           sp->nshifts = 1;
 548           sp->shifts[0] = nstates;
 549
 550           /* Patch sp into the chain of shifts at the beginning.  */
 551           sp->next = first_shift;
 552           first_shift = sp;
 553
 554           /* Create the next-to-final state, with shift to
 555              what will be the final state.  */
 556           insert_start_shift ();
 557         }
 558     }
 559   else
 560     {
 561       /* There are no shifts for any state.
 562          Make one shift, from the initial state to the next-to-final state.  */
 563
 564       sp = NEW (shifts);
 565       sp->nshifts = 1;
 566       sp->shifts[0] = nstates;
 567
 568       /* Initialize the chain of shifts with sp.  */
 569       first_shift = sp;
 570       last_shift = sp;
 571
 572       /* Create the next-to-final state, with shift to
 573          what will be the final state.  */
 574       insert_start_shift ();
 575     }
 576
 577   /* Make the final state--the one that follows a shift from the
 578      next-to-final state.
 579      The symbol for that shift is 0 (end-of-file).  */
 580   statep = (core *) xmalloc ((unsigned) (sizeof (core) - sizeof (short)));
 581   statep->number = nstates;
 582   last_state->next = statep;
 583   last_state = statep;
 584
 585   /* Make the shift from the final state to the termination state.  */
 586   sp = NEW (shifts);
 587   sp->number = nstates++;
 588   sp->nshifts = 1;
 589   sp->shifts[0] = nstates;
 590   last_shift->next = sp;
 591   last_shift = sp;
 592
 593   /* Note that the variable `final_state' refers to what we sometimes call
 594      the termination state.  */
 595   final_state = nstates;
 596
 597   /* Make the termination state.  */
 598   statep = (core *) xmalloc ((unsigned) (sizeof (core) - sizeof (short)));
 599   statep->number = nstates++;
 600   last_state->next = statep;
 601   last_state = statep;
 602 }
 603
 604
 605 /*----------------------------------------------------------------.
 606 | Find which rules can be used for reduction transitions from the |
 607 | current state and make a reductions structure for the state to  |
 608 | record their rule numbers.                                      |
 609 `----------------------------------------------------------------*/
 610
 611 static void
 612 save_reductions (void)
 613 {
 614   short *isp;
 615   short *rp1;
 616   short *rp2;
 617   int item;
 618   int count;
 619   reductions *p;
 620
 621   short *rend;
 622
 623   /* Find and count the active items that represent ends of rules. */
 624
 625   count = 0;
 626   for (isp = itemset; isp < itemsetend; isp++)
 627     {
 628       item = ritem[*isp];
 629       if (item < 0)
 630         redset[count++] = -item;
 631     }
 632
 633   /* Make a reductions structure and copy the data into it.  */
 634
 635   if (count)
 636     {
 637       p = (reductions *) xmalloc ((unsigned) (sizeof (reductions) +
 638                                               (count - 1) * sizeof (short)));
 639
 640       p->number = this_state->number;
 641       p->nreds = count;
 642
 643       rp1 = redset;
 644       rp2 = p->rules;
 645       rend = rp1 + count;
 646
 647       for (/* nothing */; rp1 < rend; ++rp1, ++rp2)
 648         *rp2 = *rp1;
 649
 650       if (last_reduction)
 651         {
 652           last_reduction->next = p;
 653           last_reduction = p;
 654         }
 655       else
 656         {
 657           first_reduction = p;
 658           last_reduction = p;
 659         }
 660     }
 661 }
 662
 663 \f
 664 /*-------------------------------------------------------------------.
 665 | Compute the nondeterministic finite state machine (see state.h for |
 666 | details) from the grammar.                                         |
 667 `-------------------------------------------------------------------*/
 668
 669 void
 670 generate_states (void)
 671 {
 672   allocate_storage ();
 673   new_closure (nitems);
 674   new_states ();
 675
 676   while (this_state)
 677     {
 678       /* Set up ruleset and itemset for the transitions out of this
 679          state.  ruleset gets a 1 bit for each rule that could reduce
 680          now.  itemset gets a vector of all the items that could be
 681          accepted next.  */
 682       closure (this_state->items, this_state->nitems);
 683       /* record the reductions allowed out of this state */
 684       save_reductions ();
 685       /* find the itemsets of the states that shifts can reach */
 686       new_itemsets ();
 687       /* find or create the core structures for those states */
 688       append_states ();
 689
 690       /* create the shifts structures for the shifts to those states,
 691          now that the state numbers transitioning to are known */
 692       if (nshifts > 0)
 693         save_shifts ();
 694
 695       /* states are queued when they are created; process them all */
 696       this_state = this_state->next;
 697     }
 698
 699   /* discard various storage */
 700   free_closure ();
 701   free_storage ();
 702
 703   /* set up initial and final states as parser wants them */
 704   augment_automaton ();
 705 }