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  * $FreeBSD: src/usr.bin/yacc/lr0.c,v 1.6 1999/08/28 01:08:00 peter Exp $
  37  */
  38
  39 #ifndef lint
  40 static char const sccsid[] = "@(#)lr0.c 5.3 (Berkeley) 1/20/91";
  41 #endif /* not lint */
  42
  43 #include <stdlib.h>
  44 #include "defs.h"
  45
  46 extern short *itemset;
  47 extern short *itemsetend;
  48 extern unsigned *ruleset;
  49
  50 int nstates;
  51 core *first_state;
  52 shifts *first_shift;
  53 reductions *first_reduction;
  54
  55 static void allocate_itemsets __P((void));
  56 static void allocate_storage __P((void));
  57 static void append_states __P((void));
  58 static void free_storage __P((void));
  59 static void generate_states __P((void));
  60 static int get_state __P((int));
  61 static void initialize_states __P((void));
  62 static void new_itemsets __P((void));
  63 static core *new_state __P((int));
  64 #ifdef DEBUG
  65 static void print_derives __P((void));
  66 #endif
  67 static void save_reductions __P((void));
  68 static void save_shifts __P((void));
  69 static void set_derives __P((void));
  70 static void set_nullable __P((void));
  71
  72 static core **state_set;
  73 static core *this_state;
  74 static core *last_state;
  75 static shifts *last_shift;
  76 static reductions *last_reduction;
  77
  78 static int nshifts;
  79 static short *shift_symbol;
  80
  81 static short *redset;
  82 static short *shiftset;
  83
  84 static short **kernel_base;
  85 static short **kernel_end;
  86 static short *kernel_items;
  87
  88
  89 static void
  90 allocate_itemsets()
  91 {
  92     register short *itemp;
  93     register short *item_end;
  94     register int symbol;
  95     register int i;
  96     register int count;
  97     register int max;
  98     register short *symbol_count;
  99
 100     count = 0;
 101     symbol_count = NEW2(nsyms, short);
 102
 103     item_end = ritem + nitems;
 104     for (itemp = ritem; itemp < item_end; itemp++)
 105     {
 106         symbol = *itemp;
 107         if (symbol >= 0)
 108         {
 109             count++;
 110             symbol_count[symbol]++;
 111         }
 112     }
 113
 114     kernel_base = NEW2(nsyms, short *);
 115     kernel_items = NEW2(count, short);
 116
 117     count = 0;
 118     max = 0;
 119     for (i = 0; i < nsyms; i++)
 120     {
 121         kernel_base[i] = kernel_items + count;
 122         count += symbol_count[i];
 123         if (max < symbol_count[i])
 124             max = symbol_count[i];
 125     }
 126
 127     shift_symbol = symbol_count;
 128     kernel_end = NEW2(nsyms, short *);
 129 }
 130
 131
 132 static void
 133 allocate_storage()
 134 {
 135     allocate_itemsets();
 136     shiftset = NEW2(nsyms, short);
 137     redset = NEW2(nrules + 1, short);
 138     state_set = NEW2(nitems, core *);
 139 }
 140
 141
 142 static void
 143 append_states()
 144 {
 145     register int i;
 146     register int j;
 147     register int symbol;
 148
 149 #ifdef  TRACE
 150     fprintf(stderr, "Entering append_states()\n");
 151 #endif
 152     for (i = 1; i < nshifts; i++)
 153     {
 154         symbol = shift_symbol[i];
 155         j = i;
 156         while (j > 0 && shift_symbol[j - 1] > symbol)
 157         {
 158             shift_symbol[j] = shift_symbol[j - 1];
 159             j--;
 160         }
 161         shift_symbol[j] = symbol;
 162     }
 163
 164     for (i = 0; i < nshifts; i++)
 165     {
 166         symbol = shift_symbol[i];
 167         shiftset[i] = get_state(symbol);
 168     }
 169 }
 170
 171
 172 static void
 173 free_storage()
 174 {
 175     FREE(shift_symbol);
 176     FREE(redset);
 177     FREE(shiftset);
 178     FREE(kernel_base);
 179     FREE(kernel_end);
 180     FREE(kernel_items);
 181     FREE(state_set);
 182 }
 183
 184
 185
 186 static void
 187 generate_states()
 188 {
 189     allocate_storage();
 190     itemset = NEW2(nitems, short);
 191     ruleset = NEW2(WORDSIZE(nrules), unsigned);
 192     set_first_derives();
 193     initialize_states();
 194
 195     while (this_state)
 196     {
 197         closure(this_state->items, this_state->nitems);
 198         save_reductions();
 199         new_itemsets();
 200         append_states();
 201
 202         if (nshifts > 0)
 203             save_shifts();
 204
 205         this_state = this_state->next;
 206     }
 207
 208     finalize_closure();
 209     free_storage();
 210 }
 211
 212
 213
 214 static int
 215 get_state(symbol)
 216 int symbol;
 217 {
 218     register int key;
 219     register short *isp1;
 220     register short *isp2;
 221     register short *iend;
 222     register core *sp;
 223     register int found;
 224     register int n;
 225
 226 #ifdef  TRACE
 227     fprintf(stderr, "Entering get_state(%d)\n", symbol);
 228 #endif
 229
 230     isp1 = kernel_base[symbol];
 231     iend = kernel_end[symbol];
 232     n = iend - isp1;
 233
 234     key = *isp1;
 235     assert(0 <= key && key < nitems);
 236     sp = state_set[key];
 237     if (sp)
 238     {
 239         found = 0;
 240         while (!found)
 241         {
 242             if (sp->nitems == n)
 243             {
 244                 found = 1;
 245                 isp1 = kernel_base[symbol];
 246                 isp2 = sp->items;
 247
 248                 while (found && isp1 < iend)
 249                 {
 250                     if (*isp1++ != *isp2++)
 251                         found = 0;
 252                 }
 253             }
 254
 255             if (!found)
 256             {
 257                 if (sp->link)
 258                 {
 259                     sp = sp->link;
 260                 }
 261                 else
 262                 {
 263                     sp = sp->link = new_state(symbol);
 264                     found = 1;
 265                 }
 266             }
 267         }
 268     }
 269     else
 270     {
 271         state_set[key] = sp = new_state(symbol);
 272     }
 273
 274     return (sp->number);
 275 }
 276
 277
 278
 279 static void
 280 initialize_states()
 281 {
 282     register int i;
 283     register short *start_derives;
 284     register core *p;
 285
 286     start_derives = derives[start_symbol];
 287     for (i = 0; start_derives[i] >= 0; ++i)
 288         continue;
 289
 290     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
 291     if (p == 0) no_space();
 292
 293     p->next = 0;
 294     p->link = 0;
 295     p->number = 0;
 296     p->accessing_symbol = 0;
 297     p->nitems = i;
 298
 299     for (i = 0;  start_derives[i] >= 0; ++i)
 300         p->items[i] = rrhs[start_derives[i]];
 301
 302     first_state = last_state = this_state = p;
 303     nstates = 1;
 304 }
 305
 306
 307 static void
 308 new_itemsets()
 309 {
 310     register int i;
 311     register int shiftcount;
 312     register short *isp;
 313     register short *ksp;
 314     register int symbol;
 315
 316     for (i = 0; i < nsyms; i++)
 317         kernel_end[i] = 0;
 318
 319     shiftcount = 0;
 320     isp = itemset;
 321     while (isp < itemsetend)
 322     {
 323         i = *isp++;
 324         symbol = ritem[i];
 325         if (symbol > 0)
 326         {
 327             ksp = kernel_end[symbol];
 328             if (!ksp)
 329             {
 330                 shift_symbol[shiftcount++] = symbol;
 331                 ksp = kernel_base[symbol];
 332             }
 333
 334             *ksp++ = i + 1;
 335             kernel_end[symbol] = ksp;
 336         }
 337     }
 338
 339     nshifts = shiftcount;
 340 }
 341
 342
 343
 344 static core *
 345 new_state(symbol)
 346 int symbol;
 347 {
 348     register int n;
 349     register core *p;
 350     register short *isp1;
 351     register short *isp2;
 352     register short *iend;
 353
 354 #ifdef  TRACE
 355     fprintf(stderr, "Entering new_state(%d)\n", symbol);
 356 #endif
 357
 358     if (nstates >= MAXSHORT)
 359         fatal("too many states");
 360
 361     isp1 = kernel_base[symbol];
 362     iend = kernel_end[symbol];
 363     n = iend - isp1;
 364
 365     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
 366     p->accessing_symbol = symbol;
 367     p->number = nstates;
 368     p->nitems = n;
 369
 370     isp2 = p->items;
 371     while (isp1 < iend)
 372         *isp2++ = *isp1++;
 373
 374     last_state->next = p;
 375     last_state = p;
 376
 377     nstates++;
 378
 379     return (p);
 380 }
 381
 382
 383 #if 0
 384 /* show_cores is used for debugging */
 385
 386 show_cores()
 387 {
 388     core *p;
 389     int i, j, k, n;
 390     int itemno;
 391
 392     k = 0;
 393     for (p = first_state; p; ++k, p = p->next)
 394     {
 395         if (k) printf("\n");
 396         printf("state %d, number = %d, accessing symbol = %s\n",
 397                 k, p->number, symbol_name[p->accessing_symbol]);
 398         n = p->nitems;
 399         for (i = 0; i < n; ++i)
 400         {
 401             itemno = p->items[i];
 402             printf("%4d  ", itemno);
 403             j = itemno;
 404             while (ritem[j] >= 0) ++j;
 405             printf("%s :", symbol_name[rlhs[-ritem[j]]]);
 406             j = rrhs[-ritem[j]];
 407             while (j < itemno)
 408                 printf(" %s", symbol_name[ritem[j++]]);
 409             printf(" .");
 410             while (ritem[j] >= 0)
 411                 printf(" %s", symbol_name[ritem[j++]]);
 412             printf("\n");
 413             fflush(stdout);
 414         }
 415     }
 416 }
 417
 418
 419 /* show_ritems is used for debugging */
 420
 421 show_ritems()
 422 {
 423     int i;
 424
 425     for (i = 0; i < nitems; ++i)
 426         printf("ritem[%d] = %d\n", i, ritem[i]);
 427 }
 428
 429
 430 /* show_rrhs is used for debugging */
 431 show_rrhs()
 432 {
 433     int i;
 434
 435     for (i = 0; i < nrules; ++i)
 436         printf("rrhs[%d] = %d\n", i, rrhs[i]);
 437 }
 438
 439
 440 /* show_shifts is used for debugging */
 441
 442 show_shifts()
 443 {
 444     shifts *p;
 445     int i, j, k;
 446
 447     k = 0;
 448     for (p = first_shift; p; ++k, p = p->next)
 449     {
 450         if (k) printf("\n");
 451         printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
 452                 p->nshifts);
 453         j = p->nshifts;
 454         for (i = 0; i < j; ++i)
 455             printf("\t%d\n", p->shift[i]);
 456     }
 457 }
 458 #endif
 459
 460
 461 static void
 462 save_shifts()
 463 {
 464     register shifts *p;
 465     register short *sp1;
 466     register short *sp2;
 467     register short *send;
 468
 469     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
 470                         (nshifts - 1) * sizeof(short)));
 471
 472     p->number = this_state->number;
 473     p->nshifts = nshifts;
 474
 475     sp1 = shiftset;
 476     sp2 = p->shift;
 477     send = shiftset + nshifts;
 478
 479     while (sp1 < send)
 480         *sp2++ = *sp1++;
 481
 482     if (last_shift)
 483     {
 484         last_shift->next = p;
 485         last_shift = p;
 486     }
 487     else
 488     {
 489         first_shift = p;
 490         last_shift = p;
 491     }
 492 }
 493
 494
 495
 496 static void
 497 save_reductions()
 498 {
 499     register short *isp;
 500     register short *rp1;
 501     register short *rp2;
 502     register int item;
 503     register int count;
 504     register reductions *p;
 505     register short *rend;
 506
 507     count = 0;
 508     for (isp = itemset; isp < itemsetend; isp++)
 509     {
 510         item = ritem[*isp];
 511         if (item < 0)
 512         {
 513             redset[count++] = -item;
 514         }
 515     }
 516
 517     if (count)
 518     {
 519         p = (reductions *) allocate((unsigned) (sizeof(reductions) +
 520                                         (count - 1) * sizeof(short)));
 521
 522         p->number = this_state->number;
 523         p->nreds = count;
 524
 525         rp1 = redset;
 526         rp2 = p->rules;
 527         rend = rp1 + count;
 528
 529         while (rp1 < rend)
 530             *rp2++ = *rp1++;
 531
 532         if (last_reduction)
 533         {
 534             last_reduction->next = p;
 535             last_reduction = p;
 536         }
 537         else
 538         {
 539             first_reduction = p;
 540             last_reduction = p;
 541         }
 542     }
 543 }
 544
 545
 546 static void
 547 set_derives()
 548 {
 549     register int i, k;
 550     register int lhs;
 551     register short *rules;
 552
 553     derives = NEW2(nsyms, short *);
 554     rules = NEW2(nvars + nrules, short);
 555
 556     k = 0;
 557     for (lhs = start_symbol; lhs < nsyms; lhs++)
 558     {
 559         derives[lhs] = rules + k;
 560         for (i = 0; i < nrules; i++)
 561         {
 562             if (rlhs[i] == lhs)
 563             {
 564                 rules[k] = i;
 565                 k++;
 566             }
 567         }
 568         rules[k] = -1;
 569         k++;
 570     }
 571
 572 #ifdef  DEBUG
 573     print_derives();
 574 #endif
 575 }
 576
 577 #if 0
 578 free_derives()
 579 {
 580     FREE(derives[start_symbol]);
 581     FREE(derives);
 582 }
 583 #endif
 584
 585 #ifdef  DEBUG
 586 static void
 587 print_derives()
 588 {
 589     register int i;
 590     register short *sp;
 591
 592     printf("\nDERIVES\n\n");
 593
 594     for (i = start_symbol; i < nsyms; i++)
 595     {
 596         printf("%s derives ", symbol_name[i]);
 597         for (sp = derives[i]; *sp >= 0; sp++)
 598         {
 599             printf("  %d", *sp);
 600         }
 601         putchar('\n');
 602     }
 603
 604     putchar('\n');
 605 }
 606 #endif
 607
 608
 609 static void
 610 set_nullable()
 611 {
 612     register int i, j;
 613     register int empty;
 614     int done;
 615
 616     nullable = MALLOC(nsyms);
 617     if (nullable == 0) no_space();
 618
 619     for (i = 0; i < nsyms; ++i)
 620         nullable[i] = 0;
 621
 622     done = 0;
 623     while (!done)
 624     {
 625         done = 1;
 626         for (i = 1; i < nitems; i++)
 627         {
 628             empty = 1;
 629             while ((j = ritem[i]) >= 0)
 630             {
 631                 if (!nullable[j])
 632                     empty = 0;
 633                 ++i;
 634             }
 635             if (empty)
 636             {
 637                 j = rlhs[-j];
 638                 if (!nullable[j])
 639                 {
 640                     nullable[j] = 1;
 641                     done = 0;
 642                 }
 643             }
 644         }
 645     }
 646
 647 #ifdef DEBUG
 648     for (i = 0; i < nsyms; i++)
 649     {
 650         if (nullable[i])
 651             printf("%s is nullable\n", symbol_name[i]);
 652         else
 653             printf("%s is not nullable\n", symbol_name[i]);
 654     }
 655 #endif
 656 }
 657
 658
 659 #if 0
 660 free_nullable()
 661 {
 662     FREE(nullable);
 663 }
 664 #endif
 665
 666
 667 void
 668 lr0()
 669 {
 670     set_derives();
 671     set_nullable();
 672     generate_states();
 673 }