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