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