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