src/LR0.c

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