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