![[BACK]](/icons/back.gif){kind=icon}
Return to lr0.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / yacc|
Return to lr0.c CVS log | Up to [local] / src / usr.bin / yacc |
1.1 ! deraadt 1: #ifndef lint
! 2: static char rcsid[] = "$Id: lr0.c,v 1.3 1993/08/02 17:56:39 mycroft Exp $";
! 3: #endif /* not lint */
! 4:
! 5: #include "defs.h"
! 6:
! 7: extern short *itemset;
! 8: extern short *itemsetend;
! 9: extern unsigned *ruleset;
! 10:
! 11: int nstates;
! 12: core *first_state;
! 13: shifts *first_shift;
! 14: reductions *first_reduction;
! 15:
! 16: int get_state();
! 17: core *new_state();
! 18:
! 19: static core **state_set;
! 20: static core *this_state;
! 21: static core *last_state;
! 22: static shifts *last_shift;
! 23: static reductions *last_reduction;
! 24:
! 25: static int nshifts;
! 26: static short *shift_symbol;
! 27:
! 28: static short *redset;
! 29: static short *shiftset;
! 30:
! 31: static short **kernel_base;
! 32: static short **kernel_end;
! 33: static short *kernel_items;
! 34:
! 35:
! 36: allocate_itemsets()
! 37: {
! 38: register short *itemp;
! 39: register short *item_end;
! 40: register int symbol;
! 41: register int i;
! 42: register int count;
! 43: register int max;
! 44: register short *symbol_count;
! 45:
! 46: count = 0;
! 47: symbol_count = NEW2(nsyms, short);
! 48:
! 49: item_end = ritem + nitems;
! 50: for (itemp = ritem; itemp < item_end; itemp++)
! 51: {
! 52: symbol = *itemp;
! 53: if (symbol >= 0)
! 54: {
! 55: count++;
! 56: symbol_count[symbol]++;
! 57: }
! 58: }
! 59:
! 60: kernel_base = NEW2(nsyms, short *);
! 61: kernel_items = NEW2(count, short);
! 62:
! 63: count = 0;
! 64: max = 0;
! 65: for (i = 0; i < nsyms; i++)
! 66: {
! 67: kernel_base[i] = kernel_items + count;
! 68: count += symbol_count[i];
! 69: if (max < symbol_count[i])
! 70: max = symbol_count[i];
! 71: }
! 72:
! 73: shift_symbol = symbol_count;
! 74: kernel_end = NEW2(nsyms, short *);
! 75: }
! 76:
! 77:
! 78: allocate_storage()
! 79: {
! 80: allocate_itemsets();
! 81: shiftset = NEW2(nsyms, short);
! 82: redset = NEW2(nrules + 1, short);
! 83: state_set = NEW2(nitems, core *);
! 84: }
! 85:
! 86:
! 87: append_states()
! 88: {
! 89: register int i;
! 90: register int j;
! 91: register int symbol;
! 92:
! 93: #ifdef TRACE
! 94: fprintf(stderr, "Entering append_states()\n");
! 95: #endif
! 96: for (i = 1; i < nshifts; i++)
! 97: {
! 98: symbol = shift_symbol[i];
! 99: j = i;
! 100: while (j > 0 && shift_symbol[j - 1] > symbol)
! 101: {
! 102: shift_symbol[j] = shift_symbol[j - 1];
! 103: j--;
! 104: }
! 105: shift_symbol[j] = symbol;
! 106: }
! 107:
! 108: for (i = 0; i < nshifts; i++)
! 109: {
! 110: symbol = shift_symbol[i];
! 111: shiftset[i] = get_state(symbol);
! 112: }
! 113: }
! 114:
! 115:
! 116: free_storage()
! 117: {
! 118: FREE(shift_symbol);
! 119: FREE(redset);
! 120: FREE(shiftset);
! 121: FREE(kernel_base);
! 122: FREE(kernel_end);
! 123: FREE(kernel_items);
! 124: FREE(state_set);
! 125: }
! 126:
! 127:
! 128:
! 129: generate_states()
! 130: {
! 131: allocate_storage();
! 132: itemset = NEW2(nitems, short);
! 133: ruleset = NEW2(WORDSIZE(nrules), unsigned);
! 134: set_first_derives();
! 135: initialize_states();
! 136:
! 137: while (this_state)
! 138: {
! 139: closure(this_state->items, this_state->nitems);
! 140: save_reductions();
! 141: new_itemsets();
! 142: append_states();
! 143:
! 144: if (nshifts > 0)
! 145: save_shifts();
! 146:
! 147: this_state = this_state->next;
! 148: }
! 149:
! 150: finalize_closure();
! 151: free_storage();
! 152: }
! 153:
! 154:
! 155:
! 156: int
! 157: get_state(symbol)
! 158: int symbol;
! 159: {
! 160: register int key;
! 161: register short *isp1;
! 162: register short *isp2;
! 163: register short *iend;
! 164: register core *sp;
! 165: register int found;
! 166: register 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 = 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:
! 220:
! 221: initialize_states()
! 222: {
! 223: register int i;
! 224: register short *start_derives;
! 225: register core *p;
! 226:
! 227: start_derives = derives[start_symbol];
! 228: for (i = 0; start_derives[i] >= 0; ++i)
! 229: continue;
! 230:
! 231: p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
! 232: if (p == 0) no_space();
! 233:
! 234: p->next = 0;
! 235: p->link = 0;
! 236: p->number = 0;
! 237: p->accessing_symbol = 0;
! 238: p->nitems = i;
! 239:
! 240: for (i = 0; start_derives[i] >= 0; ++i)
! 241: p->items[i] = rrhs[start_derives[i]];
! 242:
! 243: first_state = last_state = this_state = p;
! 244: nstates = 1;
! 245: }
! 246:
! 247:
! 248: new_itemsets()
! 249: {
! 250: register int i;
! 251: register int shiftcount;
! 252: register short *isp;
! 253: register short *ksp;
! 254: register int symbol;
! 255:
! 256: for (i = 0; i < nsyms; i++)
! 257: kernel_end[i] = 0;
! 258:
! 259: shiftcount = 0;
! 260: isp = itemset;
! 261: while (isp < itemsetend)
! 262: {
! 263: i = *isp++;
! 264: symbol = ritem[i];
! 265: if (symbol > 0)
! 266: {
! 267: ksp = kernel_end[symbol];
! 268: if (!ksp)
! 269: {
! 270: shift_symbol[shiftcount++] = symbol;
! 271: ksp = kernel_base[symbol];
! 272: }
! 273:
! 274: *ksp++ = i + 1;
! 275: kernel_end[symbol] = ksp;
! 276: }
! 277: }
! 278:
! 279: nshifts = shiftcount;
! 280: }
! 281:
! 282:
! 283:
! 284: core *
! 285: new_state(symbol)
! 286: int symbol;
! 287: {
! 288: register int n;
! 289: register core *p;
! 290: register short *isp1;
! 291: register short *isp2;
! 292: register 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 = iend - isp1;
! 304:
! 305: p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
! 306: p->accessing_symbol = symbol;
! 307: p->number = nstates;
! 308: p->nitems = 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:
! 323: /* show_cores is used for debugging */
! 324:
! 325: show_cores()
! 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) printf("\n");
! 335: printf("state %d, number = %d, accessing symbol = %s\n",
! 336: k, p->number, symbol_name[p->accessing_symbol]);
! 337: n = p->nitems;
! 338: for (i = 0; i < n; ++i)
! 339: {
! 340: itemno = p->items[i];
! 341: printf("%4d ", itemno);
! 342: j = itemno;
! 343: while (ritem[j] >= 0) ++j;
! 344: printf("%s :", symbol_name[rlhs[-ritem[j]]]);
! 345: j = rrhs[-ritem[j]];
! 346: while (j < itemno)
! 347: printf(" %s", symbol_name[ritem[j++]]);
! 348: printf(" .");
! 349: while (ritem[j] >= 0)
! 350: printf(" %s", symbol_name[ritem[j++]]);
! 351: printf("\n");
! 352: fflush(stdout);
! 353: }
! 354: }
! 355: }
! 356:
! 357:
! 358: /* show_ritems is used for debugging */
! 359:
! 360: show_ritems()
! 361: {
! 362: int i;
! 363:
! 364: for (i = 0; i < nitems; ++i)
! 365: printf("ritem[%d] = %d\n", i, ritem[i]);
! 366: }
! 367:
! 368:
! 369: /* show_rrhs is used for debugging */
! 370: show_rrhs()
! 371: {
! 372: int i;
! 373:
! 374: for (i = 0; i < nrules; ++i)
! 375: printf("rrhs[%d] = %d\n", i, rrhs[i]);
! 376: }
! 377:
! 378:
! 379: /* show_shifts is used for debugging */
! 380:
! 381: show_shifts()
! 382: {
! 383: shifts *p;
! 384: int i, j, k;
! 385:
! 386: k = 0;
! 387: for (p = first_shift; p; ++k, p = p->next)
! 388: {
! 389: if (k) printf("\n");
! 390: printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
! 391: p->nshifts);
! 392: j = p->nshifts;
! 393: for (i = 0; i < j; ++i)
! 394: printf("\t%d\n", p->shift[i]);
! 395: }
! 396: }
! 397:
! 398:
! 399: save_shifts()
! 400: {
! 401: register shifts *p;
! 402: register short *sp1;
! 403: register short *sp2;
! 404: register short *send;
! 405:
! 406: p = (shifts *) allocate((unsigned) (sizeof(shifts) +
! 407: (nshifts - 1) * sizeof(short)));
! 408:
! 409: p->number = this_state->number;
! 410: p->nshifts = 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:
! 432:
! 433: save_reductions()
! 434: {
! 435: register short *isp;
! 436: register short *rp1;
! 437: register short *rp2;
! 438: register int item;
! 439: register int count;
! 440: register reductions *p;
! 441: register short *rend;
! 442:
! 443: count = 0;
! 444: for (isp = itemset; isp < itemsetend; isp++)
! 445: {
! 446: item = ritem[*isp];
! 447: if (item < 0)
! 448: {
! 449: redset[count++] = -item;
! 450: }
! 451: }
! 452:
! 453: if (count)
! 454: {
! 455: p = (reductions *) allocate((unsigned) (sizeof(reductions) +
! 456: (count - 1) * sizeof(short)));
! 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:
! 482: set_derives()
! 483: {
! 484: register int i, k;
! 485: register int lhs;
! 486: register short *rules;
! 487:
! 488: derives = NEW2(nsyms, short *);
! 489: rules = NEW2(nvars + nrules, short);
! 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: free_derives()
! 513: {
! 514: FREE(derives[start_symbol]);
! 515: FREE(derives);
! 516: }
! 517:
! 518: #ifdef DEBUG
! 519: print_derives()
! 520: {
! 521: register int i;
! 522: register short *sp;
! 523:
! 524: printf("\nDERIVES\n\n");
! 525:
! 526: for (i = start_symbol; i < nsyms; i++)
! 527: {
! 528: printf("%s derives ", symbol_name[i]);
! 529: for (sp = derives[i]; *sp >= 0; sp++)
! 530: {
! 531: printf(" %d", *sp);
! 532: }
! 533: putchar('\n');
! 534: }
! 535:
! 536: putchar('\n');
! 537: }
! 538: #endif
! 539:
! 540:
! 541: set_nullable()
! 542: {
! 543: register int i, j;
! 544: register int empty;
! 545: int done;
! 546:
! 547: nullable = MALLOC(nsyms);
! 548: if (nullable == 0) no_space();
! 549:
! 550: for (i = 0; i < nsyms; ++i)
! 551: nullable[i] = 0;
! 552:
! 553: done = 0;
! 554: while (!done)
! 555: {
! 556: done = 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 = 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:
! 590: free_nullable()
! 591: {
! 592: FREE(nullable);
! 593: }
! 594:
! 595:
! 596: lr0()
! 597: {
! 598: set_derives();
! 599: set_nullable();
! 600: generate_states();
! 601: }