1 /* $Id: lr0.c,v 1.13 2012/05/26 00:40:47 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 short *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 short *itemp; 44 short *item_end; 45 int symbol; 46 int i; 47 int count; 48 int max; 49 short *symbol_count; 50 51 count = 0; 52 symbol_count = NEW2(nsyms, short); 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, short *); 66 kernel_items = NEW2(count, short); 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, short *); 80 } 81 82 static void 83 allocate_storage(void) 84 { 85 allocate_itemsets(); 86 shiftset = NEW2(nsyms, short); 87 redset = NEW2(nrules + 1, short); 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, short); 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 short *isp1; 162 short *isp2; 163 short *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 short *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(short)); 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 short *isp; 252 short *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 short *isp1; 287 short *isp2; 288 short *iend; 289 290 #ifdef TRACE 291 fprintf(stderr, "Entering new_state(%d)\n", symbol); 292 #endif 293 294 if (nstates >= MAXSHORT) 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(short))); 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 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 397 static void 398 save_shifts(void) 399 { 400 shifts *p; 401 short *sp1; 402 short *sp2; 403 short *send; 404 405 p = (shifts *)allocate((sizeof(shifts) + 406 (unsigned)(nshifts - 1) * sizeof(short))); 407 408 p->number = this_state->number; 409 p->nshifts = (Value_t) nshifts; 410 411 sp1 = shiftset; 412 sp2 = p->shift; 413 send = shiftset + nshifts; 414 415 while (sp1 < send) 416 *sp2++ = *sp1++; 417 418 if (last_shift) 419 { 420 last_shift->next = p; 421 last_shift = p; 422 } 423 else 424 { 425 first_shift = p; 426 last_shift = p; 427 } 428 } 429 430 static void 431 save_reductions(void) 432 { 433 short *isp; 434 short *rp1; 435 short *rp2; 436 int item; 437 Value_t count; 438 reductions *p; 439 short *rend; 440 441 count = 0; 442 for (isp = itemset; isp < itemsetend; isp++) 443 { 444 item = ritem[*isp]; 445 if (item < 0) 446 { 447 redset[count++] = (Value_t) - item; 448 } 449 } 450 451 if (count) 452 { 453 p = (reductions *)allocate((sizeof(reductions) + 454 (unsigned)(count - 1) * 455 sizeof(short))); 456 457 p->number = this_state->number; 458 p->nreds = count; 459 460 rp1 = redset; 461 rp2 = p->rules; 462 rend = rp1 + count; 463 464 while (rp1 < rend) 465 *rp2++ = *rp1++; 466 467 if (last_reduction) 468 { 469 last_reduction->next = p; 470 last_reduction = p; 471 } 472 else 473 { 474 first_reduction = p; 475 last_reduction = p; 476 } 477 } 478 } 479 480 static void 481 set_derives(void) 482 { 483 Value_t i, k; 484 int lhs; 485 short *rules; 486 487 derives = NEW2(nsyms, short *); 488 rules = NEW2(nvars + nrules, short); 489 490 k = 0; 491 for (lhs = start_symbol; lhs < nsyms; lhs++) 492 { 493 derives[lhs] = rules + k; 494 for (i = 0; i < nrules; i++) 495 { 496 if (rlhs[i] == lhs) 497 { 498 rules[k] = i; 499 k++; 500 } 501 } 502 rules[k] = -1; 503 k++; 504 } 505 506 #ifdef DEBUG 507 print_derives(); 508 #endif 509 } 510 511 #ifdef DEBUG 512 void 513 print_derives(void) 514 { 515 int i; 516 short *sp; 517 518 printf("\nDERIVES\n\n"); 519 520 for (i = start_symbol; i < nsyms; i++) 521 { 522 printf("%s derives ", symbol_name[i]); 523 for (sp = derives[i]; *sp >= 0; sp++) 524 { 525 printf(" %d", *sp); 526 } 527 putchar('\n'); 528 } 529 530 putchar('\n'); 531 } 532 #endif 533 534 static void 535 set_nullable(void) 536 { 537 int i, j; 538 int empty; 539 int done_flag; 540 541 nullable = TMALLOC(char, nsyms); 542 NO_SPACE(nullable); 543 544 for (i = 0; i < nsyms; ++i) 545 nullable[i] = 0; 546 547 done_flag = 0; 548 while (!done_flag) 549 { 550 done_flag = 1; 551 for (i = 1; i < nitems; i++) 552 { 553 empty = 1; 554 while ((j = ritem[i]) >= 0) 555 { 556 if (!nullable[j]) 557 empty = 0; 558 ++i; 559 } 560 if (empty) 561 { 562 j = rlhs[-j]; 563 if (!nullable[j]) 564 { 565 nullable[j] = 1; 566 done_flag = 0; 567 } 568 } 569 } 570 } 571 572 #ifdef DEBUG 573 for (i = 0; i < nsyms; i++) 574 { 575 if (nullable[i]) 576 printf("%s is nullable\n", symbol_name[i]); 577 else 578 printf("%s is not nullable\n", symbol_name[i]); 579 } 580 #endif 581 } 582 583 void 584 lr0(void) 585 { 586 set_derives(); 587 set_nullable(); 588 generate_states(); 589 } 590 591 #ifdef NO_LEAKS 592 void 593 lr0_leaks(void) 594 { 595 DO_FREE(derives[start_symbol]); 596 DO_FREE(derives); 597 DO_FREE(nullable); 598 } 599 #endif 600