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