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