1 /* $NetBSD: lr0.c,v 1.12 2018/12/23 20:27:23 jakllsch Exp $ */ 2 3 /* Id: lr0.c,v 1.19 2016/06/07 00:21:53 tom Exp */ 4 5 #include "defs.h" 6 7 #include <sys/cdefs.h> 8 __RCSID("$NetBSD: lr0.c,v 1.12 2018/12/23 20:27:23 jakllsch 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 symbol; 53 int i; 54 int count; 55 int max; 56 Value_t *symbol_count; 57 58 count = 0; 59 symbol_count = NEW2(nsyms, Value_t); 60 61 item_end = ritem + nitems; 62 for (itemp = ritem; itemp < item_end; itemp++) 63 { 64 symbol = *itemp; 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 int j; 103 Value_t symbol; 104 105 #ifdef TRACE 106 fprintf(stderr, "Entering append_states()\n"); 107 #endif 108 for (i = 1; i < nshifts; i++) 109 { 110 symbol = shift_symbol[i]; 111 j = 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 *isp2; 170 Value_t *iend; 171 core *sp; 172 int found; 173 int n; 174 175 #ifdef TRACE 176 fprintf(stderr, "Entering get_state(%d)\n", symbol); 177 #endif 178 179 isp1 = kernel_base[symbol]; 180 iend = kernel_end[symbol]; 181 n = (int)(iend - isp1); 182 183 key = *isp1; 184 assert(0 <= key && key < nitems); 185 sp = state_set[key]; 186 if (sp) 187 { 188 found = 0; 189 while (!found) 190 { 191 if (sp->nitems == n) 192 { 193 found = 1; 194 isp1 = kernel_base[symbol]; 195 isp2 = sp->items; 196 197 while (found && isp1 < iend) 198 { 199 if (*isp1++ != *isp2++) 200 found = 0; 201 } 202 } 203 204 if (!found) 205 { 206 if (sp->link) 207 { 208 sp = sp->link; 209 } 210 else 211 { 212 sp = sp->link = new_state(symbol); 213 found = 1; 214 } 215 } 216 } 217 } 218 else 219 { 220 state_set[key] = sp = new_state(symbol); 221 } 222 223 return (sp->number); 224 } 225 226 static void 227 initialize_states(void) 228 { 229 unsigned i; 230 Value_t *start_derives; 231 core *p; 232 233 start_derives = derives[start_symbol]; 234 for (i = 0; start_derives[i] >= 0; ++i) 235 continue; 236 237 p = (core *)MALLOC(sizeof(core) + i * sizeof(Value_t)); 238 NO_SPACE(p); 239 240 p->next = 0; 241 p->link = 0; 242 p->number = 0; 243 p->accessing_symbol = 0; 244 p->nitems = (Value_t)i; 245 246 for (i = 0; start_derives[i] >= 0; ++i) 247 p->items[i] = rrhs[start_derives[i]]; 248 249 first_state = last_state = this_state = p; 250 nstates = 1; 251 } 252 253 static void 254 new_itemsets(void) 255 { 256 Value_t i; 257 int shiftcount; 258 Value_t *isp; 259 Value_t *ksp; 260 Value_t symbol; 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 i = *isp++; 270 symbol = ritem[i]; 271 if (symbol > 0) 272 { 273 ksp = kernel_end[symbol]; 274 if (!ksp) 275 { 276 shift_symbol[shiftcount++] = symbol; 277 ksp = kernel_base[symbol]; 278 } 279 280 *ksp++ = (Value_t)(i + 1); 281 kernel_end[symbol] = ksp; 282 } 283 } 284 285 nshifts = shiftcount; 286 } 287 288 static core * 289 new_state(int symbol) 290 { 291 unsigned n; 292 core *p; 293 Value_t *isp1; 294 Value_t *isp2; 295 Value_t *iend; 296 297 #ifdef TRACE 298 fprintf(stderr, "Entering new_state(%d)\n", symbol); 299 #endif 300 301 if (nstates >= MAXYYINT) 302 fatal("too many states"); 303 304 isp1 = kernel_base[symbol]; 305 iend = kernel_end[symbol]; 306 n = (unsigned)(iend - isp1); 307 308 p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(Value_t))); 309 p->accessing_symbol = (Value_t)symbol; 310 p->number = (Value_t)nstates; 311 p->nitems = (Value_t)n; 312 313 isp2 = p->items; 314 while (isp1 < iend) 315 *isp2++ = *isp1++; 316 317 last_state->next = p; 318 last_state = p; 319 320 nstates++; 321 322 return (p); 323 } 324 325 /* show_cores is used for debugging */ 326 #ifdef DEBUG 327 void 328 show_cores(void) 329 { 330 core *p; 331 int i, j, k, n; 332 int itemno; 333 334 k = 0; 335 for (p = first_state; p; ++k, p = p->next) 336 { 337 if (k) 338 printf("\n"); 339 printf("state %d, number = %d, accessing symbol = %s\n", 340 k, p->number, symbol_name[p->accessing_symbol]); 341 n = p->nitems; 342 for (i = 0; i < n; ++i) 343 { 344 itemno = p->items[i]; 345 printf("%4d ", itemno); 346 j = itemno; 347 while (ritem[j] >= 0) 348 ++j; 349 printf("%s :", symbol_name[rlhs[-ritem[j]]]); 350 j = rrhs[-ritem[j]]; 351 while (j < itemno) 352 printf(" %s", symbol_name[ritem[j++]]); 353 printf(" ."); 354 while (ritem[j] >= 0) 355 printf(" %s", symbol_name[ritem[j++]]); 356 printf("\n"); 357 fflush(stdout); 358 } 359 } 360 } 361 362 /* show_ritems is used for debugging */ 363 364 void 365 show_ritems(void) 366 { 367 int i; 368 369 for (i = 0; i < nitems; ++i) 370 printf("ritem[%d] = %d\n", i, ritem[i]); 371 } 372 373 /* show_rrhs is used for debugging */ 374 void 375 show_rrhs(void) 376 { 377 int i; 378 379 for (i = 0; i < nrules; ++i) 380 printf("rrhs[%d] = %d\n", i, rrhs[i]); 381 } 382 383 /* show_shifts is used for debugging */ 384 385 void 386 show_shifts(void) 387 { 388 shifts *p; 389 int i, j, k; 390 391 k = 0; 392 for (p = first_shift; p; ++k, p = p->next) 393 { 394 if (k) 395 printf("\n"); 396 printf("shift %d, number = %d, nshifts = %d\n", k, p->number, 397 p->nshifts); 398 j = p->nshifts; 399 for (i = 0; i < j; ++i) 400 printf("\t%d\n", p->shift[i]); 401 } 402 } 403 #endif 404 405 static void 406 save_shifts(void) 407 { 408 shifts *p; 409 Value_t *sp1; 410 Value_t *sp2; 411 Value_t *send; 412 413 p = (shifts *)allocate((sizeof(shifts) + 414 (unsigned)(nshifts - 1) * sizeof(Value_t))); 415 416 p->number = this_state->number; 417 p->nshifts = (Value_t)nshifts; 418 419 sp1 = shiftset; 420 sp2 = p->shift; 421 send = shiftset + nshifts; 422 423 while (sp1 < send) 424 *sp2++ = *sp1++; 425 426 if (last_shift) 427 { 428 last_shift->next = p; 429 last_shift = p; 430 } 431 else 432 { 433 first_shift = p; 434 last_shift = p; 435 } 436 } 437 438 static void 439 save_reductions(void) 440 { 441 Value_t *isp; 442 Value_t *rp1; 443 Value_t *rp2; 444 int item; 445 Value_t count; 446 reductions *p; 447 Value_t *rend; 448 449 count = 0; 450 for (isp = itemset; isp < itemsetend; isp++) 451 { 452 item = ritem[*isp]; 453 if (item < 0) 454 { 455 redset[count++] = (Value_t)-item; 456 } 457 } 458 459 if (count) 460 { 461 p = (reductions *)allocate((sizeof(reductions) + 462 (unsigned)(count - 1) * 463 sizeof(Value_t))); 464 465 p->number = this_state->number; 466 p->nreds = count; 467 468 rp1 = redset; 469 rp2 = p->rules; 470 rend = rp1 + count; 471 472 while (rp1 < rend) 473 *rp2++ = *rp1++; 474 475 if (last_reduction) 476 { 477 last_reduction->next = p; 478 last_reduction = p; 479 } 480 else 481 { 482 first_reduction = p; 483 last_reduction = p; 484 } 485 } 486 } 487 488 static void 489 set_derives(void) 490 { 491 Value_t i, k; 492 int lhs; 493 494 derives = NEW2(nsyms, Value_t *); 495 rules = NEW2(nvars + nrules, Value_t); 496 497 k = 0; 498 for (lhs = start_symbol; lhs < nsyms; lhs++) 499 { 500 derives[lhs] = rules + k; 501 for (i = 0; i < nrules; i++) 502 { 503 if (rlhs[i] == lhs) 504 { 505 rules[k] = i; 506 k++; 507 } 508 } 509 rules[k] = -1; 510 k++; 511 } 512 513 #ifdef DEBUG 514 print_derives(); 515 #endif 516 } 517 518 #ifdef DEBUG 519 void 520 print_derives(void) 521 { 522 int i; 523 Value_t *sp; 524 525 printf("\nDERIVES\n\n"); 526 527 for (i = start_symbol; i < nsyms; i++) 528 { 529 printf("%s derives ", symbol_name[i]); 530 for (sp = derives[i]; *sp >= 0; sp++) 531 { 532 printf(" %d", *sp); 533 } 534 putchar('\n'); 535 } 536 537 putchar('\n'); 538 } 539 #endif 540 541 static void 542 set_nullable(void) 543 { 544 int i, j; 545 int empty; 546 int done_flag; 547 548 nullable = TMALLOC(char, nsyms); 549 NO_SPACE(nullable); 550 551 for (i = 0; i < nsyms; ++i) 552 nullable[i] = 0; 553 554 done_flag = 0; 555 while (!done_flag) 556 { 557 done_flag = 1; 558 for (i = 1; i < nitems; i++) 559 { 560 empty = 1; 561 while ((j = ritem[i]) >= 0) 562 { 563 if (!nullable[j]) 564 empty = 0; 565 ++i; 566 } 567 if (empty) 568 { 569 j = rlhs[-j]; 570 if (!nullable[j]) 571 { 572 nullable[j] = 1; 573 done_flag = 0; 574 } 575 } 576 } 577 } 578 579 #ifdef DEBUG 580 for (i = 0; i < nsyms; i++) 581 { 582 if (nullable[i]) 583 printf("%s is nullable\n", symbol_name[i]); 584 else 585 printf("%s is not nullable\n", symbol_name[i]); 586 } 587 #endif 588 } 589 590 void 591 lr0(void) 592 { 593 set_derives(); 594 set_nullable(); 595 generate_states(); 596 } 597 598 #ifdef NO_LEAKS 599 void 600 lr0_leaks(void) 601 { 602 if (derives) 603 { 604 if (derives[start_symbol] != rules) 605 { 606 DO_FREE(derives[start_symbol]); 607 } 608 DO_FREE(derives); 609 DO_FREE(rules); 610 } 611 DO_FREE(nullable); 612 } 613 #endif 614