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