1 /* $NetBSD: lr0.c,v 1.16 2026/05/03 15:29:19 christos Exp $ */ 2 3 /* Id: lr0.c,v 1.23 2025/10/08 00:22:08 tom Exp */ 4 5 #include "defs.h" 6 7 #include <sys/cdefs.h> 8 __RCSID("$NetBSD: lr0.c,v 1.16 2026/05/03 15:29:19 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 Value_t 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 const 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 const Value_t *isp1; 169 const 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 const 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 const Value_t *start_derives; 232 core *p; 233 234 start_derives = derives[start_symbol]; 235 for (i = 0; start_derives[i] >= 0; ++i) 236 { 237 ; 238 } 239 240 p = (core *)MALLOC(sizeof(core) + i * sizeof(Value_t)); 241 NO_SPACE(p); 242 243 p->next = NULL; 244 p->link = NULL; 245 p->number = 0; 246 p->accessing_symbol = 0; 247 p->nitems = (Value_t)i; 248 249 for (i = 0; start_derives[i] >= 0; ++i) 250 p->items[i] = rrhs[start_derives[i]]; 251 252 first_state = last_state = this_state = p; 253 nstates = 1; 254 } 255 256 static void 257 new_itemsets(void) 258 { 259 Value_t i; 260 int shiftcount; 261 const Value_t *isp; 262 Value_t *ksp; 263 264 for (i = 0; i < nsyms; i++) 265 kernel_end[i] = NULL; 266 267 shiftcount = 0; 268 isp = itemset; 269 while (isp < itemsetend) 270 { 271 int j = *isp++; 272 Value_t symbol = ritem[j]; 273 274 if (symbol > 0) 275 { 276 ksp = kernel_end[symbol]; 277 if (!ksp) 278 { 279 shift_symbol[shiftcount++] = symbol; 280 ksp = kernel_base[symbol]; 281 } 282 283 *ksp++ = (Value_t)(j + 1); 284 kernel_end[symbol] = ksp; 285 } 286 } 287 288 nshifts = shiftcount; 289 } 290 291 static core * 292 new_state(int symbol) 293 { 294 unsigned n; 295 core *p; 296 const Value_t *isp1; 297 Value_t *isp2; 298 const Value_t *iend; 299 300 #ifdef TRACE 301 fprintf(stderr, "Entering new_state(%d)\n", symbol); 302 #endif 303 304 if (nstates >= MAXYYINT) 305 fatal("too many states"); 306 307 isp1 = kernel_base[symbol]; 308 iend = kernel_end[symbol]; 309 n = (unsigned)(iend - isp1); 310 311 p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(Value_t))); 312 p->accessing_symbol = (Value_t)symbol; 313 p->number = (Value_t)nstates; 314 p->nitems = (Value_t)n; 315 316 isp2 = p->items; 317 while (isp1 < iend) 318 *isp2++ = *isp1++; 319 320 last_state->next = p; 321 last_state = p; 322 323 nstates++; 324 325 return (p); 326 } 327 328 /* show_cores is used for debugging */ 329 #ifdef DEBUG 330 void 331 show_cores(void) 332 { 333 core *p; 334 int i, j, k, n; 335 int itemno; 336 337 k = 0; 338 for (p = first_state; p; ++k, p = p->next) 339 { 340 if (k) 341 printf("\n"); 342 printf("state %d, number = %d, accessing symbol = %s\n", 343 k, p->number, symbol_name[p->accessing_symbol]); 344 n = p->nitems; 345 for (i = 0; i < n; ++i) 346 { 347 itemno = p->items[i]; 348 printf("%4d ", itemno); 349 j = itemno; 350 while (ritem[j] >= 0) 351 ++j; 352 printf("%s :", symbol_name[rlhs[-ritem[j]]]); 353 j = rrhs[-ritem[j]]; 354 while (j < itemno) 355 printf(" %s", symbol_name[ritem[j++]]); 356 printf(" ."); 357 while (ritem[j] >= 0) 358 printf(" %s", symbol_name[ritem[j++]]); 359 printf("\n"); 360 fflush(stdout); 361 } 362 } 363 } 364 365 /* show_ritems is used for debugging */ 366 367 void 368 show_ritems(void) 369 { 370 int i; 371 372 for (i = 0; i < nitems; ++i) 373 printf("ritem[%d] = %d\n", i, ritem[i]); 374 } 375 376 /* show_rrhs is used for debugging */ 377 void 378 show_rrhs(void) 379 { 380 int i; 381 382 for (i = 0; i < nrules; ++i) 383 printf("rrhs[%d] = %d\n", i, rrhs[i]); 384 } 385 386 /* show_shifts is used for debugging */ 387 388 void 389 show_shifts(void) 390 { 391 shifts *p; 392 int i, j, k; 393 394 k = 0; 395 for (p = first_shift; p; ++k, p = p->next) 396 { 397 if (k) 398 printf("\n"); 399 printf("shift %d, number = %d, nshifts = %d\n", k, p->number, 400 p->nshifts); 401 j = p->nshifts; 402 for (i = 0; i < j; ++i) 403 printf("\t%d\n", p->shift[i]); 404 } 405 } 406 #endif 407 408 static void 409 save_shifts(void) 410 { 411 shifts *p; 412 const Value_t *sp1; 413 Value_t *sp2; 414 const Value_t *send; 415 416 p = (shifts *)allocate((sizeof(shifts) + 417 (unsigned)(nshifts - 1) * sizeof(Value_t))); 418 419 p->number = this_state->number; 420 p->nshifts = (Value_t)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 static void 442 save_reductions(void) 443 { 444 Value_t *isp; 445 Value_t *rp1; 446 Value_t count; 447 reductions *p; 448 449 count = 0; 450 for (isp = itemset; isp < itemsetend; isp++) 451 { 452 int item = ritem[*isp]; 453 454 if (item < 0) 455 { 456 redset[count++] = (Value_t)-item; 457 } 458 } 459 460 if (count) 461 { 462 Value_t *rp2; 463 const Value_t *rend; 464 465 p = (reductions *)allocate((sizeof(reductions) + 466 (unsigned)(count - 1) * 467 sizeof(Value_t))); 468 469 p->number = this_state->number; 470 p->nreds = count; 471 472 rp1 = redset; 473 rp2 = p->rules; 474 rend = rp1 + count; 475 476 while (rp1 < rend) 477 *rp2++ = *rp1++; 478 479 if (last_reduction) 480 { 481 last_reduction->next = p; 482 last_reduction = p; 483 } 484 else 485 { 486 first_reduction = p; 487 last_reduction = p; 488 } 489 } 490 } 491 492 static void 493 set_derives(void) 494 { 495 Value_t i, k; 496 int lhs; 497 498 derives = NEW2(nsyms, Value_t *); 499 rules = NEW2(nvars + nrules, Value_t); 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 #ifdef DEBUG 523 void 524 print_derives(void) 525 { 526 int i; 527 Value_t *sp; 528 529 printf("\nDERIVES\n\n"); 530 531 for (i = start_symbol; i < nsyms; i++) 532 { 533 printf("%s derives ", symbol_name[i]); 534 for (sp = derives[i]; *sp >= 0; sp++) 535 { 536 printf(" %d", *sp); 537 } 538 putchar('\n'); 539 } 540 541 putchar('\n'); 542 } 543 #endif 544 545 static void 546 set_nullable(void) 547 { 548 int i, j; 549 int empty; 550 int done_flag; 551 552 nullable = TMALLOC(char, nsyms); 553 NO_SPACE(nullable); 554 555 for (i = 0; i < nsyms; ++i) 556 nullable[i] = 0; 557 558 done_flag = 0; 559 while (!done_flag) 560 { 561 done_flag = 1; 562 for (i = 1; i < nitems; i++) 563 { 564 empty = 1; 565 while ((j = ritem[i]) >= 0) 566 { 567 if (!nullable[j]) 568 empty = 0; 569 ++i; 570 } 571 if (empty) 572 { 573 j = rlhs[-j]; 574 if (!nullable[j]) 575 { 576 nullable[j] = 1; 577 done_flag = 0; 578 } 579 } 580 } 581 } 582 583 #ifdef DEBUG 584 for (i = 0; i < nsyms; i++) 585 { 586 if (nullable[i]) 587 printf("%s is nullable\n", symbol_name[i]); 588 else 589 printf("%s is not nullable\n", symbol_name[i]); 590 } 591 #endif 592 } 593 594 void 595 lr0(void) 596 { 597 set_derives(); 598 set_nullable(); 599 generate_states(); 600 } 601 602 #ifdef NO_LEAKS 603 void 604 lr0_leaks(void) 605 { 606 if (derives) 607 { 608 if (derives[start_symbol] != rules) 609 { 610 DO_FREE(derives[start_symbol]); 611 } 612 DO_FREE(derives); 613 DO_FREE(rules); 614 } 615 DO_FREE(nullable); 616 } 617 #endif 618
Indexes created Thu Sep 24 00:25:51 UTC 2026