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