![[BACK]](/icons/back.gif){kind=icon}
Return to lalr.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / yacc|
Return to lalr.c CVS log | Up to [local] / src / usr.bin / yacc |
1.1 ! deraadt 1: #ifndef lint
! 2: static char rcsid[] = "$Id: lalr.c,v 1.3 1993/08/02 17:56:38 mycroft Exp $";
! 3: #endif /* not lint */
! 4:
! 5: #include "defs.h"
! 6:
! 7: typedef
! 8: struct shorts
! 9: {
! 10: struct shorts *next;
! 11: short value;
! 12: }
! 13: shorts;
! 14:
! 15: int tokensetsize;
! 16: short *lookaheads;
! 17: short *LAruleno;
! 18: unsigned *LA;
! 19: short *accessing_symbol;
! 20: core **state_table;
! 21: shifts **shift_table;
! 22: reductions **reduction_table;
! 23: short *goto_map;
! 24: short *from_state;
! 25: short *to_state;
! 26:
! 27: short **transpose();
! 28:
! 29: static int infinity;
! 30: static int maxrhs;
! 31: static int ngotos;
! 32: static unsigned *F;
! 33: static short **includes;
! 34: static shorts **lookback;
! 35: static short **R;
! 36: static short *INDEX;
! 37: static short *VERTICES;
! 38: static int top;
! 39:
! 40:
! 41: lalr()
! 42: {
! 43: tokensetsize = WORDSIZE(ntokens);
! 44:
! 45: set_state_table();
! 46: set_accessing_symbol();
! 47: set_shift_table();
! 48: set_reduction_table();
! 49: set_maxrhs();
! 50: initialize_LA();
! 51: set_goto_map();
! 52: initialize_F();
! 53: build_relations();
! 54: compute_FOLLOWS();
! 55: compute_lookaheads();
! 56: }
! 57:
! 58:
! 59:
! 60: set_state_table()
! 61: {
! 62: register core *sp;
! 63:
! 64: state_table = NEW2(nstates, core *);
! 65: for (sp = first_state; sp; sp = sp->next)
! 66: state_table[sp->number] = sp;
! 67: }
! 68:
! 69:
! 70:
! 71: set_accessing_symbol()
! 72: {
! 73: register core *sp;
! 74:
! 75: accessing_symbol = NEW2(nstates, short);
! 76: for (sp = first_state; sp; sp = sp->next)
! 77: accessing_symbol[sp->number] = sp->accessing_symbol;
! 78: }
! 79:
! 80:
! 81:
! 82: set_shift_table()
! 83: {
! 84: register shifts *sp;
! 85:
! 86: shift_table = NEW2(nstates, shifts *);
! 87: for (sp = first_shift; sp; sp = sp->next)
! 88: shift_table[sp->number] = sp;
! 89: }
! 90:
! 91:
! 92:
! 93: set_reduction_table()
! 94: {
! 95: register reductions *rp;
! 96:
! 97: reduction_table = NEW2(nstates, reductions *);
! 98: for (rp = first_reduction; rp; rp = rp->next)
! 99: reduction_table[rp->number] = rp;
! 100: }
! 101:
! 102:
! 103:
! 104: set_maxrhs()
! 105: {
! 106: register short *itemp;
! 107: register short *item_end;
! 108: register int length;
! 109: register int max;
! 110:
! 111: length = 0;
! 112: max = 0;
! 113: item_end = ritem + nitems;
! 114: for (itemp = ritem; itemp < item_end; itemp++)
! 115: {
! 116: if (*itemp >= 0)
! 117: {
! 118: length++;
! 119: }
! 120: else
! 121: {
! 122: if (length > max) max = length;
! 123: length = 0;
! 124: }
! 125: }
! 126:
! 127: maxrhs = max;
! 128: }
! 129:
! 130:
! 131:
! 132: initialize_LA()
! 133: {
! 134: register int i, j, k;
! 135: register reductions *rp;
! 136:
! 137: lookaheads = NEW2(nstates + 1, short);
! 138:
! 139: k = 0;
! 140: for (i = 0; i < nstates; i++)
! 141: {
! 142: lookaheads[i] = k;
! 143: rp = reduction_table[i];
! 144: if (rp)
! 145: k += rp->nreds;
! 146: }
! 147: lookaheads[nstates] = k;
! 148:
! 149: LA = NEW2(k * tokensetsize, unsigned);
! 150: LAruleno = NEW2(k, short);
! 151: lookback = NEW2(k, shorts *);
! 152:
! 153: k = 0;
! 154: for (i = 0; i < nstates; i++)
! 155: {
! 156: rp = reduction_table[i];
! 157: if (rp)
! 158: {
! 159: for (j = 0; j < rp->nreds; j++)
! 160: {
! 161: LAruleno[k] = rp->rules[j];
! 162: k++;
! 163: }
! 164: }
! 165: }
! 166: }
! 167:
! 168:
! 169: set_goto_map()
! 170: {
! 171: register shifts *sp;
! 172: register int i;
! 173: register int symbol;
! 174: register int k;
! 175: register short *temp_map;
! 176: register int state2;
! 177: register int state1;
! 178:
! 179: goto_map = NEW2(nvars + 1, short) - ntokens;
! 180: temp_map = NEW2(nvars + 1, short) - ntokens;
! 181:
! 182: ngotos = 0;
! 183: for (sp = first_shift; sp; sp = sp->next)
! 184: {
! 185: for (i = sp->nshifts - 1; i >= 0; i--)
! 186: {
! 187: symbol = accessing_symbol[sp->shift[i]];
! 188:
! 189: if (ISTOKEN(symbol)) break;
! 190:
! 191: if (ngotos == MAXSHORT)
! 192: fatal("too many gotos");
! 193:
! 194: ngotos++;
! 195: goto_map[symbol]++;
! 196: }
! 197: }
! 198:
! 199: k = 0;
! 200: for (i = ntokens; i < nsyms; i++)
! 201: {
! 202: temp_map[i] = k;
! 203: k += goto_map[i];
! 204: }
! 205:
! 206: for (i = ntokens; i < nsyms; i++)
! 207: goto_map[i] = temp_map[i];
! 208:
! 209: goto_map[nsyms] = ngotos;
! 210: temp_map[nsyms] = ngotos;
! 211:
! 212: from_state = NEW2(ngotos, short);
! 213: to_state = NEW2(ngotos, short);
! 214:
! 215: for (sp = first_shift; sp; sp = sp->next)
! 216: {
! 217: state1 = sp->number;
! 218: for (i = sp->nshifts - 1; i >= 0; i--)
! 219: {
! 220: state2 = sp->shift[i];
! 221: symbol = accessing_symbol[state2];
! 222:
! 223: if (ISTOKEN(symbol)) break;
! 224:
! 225: k = temp_map[symbol]++;
! 226: from_state[k] = state1;
! 227: to_state[k] = state2;
! 228: }
! 229: }
! 230:
! 231: FREE(temp_map + ntokens);
! 232: }
! 233:
! 234:
! 235:
! 236: /* Map_goto maps a state/symbol pair into its numeric representation. */
! 237:
! 238: int
! 239: map_goto(state, symbol)
! 240: int state;
! 241: int symbol;
! 242: {
! 243: register int high;
! 244: register int low;
! 245: register int middle;
! 246: register int s;
! 247:
! 248: low = goto_map[symbol];
! 249: high = goto_map[symbol + 1];
! 250:
! 251: for (;;)
! 252: {
! 253: assert(low <= high);
! 254: middle = (low + high) >> 1;
! 255: s = from_state[middle];
! 256: if (s == state)
! 257: return (middle);
! 258: else if (s < state)
! 259: low = middle + 1;
! 260: else
! 261: high = middle - 1;
! 262: }
! 263: }
! 264:
! 265:
! 266:
! 267: initialize_F()
! 268: {
! 269: register int i;
! 270: register int j;
! 271: register int k;
! 272: register shifts *sp;
! 273: register short *edge;
! 274: register unsigned *rowp;
! 275: register short *rp;
! 276: register short **reads;
! 277: register int nedges;
! 278: register int stateno;
! 279: register int symbol;
! 280: register int nwords;
! 281:
! 282: nwords = ngotos * tokensetsize;
! 283: F = NEW2(nwords, unsigned);
! 284:
! 285: reads = NEW2(ngotos, short *);
! 286: edge = NEW2(ngotos + 1, short);
! 287: nedges = 0;
! 288:
! 289: rowp = F;
! 290: for (i = 0; i < ngotos; i++)
! 291: {
! 292: stateno = to_state[i];
! 293: sp = shift_table[stateno];
! 294:
! 295: if (sp)
! 296: {
! 297: k = sp->nshifts;
! 298:
! 299: for (j = 0; j < k; j++)
! 300: {
! 301: symbol = accessing_symbol[sp->shift[j]];
! 302: if (ISVAR(symbol))
! 303: break;
! 304: SETBIT(rowp, symbol);
! 305: }
! 306:
! 307: for (; j < k; j++)
! 308: {
! 309: symbol = accessing_symbol[sp->shift[j]];
! 310: if (nullable[symbol])
! 311: edge[nedges++] = map_goto(stateno, symbol);
! 312: }
! 313:
! 314: if (nedges)
! 315: {
! 316: reads[i] = rp = NEW2(nedges + 1, short);
! 317:
! 318: for (j = 0; j < nedges; j++)
! 319: rp[j] = edge[j];
! 320:
! 321: rp[nedges] = -1;
! 322: nedges = 0;
! 323: }
! 324: }
! 325:
! 326: rowp += tokensetsize;
! 327: }
! 328:
! 329: SETBIT(F, 0);
! 330: digraph(reads);
! 331:
! 332: for (i = 0; i < ngotos; i++)
! 333: {
! 334: if (reads[i])
! 335: FREE(reads[i]);
! 336: }
! 337:
! 338: FREE(reads);
! 339: FREE(edge);
! 340: }
! 341:
! 342:
! 343:
! 344: build_relations()
! 345: {
! 346: register int i;
! 347: register int j;
! 348: register int k;
! 349: register short *rulep;
! 350: register short *rp;
! 351: register shifts *sp;
! 352: register int length;
! 353: register int nedges;
! 354: register int done;
! 355: register int state1;
! 356: register int stateno;
! 357: register int symbol1;
! 358: register int symbol2;
! 359: register short *shortp;
! 360: register short *edge;
! 361: register short *states;
! 362: register short **new_includes;
! 363:
! 364: includes = NEW2(ngotos, short *);
! 365: edge = NEW2(ngotos + 1, short);
! 366: states = NEW2(maxrhs + 1, short);
! 367:
! 368: for (i = 0; i < ngotos; i++)
! 369: {
! 370: nedges = 0;
! 371: state1 = from_state[i];
! 372: symbol1 = accessing_symbol[to_state[i]];
! 373:
! 374: for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
! 375: {
! 376: length = 1;
! 377: states[0] = state1;
! 378: stateno = state1;
! 379:
! 380: for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
! 381: {
! 382: symbol2 = *rp;
! 383: sp = shift_table[stateno];
! 384: k = sp->nshifts;
! 385:
! 386: for (j = 0; j < k; j++)
! 387: {
! 388: stateno = sp->shift[j];
! 389: if (accessing_symbol[stateno] == symbol2) break;
! 390: }
! 391:
! 392: states[length++] = stateno;
! 393: }
! 394:
! 395: add_lookback_edge(stateno, *rulep, i);
! 396:
! 397: length--;
! 398: done = 0;
! 399: while (!done)
! 400: {
! 401: done = 1;
! 402: rp--;
! 403: if (ISVAR(*rp))
! 404: {
! 405: stateno = states[--length];
! 406: edge[nedges++] = map_goto(stateno, *rp);
! 407: if (nullable[*rp] && length > 0) done = 0;
! 408: }
! 409: }
! 410: }
! 411:
! 412: if (nedges)
! 413: {
! 414: includes[i] = shortp = NEW2(nedges + 1, short);
! 415: for (j = 0; j < nedges; j++)
! 416: shortp[j] = edge[j];
! 417: shortp[nedges] = -1;
! 418: }
! 419: }
! 420:
! 421: new_includes = transpose(includes, ngotos);
! 422:
! 423: for (i = 0; i < ngotos; i++)
! 424: if (includes[i])
! 425: FREE(includes[i]);
! 426:
! 427: FREE(includes);
! 428:
! 429: includes = new_includes;
! 430:
! 431: FREE(edge);
! 432: FREE(states);
! 433: }
! 434:
! 435:
! 436: add_lookback_edge(stateno, ruleno, gotono)
! 437: int stateno, ruleno, gotono;
! 438: {
! 439: register int i, k;
! 440: register int found;
! 441: register shorts *sp;
! 442:
! 443: i = lookaheads[stateno];
! 444: k = lookaheads[stateno + 1];
! 445: found = 0;
! 446: while (!found && i < k)
! 447: {
! 448: if (LAruleno[i] == ruleno)
! 449: found = 1;
! 450: else
! 451: ++i;
! 452: }
! 453: assert(found);
! 454:
! 455: sp = NEW(shorts);
! 456: sp->next = lookback[i];
! 457: sp->value = gotono;
! 458: lookback[i] = sp;
! 459: }
! 460:
! 461:
! 462:
! 463: short **
! 464: transpose(R, n)
! 465: short **R;
! 466: int n;
! 467: {
! 468: register short **new_R;
! 469: register short **temp_R;
! 470: register short *nedges;
! 471: register short *sp;
! 472: register int i;
! 473: register int k;
! 474:
! 475: nedges = NEW2(n, short);
! 476:
! 477: for (i = 0; i < n; i++)
! 478: {
! 479: sp = R[i];
! 480: if (sp)
! 481: {
! 482: while (*sp >= 0)
! 483: nedges[*sp++]++;
! 484: }
! 485: }
! 486:
! 487: new_R = NEW2(n, short *);
! 488: temp_R = NEW2(n, short *);
! 489:
! 490: for (i = 0; i < n; i++)
! 491: {
! 492: k = nedges[i];
! 493: if (k > 0)
! 494: {
! 495: sp = NEW2(k + 1, short);
! 496: new_R[i] = sp;
! 497: temp_R[i] = sp;
! 498: sp[k] = -1;
! 499: }
! 500: }
! 501:
! 502: FREE(nedges);
! 503:
! 504: for (i = 0; i < n; i++)
! 505: {
! 506: sp = R[i];
! 507: if (sp)
! 508: {
! 509: while (*sp >= 0)
! 510: *temp_R[*sp++]++ = i;
! 511: }
! 512: }
! 513:
! 514: FREE(temp_R);
! 515:
! 516: return (new_R);
! 517: }
! 518:
! 519:
! 520:
! 521: compute_FOLLOWS()
! 522: {
! 523: digraph(includes);
! 524: }
! 525:
! 526:
! 527: compute_lookaheads()
! 528: {
! 529: register int i, n;
! 530: register unsigned *fp1, *fp2, *fp3;
! 531: register shorts *sp, *next;
! 532: register unsigned *rowp;
! 533:
! 534: rowp = LA;
! 535: n = lookaheads[nstates];
! 536: for (i = 0; i < n; i++)
! 537: {
! 538: fp3 = rowp + tokensetsize;
! 539: for (sp = lookback[i]; sp; sp = sp->next)
! 540: {
! 541: fp1 = rowp;
! 542: fp2 = F + tokensetsize * sp->value;
! 543: while (fp1 < fp3)
! 544: *fp1++ |= *fp2++;
! 545: }
! 546: rowp = fp3;
! 547: }
! 548:
! 549: for (i = 0; i < n; i++)
! 550: for (sp = lookback[i]; sp; sp = next)
! 551: {
! 552: next = sp->next;
! 553: FREE(sp);
! 554: }
! 555:
! 556: FREE(lookback);
! 557: FREE(F);
! 558: }
! 559:
! 560:
! 561: digraph(relation)
! 562: short **relation;
! 563: {
! 564: register int i;
! 565:
! 566: infinity = ngotos + 2;
! 567: INDEX = NEW2(ngotos + 1, short);
! 568: VERTICES = NEW2(ngotos + 1, short);
! 569: top = 0;
! 570:
! 571: R = relation;
! 572:
! 573: for (i = 0; i < ngotos; i++)
! 574: INDEX[i] = 0;
! 575:
! 576: for (i = 0; i < ngotos; i++)
! 577: {
! 578: if (INDEX[i] == 0 && R[i])
! 579: traverse(i);
! 580: }
! 581:
! 582: FREE(INDEX);
! 583: FREE(VERTICES);
! 584: }
! 585:
! 586:
! 587:
! 588: traverse(i)
! 589: register int i;
! 590: {
! 591: register unsigned *fp1;
! 592: register unsigned *fp2;
! 593: register unsigned *fp3;
! 594: register int j;
! 595: register short *rp;
! 596:
! 597: int height;
! 598: unsigned *base;
! 599:
! 600: VERTICES[++top] = i;
! 601: INDEX[i] = height = top;
! 602:
! 603: base = F + i * tokensetsize;
! 604: fp3 = base + tokensetsize;
! 605:
! 606: rp = R[i];
! 607: if (rp)
! 608: {
! 609: while ((j = *rp++) >= 0)
! 610: {
! 611: if (INDEX[j] == 0)
! 612: traverse(j);
! 613:
! 614: if (INDEX[i] > INDEX[j])
! 615: INDEX[i] = INDEX[j];
! 616:
! 617: fp1 = base;
! 618: fp2 = F + j * tokensetsize;
! 619:
! 620: while (fp1 < fp3)
! 621: *fp1++ |= *fp2++;
! 622: }
! 623: }
! 624:
! 625: if (INDEX[i] == height)
! 626: {
! 627: for (;;)
! 628: {
! 629: j = VERTICES[top--];
! 630: INDEX[j] = infinity;
! 631:
! 632: if (i == j)
! 633: break;
! 634:
! 635: fp1 = base;
! 636: fp2 = F + j * tokensetsize;
! 637:
! 638: while (fp1 < fp3)
! 639: *fp2++ = *fp1++;
! 640: }
! 641: }
! 642: }