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