src/LR0.c

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