1 /* $OpenBSD: lr0.c,v 1.8 2003/06/19 16:34:53 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. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #ifndef lint 37 #if 0 38 static char sccsid[] = "@(#)lr0.c 5.3 (Berkeley) 1/20/91"; 39 #else 40 static char rcsid[] = "$OpenBSD: lr0.c,v 1.8 2003/06/19 16:34:53 pvalchev Exp $"; 41 #endif 42 #endif /* not lint */ 43 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 int get_state(int); 56 core *new_state(int); 57 58 void allocate_itemsets(void); 59 void allocate_storage(void); 60 void append_states(void); 61 void free_storage(void); 62 void generate_states(void); 63 void initialize_states(void); 64 void new_itemsets(void); 65 void show_cores(void); 66 void show_ritems(void); 67 void show_rrhs(void); 68 void show_shifts(void); 69 void save_shifts(void); 70 void save_reductions(void); 71 void set_derives(void); 72 void print_derives(void); 73 void set_nullable(void); 74 void free_derives(void); 75 void free_nullable(void); 76 77 static core **state_set; 78 static core *this_state; 79 static core *last_state; 80 static shifts *last_shift; 81 static reductions *last_reduction; 82 83 static int nshifts; 84 static short *shift_symbol; 85 86 static short *redset; 87 static short *shiftset; 88 89 static short **kernel_base; 90 static short **kernel_end; 91 static short *kernel_items; 92 93 void 94 allocate_itemsets(void) 95 { 96 short *itemp; 97 short *item_end; 98 int symbol; 99 int i; 100 int count; 101 int max; 102 short *symbol_count; 103 104 count = 0; 105 symbol_count = NEW2(nsyms, short); 106 107 item_end = ritem + nitems; 108 for (itemp = ritem; itemp < item_end; itemp++) 109 { 110 symbol = *itemp; 111 if (symbol >= 0) 112 { 113 count++; 114 symbol_count[symbol]++; 115 } 116 } 117 118 kernel_base = NEW2(nsyms, short *); 119 kernel_items = NEW2(count, short); 120 121 count = 0; 122 max = 0; 123 for (i = 0; i < nsyms; i++) 124 { 125 kernel_base[i] = kernel_items + count; 126 count += symbol_count[i]; 127 if (max < symbol_count[i]) 128 max = symbol_count[i]; 129 } 130 131 shift_symbol = symbol_count; 132 kernel_end = NEW2(nsyms, short *); 133 } 134 135 void 136 allocate_storage(void) 137 { 138 allocate_itemsets(); 139 shiftset = NEW2(nsyms, short); 140 redset = NEW2(nrules + 1, short); 141 state_set = NEW2(nitems, core *); 142 } 143 144 void 145 append_states(void) 146 { 147 int i; 148 int j; 149 int symbol; 150 151 #ifdef TRACE 152 fprintf(stderr, "Entering append_states()\n"); 153 #endif 154 for (i = 1; i < nshifts; i++) 155 { 156 symbol = shift_symbol[i]; 157 j = i; 158 while (j > 0 && shift_symbol[j - 1] > symbol) 159 { 160 shift_symbol[j] = shift_symbol[j - 1]; 161 j--; 162 } 163 shift_symbol[j] = symbol; 164 } 165 166 for (i = 0; i < nshifts; i++) 167 { 168 symbol = shift_symbol[i]; 169 shiftset[i] = get_state(symbol); 170 } 171 } 172 173 void 174 free_storage(void) 175 { 176 FREE(shift_symbol); 177 FREE(redset); 178 FREE(shiftset); 179 FREE(kernel_base); 180 FREE(kernel_end); 181 FREE(kernel_items); 182 FREE(state_set); 183 } 184 185 186 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 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 void 278 initialize_states(void) 279 { 280 int i; 281 short *start_derives; 282 core *p; 283 284 start_derives = derives[start_symbol]; 285 for (i = 0; start_derives[i] >= 0; ++i) 286 continue; 287 288 p = (core *) MALLOC(sizeof(core) + i*sizeof(short)); 289 if (p == 0) no_space(); 290 291 p->next = 0; 292 p->link = 0; 293 p->number = 0; 294 p->accessing_symbol = 0; 295 p->nitems = i; 296 297 for (i = 0; start_derives[i] >= 0; ++i) 298 p->items[i] = rrhs[start_derives[i]]; 299 300 first_state = last_state = this_state = p; 301 nstates = 1; 302 } 303 304 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] = 0; 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 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 /* show_cores is used for debugging */ 380 381 void 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 void 418 show_ritems(void) 419 { 420 int i; 421 422 for (i = 0; i < nitems; ++i) 423 printf("ritem[%d] = %d\n", i, ritem[i]); 424 } 425 426 427 /* show_rrhs is used for debugging */ 428 429 void 430 show_rrhs(void) 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 void 442 show_shifts(void) 443 { 444 shifts *p; 445 int i, j, k; 446 447 k = 0; 448 for (p = first_shift; p; ++k, p = p->next) 449 { 450 if (k) printf("\n"); 451 printf("shift %d, number = %d, nshifts = %d\n", k, p->number, 452 p->nshifts); 453 j = p->nshifts; 454 for (i = 0; i < j; ++i) 455 printf("\t%d\n", p->shift[i]); 456 } 457 } 458 459 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 void 494 save_reductions(void) 495 { 496 short *isp; 497 short *rp1; 498 short *rp2; 499 int item; 500 int count; 501 reductions *p; 502 short *rend; 503 504 count = 0; 505 for (isp = itemset; isp < itemsetend; isp++) 506 { 507 item = ritem[*isp]; 508 if (item < 0) 509 { 510 redset[count++] = -item; 511 } 512 } 513 514 if (count) 515 { 516 p = (reductions *) allocate((unsigned) (sizeof(reductions) + 517 (count - 1) * sizeof(short))); 518 519 p->number = this_state->number; 520 p->nreds = count; 521 522 rp1 = redset; 523 rp2 = p->rules; 524 rend = rp1 + count; 525 526 while (rp1 < rend) 527 *rp2++ = *rp1++; 528 529 if (last_reduction) 530 { 531 last_reduction->next = p; 532 last_reduction = p; 533 } 534 else 535 { 536 first_reduction = p; 537 last_reduction = p; 538 } 539 } 540 } 541 542 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 void 574 free_derives(void) 575 { 576 FREE(derives[start_symbol]); 577 FREE(derives); 578 } 579 580 #ifdef DEBUG 581 void 582 print_derives(void) 583 { 584 int i; 585 short *sp; 586 587 printf("\nDERIVES\n\n"); 588 589 for (i = start_symbol; i < nsyms; i++) 590 { 591 printf("%s derives ", symbol_name[i]); 592 for (sp = derives[i]; *sp >= 0; sp++) 593 { 594 printf(" %d", *sp); 595 } 596 putchar('\n'); 597 } 598 599 putchar('\n'); 600 } 601 #endif 602 603 void 604 set_nullable(void) 605 { 606 int i, j; 607 int empty; 608 int done; 609 610 nullable = MALLOC(nsyms); 611 if (nullable == 0) no_space(); 612 613 for (i = 0; i < nsyms; ++i) 614 nullable[i] = 0; 615 616 done = 0; 617 while (!done) 618 { 619 done = 1; 620 for (i = 1; i < nitems; i++) 621 { 622 empty = 1; 623 while ((j = ritem[i]) >= 0) 624 { 625 if (!nullable[j]) 626 empty = 0; 627 ++i; 628 } 629 if (empty) 630 { 631 j = rlhs[-j]; 632 if (!nullable[j]) 633 { 634 nullable[j] = 1; 635 done = 0; 636 } 637 } 638 } 639 } 640 641 #ifdef DEBUG 642 for (i = 0; i < nsyms; i++) 643 { 644 if (nullable[i]) 645 printf("%s is nullable\n", symbol_name[i]); 646 else 647 printf("%s is not nullable\n", symbol_name[i]); 648 } 649 #endif 650 } 651 652 void 653 free_nullable(void) 654 { 655 FREE(nullable); 656 } 657 658 void 659 lr0(void) 660 { 661 set_derives(); 662 set_nullable(); 663 generate_states(); 664 } 665