usr.bin/yacc/lr0.c

   1 /*
   2  * Copyright (c) 1989 The Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Robert Paul Corbett.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #if 0
  38 #ifndef lint
  39 static char sccsid[] = "@(#)lr0.c       5.3 (Berkeley) 1/20/91";
  40 #endif
  41 #endif
  42
  43 #include <sys/cdefs.h>
  44 __FBSDID("$FreeBSD$");
  45
  46 #include <limits.h>
  47 #include <stdlib.h>
  48 #include "defs.h"
  49
  50 extern short *itemset;
  51 extern short *itemsetend;
  52 extern unsigned *ruleset;
  53
  54 int nstates;
  55 core *first_state;
  56 shifts *first_shift;
  57 reductions *first_reduction;
  58
  59 static void allocate_itemsets(void);
  60 static void allocate_storage(void);
  61 static void append_states(void);
  62 static void free_storage(void);
  63 static void generate_states(void);
  64 static int get_state(int);
  65 static void initialize_states(void);
  66 static void new_itemsets(void);
  67 static core *new_state(int);
  68 #ifdef DEBUG
  69 static void print_derives(void);
  70 #endif
  71 static void save_reductions(void);
  72 static void save_shifts(void);
  73 static void set_derives(void);
  74 static void set_nullable(void);
  75
  76 static core **state_set;
  77 static core *this_state;
  78 static core *last_state;
  79 static shifts *last_shift;
  80 static reductions *last_reduction;
  81
  82 static int nshifts;
  83 static short *shift_symbol;
  84
  85 static short *redset;
  86 static short *shiftset;
  87
  88 static short **kernel_base;
  89 static short **kernel_end;
  90 static short *kernel_items;
  91
  92
  93 static void
  94 allocate_itemsets()
  95 {
  96     short *itemp;
  97     short *item_end;
  98     int symbol;
  99     int i;
 100     int count;
 101     int max;
 102     short *symbol_count;
 103
 104     count = 0;
 105     symbol_count = NEW2(nsyms, short);
 106
 107     item_end = ritem + nitems;
 108     for (itemp = ritem; itemp < item_end; itemp++)
 109     {
 110         symbol = *itemp;
 111         if (symbol >= 0)
 112         {
 113             count++;
 114             symbol_count[symbol]++;
 115         }
 116     }
 117
 118     kernel_base = NEW2(nsyms, short *);
 119     kernel_items = NEW2(count, short);
 120
 121     count = 0;
 122     max = 0;
 123     for (i = 0; i < nsyms; i++)
 124     {
 125         kernel_base[i] = kernel_items + count;
 126         count += symbol_count[i];
 127         if (max < symbol_count[i])
 128             max = symbol_count[i];
 129     }
 130
 131     shift_symbol = symbol_count;
 132     kernel_end = NEW2(nsyms, short *);
 133 }
 134
 135
 136 static void
 137 allocate_storage()
 138 {
 139     allocate_itemsets();
 140     shiftset = NEW2(nsyms, short);
 141     redset = NEW2(nrules + 1, short);
 142     state_set = NEW2(nitems, core *);
 143 }
 144
 145
 146 static void
 147 append_states()
 148 {
 149     int i;
 150     int j;
 151     int symbol;
 152
 153 #ifdef  TRACE
 154     fprintf(stderr, "Entering append_states()\n");
 155 #endif
 156     for (i = 1; i < nshifts; i++)
 157     {
 158         symbol = shift_symbol[i];
 159         j = i;
 160         while (j > 0 && shift_symbol[j - 1] > symbol)
 161         {
 162             shift_symbol[j] = shift_symbol[j - 1];
 163             j--;
 164         }
 165         shift_symbol[j] = symbol;
 166     }
 167
 168     for (i = 0; i < nshifts; i++)
 169     {
 170         symbol = shift_symbol[i];
 171         shiftset[i] = get_state(symbol);
 172     }
 173 }
 174
 175
 176 static void
 177 free_storage()
 178 {
 179     FREE(shift_symbol);
 180     FREE(redset);
 181     FREE(shiftset);
 182     FREE(kernel_base);
 183     FREE(kernel_end);
 184     FREE(kernel_items);
 185     FREE(state_set);
 186 }
 187
 188
 189
 190 static void
 191 generate_states()
 192 {
 193     allocate_storage();
 194     itemset = NEW2(nitems, short);
 195     ruleset = NEW2(WORDSIZE(nrules), unsigned);
 196     set_first_derives();
 197     initialize_states();
 198
 199     while (this_state)
 200     {
 201         closure(this_state->items, this_state->nitems);
 202         save_reductions();
 203         new_itemsets();
 204         append_states();
 205
 206         if (nshifts > 0)
 207             save_shifts();
 208
 209         this_state = this_state->next;
 210     }
 211
 212     finalize_closure();
 213     free_storage();
 214 }
 215
 216
 217
 218 static int
 219 get_state(symbol)
 220 int symbol;
 221 {
 222     int key;
 223     short *isp1;
 224     short *isp2;
 225     short *iend;
 226     core *sp;
 227     int found;
 228     int n;
 229
 230 #ifdef  TRACE
 231     fprintf(stderr, "Entering get_state(%d)\n", symbol);
 232 #endif
 233
 234     isp1 = kernel_base[symbol];
 235     iend = kernel_end[symbol];
 236     n = iend - isp1;
 237
 238     key = *isp1;
 239     assert(0 <= key && key < nitems);
 240     sp = state_set[key];
 241     if (sp)
 242     {
 243         found = 0;
 244         while (!found)
 245         {
 246             if (sp->nitems == n)
 247             {
 248                 found = 1;
 249                 isp1 = kernel_base[symbol];
 250                 isp2 = sp->items;
 251
 252                 while (found && isp1 < iend)
 253                 {
 254                     if (*isp1++ != *isp2++)
 255                         found = 0;
 256                 }
 257             }
 258
 259             if (!found)
 260             {
 261                 if (sp->link)
 262                 {
 263                     sp = sp->link;
 264                 }
 265                 else
 266                 {
 267                     sp = sp->link = new_state(symbol);
 268                     found = 1;
 269                 }
 270             }
 271         }
 272     }
 273     else
 274     {
 275         state_set[key] = sp = new_state(symbol);
 276     }
 277
 278     return (sp->number);
 279 }
 280
 281
 282
 283 static void
 284 initialize_states()
 285 {
 286     int i;
 287     short *start_derives;
 288     core *p;
 289
 290     start_derives = derives[start_symbol];
 291     for (i = 0; start_derives[i] >= 0; ++i)
 292         continue;
 293
 294     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
 295     if (p == 0) no_space();
 296
 297     p->next = 0;
 298     p->link = 0;
 299     p->number = 0;
 300     p->accessing_symbol = 0;
 301     p->nitems = i;
 302
 303     for (i = 0;  start_derives[i] >= 0; ++i)
 304         p->items[i] = rrhs[start_derives[i]];
 305
 306     first_state = last_state = this_state = p;
 307     nstates = 1;
 308 }
 309
 310
 311 static void
 312 new_itemsets()
 313 {
 314     int i;
 315     int shiftcount;
 316     short *isp;
 317     short *ksp;
 318     int symbol;
 319
 320     for (i = 0; i < nsyms; i++)
 321         kernel_end[i] = 0;
 322
 323     shiftcount = 0;
 324     isp = itemset;
 325     while (isp < itemsetend)
 326     {
 327         i = *isp++;
 328         symbol = ritem[i];
 329         if (symbol > 0)
 330         {
 331             ksp = kernel_end[symbol];
 332             if (!ksp)
 333             {
 334                 shift_symbol[shiftcount++] = symbol;
 335                 ksp = kernel_base[symbol];
 336             }
 337
 338             *ksp++ = i + 1;
 339             kernel_end[symbol] = ksp;
 340         }
 341     }
 342
 343     nshifts = shiftcount;
 344 }
 345
 346
 347
 348 static core *
 349 new_state(symbol)
 350 int symbol;
 351 {
 352     int n;
 353     core *p;
 354     short *isp1;
 355     short *isp2;
 356     short *iend;
 357
 358 #ifdef  TRACE
 359     fprintf(stderr, "Entering new_state(%d)\n", symbol);
 360 #endif
 361
 362     if (nstates >= SHRT_MAX)
 363         fatal("too many states");
 364
 365     isp1 = kernel_base[symbol];
 366     iend = kernel_end[symbol];
 367     n = iend - isp1;
 368
 369     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
 370     p->accessing_symbol = symbol;
 371     p->number = nstates;
 372     p->nitems = n;
 373
 374     isp2 = p->items;
 375     while (isp1 < iend)
 376         *isp2++ = *isp1++;
 377
 378     last_state->next = p;
 379     last_state = p;
 380
 381     nstates++;
 382
 383     return (p);
 384 }
 385
 386
 387 #if 0
 388 /* show_cores is used for debugging */
 389
 390 show_cores()
 391 {
 392     core *p;
 393     int i, j, k, n;
 394     int itemno;
 395
 396     k = 0;
 397     for (p = first_state; p; ++k, p = p->next)
 398     {
 399         if (k) printf("\n");
 400         printf("state %d, number = %d, accessing symbol = %s\n",
 401                 k, p->number, symbol_name[p->accessing_symbol]);
 402         n = p->nitems;
 403         for (i = 0; i < n; ++i)
 404         {
 405             itemno = p->items[i];
 406             printf("%4d  ", itemno);
 407             j = itemno;
 408             while (ritem[j] >= 0) ++j;
 409             printf("%s :", symbol_name[rlhs[-ritem[j]]]);
 410             j = rrhs[-ritem[j]];
 411             while (j < itemno)
 412                 printf(" %s", symbol_name[ritem[j++]]);
 413             printf(" .");
 414             while (ritem[j] >= 0)
 415                 printf(" %s", symbol_name[ritem[j++]]);
 416             printf("\n");
 417             fflush(stdout);
 418         }
 419     }
 420 }
 421
 422
 423 /* show_ritems is used for debugging */
 424
 425 show_ritems()
 426 {
 427     int i;
 428
 429     for (i = 0; i < nitems; ++i)
 430         printf("ritem[%d] = %d\n", i, ritem[i]);
 431 }
 432
 433
 434 /* show_rrhs is used for debugging */
 435 show_rrhs()
 436 {
 437     int i;
 438
 439     for (i = 0; i < nrules; ++i)
 440         printf("rrhs[%d] = %d\n", i, rrhs[i]);
 441 }
 442
 443
 444 /* show_shifts is used for debugging */
 445
 446 show_shifts()
 447 {
 448     shifts *p;
 449     int i, j, k;
 450
 451     k = 0;
 452     for (p = first_shift; p; ++k, p = p->next)
 453     {
 454         if (k) printf("\n");
 455         printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
 456                 p->nshifts);
 457         j = p->nshifts;
 458         for (i = 0; i < j; ++i)
 459             printf("\t%d\n", p->shift[i]);
 460     }
 461 }
 462 #endif
 463
 464
 465 static void
 466 save_shifts()
 467 {
 468     shifts *p;
 469     short *sp1;
 470     short *sp2;
 471     short *send;
 472
 473     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
 474                         (nshifts - 1) * sizeof(short)));
 475
 476     p->number = this_state->number;
 477     p->nshifts = nshifts;
 478
 479     sp1 = shiftset;
 480     sp2 = p->shift;
 481     send = shiftset + nshifts;
 482
 483     while (sp1 < send)
 484         *sp2++ = *sp1++;
 485
 486     if (last_shift)
 487     {
 488         last_shift->next = p;
 489         last_shift = p;
 490     }
 491     else
 492     {
 493         first_shift = p;
 494         last_shift = p;
 495     }
 496 }
 497
 498
 499
 500 static void
 501 save_reductions()
 502 {
 503     short *isp;
 504     short *rp1;
 505     short *rp2;
 506     int item;
 507     int count;
 508     reductions *p;
 509     short *rend;
 510
 511     count = 0;
 512     for (isp = itemset; isp < itemsetend; isp++)
 513     {
 514         item = ritem[*isp];
 515         if (item < 0)
 516         {
 517             redset[count++] = -item;
 518         }
 519     }
 520
 521     if (count)
 522     {
 523         p = (reductions *) allocate((unsigned) (sizeof(reductions) +
 524                                         (count - 1) * sizeof(short)));
 525
 526         p->number = this_state->number;
 527         p->nreds = count;
 528
 529         rp1 = redset;
 530         rp2 = p->rules;
 531         rend = rp1 + count;
 532
 533         while (rp1 < rend)
 534             *rp2++ = *rp1++;
 535
 536         if (last_reduction)
 537         {
 538             last_reduction->next = p;
 539             last_reduction = p;
 540         }
 541         else
 542         {
 543             first_reduction = p;
 544             last_reduction = p;
 545         }
 546     }
 547 }
 548
 549
 550 static void
 551 set_derives()
 552 {
 553     int i, k;
 554     int lhs;
 555     short *rules;
 556
 557     derives = NEW2(nsyms, short *);
 558     rules = NEW2(nvars + nrules, short);
 559
 560     k = 0;
 561     for (lhs = start_symbol; lhs < nsyms; lhs++)
 562     {
 563         derives[lhs] = rules + k;
 564         for (i = 0; i < nrules; i++)
 565         {
 566             if (rlhs[i] == lhs)
 567             {
 568                 rules[k] = i;
 569                 k++;
 570             }
 571         }
 572         rules[k] = -1;
 573         k++;
 574     }
 575
 576 #ifdef  DEBUG
 577     print_derives();
 578 #endif
 579 }
 580
 581 #if 0
 582 free_derives()
 583 {
 584     FREE(derives[start_symbol]);
 585     FREE(derives);
 586 }
 587 #endif
 588
 589 #ifdef  DEBUG
 590 static void
 591 print_derives()
 592 {
 593     int i;
 594     short *sp;
 595
 596     printf("\nDERIVES\n\n");
 597
 598     for (i = start_symbol; i < nsyms; i++)
 599     {
 600         printf("%s derives ", symbol_name[i]);
 601         for (sp = derives[i]; *sp >= 0; sp++)
 602         {
 603             printf("  %d", *sp);
 604         }
 605         putchar('\n');
 606     }
 607
 608     putchar('\n');
 609 }
 610 #endif
 611
 612
 613 static void
 614 set_nullable()
 615 {
 616     int i, j;
 617     int empty;
 618     int done1;
 619
 620     nullable = MALLOC(nsyms);
 621     if (nullable == 0) no_space();
 622
 623     for (i = 0; i < nsyms; ++i)
 624         nullable[i] = 0;
 625
 626     done1 = 0;
 627     while (!done1)
 628     {
 629         done1 = 1;
 630         for (i = 1; i < nitems; i++)
 631         {
 632             empty = 1;
 633             while ((j = ritem[i]) >= 0)
 634             {
 635                 if (!nullable[j])
 636                     empty = 0;
 637                 ++i;
 638             }
 639             if (empty)
 640             {
 641                 j = rlhs[-j];
 642                 if (!nullable[j])
 643                 {
 644                     nullable[j] = 1;
 645                     done1 = 0;
 646                 }
 647             }
 648         }
 649     }
 650
 651 #ifdef DEBUG
 652     for (i = 0; i < nsyms; i++)
 653     {
 654         if (nullable[i])
 655             printf("%s is nullable\n", symbol_name[i]);
 656         else
 657             printf("%s is not nullable\n", symbol_name[i]);
 658     }
 659 #endif
 660 }
 661
 662
 663 #if 0
 664 free_nullable()
 665 {
 666     FREE(nullable);
 667 }
 668 #endif
 669
 670
 671 void
 672 lr0()
 673 {
 674     set_derives();
 675     set_nullable();
 676     generate_states();
 677 }