1 /* $NetBSD: lr0.c,v 1.2 2009/10/29 00:56:20 christos Exp $ */ 2 /* Id: lr0.c,v 1.9 2009/10/27 09:20:39 tom Exp */ 3 4 #include "defs.h" 5 6 #include <sys/cdefs.h> 7 __RCSID("$NetBSD: lr0.c,v 1.2 2009/10/29 00:56:20 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 = 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 if (p == 0) 236 no_space(); 237 238 p->next = 0; 239 p->link = 0; 240 p->number = 0; 241 p->accessing_symbol = 0; 242 p->nitems = (Value_t) i; 243 244 for (i = 0; start_derives[i] >= 0; ++i) 245 p->items[i] = rrhs[start_derives[i]]; 246 247 first_state = last_state = this_state = p; 248 nstates = 1; 249 } 250 251 static void 252 new_itemsets(void) 253 { 254 Value_t i; 255 int shiftcount; 256 short *isp; 257 short *ksp; 258 Value_t symbol; 259 260 for (i = 0; i < nsyms; i++) 261 kernel_end[i] = 0; 262 263 shiftcount = 0; 264 isp = itemset; 265 while (isp < itemsetend) 266 { 267 i = *isp++; 268 symbol = ritem[i]; 269 if (symbol > 0) 270 { 271 ksp = kernel_end[symbol]; 272 if (!ksp) 273 { 274 shift_symbol[shiftcount++] = symbol; 275 ksp = kernel_base[symbol]; 276 } 277 278 *ksp++ = (Value_t) (i + 1); 279 kernel_end[symbol] = ksp; 280 } 281 } 282 283 nshifts = shiftcount; 284 } 285 286 static core * 287 new_state(int symbol) 288 { 289 unsigned n; 290 core *p; 291 short *isp1; 292 short *isp2; 293 short *iend; 294 295 #ifdef TRACE 296 fprintf(stderr, "Entering new_state(%d)\n", symbol); 297 #endif 298 299 if (nstates >= MAXSHORT) 300 fatal("too many states"); 301 302 isp1 = kernel_base[symbol]; 303 iend = kernel_end[symbol]; 304 n = (unsigned)(iend - isp1); 305 306 p = (core *)allocate((unsigned)(sizeof(core) + (n - 1) * sizeof(short))); 307 p->accessing_symbol = (Value_t) symbol; 308 p->number = (Value_t) nstates; 309 p->nitems = (Value_t) n; 310 311 isp2 = p->items; 312 while (isp1 < iend) 313 *isp2++ = *isp1++; 314 315 last_state->next = p; 316 last_state = p; 317 318 nstates++; 319 320 return (p); 321 } 322 323 /* show_cores is used for debugging */ 324 325 void 326 show_cores(void) 327 { 328 core *p; 329 int i, j, k, n; 330 int itemno; 331 332 k = 0; 333 for (p = first_state; p; ++k, p = p->next) 334 { 335 if (k) 336 printf("\n"); 337 printf("state %d, number = %d, accessing symbol = %s\n", 338 k, p->number, symbol_name[p->accessing_symbol]); 339 n = p->nitems; 340 for (i = 0; i < n; ++i) 341 { 342 itemno = p->items[i]; 343 printf("%4d ", itemno); 344 j = itemno; 345 while (ritem[j] >= 0) 346 ++j; 347 printf("%s :", symbol_name[rlhs[-ritem[j]]]); 348 j = rrhs[-ritem[j]]; 349 while (j < itemno) 350 printf(" %s", symbol_name[ritem[j++]]); 351 printf(" ."); 352 while (ritem[j] >= 0) 353 printf(" %s", symbol_name[ritem[j++]]); 354 printf("\n"); 355 fflush(stdout); 356 } 357 } 358 } 359 360 /* show_ritems is used for debugging */ 361 362 void 363 show_ritems(void) 364 { 365 int i; 366 367 for (i = 0; i < nitems; ++i) 368 printf("ritem[%d] = %d\n", i, ritem[i]); 369 } 370 371 /* show_rrhs is used for debugging */ 372 void 373 show_rrhs(void) 374 { 375 int i; 376 377 for (i = 0; i < nrules; ++i) 378 printf("rrhs[%d] = %d\n", i, rrhs[i]); 379 } 380 381 /* show_shifts is used for debugging */ 382 383 void 384 show_shifts(void) 385 { 386 shifts *p; 387 int i, j, k; 388 389 k = 0; 390 for (p = first_shift; p; ++k, p = p->next) 391 { 392 if (k) 393 printf("\n"); 394 printf("shift %d, number = %d, nshifts = %d\n", k, p->number, 395 p->nshifts); 396 j = p->nshifts; 397 for (i = 0; i < j; ++i) 398 printf("\t%d\n", p->shift[i]); 399 } 400 } 401 402 static void 403 save_shifts(void) 404 { 405 shifts *p; 406 short *sp1; 407 short *sp2; 408 short *send; 409 410 p = (shifts *)allocate((unsigned)(sizeof(shifts) + 411 (unsigned)(nshifts - 1) * sizeof(short))); 412 413 p->number = this_state->number; 414 p->nshifts = (Value_t) nshifts; 415 416 sp1 = shiftset; 417 sp2 = p->shift; 418 send = shiftset + nshifts; 419 420 while (sp1 < send) 421 *sp2++ = *sp1++; 422 423 if (last_shift) 424 { 425 last_shift->next = p; 426 last_shift = p; 427 } 428 else 429 { 430 first_shift = p; 431 last_shift = p; 432 } 433 } 434 435 static void 436 save_reductions(void) 437 { 438 short *isp; 439 short *rp1; 440 short *rp2; 441 int item; 442 Value_t count; 443 reductions *p; 444 short *rend; 445 446 count = 0; 447 for (isp = itemset; isp < itemsetend; isp++) 448 { 449 item = ritem[*isp]; 450 if (item < 0) 451 { 452 redset[count++] = (Value_t) - item; 453 } 454 } 455 456 if (count) 457 { 458 p = (reductions *)allocate((unsigned)(sizeof(reductions) + 459 (unsigned)(count - 1) * 460 sizeof(short))); 461 462 p->number = this_state->number; 463 p->nreds = count; 464 465 rp1 = redset; 466 rp2 = p->rules; 467 rend = rp1 + count; 468 469 while (rp1 < rend) 470 *rp2++ = *rp1++; 471 472 if (last_reduction) 473 { 474 last_reduction->next = p; 475 last_reduction = p; 476 } 477 else 478 { 479 first_reduction = p; 480 last_reduction = p; 481 } 482 } 483 } 484 485 static void 486 set_derives(void) 487 { 488 Value_t i, k; 489 int lhs; 490 short *rules; 491 492 derives = NEW2(nsyms, short *); 493 rules = NEW2(nvars + nrules, short); 494 495 k = 0; 496 for (lhs = start_symbol; lhs < nsyms; lhs++) 497 { 498 derives[lhs] = rules + k; 499 for (i = 0; i < nrules; i++) 500 { 501 if (rlhs[i] == lhs) 502 { 503 rules[k] = i; 504 k++; 505 } 506 } 507 rules[k] = -1; 508 k++; 509 } 510 511 #ifdef DEBUG 512 print_derives(); 513 #endif 514 } 515 516 #ifdef DEBUG 517 void 518 print_derives(void) 519 { 520 int i; 521 short *sp; 522 523 printf("\nDERIVES\n\n"); 524 525 for (i = start_symbol; i < nsyms; i++) 526 { 527 printf("%s derives ", symbol_name[i]); 528 for (sp = derives[i]; *sp >= 0; sp++) 529 { 530 printf(" %d", *sp); 531 } 532 putchar('\n'); 533 } 534 535 putchar('\n'); 536 } 537 #endif 538 539 static void 540 set_nullable(void) 541 { 542 int i, j; 543 int empty; 544 int done_flag; 545 546 nullable = MALLOC(nsyms); 547 if (nullable == 0) 548 no_space(); 549 550 for (i = 0; i < nsyms; ++i) 551 nullable[i] = 0; 552 553 done_flag = 0; 554 while (!done_flag) 555 { 556 done_flag = 1; 557 for (i = 1; i < nitems; i++) 558 { 559 empty = 1; 560 while ((j = ritem[i]) >= 0) 561 { 562 if (!nullable[j]) 563 empty = 0; 564 ++i; 565 } 566 if (empty) 567 { 568 j = rlhs[-j]; 569 if (!nullable[j]) 570 { 571 nullable[j] = 1; 572 done_flag = 0; 573 } 574 } 575 } 576 } 577 578 #ifdef DEBUG 579 for (i = 0; i < nsyms; i++) 580 { 581 if (nullable[i]) 582 printf("%s is nullable\n", symbol_name[i]); 583 else 584 printf("%s is not nullable\n", symbol_name[i]); 585 } 586 #endif 587 } 588 589 void 590 lr0(void) 591 { 592 set_derives(); 593 set_nullable(); 594 generate_states(); 595 } 596 597 #ifdef NO_LEAKS 598 void 599 lr0_leaks(void) 600 { 601 DO_FREE(derives[start_symbol]); 602 DO_FREE(derives); 603 DO_FREE(nullable); 604 } 605 #endif 606