1/* $NetBSD: lr0.c,v 1.6 2011/09/10 21:29:04 christos Exp $ */ 2/* Id: lr0.c,v 1.12 2010/06/09 08:53:17 tom Exp */ 3 4#include "defs.h" 5 6#include <sys/cdefs.h> 7__RCSID("$NetBSD: lr0.c,v 1.6 2011/09/10 21:29:04 christos Exp $"); 8 9static core *new_state(int symbol); 10static Value_t get_state(int symbol); 11static void allocate_itemsets(void); 12static void allocate_storage(void); 13static void append_states(void); 14static void free_storage(void); 15static void generate_states(void); 16static void initialize_states(void); 17static void new_itemsets(void); 18static void save_reductions(void); 19static void save_shifts(void); 20static void set_derives(void); 21static void set_nullable(void); 22 23int nstates; 24core *first_state; 25shifts *first_shift; 26reductions *first_reduction; 27 28static core **state_set; 29static core *this_state; 30static core *last_state; 31static shifts *last_shift; 32static reductions *last_reduction; 33 34static int nshifts; 35static short *shift_symbol; 36 37static Value_t *redset; 38static Value_t *shiftset; 39 40static Value_t **kernel_base; 41static Value_t **kernel_end; 42static Value_t *kernel_items; 43 44static void 45allocate_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 86static void 87allocate_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 95static void 96append_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 124static void 125free_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 136static void 137generate_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 161static Value_t 162get_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 223static void 224initialize_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 250static void 251new_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 285static core * 286new_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 324void 325show_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 361void 362show_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 */ 371void 372show_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 382void 383show_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 401static void 402save_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 434static void 435save_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 484static void 485set_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 516void 517print_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 538static void 539set_nullable(void) 540{ 541 int i, j; 542 int empty; 543 int done_flag; 544 545 nullable = MALLOC(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 587void 588lr0(void) 589{ 590 set_derives(); 591 set_nullable(); 592 generate_states(); 593} 594 595#ifdef NO_LEAKS 596void 597lr0_leaks(void) 598{ 599 DO_FREE(derives[start_symbol]); 600 DO_FREE(derives); 601 DO_FREE(nullable); 602} 603#endif 604