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