1 /* $OpenBSD: lr0.c,v 1.4 2001/07/16 06:29:44 pvalchev Exp $ */ 2 /* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 jtc Exp $ */ 3 4 /* 5 * Copyright (c) 1989 The Regents of the University of California. 6 * All rights reserved. 7 * 8 * This code is derived from software contributed to Berkeley by 9 * Robert Paul Corbett. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 3. All advertising materials mentioning features or use of this software 20 * must display the following acknowledgement: 21 * This product includes software developed by the University of 22 * California, Berkeley and its contributors. 23 * 4. Neither the name of the University nor the names of its contributors 24 * may be used to endorse or promote products derived from this software 25 * without specific prior written permission. 26 * 27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 30 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 37 * SUCH DAMAGE. 38 */ 39 40 #ifndef lint 41 #if 0 42 static char sccsid[] = "@(#)lr0.c 5.3 (Berkeley) 1/20/91"; 43 #else 44 static char rcsid[] = "$OpenBSD: lr0.c,v 1.4 2001/07/16 06:29:44 pvalchev Exp $"; 45 #endif 46 #endif /* not lint */ 47 48 #include "defs.h" 49 50 extern short *itemset; 51 extern short *itemsetend; 52 extern unsigned *ruleset; 53 54 int nstates; 55 core *first_state; 56 shifts *first_shift; 57 reductions *first_reduction; 58 59 int get_state __P((int)); 60 core *new_state __P((int)); 61 62 void allocate_itemsets __P((void)); 63 void allocate_storage __P((void)); 64 void append_states __P((void)); 65 void free_storage __P((void)); 66 void generate_states __P((void)); 67 void initialize_states __P((void)); 68 void new_itemsets __P((void)); 69 void show_cores __P((void)); 70 void show_ritems __P((void)); 71 void show_rrhs __P((void)); 72 void show_shifts __P((void)); 73 void save_shifts __P((void)); 74 void save_reductions __P((void)); 75 void set_derives __P((void)); 76 void print_derives __P((void)); 77 void set_nullable __P((void)); 78 void free_derives __P((void)); 79 void free_nullable __P((void)); 80 81 static core **state_set; 82 static core *this_state; 83 static core *last_state; 84 static shifts *last_shift; 85 static reductions *last_reduction; 86 87 static int nshifts; 88 static short *shift_symbol; 89 90 static short *redset; 91 static short *shiftset; 92 93 static short **kernel_base; 94 static short **kernel_end; 95 static short *kernel_items; 96 97 void 98 allocate_itemsets() 99 { 100 register short *itemp; 101 register short *item_end; 102 register int symbol; 103 register int i; 104 register int count; 105 register int max; 106 register short *symbol_count; 107 108 count = 0; 109 symbol_count = NEW2(nsyms, short); 110 111 item_end = ritem + nitems; 112 for (itemp = ritem; itemp < item_end; itemp++) 113 { 114 symbol = *itemp; 115 if (symbol >= 0) 116 { 117 count++; 118 symbol_count[symbol]++; 119 } 120 } 121 122 kernel_base = NEW2(nsyms, short *); 123 kernel_items = NEW2(count, short); 124 125 count = 0; 126 max = 0; 127 for (i = 0; i < nsyms; i++) 128 { 129 kernel_base[i] = kernel_items + count; 130 count += symbol_count[i]; 131 if (max < symbol_count[i]) 132 max = symbol_count[i]; 133 } 134 135 shift_symbol = symbol_count; 136 kernel_end = NEW2(nsyms, short *); 137 } 138 139 void 140 allocate_storage() 141 { 142 allocate_itemsets(); 143 shiftset = NEW2(nsyms, short); 144 redset = NEW2(nrules + 1, short); 145 state_set = NEW2(nitems, core *); 146 } 147 148 void 149 append_states() 150 { 151 register int i; 152 register int j; 153 register int symbol; 154 155 #ifdef TRACE 156 fprintf(stderr, "Entering append_states()\n"); 157 #endif 158 for (i = 1; i < nshifts; i++) 159 { 160 symbol = shift_symbol[i]; 161 j = i; 162 while (j > 0 && shift_symbol[j - 1] > symbol) 163 { 164 shift_symbol[j] = shift_symbol[j - 1]; 165 j--; 166 } 167 shift_symbol[j] = symbol; 168 } 169 170 for (i = 0; i < nshifts; i++) 171 { 172 symbol = shift_symbol[i]; 173 shiftset[i] = get_state(symbol); 174 } 175 } 176 177 void 178 free_storage() 179 { 180 FREE(shift_symbol); 181 FREE(redset); 182 FREE(shiftset); 183 FREE(kernel_base); 184 FREE(kernel_end); 185 FREE(kernel_items); 186 FREE(state_set); 187 } 188 189 190 void 191 generate_states() 192 { 193 allocate_storage(); 194 itemset = NEW2(nitems, short); 195 ruleset = NEW2(WORDSIZE(nrules), unsigned); 196 set_first_derives(); 197 initialize_states(); 198 199 while (this_state) 200 { 201 closure(this_state->items, this_state->nitems); 202 save_reductions(); 203 new_itemsets(); 204 append_states(); 205 206 if (nshifts > 0) 207 save_shifts(); 208 209 this_state = this_state->next; 210 } 211 212 finalize_closure(); 213 free_storage(); 214 } 215 216 217 218 int 219 get_state(symbol) 220 int symbol; 221 { 222 register int key; 223 register short *isp1; 224 register short *isp2; 225 register short *iend; 226 register core *sp; 227 register int found; 228 register int n; 229 230 #ifdef TRACE 231 fprintf(stderr, "Entering get_state(%d)\n", symbol); 232 #endif 233 234 isp1 = kernel_base[symbol]; 235 iend = kernel_end[symbol]; 236 n = iend - isp1; 237 238 key = *isp1; 239 assert(0 <= key && key < nitems); 240 sp = state_set[key]; 241 if (sp) 242 { 243 found = 0; 244 while (!found) 245 { 246 if (sp->nitems == n) 247 { 248 found = 1; 249 isp1 = kernel_base[symbol]; 250 isp2 = sp->items; 251 252 while (found && isp1 < iend) 253 { 254 if (*isp1++ != *isp2++) 255 found = 0; 256 } 257 } 258 259 if (!found) 260 { 261 if (sp->link) 262 { 263 sp = sp->link; 264 } 265 else 266 { 267 sp = sp->link = new_state(symbol); 268 found = 1; 269 } 270 } 271 } 272 } 273 else 274 { 275 state_set[key] = sp = new_state(symbol); 276 } 277 278 return (sp->number); 279 } 280 281 282 void 283 initialize_states() 284 { 285 register int i; 286 register short *start_derives; 287 register core *p; 288 289 start_derives = derives[start_symbol]; 290 for (i = 0; start_derives[i] >= 0; ++i) 291 continue; 292 293 p = (core *) MALLOC(sizeof(core) + i*sizeof(short)); 294 if (p == 0) no_space(); 295 296 p->next = 0; 297 p->link = 0; 298 p->number = 0; 299 p->accessing_symbol = 0; 300 p->nitems = i; 301 302 for (i = 0; start_derives[i] >= 0; ++i) 303 p->items[i] = rrhs[start_derives[i]]; 304 305 first_state = last_state = this_state = p; 306 nstates = 1; 307 } 308 309 void 310 new_itemsets() 311 { 312 register int i; 313 register int shiftcount; 314 register short *isp; 315 register short *ksp; 316 register int symbol; 317 318 for (i = 0; i < nsyms; i++) 319 kernel_end[i] = 0; 320 321 shiftcount = 0; 322 isp = itemset; 323 while (isp < itemsetend) 324 { 325 i = *isp++; 326 symbol = ritem[i]; 327 if (symbol > 0) 328 { 329 ksp = kernel_end[symbol]; 330 if (!ksp) 331 { 332 shift_symbol[shiftcount++] = symbol; 333 ksp = kernel_base[symbol]; 334 } 335 336 *ksp++ = i + 1; 337 kernel_end[symbol] = ksp; 338 } 339 } 340 341 nshifts = shiftcount; 342 } 343 344 345 346 core * 347 new_state(symbol) 348 int symbol; 349 { 350 register int n; 351 register core *p; 352 register short *isp1; 353 register short *isp2; 354 register short *iend; 355 356 #ifdef TRACE 357 fprintf(stderr, "Entering new_state(%d)\n", symbol); 358 #endif 359 360 if (nstates >= MAXSHORT) 361 fatal("too many states"); 362 363 isp1 = kernel_base[symbol]; 364 iend = kernel_end[symbol]; 365 n = iend - isp1; 366 367 p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short))); 368 p->accessing_symbol = symbol; 369 p->number = nstates; 370 p->nitems = n; 371 372 isp2 = p->items; 373 while (isp1 < iend) 374 *isp2++ = *isp1++; 375 376 last_state->next = p; 377 last_state = p; 378 379 nstates++; 380 381 return (p); 382 } 383 384 385 /* show_cores is used for debugging */ 386 387 void 388 show_cores() 389 { 390 core *p; 391 int i, j, k, n; 392 int itemno; 393 394 k = 0; 395 for (p = first_state; p; ++k, p = p->next) 396 { 397 if (k) printf("\n"); 398 printf("state %d, number = %d, accessing symbol = %s\n", 399 k, p->number, symbol_name[p->accessing_symbol]); 400 n = p->nitems; 401 for (i = 0; i < n; ++i) 402 { 403 itemno = p->items[i]; 404 printf("%4d ", itemno); 405 j = itemno; 406 while (ritem[j] >= 0) ++j; 407 printf("%s :", symbol_name[rlhs[-ritem[j]]]); 408 j = rrhs[-ritem[j]]; 409 while (j < itemno) 410 printf(" %s", symbol_name[ritem[j++]]); 411 printf(" ."); 412 while (ritem[j] >= 0) 413 printf(" %s", symbol_name[ritem[j++]]); 414 printf("\n"); 415 fflush(stdout); 416 } 417 } 418 } 419 420 421 /* show_ritems is used for debugging */ 422 423 void 424 show_ritems() 425 { 426 int i; 427 428 for (i = 0; i < nitems; ++i) 429 printf("ritem[%d] = %d\n", i, ritem[i]); 430 } 431 432 433 /* show_rrhs is used for debugging */ 434 435 void 436 show_rrhs() 437 { 438 int i; 439 440 for (i = 0; i < nrules; ++i) 441 printf("rrhs[%d] = %d\n", i, rrhs[i]); 442 } 443 444 445 /* show_shifts is used for debugging */ 446 447 void 448 show_shifts() 449 { 450 shifts *p; 451 int i, j, k; 452 453 k = 0; 454 for (p = first_shift; p; ++k, p = p->next) 455 { 456 if (k) printf("\n"); 457 printf("shift %d, number = %d, nshifts = %d\n", k, p->number, 458 p->nshifts); 459 j = p->nshifts; 460 for (i = 0; i < j; ++i) 461 printf("\t%d\n", p->shift[i]); 462 } 463 } 464 465 void 466 save_shifts() 467 { 468 register shifts *p; 469 register short *sp1; 470 register short *sp2; 471 register short *send; 472 473 p = (shifts *) allocate((unsigned) (sizeof(shifts) + 474 (nshifts - 1) * sizeof(short))); 475 476 p->number = this_state->number; 477 p->nshifts = nshifts; 478 479 sp1 = shiftset; 480 sp2 = p->shift; 481 send = shiftset + nshifts; 482 483 while (sp1 < send) 484 *sp2++ = *sp1++; 485 486 if (last_shift) 487 { 488 last_shift->next = p; 489 last_shift = p; 490 } 491 else 492 { 493 first_shift = p; 494 last_shift = p; 495 } 496 } 497 498 499 void 500 save_reductions() 501 { 502 register short *isp; 503 register short *rp1; 504 register short *rp2; 505 register int item; 506 register int count; 507 register reductions *p; 508 register short *rend; 509 510 count = 0; 511 for (isp = itemset; isp < itemsetend; isp++) 512 { 513 item = ritem[*isp]; 514 if (item < 0) 515 { 516 redset[count++] = -item; 517 } 518 } 519 520 if (count) 521 { 522 p = (reductions *) allocate((unsigned) (sizeof(reductions) + 523 (count - 1) * sizeof(short))); 524 525 p->number = this_state->number; 526 p->nreds = count; 527 528 rp1 = redset; 529 rp2 = p->rules; 530 rend = rp1 + count; 531 532 while (rp1 < rend) 533 *rp2++ = *rp1++; 534 535 if (last_reduction) 536 { 537 last_reduction->next = p; 538 last_reduction = p; 539 } 540 else 541 { 542 first_reduction = p; 543 last_reduction = p; 544 } 545 } 546 } 547 548 void 549 set_derives() 550 { 551 register int i, k; 552 register int lhs; 553 register short *rules; 554 555 derives = NEW2(nsyms, short *); 556 rules = NEW2(nvars + nrules, short); 557 558 k = 0; 559 for (lhs = start_symbol; lhs < nsyms; lhs++) 560 { 561 derives[lhs] = rules + k; 562 for (i = 0; i < nrules; i++) 563 { 564 if (rlhs[i] == lhs) 565 { 566 rules[k] = i; 567 k++; 568 } 569 } 570 rules[k] = -1; 571 k++; 572 } 573 574 #ifdef DEBUG 575 print_derives(); 576 #endif 577 } 578 579 void 580 free_derives() 581 { 582 FREE(derives[start_symbol]); 583 FREE(derives); 584 } 585 586 #ifdef DEBUG 587 void 588 print_derives() 589 { 590 register int i; 591 register short *sp; 592 593 printf("\nDERIVES\n\n"); 594 595 for (i = start_symbol; i < nsyms; i++) 596 { 597 printf("%s derives ", symbol_name[i]); 598 for (sp = derives[i]; *sp >= 0; sp++) 599 { 600 printf(" %d", *sp); 601 } 602 putchar('\n'); 603 } 604 605 putchar('\n'); 606 } 607 #endif 608 609 void 610 set_nullable() 611 { 612 register int i, j; 613 register int empty; 614 int done; 615 616 nullable = MALLOC(nsyms); 617 if (nullable == 0) no_space(); 618 619 for (i = 0; i < nsyms; ++i) 620 nullable[i] = 0; 621 622 done = 0; 623 while (!done) 624 { 625 done = 1; 626 for (i = 1; i < nitems; i++) 627 { 628 empty = 1; 629 while ((j = ritem[i]) >= 0) 630 { 631 if (!nullable[j]) 632 empty = 0; 633 ++i; 634 } 635 if (empty) 636 { 637 j = rlhs[-j]; 638 if (!nullable[j]) 639 { 640 nullable[j] = 1; 641 done = 0; 642 } 643 } 644 } 645 } 646 647 #ifdef DEBUG 648 for (i = 0; i < nsyms; i++) 649 { 650 if (nullable[i]) 651 printf("%s is nullable\n", symbol_name[i]); 652 else 653 printf("%s is not nullable\n", symbol_name[i]); 654 } 655 #endif 656 } 657 658 void 659 free_nullable() 660 { 661 FREE(nullable); 662 } 663 664 void 665 lr0() 666 { 667 set_derives(); 668 set_nullable(); 669 generate_states(); 670 } 671