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