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.2 2003/06/17 04:29:34 dillon 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 __P((void));
  55 static void allocate_storage __P((void));
  56 static void append_states __P((void));
  57 static void free_storage __P((void));
  58 static void generate_states __P((void));
  59 static int get_state __P((int));
  60 static void initialize_states __P((void));
  61 static void new_itemsets __P((void));
  62 static core *new_state __P((int));
  63 #ifdef DEBUG
  64 static void print_derives __P((void));
  65 #endif
  66 static void save_reductions __P((void));
  67 static void save_shifts __P((void));
  68 static void set_derives __P((void));
  69 static void set_nullable __P((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()
  90 {
  91     register short *itemp;
  92     register short *item_end;
  93     register int symbol;
  94     register int i;
  95     register int count;
  96     register int max;
  97     register 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()
 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()
 143 {
 144     register int i;
 145     register int j;
 146     register 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()
 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()
 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(symbol)
 215 int symbol;
 216 {
 217     register int key;
 218     register short *isp1;
 219     register short *isp2;
 220     register short *iend;
 221     register core *sp;
 222     register int found;
 223     register int n;
 224
 225 #ifdef  TRACE
 226     fprintf(stderr, "Entering get_state(%d)\n", symbol);
 227 #endif
 228
 229     isp1 = kernel_base[symbol];
 230     iend = kernel_end[symbol];
 231     n = iend - isp1;
 232
 233     key = *isp1;
 234     assert(0 <= key && key < nitems);
 235     sp = state_set[key];
 236     if (sp)
 237     {
 238         found = 0;
 239         while (!found)
 240         {
 241             if (sp->nitems == n)
 242             {
 243                 found = 1;
 244                 isp1 = kernel_base[symbol];
 245                 isp2 = sp->items;
 246
 247                 while (found && isp1 < iend)
 248                 {
 249                     if (*isp1++ != *isp2++)
 250                         found = 0;
 251                 }
 252             }
 253
 254             if (!found)
 255             {
 256                 if (sp->link)
 257                 {
 258                     sp = sp->link;
 259                 }
 260                 else
 261                 {
 262                     sp = sp->link = new_state(symbol);
 263                     found = 1;
 264                 }
 265             }
 266         }
 267     }
 268     else
 269     {
 270         state_set[key] = sp = new_state(symbol);
 271     }
 272
 273     return (sp->number);
 274 }
 275
 276
 277
 278 static void
 279 initialize_states()
 280 {
 281     register int i;
 282     register short *start_derives;
 283     register core *p;
 284
 285     start_derives = derives[start_symbol];
 286     for (i = 0; start_derives[i] >= 0; ++i)
 287         continue;
 288
 289     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
 290     if (p == 0) no_space();
 291
 292     p->next = 0;
 293     p->link = 0;
 294     p->number = 0;
 295     p->accessing_symbol = 0;
 296     p->nitems = i;
 297
 298     for (i = 0;  start_derives[i] >= 0; ++i)
 299         p->items[i] = rrhs[start_derives[i]];
 300
 301     first_state = last_state = this_state = p;
 302     nstates = 1;
 303 }
 304
 305
 306 static void
 307 new_itemsets()
 308 {
 309     register int i;
 310     register int shiftcount;
 311     register short *isp;
 312     register short *ksp;
 313     register int symbol;
 314
 315     for (i = 0; i < nsyms; i++)
 316         kernel_end[i] = 0;
 317
 318     shiftcount = 0;
 319     isp = itemset;
 320     while (isp < itemsetend)
 321     {
 322         i = *isp++;
 323         symbol = ritem[i];
 324         if (symbol > 0)
 325         {
 326             ksp = kernel_end[symbol];
 327             if (!ksp)
 328             {
 329                 shift_symbol[shiftcount++] = symbol;
 330                 ksp = kernel_base[symbol];
 331             }
 332
 333             *ksp++ = i + 1;
 334             kernel_end[symbol] = ksp;
 335         }
 336     }
 337
 338     nshifts = shiftcount;
 339 }
 340
 341
 342
 343 static core *
 344 new_state(symbol)
 345 int symbol;
 346 {
 347     register int n;
 348     register core *p;
 349     register short *isp1;
 350     register short *isp2;
 351     register short *iend;
 352
 353 #ifdef  TRACE
 354     fprintf(stderr, "Entering new_state(%d)\n", symbol);
 355 #endif
 356
 357     if (nstates >= MAXSHORT)
 358         fatal("too many states");
 359
 360     isp1 = kernel_base[symbol];
 361     iend = kernel_end[symbol];
 362     n = iend - isp1;
 363
 364     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
 365     p->accessing_symbol = symbol;
 366     p->number = nstates;
 367     p->nitems = n;
 368
 369     isp2 = p->items;
 370     while (isp1 < iend)
 371         *isp2++ = *isp1++;
 372
 373     last_state->next = p;
 374     last_state = p;
 375
 376     nstates++;
 377
 378     return (p);
 379 }
 380
 381
 382 #if 0
 383 /* show_cores is used for debugging */
 384
 385 show_cores()
 386 {
 387     core *p;
 388     int i, j, k, n;
 389     int itemno;
 390
 391     k = 0;
 392     for (p = first_state; p; ++k, p = p->next)
 393     {
 394         if (k) printf("\n");
 395         printf("state %d, number = %d, accessing symbol = %s\n",
 396                 k, p->number, symbol_name[p->accessing_symbol]);
 397         n = p->nitems;
 398         for (i = 0; i < n; ++i)
 399         {
 400             itemno = p->items[i];
 401             printf("%4d  ", itemno);
 402             j = itemno;
 403             while (ritem[j] >= 0) ++j;
 404             printf("%s :", symbol_name[rlhs[-ritem[j]]]);
 405             j = rrhs[-ritem[j]];
 406             while (j < itemno)
 407                 printf(" %s", symbol_name[ritem[j++]]);
 408             printf(" .");
 409             while (ritem[j] >= 0)
 410                 printf(" %s", symbol_name[ritem[j++]]);
 411             printf("\n");
 412             fflush(stdout);
 413         }
 414     }
 415 }
 416
 417
 418 /* show_ritems is used for debugging */
 419
 420 show_ritems()
 421 {
 422     int i;
 423
 424     for (i = 0; i < nitems; ++i)
 425         printf("ritem[%d] = %d\n", i, ritem[i]);
 426 }
 427
 428
 429 /* show_rrhs is used for debugging */
 430 show_rrhs()
 431 {
 432     int i;
 433
 434     for (i = 0; i < nrules; ++i)
 435         printf("rrhs[%d] = %d\n", i, rrhs[i]);
 436 }
 437
 438
 439 /* show_shifts is used for debugging */
 440
 441 show_shifts()
 442 {
 443     shifts *p;
 444     int i, j, k;
 445
 446     k = 0;
 447     for (p = first_shift; p; ++k, p = p->next)
 448     {
 449         if (k) printf("\n");
 450         printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
 451                 p->nshifts);
 452         j = p->nshifts;
 453         for (i = 0; i < j; ++i)
 454             printf("\t%d\n", p->shift[i]);
 455     }
 456 }
 457 #endif
 458
 459
 460 static void
 461 save_shifts()
 462 {
 463     register shifts *p;
 464     register short *sp1;
 465     register short *sp2;
 466     register short *send;
 467
 468     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
 469                         (nshifts - 1) * sizeof(short)));
 470
 471     p->number = this_state->number;
 472     p->nshifts = nshifts;
 473
 474     sp1 = shiftset;
 475     sp2 = p->shift;
 476     send = shiftset + nshifts;
 477
 478     while (sp1 < send)
 479         *sp2++ = *sp1++;
 480
 481     if (last_shift)
 482     {
 483         last_shift->next = p;
 484         last_shift = p;
 485     }
 486     else
 487     {
 488         first_shift = p;
 489         last_shift = p;
 490     }
 491 }
 492
 493
 494
 495 static void
 496 save_reductions()
 497 {
 498     register short *isp;
 499     register short *rp1;
 500     register short *rp2;
 501     register int item;
 502     register int count;
 503     register reductions *p;
 504     register short *rend;
 505
 506     count = 0;
 507     for (isp = itemset; isp < itemsetend; isp++)
 508     {
 509         item = ritem[*isp];
 510         if (item < 0)
 511         {
 512             redset[count++] = -item;
 513         }
 514     }
 515
 516     if (count)
 517     {
 518         p = (reductions *) allocate((unsigned) (sizeof(reductions) +
 519                                         (count - 1) * sizeof(short)));
 520
 521         p->number = this_state->number;
 522         p->nreds = count;
 523
 524         rp1 = redset;
 525         rp2 = p->rules;
 526         rend = rp1 + count;
 527
 528         while (rp1 < rend)
 529             *rp2++ = *rp1++;
 530
 531         if (last_reduction)
 532         {
 533             last_reduction->next = p;
 534             last_reduction = p;
 535         }
 536         else
 537         {
 538             first_reduction = p;
 539             last_reduction = p;
 540         }
 541     }
 542 }
 543
 544
 545 static void
 546 set_derives()
 547 {
 548     register int i, k;
 549     register int lhs;
 550     register short *rules;
 551
 552     derives = NEW2(nsyms, short *);
 553     rules = NEW2(nvars + nrules, short);
 554
 555     k = 0;
 556     for (lhs = start_symbol; lhs < nsyms; lhs++)
 557     {
 558         derives[lhs] = rules + k;
 559         for (i = 0; i < nrules; i++)
 560         {
 561             if (rlhs[i] == lhs)
 562             {
 563                 rules[k] = i;
 564                 k++;
 565             }
 566         }
 567         rules[k] = -1;
 568         k++;
 569     }
 570
 571 #ifdef  DEBUG
 572     print_derives();
 573 #endif
 574 }
 575
 576 #if 0
 577 free_derives()
 578 {
 579     FREE(derives[start_symbol]);
 580     FREE(derives);
 581 }
 582 #endif
 583
 584 #ifdef  DEBUG
 585 static void
 586 print_derives()
 587 {
 588     register int i;
 589     register short *sp;
 590
 591     printf("\nDERIVES\n\n");
 592
 593     for (i = start_symbol; i < nsyms; i++)
 594     {
 595         printf("%s derives ", symbol_name[i]);
 596         for (sp = derives[i]; *sp >= 0; sp++)
 597         {
 598             printf("  %d", *sp);
 599         }
 600         putchar('\n');
 601     }
 602
 603     putchar('\n');
 604 }
 605 #endif
 606
 607
 608 static void
 609 set_nullable()
 610 {
 611     register int i, j;
 612     register int empty;
 613     int done;
 614
 615     nullable = MALLOC(nsyms);
 616     if (nullable == 0) no_space();
 617
 618     for (i = 0; i < nsyms; ++i)
 619         nullable[i] = 0;
 620
 621     done = 0;
 622     while (!done)
 623     {
 624         done = 1;
 625         for (i = 1; i < nitems; i++)
 626         {
 627             empty = 1;
 628             while ((j = ritem[i]) >= 0)
 629             {
 630                 if (!nullable[j])
 631                     empty = 0;
 632                 ++i;
 633             }
 634             if (empty)
 635             {
 636                 j = rlhs[-j];
 637                 if (!nullable[j])
 638                 {
 639                     nullable[j] = 1;
 640                     done = 0;
 641                 }
 642             }
 643         }
 644     }
 645
 646 #ifdef DEBUG
 647     for (i = 0; i < nsyms; i++)
 648     {
 649         if (nullable[i])
 650             printf("%s is nullable\n", symbol_name[i]);
 651         else
 652             printf("%s is not nullable\n", symbol_name[i]);
 653     }
 654 #endif
 655 }
 656
 657
 658 #if 0
 659 free_nullable()
 660 {
 661     FREE(nullable);
 662 }
 663 #endif
 664
 665
 666 void
 667 lr0()
 668 {
 669     set_derives();
 670     set_nullable();
 671     generate_states();
 672 }