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