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   short *isp1;
 200   short *isp2;
 201   short *iend;
 202
 203 #if TRACE
 204   fprintf (stderr, "Entering new_state, symbol = %d, state = %d\n",
 205            symbol, nstates);
 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 = CORE_ALLOC (n);
 216   p->accessing_symbol = symbol;
 217   p->number = nstates;
 218   p->nitems = n;
 219
 220   isp2 = p->items;
 221   while (isp1 < iend)
 222     *isp2++ = *isp1++;
 223
 224   last_state->next = p;
 225   last_state = p;
 226
 227   nstates++;
 228
 229   return p;
 230 }
 231
 232
 233 /*--------------------------------------------------------------.
 234 | Find the state number for the state we would get to (from the |
 235 | current state) by shifting symbol.  Create a new state if no  |
 236 | equivalent one exists already.  Used by append_states.         |
 237 `--------------------------------------------------------------*/
 238
 239 static int
 240 get_state (int symbol)
 241 {
 242   int key;
 243   short *isp1;
 244   short *isp2;
 245   short *iend;
 246   core *sp;
 247   int found;
 248
 249   int n;
 250
 251 #if TRACE
 252   fprintf (stderr, "Entering get_state, symbol = %d\n", symbol);
 253 #endif
 254
 255   isp1 = kernel_base[symbol];
 256   iend = kernel_end[symbol];
 257   n = iend - isp1;
 258
 259   /* add up the target state's active item numbers to get a hash key */
 260   key = 0;
 261   while (isp1 < iend)
 262     key += *isp1++;
 263
 264   key = key % STATE_TABLE_SIZE;
 265
 266   sp = state_table[key];
 267
 268   if (sp)
 269     {
 270       found = 0;
 271       while (!found)
 272         {
 273           if (sp->nitems == n)
 274             {
 275               found = 1;
 276               isp1 = kernel_base[symbol];
 277               isp2 = sp->items;
 278
 279               while (found && isp1 < iend)
 280                 {
 281                   if (*isp1++ != *isp2++)
 282                     found = 0;
 283                 }
 284             }
 285
 286           if (!found)
 287             {
 288               if (sp->link)
 289                 {
 290                   sp = sp->link;
 291                 }
 292               else              /* bucket exhausted and no match */
 293                 {
 294                   sp = sp->link = new_state (symbol);
 295                   found = 1;
 296                 }
 297             }
 298         }
 299     }
 300   else                          /* bucket is empty */
 301     {
 302       state_table[key] = sp = new_state (symbol);
 303     }
 304
 305   return sp->number;
 306 }
 307
 308 /*------------------------------------------------------------------.
 309 | Use the information computed by new_itemsets to find the state    |
 310 | numbers reached by each shift transition from the current state.  |
 311 |                                                                   |
 312 | shiftset is set up as a vector of state numbers of those states.  |
 313 `------------------------------------------------------------------*/
 314
 315 static void
 316 append_states (void)
 317 {
 318   int i;
 319   int j;
 320   int symbol;
 321
 322 #if TRACE
 323   fprintf (stderr, "Entering append_states\n");
 324 #endif
 325
 326   /* first sort shift_symbol into increasing order */
 327
 328   for (i = 1; i < nshifts; i++)
 329     {
 330       symbol = shift_symbol[i];
 331       j = i;
 332       while (j > 0 && shift_symbol[j - 1] > symbol)
 333         {
 334           shift_symbol[j] = shift_symbol[j - 1];
 335           j--;
 336         }
 337       shift_symbol[j] = symbol;
 338     }
 339
 340   for (i = 0; i < nshifts; i++)
 341     {
 342       symbol = shift_symbol[i];
 343       shiftset[i] = get_state (symbol);
 344     }
 345 }
 346
 347
 348 static void
 349 new_states (void)
 350 {
 351   core *p;
 352
 353   p = CORE_ALLOC (0);
 354   first_state = last_state = this_state = p;
 355   nstates = 1;
 356 }
 357
 358
 359 static void
 360 save_shifts (void)
 361 {
 362   shifts *p;
 363   short *sp1;
 364   short *sp2;
 365   short *send;
 366
 367   p = SHIFTS_ALLOC (nshifts);
 368
 369   p->number = this_state->number;
 370   p->nshifts = nshifts;
 371
 372   sp1 = shiftset;
 373   sp2 = p->shifts;
 374   send = shiftset + nshifts;
 375
 376   while (sp1 < send)
 377     *sp2++ = *sp1++;
 378
 379   if (last_shift)
 380     {
 381       last_shift->next = p;
 382       last_shift = p;
 383     }
 384   else
 385     {
 386       first_shift = p;
 387       last_shift = p;
 388     }
 389 }
 390
 391
 392 /*------------------------------------------------------------------.
 393 | Subroutine of augment_automaton.  Create the next-to-final state, |
 394 | to which a shift has already been made in the initial state.      |
 395 `------------------------------------------------------------------*/
 396
 397 static void
 398 insert_start_shift (void)
 399 {
 400   core *statep;
 401   shifts *sp;
 402
 403   statep = CORE_ALLOC (0);
 404   statep->number = nstates;
 405   statep->accessing_symbol = start_symbol;
 406
 407   last_state->next = statep;
 408   last_state = statep;
 409
 410   /* Make a shift from this state to (what will be) the final state.  */
 411   sp = SHIFTS_ALLOC (1);
 412   sp->number = nstates++;
 413   sp->nshifts = 1;
 414   sp->shifts[0] = nstates;
 415
 416   last_shift->next = sp;
 417   last_shift = sp;
 418 }
 419
 420
 421 /*------------------------------------------------------------------.
 422 | Make sure that the initial state has a shift that accepts the     |
 423 | grammar's start symbol and goes to the next-to-final state, which |
 424 | has a shift going to the final state, which has a shift to the    |
 425 | termination state.  Create such states and shifts if they don't   |
 426 | happen to exist already.                                          |
 427 `------------------------------------------------------------------*/
 428
 429 static void
 430 augment_automaton (void)
 431 {
 432   int i;
 433   int k;
 434   core *statep;
 435   shifts *sp;
 436   shifts *sp2;
 437   shifts *sp1 = NULL;
 438
 439   sp = first_shift;
 440
 441   if (sp)
 442     {
 443       if (sp->number == 0)
 444         {
 445           k = sp->nshifts;
 446           statep = first_state->next;
 447
 448           /* The states reached by shifts from first_state are numbered 1...K.
 449              Look for one reached by start_symbol.  */
 450           while (statep->accessing_symbol < start_symbol
 451                  && statep->number < k)
 452             statep = statep->next;
 453
 454           if (statep->accessing_symbol == start_symbol)
 455             {
 456               /* We already have a next-to-final state.
 457                  Make sure it has a shift to what will be the final state.  */
 458               k = statep->number;
 459
 460               while (sp && sp->number < k)
 461                 {
 462                   sp1 = sp;
 463                   sp = sp->next;
 464                 }
 465
 466               if (sp && sp->number == k)
 467                 {
 468                   sp2 = SHIFTS_ALLOC (sp->nshifts + 1);
 469                   sp2->number = k;
 470                   sp2->nshifts = sp->nshifts + 1;
 471                   sp2->shifts[0] = nstates;
 472                   for (i = sp->nshifts; i > 0; i--)
 473                     sp2->shifts[i] = sp->shifts[i - 1];
 474
 475                   /* Patch sp2 into the chain of shifts in place of sp,
 476                      following sp1.  */
 477                   sp2->next = sp->next;
 478                   sp1->next = sp2;
 479                   if (sp == last_shift)
 480                     last_shift = sp2;
 481                   XFREE (sp);
 482                 }
 483               else
 484                 {
 485                   sp2 = SHIFTS_ALLOC (1);
 486                   sp2->number = k;
 487                   sp2->nshifts = 1;
 488                   sp2->shifts[0] = nstates;
 489
 490                   /* Patch sp2 into the chain of shifts between sp1 and sp.  */
 491                   sp2->next = sp;
 492                   sp1->next = sp2;
 493                   if (sp == 0)
 494                     last_shift = sp2;
 495                 }
 496             }
 497           else
 498             {
 499               /* There is no next-to-final state as yet.  */
 500               /* Add one more shift in first_shift,
 501                  going to the next-to-final state (yet to be made).  */
 502               sp = first_shift;
 503
 504               sp2 = SHIFTS_ALLOC (sp->nshifts + 1);
 505               sp2->nshifts = sp->nshifts + 1;
 506
 507               /* Stick this shift into the vector at the proper place.  */
 508               statep = first_state->next;
 509               for (k = 0, i = 0; i < sp->nshifts; k++, i++)
 510                 {
 511                   if (statep->accessing_symbol > start_symbol && i == k)
 512                     sp2->shifts[k++] = nstates;
 513                   sp2->shifts[k] = sp->shifts[i];
 514                   statep = statep->next;
 515                 }
 516               if (i == k)
 517                 sp2->shifts[k++] = nstates;
 518
 519               /* Patch sp2 into the chain of shifts
 520                  in place of sp, at the beginning.  */
 521               sp2->next = sp->next;
 522               first_shift = sp2;
 523               if (last_shift == sp)
 524                 last_shift = sp2;
 525
 526               XFREE (sp);
 527
 528               /* Create the next-to-final state, with shift to
 529                  what will be the final state.  */
 530               insert_start_shift ();
 531             }
 532         }
 533       else
 534         {
 535           /* The initial state didn't even have any shifts.
 536              Give it one shift, to the next-to-final state.  */
 537           sp = SHIFTS_ALLOC (1);
 538           sp->nshifts = 1;
 539           sp->shifts[0] = nstates;
 540
 541           /* Patch sp into the chain of shifts at the beginning.  */
 542           sp->next = first_shift;
 543           first_shift = sp;
 544
 545           /* Create the next-to-final state, with shift to
 546              what will be the final state.  */
 547           insert_start_shift ();
 548         }
 549     }
 550   else
 551     {
 552       /* There are no shifts for any state.
 553          Make one shift, from the initial state to the next-to-final state.  */
 554
 555       sp = SHIFTS_ALLOC (1);
 556       sp->nshifts = 1;
 557       sp->shifts[0] = nstates;
 558
 559       /* Initialize the chain of shifts with sp.  */
 560       first_shift = sp;
 561       last_shift = sp;
 562
 563       /* Create the next-to-final state, with shift to
 564          what will be the final state.  */
 565       insert_start_shift ();
 566     }
 567
 568   /* Make the final state--the one that follows a shift from the
 569      next-to-final state.
 570      The symbol for that shift is 0 (end-of-file).  */
 571   statep = CORE_ALLOC (0);
 572   statep->number = nstates;
 573   last_state->next = statep;
 574   last_state = statep;
 575
 576   /* Make the shift from the final state to the termination state.  */
 577   sp = SHIFTS_ALLOC (1);
 578   sp->number = nstates++;
 579   sp->nshifts = 1;
 580   sp->shifts[0] = nstates;
 581   last_shift->next = sp;
 582   last_shift = sp;
 583
 584   /* Note that the variable `final_state' refers to what we sometimes call
 585      the termination state.  */
 586   final_state = nstates;
 587
 588   /* Make the termination state.  */
 589   statep = CORE_ALLOC (0);
 590   statep->number = nstates++;
 591   last_state->next = statep;
 592   last_state = statep;
 593 }
 594
 595
 596 /*----------------------------------------------------------------.
 597 | Find which rules can be used for reduction transitions from the |
 598 | current state and make a reductions structure for the state to  |
 599 | record their rule numbers.                                      |
 600 `----------------------------------------------------------------*/
 601
 602 static void
 603 save_reductions (void)
 604 {
 605   short *isp;
 606   short *rp1;
 607   short *rp2;
 608   int item;
 609   int count;
 610   reductions *p;
 611
 612   short *rend;
 613
 614   /* Find and count the active items that represent ends of rules. */
 615
 616   count = 0;
 617   for (isp = itemset; isp < itemsetend; isp++)
 618     {
 619       item = ritem[*isp];
 620       if (item < 0)
 621         redset[count++] = -item;
 622     }
 623
 624   /* Make a reductions structure and copy the data into it.  */
 625
 626   if (count)
 627     {
 628       p = REDUCTIONS_ALLOC (count);
 629
 630       p->number = this_state->number;
 631       p->nreds = count;
 632
 633       rp1 = redset;
 634       rp2 = p->rules;
 635       rend = rp1 + count;
 636
 637       for (/* nothing */; rp1 < rend; ++rp1, ++rp2)
 638         *rp2 = *rp1;
 639
 640       if (last_reduction)
 641         {
 642           last_reduction->next = p;
 643           last_reduction = p;
 644         }
 645       else
 646         {
 647           first_reduction = p;
 648           last_reduction = p;
 649         }
 650     }
 651 }
 652
 653 \f
 654 /*-------------------------------------------------------------------.
 655 | Compute the nondeterministic finite state machine (see state.h for |
 656 | details) from the grammar.                                         |
 657 `-------------------------------------------------------------------*/
 658
 659 void
 660 generate_states (void)
 661 {
 662   allocate_storage ();
 663   new_closure (nitems);
 664   new_states ();
 665
 666   while (this_state)
 667     {
 668       /* Set up ruleset and itemset for the transitions out of this
 669          state.  ruleset gets a 1 bit for each rule that could reduce
 670          now.  itemset gets a vector of all the items that could be
 671          accepted next.  */
 672       closure (this_state->items, this_state->nitems);
 673       /* record the reductions allowed out of this state */
 674       save_reductions ();
 675       /* find the itemsets of the states that shifts can reach */
 676       new_itemsets ();
 677       /* find or create the core structures for those states */
 678       append_states ();
 679
 680       /* create the shifts structures for the shifts to those states,
 681          now that the state numbers transitioning to are known */
 682       if (nshifts > 0)
 683         save_shifts ();
 684
 685       /* states are queued when they are created; process them all */
 686       this_state = this_state->next;
 687     }
 688
 689   /* discard various storage */
 690   free_closure ();
 691   free_storage ();
 692
 693   /* set up initial and final states as parser wants them */
 694   augment_automaton ();
 695 }