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  * 4. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 #if 0
  34 #ifndef lint
  35 static char sccsid[] = "@(#)lr0.c       5.3 (Berkeley) 1/20/91";
  36 #endif
  37 #endif
  38
  39 #include <sys/cdefs.h>
  40 __FBSDID("$FreeBSD$");
  41
  42 #include <limits.h>
  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(void);
  56 static void allocate_storage(void);
  57 static void append_states(void);
  58 static void free_storage(void);
  59 static void generate_states(void);
  60 static int get_state(int);
  61 static void initialize_states(void);
  62 static void new_itemsets(void);
  63 static core *new_state(int);
  64 #ifdef DEBUG
  65 static void print_derives(void);
  66 #endif
  67 static void save_reductions(void);
  68 static void save_shifts(void);
  69 static void set_derives(void);
  70 static void set_nullable(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(void)
  91 {
  92     short *itemp;
  93     short *item_end;
  94     int symbol;
  95     int i;
  96     int count;
  97     int max;
  98     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(void)
 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(void)
 144 {
 145     int i;
 146     int j;
 147     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(void)
 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(void)
 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(int symbol)
 216 {
 217     int key;
 218     short *isp1;
 219     short *isp2;
 220     short *iend;
 221     core *sp;
 222     int found;
 223     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(void)
 280 {
 281     int i;
 282     short *start_derives;
 283     core *p;
 284
 285     start_derives = derives[start_symbol];
 286     for (i = 0; start_derives[i] >= 0; ++i)
 287         continue;
 288
 289     p = 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(void)
 308 {
 309     int i;
 310     int shiftcount;
 311     short *isp;
 312     short *ksp;
 313     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(int symbol)
 345 {
 346     int n;
 347     core *p;
 348     short *isp1;
 349     short *isp2;
 350     short *iend;
 351
 352 #ifdef  TRACE
 353     fprintf(stderr, "Entering new_state(%d)\n", symbol);
 354 #endif
 355
 356     if (nstates >= SHRT_MAX)
 357         fatal("too many states");
 358
 359     isp1 = kernel_base[symbol];
 360     iend = kernel_end[symbol];
 361     n = iend - isp1;
 362
 363     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
 364     p->accessing_symbol = symbol;
 365     p->number = nstates;
 366     p->nitems = n;
 367
 368     isp2 = p->items;
 369     while (isp1 < iend)
 370         *isp2++ = *isp1++;
 371
 372     last_state->next = p;
 373     last_state = p;
 374
 375     nstates++;
 376
 377     return (p);
 378 }
 379
 380
 381 #if 0
 382 /* show_cores is used for debugging */
 383
 384 show_cores(void)
 385 {
 386     core *p;
 387     int i, j, k, n;
 388     int itemno;
 389
 390     k = 0;
 391     for (p = first_state; p; ++k, p = p->next)
 392     {
 393         if (k) printf("\n");
 394         printf("state %d, number = %d, accessing symbol = %s\n",
 395                 k, p->number, symbol_name[p->accessing_symbol]);
 396         n = p->nitems;
 397         for (i = 0; i < n; ++i)
 398         {
 399             itemno = p->items[i];
 400             printf("%4d  ", itemno);
 401             j = itemno;
 402             while (ritem[j] >= 0) ++j;
 403             printf("%s :", symbol_name[rlhs[-ritem[j]]]);
 404             j = rrhs[-ritem[j]];
 405             while (j < itemno)
 406                 printf(" %s", symbol_name[ritem[j++]]);
 407             printf(" .");
 408             while (ritem[j] >= 0)
 409                 printf(" %s", symbol_name[ritem[j++]]);
 410             printf("\n");
 411             fflush(stdout);
 412         }
 413     }
 414 }
 415
 416
 417 /* show_ritems is used for debugging */
 418
 419 show_ritems(void)
 420 {
 421     int i;
 422
 423     for (i = 0; i < nitems; ++i)
 424         printf("ritem[%d] = %d\n", i, ritem[i]);
 425 }
 426
 427
 428 /* show_rrhs is used for debugging */
 429 show_rrhs(void)
 430 {
 431     int i;
 432
 433     for (i = 0; i < nrules; ++i)
 434         printf("rrhs[%d] = %d\n", i, rrhs[i]);
 435 }
 436
 437
 438 /* show_shifts is used for debugging */
 439
 440 show_shifts(void)
 441 {
 442     shifts *p;
 443     int i, j, k;
 444
 445     k = 0;
 446     for (p = first_shift; p; ++k, p = p->next)
 447     {
 448         if (k) printf("\n");
 449         printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
 450                 p->nshifts);
 451         j = p->nshifts;
 452         for (i = 0; i < j; ++i)
 453             printf("\t%d\n", p->shift[i]);
 454     }
 455 }
 456 #endif
 457
 458
 459 static void
 460 save_shifts(void)
 461 {
 462     shifts *p;
 463     short *sp1;
 464     short *sp2;
 465     short *send;
 466
 467     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
 468                         (nshifts - 1) * sizeof(short)));
 469
 470     p->number = this_state->number;
 471     p->nshifts = nshifts;
 472
 473     sp1 = shiftset;
 474     sp2 = p->shift;
 475     send = shiftset + nshifts;
 476
 477     while (sp1 < send)
 478         *sp2++ = *sp1++;
 479
 480     if (last_shift)
 481     {
 482         last_shift->next = p;
 483         last_shift = p;
 484     }
 485     else
 486     {
 487         first_shift = p;
 488         last_shift = p;
 489     }
 490 }
 491
 492
 493
 494 static void
 495 save_reductions(void)
 496 {
 497     short *isp;
 498     short *rp1;
 499     short *rp2;
 500     int item;
 501     int count;
 502     reductions *p;
 503     short *rend;
 504
 505     count = 0;
 506     for (isp = itemset; isp < itemsetend; isp++)
 507     {
 508         item = ritem[*isp];
 509         if (item < 0)
 510         {
 511             redset[count++] = -item;
 512         }
 513     }
 514
 515     if (count)
 516     {
 517         p = (reductions *) allocate((unsigned) (sizeof(reductions) +
 518                                         (count - 1) * sizeof(short)));
 519
 520         p->number = this_state->number;
 521         p->nreds = count;
 522
 523         rp1 = redset;
 524         rp2 = p->rules;
 525         rend = rp1 + count;
 526
 527         while (rp1 < rend)
 528             *rp2++ = *rp1++;
 529
 530         if (last_reduction)
 531         {
 532             last_reduction->next = p;
 533             last_reduction = p;
 534         }
 535         else
 536         {
 537             first_reduction = p;
 538             last_reduction = p;
 539         }
 540     }
 541 }
 542
 543
 544 static void
 545 set_derives(void)
 546 {
 547     int i, k;
 548     int lhs;
 549     short *rules;
 550
 551     derives = NEW2(nsyms, short *);
 552     rules = NEW2(nvars + nrules, short);
 553
 554     k = 0;
 555     for (lhs = start_symbol; lhs < nsyms; lhs++)
 556     {
 557         derives[lhs] = rules + k;
 558         for (i = 0; i < nrules; i++)
 559         {
 560             if (rlhs[i] == lhs)
 561             {
 562                 rules[k] = i;
 563                 k++;
 564             }
 565         }
 566         rules[k] = -1;
 567         k++;
 568     }
 569
 570 #ifdef  DEBUG
 571     print_derives();
 572 #endif
 573 }
 574
 575 #if 0
 576 free_derives()
 577 {
 578     free(derives[start_symbol]);
 579     free(derives);
 580 }
 581 #endif
 582
 583 #ifdef  DEBUG
 584 static void
 585 print_derives(void)
 586 {
 587     int i;
 588     short *sp;
 589
 590     printf("\nDERIVES\n\n");
 591
 592     for (i = start_symbol; i < nsyms; i++)
 593     {
 594         printf("%s derives ", symbol_name[i]);
 595         for (sp = derives[i]; *sp >= 0; sp++)
 596         {
 597             printf("  %d", *sp);
 598         }
 599         putchar('\n');
 600     }
 601
 602     putchar('\n');
 603 }
 604 #endif
 605
 606
 607 static void
 608 set_nullable(void)
 609 {
 610     int i, j;
 611     int empty;
 612     int done1;
 613
 614     nullable = malloc(nsyms);
 615     if (nullable == 0) no_space();
 616
 617     for (i = 0; i < nsyms; ++i)
 618         nullable[i] = 0;
 619
 620     done1 = 0;
 621     while (!done1)
 622     {
 623         done1 = 1;
 624         for (i = 1; i < nitems; i++)
 625         {
 626             empty = 1;
 627             while ((j = ritem[i]) >= 0)
 628             {
 629                 if (!nullable[j])
 630                     empty = 0;
 631                 ++i;
 632             }
 633             if (empty)
 634             {
 635                 j = rlhs[-j];
 636                 if (!nullable[j])
 637                 {
 638                     nullable[j] = 1;
 639                     done1 = 0;
 640                 }
 641             }
 642         }
 643     }
 644
 645 #ifdef DEBUG
 646     for (i = 0; i < nsyms; i++)
 647     {
 648         if (nullable[i])
 649             printf("%s is nullable\n", symbol_name[i]);
 650         else
 651             printf("%s is not nullable\n", symbol_name[i]);
 652     }
 653 #endif
 654 }
 655
 656
 657 #if 0
 658 free_nullable(void)
 659 {
 660     free(nullable);
 661 }
 662 #endif
 663
 664
 665 void
 666 lr0(void)
 667 {
 668     set_derives();
 669     set_nullable();
 670     generate_states();
 671 }