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