src/LR0.c

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