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