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