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