usr.bin/yacc/lr0.c

   1 /*      $NetBSD: lr0.c,v 1.9 2006/05/24 18:01:43 christos Exp $ */
   2
   3 /*
   4  * Copyright (c) 1989 The Regents of the University of California.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Robert Paul Corbett.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <sys/cdefs.h>
  36 #if defined(__RCSID) && !defined(lint)
  37 #if 0
  38 static char sccsid[] = "@(#)lr0.c       5.3 (Berkeley) 1/20/91";
  39 #else
  40 __RCSID("$NetBSD: lr0.c,v 1.9 2006/05/24 18:01:43 christos Exp $");
  41 #endif
  42 #endif /* not lint */
  43
  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 int get_state(int);
  56 static core *new_state(int);
  57
  58 static void allocate_itemsets(void);
  59 static void allocate_storage(void);
  60 static void append_states(void);
  61 static void free_storage(void);
  62 static void generate_states(void);
  63 static void initialize_states(void);
  64 static void new_itemsets(void);
  65 #ifdef DEBUG
  66 static void show_cores(void);
  67 static void show_ritems(void);
  68 static void show_rrhs(void);
  69 static void show_shifts(void);
  70 #endif
  71 static void save_shifts(void);
  72 static void save_reductions(void);
  73 static void set_derives(void);
  74 static void set_nullable(void);
  75 #ifdef DEBUG
  76 static void print_derives(void);
  77 static void free_derives(void);
  78 static void free_nullable(void);
  79 #endif
  80
  81 static core **state_set;
  82 static core *this_state;
  83 static core *last_state;
  84 static shifts *last_shift;
  85 static reductions *last_reduction;
  86
  87 static int nshifts;
  88 static short *shift_symbol;
  89
  90 static short *redset;
  91 static short *shiftset;
  92
  93 static short **kernel_base;
  94 static short **kernel_end;
  95 static short *kernel_items;
  96
  97 static void
  98 allocate_itemsets(void)
  99 {
 100     short *itemp;
 101     short *item_end;
 102     int symbol;
 103     int i;
 104     int count;
 105     int max;
 106     short *symbol_count;
 107
 108     count = 0;
 109     symbol_count = NEW2(nsyms, short);
 110
 111     item_end = ritem + nitems;
 112     for (itemp = ritem; itemp < item_end; itemp++)
 113     {
 114         symbol = *itemp;
 115         if (symbol >= 0)
 116         {
 117             count++;
 118             symbol_count[symbol]++;
 119         }
 120     }
 121
 122     kernel_base = NEW2(nsyms, short *);
 123     kernel_items = NEW2(count, short);
 124
 125     count = 0;
 126     max = 0;
 127     for (i = 0; i < nsyms; i++)
 128     {
 129         kernel_base[i] = kernel_items + count;
 130         count += symbol_count[i];
 131         if (max < symbol_count[i])
 132             max = symbol_count[i];
 133     }
 134
 135     shift_symbol = symbol_count;
 136     kernel_end = NEW2(nsyms, short *);
 137 }
 138
 139 static void
 140 allocate_storage(void)
 141 {
 142     allocate_itemsets();
 143     shiftset = NEW2(nsyms, short);
 144     redset = NEW2(nrules + 1, short);
 145     state_set = NEW2(nitems, core *);
 146 }
 147
 148 static void
 149 append_states(void)
 150 {
 151     int i;
 152     int j;
 153     int symbol;
 154
 155 #ifdef  TRACE
 156     fprintf(stderr, "Entering append_states()\n");
 157 #endif
 158     for (i = 1; i < nshifts; i++)
 159     {
 160         symbol = shift_symbol[i];
 161         j = i;
 162         while (j > 0 && shift_symbol[j - 1] > symbol)
 163         {
 164             shift_symbol[j] = shift_symbol[j - 1];
 165             j--;
 166         }
 167         shift_symbol[j] = symbol;
 168     }
 169
 170     for (i = 0; i < nshifts; i++)
 171     {
 172         symbol = shift_symbol[i];
 173         shiftset[i] = get_state(symbol);
 174     }
 175 }
 176
 177 static void
 178 free_storage(void)
 179 {
 180     FREE(shift_symbol);
 181     FREE(redset);
 182     FREE(shiftset);
 183     FREE(kernel_base);
 184     FREE(kernel_end);
 185     FREE(kernel_items);
 186     FREE(state_set);
 187 }
 188
 189
 190 static void
 191 generate_states(void)
 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(int symbol)
 220 {
 221     int key;
 222     short *isp1;
 223     short *isp2;
 224     short *iend;
 225     core *sp;
 226     int found;
 227     int n;
 228
 229 #ifdef  TRACE
 230     fprintf(stderr, "Entering get_state(%d)\n", symbol);
 231 #endif
 232
 233     isp1 = kernel_base[symbol];
 234     iend = kernel_end[symbol];
 235     n = iend - isp1;
 236
 237     key = *isp1;
 238     assert(0 <= key && key < nitems);
 239     sp = state_set[key];
 240     if (sp)
 241     {
 242         found = 0;
 243         while (!found)
 244         {
 245             if (sp->nitems == n)
 246             {
 247                 found = 1;
 248                 isp1 = kernel_base[symbol];
 249                 isp2 = sp->items;
 250
 251                 while (found && isp1 < iend)
 252                 {
 253                     if (*isp1++ != *isp2++)
 254                         found = 0;
 255                 }
 256             }
 257
 258             if (!found)
 259             {
 260                 if (sp->link)
 261                 {
 262                     sp = sp->link;
 263                 }
 264                 else
 265                 {
 266                     sp = sp->link = new_state(symbol);
 267                     found = 1;
 268                 }
 269             }
 270         }
 271     }
 272     else
 273     {
 274         state_set[key] = sp = new_state(symbol);
 275     }
 276
 277     return (sp->number);
 278 }
 279
 280
 281 static void
 282 initialize_states(void)
 283 {
 284     int i;
 285     short *start_derives;
 286     core *p;
 287
 288     start_derives = derives[start_symbol];
 289     for (i = 0; start_derives[i] >= 0; ++i)
 290         continue;
 291
 292     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
 293     if (p == 0) no_space();
 294
 295     p->next = 0;
 296     p->link = 0;
 297     p->number = 0;
 298     p->accessing_symbol = 0;
 299     p->nitems = i;
 300
 301     for (i = 0;  start_derives[i] >= 0; ++i)
 302         p->items[i] = rrhs[start_derives[i]];
 303
 304     first_state = last_state = this_state = p;
 305     nstates = 1;
 306 }
 307
 308
 309 static void
 310 new_itemsets(void)
 311 {
 312     int i;
 313     int shiftcount;
 314     short *isp;
 315     short *ksp;
 316     int symbol;
 317
 318     for (i = 0; i < nsyms; i++)
 319         kernel_end[i] = 0;
 320
 321     shiftcount = 0;
 322     isp = itemset;
 323     while (isp < itemsetend)
 324     {
 325         i = *isp++;
 326         symbol = ritem[i];
 327         if (symbol > 0)
 328         {
 329             ksp = kernel_end[symbol];
 330             if (!ksp)
 331             {
 332                 shift_symbol[shiftcount++] = symbol;
 333                 ksp = kernel_base[symbol];
 334             }
 335
 336             *ksp++ = i + 1;
 337             kernel_end[symbol] = ksp;
 338         }
 339     }
 340
 341     nshifts = shiftcount;
 342 }
 343
 344
 345
 346 static core *
 347 new_state(int symbol)
 348 {
 349     int n;
 350     core *p;
 351     short *isp1;
 352     short *isp2;
 353     short *iend;
 354
 355 #ifdef  TRACE
 356     fprintf(stderr, "Entering new_state(%d)\n", symbol);
 357 #endif
 358
 359     if (nstates >= MAXSHORT)
 360         fatal("too many states");
 361
 362     isp1 = kernel_base[symbol];
 363     iend = kernel_end[symbol];
 364     n = iend - isp1;
 365
 366     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
 367     p->accessing_symbol = symbol;
 368     p->number = nstates;
 369     p->nitems = n;
 370
 371     isp2 = p->items;
 372     while (isp1 < iend)
 373         *isp2++ = *isp1++;
 374
 375     last_state->next = p;
 376     last_state = p;
 377
 378     nstates++;
 379
 380     return (p);
 381 }
 382
 383 #ifdef DEBUG
 384 /* show_cores is used for debugging */
 385 static void
 386 show_cores(void)
 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 static void
 421 show_ritems(void)
 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 static void
 432 show_rrhs(void)
 433 {
 434     int i;
 435
 436     for (i = 0; i < nrules; ++i)
 437         printf("rrhs[%d] = %d\n", i, rrhs[i]);
 438 }
 439
 440
 441 /* show_shifts is used for debugging */
 442 static void
 443 show_shifts(void)
 444 {
 445     shifts *p;
 446     int i, j, k;
 447
 448     k = 0;
 449     for (p = first_shift; p; ++k, p = p->next)
 450     {
 451         if (k) printf("\n");
 452         printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
 453                 p->nshifts);
 454         j = p->nshifts;
 455         for (i = 0; i < j; ++i)
 456             printf("\t%d\n", p->shift[i]);
 457     }
 458 }
 459 #endif
 460
 461
 462 static void
 463 save_shifts(void)
 464 {
 465     shifts *p;
 466     short *sp1;
 467     short *sp2;
 468     short *send;
 469
 470     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
 471                         (nshifts - 1) * sizeof(short)));
 472
 473     p->number = this_state->number;
 474     p->nshifts = nshifts;
 475
 476     sp1 = shiftset;
 477     sp2 = p->shift;
 478     send = shiftset + nshifts;
 479
 480     while (sp1 < send)
 481         *sp2++ = *sp1++;
 482
 483     if (last_shift)
 484     {
 485         last_shift->next = p;
 486         last_shift = p;
 487     }
 488     else
 489     {
 490         first_shift = p;
 491         last_shift = p;
 492     }
 493 }
 494
 495
 496 static void
 497 save_reductions(void)
 498 {
 499     short *isp;
 500     short *rp1;
 501     short *rp2;
 502     int item;
 503     int count;
 504     reductions *p;
 505     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(void)
 548 {
 549     int i, k;
 550     int lhs;
 551     short *rules;
 552
 553     derives = NEW2(nsyms, short *);
 554     if (start_symbol >= nsyms)
 555         return;
 556
 557     rules = NEW2(nvars + nrules, short);
 558
 559     k = 0;
 560     for (lhs = start_symbol; lhs < nsyms; lhs++)
 561     {
 562         derives[lhs] = rules + k;
 563         for (i = 0; i < nrules; i++)
 564         {
 565             if (rlhs[i] == lhs)
 566             {
 567                 rules[k] = i;
 568                 k++;
 569             }
 570         }
 571         rules[k] = -1;
 572         k++;
 573     }
 574
 575 #ifdef  DEBUG
 576     print_derives();
 577 #endif
 578 }
 579
 580 #ifdef DEBUG
 581 static void
 582 free_derives(void)
 583 {
 584     FREE(derives[start_symbol]);
 585     FREE(derives);
 586 }
 587 #endif
 588
 589 #ifdef  DEBUG
 590 static void
 591 print_derives(void)
 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(void)
 615 {
 616     int i, j;
 617     int empty;
 618     int isdone;
 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     isdone = 0;
 627     while (!isdone)
 628     {
 629         isdone = 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                     isdone = 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 #ifdef DEBUG
 664 static void
 665 free_nullable(void)
 666 {
 667     FREE(nullable);
 668 }
 669 #endif
 670
 671
 672 void
 673 lr0(void)
 674 {
 675     set_derives();
 676     set_nullable();
 677     generate_states();
 678 }