Annotation of src/usr.bin/yacc/lalr.c, Revision 1.15
1.15 ! tedu 1: /* $OpenBSD: lalr.c,v 1.14 2014/01/10 11:19:31 sthen Exp $ */
1.2 deraadt 2: /* $NetBSD: lalr.c,v 1.4 1996/03/19 03:21:33 jtc Exp $ */
3:
4: /*
5: * Copyright (c) 1989 The Regents of the University of California.
6: * All rights reserved.
7: *
8: * This code is derived from software contributed to Berkeley by
9: * Robert Paul Corbett.
10: *
11: * Redistribution and use in source and binary forms, with or without
12: * modification, are permitted provided that the following conditions
13: * are met:
14: * 1. Redistributions of source code must retain the above copyright
15: * notice, this list of conditions and the following disclaimer.
16: * 2. Redistributions in binary form must reproduce the above copyright
17: * notice, this list of conditions and the following disclaimer in the
18: * documentation and/or other materials provided with the distribution.
1.7 millert 19: * 3. Neither the name of the University nor the names of its contributors
1.2 deraadt 20: * may be used to endorse or promote products derived from this software
21: * without specific prior written permission.
22: *
23: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33: * SUCH DAMAGE.
34: */
1.1 deraadt 35:
36: #include "defs.h"
37:
1.15 ! tedu 38: typedef struct shorts {
! 39: struct shorts *next;
! 40: short value;
! 41: } shorts;
1.1 deraadt 42:
43: int tokensetsize;
44: short *lookaheads;
45: short *LAruleno;
46: unsigned *LA;
47: short *accessing_symbol;
48: core **state_table;
49: shifts **shift_table;
50: reductions **reduction_table;
51: short *goto_map;
52: short *from_state;
53: short *to_state;
54:
55: short **transpose();
1.6 millert 56: void set_state_table(void);
57: void set_accessing_symbol(void);
58: void set_shift_table(void);
59: void set_reduction_table(void);
60: void set_maxrhs(void);
61: void initialize_LA(void);
62: void set_goto_map(void);
63: void initialize_F(void);
64: void build_relations(void);
65: void compute_FOLLOWS(void);
66: void compute_lookaheads(void);
67: int map_goto(int, int);
68: void digraph(short **);
69: void add_lookback_edge(int, int, int);
70: void traverse(int);
1.1 deraadt 71:
72: static int infinity;
73: static int maxrhs;
74: static int ngotos;
75: static unsigned *F;
76: static short **includes;
77: static shorts **lookback;
78: static short **R;
79: static short *INDEX;
80: static short *VERTICES;
81: static int top;
82:
1.4 pvalchev 83: void
1.8 pvalchev 84: lalr(void)
1.1 deraadt 85: {
1.15 ! tedu 86: tokensetsize = WORDSIZE(ntokens);
1.1 deraadt 87:
1.15 ! tedu 88: set_state_table();
! 89: set_accessing_symbol();
! 90: set_shift_table();
! 91: set_reduction_table();
! 92: set_maxrhs();
! 93: initialize_LA();
! 94: set_goto_map();
! 95: initialize_F();
! 96: build_relations();
! 97: compute_FOLLOWS();
! 98: compute_lookaheads();
! 99: free_derives();
! 100: free_nullable();
1.1 deraadt 101: }
102:
103:
1.4 pvalchev 104: void
1.8 pvalchev 105: set_state_table(void)
1.1 deraadt 106: {
1.15 ! tedu 107: core *sp;
1.1 deraadt 108:
1.15 ! tedu 109: state_table = NEW2(nstates, core *);
! 110: for (sp = first_state; sp; sp = sp->next)
! 111: state_table[sp->number] = sp;
1.1 deraadt 112: }
113:
114:
1.4 pvalchev 115: void
1.8 pvalchev 116: set_accessing_symbol(void)
1.1 deraadt 117: {
1.15 ! tedu 118: core *sp;
1.1 deraadt 119:
1.15 ! tedu 120: accessing_symbol = NEW2(nstates, short);
! 121: for (sp = first_state; sp; sp = sp->next)
! 122: accessing_symbol[sp->number] = sp->accessing_symbol;
1.1 deraadt 123: }
124:
125:
1.4 pvalchev 126: void
1.8 pvalchev 127: set_shift_table(void)
1.1 deraadt 128: {
1.15 ! tedu 129: shifts *sp;
1.1 deraadt 130:
1.15 ! tedu 131: shift_table = NEW2(nstates, shifts *);
! 132: for (sp = first_shift; sp; sp = sp->next)
! 133: shift_table[sp->number] = sp;
1.1 deraadt 134: }
135:
136:
1.4 pvalchev 137: void
1.8 pvalchev 138: set_reduction_table(void)
1.1 deraadt 139: {
1.15 ! tedu 140: reductions *rp;
1.1 deraadt 141:
1.15 ! tedu 142: reduction_table = NEW2(nstates, reductions *);
! 143: for (rp = first_reduction; rp; rp = rp->next)
! 144: reduction_table[rp->number] = rp;
1.1 deraadt 145: }
146:
147:
1.4 pvalchev 148: void
1.8 pvalchev 149: set_maxrhs(void)
1.1 deraadt 150: {
1.15 ! tedu 151: short *itemp;
! 152: short *item_end;
! 153: int length;
! 154: int max;
! 155:
! 156: length = 0;
! 157: max = 0;
! 158: item_end = ritem + nitems;
! 159: for (itemp = ritem; itemp < item_end; itemp++) {
! 160: if (*itemp >= 0) {
! 161: length++;
! 162: } else {
! 163: if (length > max) max = length;
! 164: length = 0;
! 165: }
1.1 deraadt 166: }
167:
1.15 ! tedu 168: maxrhs = max;
1.1 deraadt 169: }
170:
171:
1.4 pvalchev 172: void
1.8 pvalchev 173: initialize_LA(void)
1.1 deraadt 174: {
1.15 ! tedu 175: int i, j, k;
! 176: reductions *rp;
1.1 deraadt 177:
1.15 ! tedu 178: lookaheads = NEW2(nstates + 1, short);
1.1 deraadt 179:
1.15 ! tedu 180: k = 0;
! 181: for (i = 0; i < nstates; i++) {
! 182: lookaheads[i] = k;
! 183: rp = reduction_table[i];
! 184: if (rp)
! 185: k += rp->nreds;
! 186: }
! 187: lookaheads[nstates] = k;
! 188:
! 189: LA = NEW2(k * tokensetsize, unsigned);
! 190: LAruleno = NEW2(k, short);
! 191: lookback = NEW2(k, shorts *);
! 192:
! 193: k = 0;
! 194: for (i = 0; i < nstates; i++) {
! 195: rp = reduction_table[i];
! 196: if (rp) {
! 197: for (j = 0; j < rp->nreds; j++) {
! 198: LAruleno[k] = rp->rules[j];
! 199: k++;
! 200: }
! 201: }
1.1 deraadt 202: }
203: }
204:
1.4 pvalchev 205: void
1.8 pvalchev 206: set_goto_map(void)
1.1 deraadt 207: {
1.15 ! tedu 208: shifts *sp;
! 209: int i;
! 210: int symbol;
! 211: int k;
! 212: short *temp_map;
! 213: int state2;
! 214: int state1;
! 215:
! 216: goto_map = NEW2(nvars + 1, short) - ntokens;
! 217: temp_map = NEW2(nvars + 1, short) - ntokens;
! 218:
! 219: ngotos = 0;
! 220: for (sp = first_shift; sp; sp = sp->next) {
! 221: for (i = sp->nshifts - 1; i >= 0; i--) {
! 222: symbol = accessing_symbol[sp->shift[i]];
! 223:
! 224: if (ISTOKEN(symbol)) break;
! 225:
! 226: if (ngotos == MAXSHORT)
! 227: fatal("too many gotos");
! 228:
! 229: ngotos++;
! 230: goto_map[symbol]++;
! 231: }
! 232: }
! 233:
! 234: k = 0;
! 235: for (i = ntokens; i < nsyms; i++) {
! 236: temp_map[i] = k;
! 237: k += goto_map[i];
! 238: }
! 239:
! 240: for (i = ntokens; i < nsyms; i++)
! 241: goto_map[i] = temp_map[i];
! 242:
! 243: goto_map[nsyms] = ngotos;
! 244: temp_map[nsyms] = ngotos;
! 245:
! 246: from_state = NEW2(ngotos, short);
! 247: to_state = NEW2(ngotos, short);
! 248:
! 249: for (sp = first_shift; sp; sp = sp->next) {
! 250: state1 = sp->number;
! 251: for (i = sp->nshifts - 1; i >= 0; i--) {
! 252: state2 = sp->shift[i];
! 253: symbol = accessing_symbol[state2];
! 254:
! 255: if (ISTOKEN(symbol)) break;
! 256:
! 257: k = temp_map[symbol]++;
! 258: from_state[k] = state1;
! 259: to_state[k] = state2;
! 260: }
1.1 deraadt 261: }
262:
1.15 ! tedu 263: free(temp_map + ntokens);
1.1 deraadt 264: }
265:
266:
267:
268: /* Map_goto maps a state/symbol pair into its numeric representation. */
269:
270: int
1.8 pvalchev 271: map_goto(int state, int symbol)
1.1 deraadt 272: {
1.15 ! tedu 273: int high;
! 274: int low;
! 275: int middle;
! 276: int s;
! 277:
! 278: low = goto_map[symbol];
! 279: high = goto_map[symbol + 1];
! 280:
! 281: for (;;) {
! 282: assert(low <= high);
! 283: middle = (low + high) >> 1;
! 284: s = from_state[middle];
! 285: if (s == state)
! 286: return (middle);
! 287: else if (s < state)
! 288: low = middle + 1;
! 289: else
! 290: high = middle - 1;
! 291: }
1.1 deraadt 292: }
293:
294:
1.4 pvalchev 295: void
1.8 pvalchev 296: initialize_F(void)
1.1 deraadt 297: {
1.15 ! tedu 298: int i;
! 299: int j;
! 300: int k;
! 301: shifts *sp;
! 302: short *edge;
! 303: unsigned *rowp;
! 304: short *rp;
! 305: short **reads;
! 306: int nedges;
! 307: int stateno;
! 308: int symbol;
! 309: int nwords;
! 310:
! 311: nwords = ngotos * tokensetsize;
! 312: F = NEW2(nwords, unsigned);
! 313:
! 314: reads = NEW2(ngotos, short *);
! 315: edge = NEW2(ngotos + 1, short);
! 316: nedges = 0;
! 317:
! 318: rowp = F;
! 319: for (i = 0; i < ngotos; i++) {
! 320: stateno = to_state[i];
! 321: sp = shift_table[stateno];
! 322:
! 323: if (sp) {
! 324: k = sp->nshifts;
! 325:
! 326: for (j = 0; j < k; j++) {
! 327: symbol = accessing_symbol[sp->shift[j]];
! 328: if (ISVAR(symbol))
! 329: break;
! 330: SETBIT(rowp, symbol);
! 331: }
! 332:
! 333: for (; j < k; j++) {
! 334: symbol = accessing_symbol[sp->shift[j]];
! 335: if (nullable[symbol])
! 336: edge[nedges++] = map_goto(stateno, symbol);
! 337: }
! 338:
! 339: if (nedges) {
! 340: reads[i] = rp = NEW2(nedges + 1, short);
! 341:
! 342: for (j = 0; j < nedges; j++)
! 343: rp[j] = edge[j];
! 344:
! 345: rp[nedges] = -1;
! 346: nedges = 0;
! 347: }
! 348: }
1.1 deraadt 349:
1.15 ! tedu 350: rowp += tokensetsize;
! 351: }
! 352:
! 353: SETBIT(F, 0);
! 354: digraph(reads);
! 355:
! 356: for (i = 0; i < ngotos; i++) {
! 357: if (reads[i])
! 358: free(reads[i]);
! 359: }
! 360:
! 361: free(reads);
! 362: free(edge);
1.1 deraadt 363: }
364:
365:
1.4 pvalchev 366: void
1.8 pvalchev 367: build_relations(void)
1.1 deraadt 368: {
1.15 ! tedu 369: int i;
! 370: int j;
! 371: int k;
! 372: short *rulep;
! 373: short *rp;
! 374: shifts *sp;
! 375: int length;
! 376: int nedges;
! 377: int done;
! 378: int state1;
! 379: int stateno;
! 380: int symbol1;
! 381: int symbol2;
! 382: short *shortp;
! 383: short *edge;
! 384: short *states;
! 385: short **new_includes;
! 386:
! 387: includes = NEW2(ngotos, short *);
! 388: edge = NEW2(ngotos + 1, short);
! 389: states = NEW2(maxrhs + 1, short);
! 390:
! 391: for (i = 0; i < ngotos; i++) {
! 392: nedges = 0;
! 393: state1 = from_state[i];
! 394: symbol1 = accessing_symbol[to_state[i]];
! 395:
! 396: for (rulep = derives[symbol1]; *rulep >= 0; rulep++) {
! 397: length = 1;
! 398: states[0] = state1;
! 399: stateno = state1;
! 400:
! 401: for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++) {
! 402: symbol2 = *rp;
! 403: sp = shift_table[stateno];
! 404: k = sp->nshifts;
! 405:
! 406: for (j = 0; j < k; j++) {
! 407: stateno = sp->shift[j];
! 408: if (accessing_symbol[stateno] == symbol2)
! 409: break;
! 410: }
! 411:
! 412: states[length++] = stateno;
! 413: }
! 414:
! 415: add_lookback_edge(stateno, *rulep, i);
! 416:
! 417: length--;
! 418: done = 0;
! 419: while (!done) {
! 420: done = 1;
! 421: rp--;
! 422: if (ISVAR(*rp)) {
! 423: stateno = states[--length];
! 424: edge[nedges++] = map_goto(stateno, *rp);
! 425: if (nullable[*rp] && length > 0)
! 426: done = 0;
! 427: }
! 428: }
! 429: }
1.1 deraadt 430:
1.15 ! tedu 431: if (nedges) {
! 432: includes[i] = shortp = NEW2(nedges + 1, short);
! 433: for (j = 0; j < nedges; j++)
! 434: shortp[j] = edge[j];
! 435: shortp[nedges] = -1;
! 436: }
! 437: }
! 438:
! 439: new_includes = transpose(includes, ngotos);
1.1 deraadt 440:
1.15 ! tedu 441: for (i = 0; i < ngotos; i++)
! 442: if (includes[i])
! 443: free(includes[i]);
1.1 deraadt 444:
1.15 ! tedu 445: free(includes);
! 446:
! 447: includes = new_includes;
! 448:
! 449: free(edge);
! 450: free(states);
1.1 deraadt 451: }
452:
1.4 pvalchev 453: void
1.8 pvalchev 454: add_lookback_edge(int stateno, int ruleno, int gotono)
1.1 deraadt 455: {
1.15 ! tedu 456: int i, k;
! 457: int found;
! 458: shorts *sp;
! 459:
! 460: i = lookaheads[stateno];
! 461: k = lookaheads[stateno + 1];
! 462: found = 0;
! 463: while (!found && i < k) {
! 464: if (LAruleno[i] == ruleno)
! 465: found = 1;
! 466: else
! 467: ++i;
! 468: }
! 469: assert(found);
! 470:
! 471: sp = NEW(shorts);
! 472: sp->next = lookback[i];
! 473: sp->value = gotono;
! 474: lookback[i] = sp;
1.1 deraadt 475: }
476:
477:
478:
479: short **
1.8 pvalchev 480: transpose(short **R, int n)
1.1 deraadt 481: {
1.15 ! tedu 482: short **new_R;
! 483: short **temp_R;
! 484: short *nedges;
! 485: short *sp;
! 486: int i;
! 487: int k;
! 488:
! 489: nedges = NEW2(n, short);
! 490:
! 491: for (i = 0; i < n; i++) {
! 492: sp = R[i];
! 493: if (sp) {
! 494: while (*sp >= 0)
! 495: nedges[*sp++]++;
! 496: }
! 497: }
! 498:
! 499: new_R = NEW2(n, short *);
! 500: temp_R = NEW2(n, short *);
! 501:
! 502: for (i = 0; i < n; i++) {
! 503: k = nedges[i];
! 504: if (k > 0) {
! 505: sp = NEW2(k + 1, short);
! 506: new_R[i] = sp;
! 507: temp_R[i] = sp;
! 508: sp[k] = -1;
! 509: }
! 510: }
! 511:
! 512: free(nedges);
! 513:
! 514: for (i = 0; i < n; i++) {
! 515: sp = R[i];
! 516: if (sp) {
! 517: while (*sp >= 0)
! 518: *temp_R[*sp++]++ = i;
! 519: }
1.1 deraadt 520: }
521:
1.15 ! tedu 522: free(temp_R);
1.1 deraadt 523:
1.15 ! tedu 524: return (new_R);
1.1 deraadt 525: }
526:
527:
1.4 pvalchev 528: void
1.8 pvalchev 529: compute_FOLLOWS(void)
1.1 deraadt 530: {
1.15 ! tedu 531: digraph(includes);
1.1 deraadt 532: }
533:
1.4 pvalchev 534: void
1.8 pvalchev 535: compute_lookaheads(void)
1.1 deraadt 536: {
1.15 ! tedu 537: int i, n;
! 538: unsigned *fp1, *fp2, *fp3;
! 539: shorts *sp, *next;
! 540: unsigned *rowp;
! 541:
! 542: rowp = LA;
! 543: n = lookaheads[nstates];
! 544: for (i = 0; i < n; i++) {
! 545: fp3 = rowp + tokensetsize;
! 546: for (sp = lookback[i]; sp; sp = sp->next) {
! 547: fp1 = rowp;
! 548: fp2 = F + tokensetsize * sp->value;
! 549: while (fp1 < fp3)
! 550: *fp1++ |= *fp2++;
! 551: }
! 552: rowp = fp3;
! 553: }
! 554:
! 555: for (i = 0; i < n; i++)
! 556: for (sp = lookback[i]; sp; sp = next) {
! 557: next = sp->next;
! 558: free(sp);
! 559: }
1.1 deraadt 560:
1.15 ! tedu 561: free(lookback);
! 562: free(F);
1.1 deraadt 563: }
564:
1.4 pvalchev 565: void
1.8 pvalchev 566: digraph(short **relation)
1.1 deraadt 567: {
1.15 ! tedu 568: int i;
1.1 deraadt 569:
1.15 ! tedu 570: infinity = ngotos + 2;
! 571: INDEX = NEW2(ngotos + 1, short);
! 572: VERTICES = NEW2(ngotos + 1, short);
! 573: top = 0;
! 574: R = relation;
! 575:
! 576: memset(INDEX, 0, ngotos * sizeof(short));
! 577: for (i = 0; i < ngotos; i++)
! 578: if (R[i])
! 579: traverse(i);
1.1 deraadt 580:
1.15 ! tedu 581: free(INDEX);
! 582: free(VERTICES);
1.1 deraadt 583: }
584:
585:
1.4 pvalchev 586: void
1.8 pvalchev 587: traverse(int i)
1.1 deraadt 588: {
1.15 ! tedu 589: unsigned *fp1;
! 590: unsigned *fp2;
! 591: unsigned *fp3;
! 592: int j;
! 593: short *rp;
! 594:
! 595: int height;
! 596: unsigned *base;
! 597:
! 598: VERTICES[++top] = i;
! 599: INDEX[i] = height = top;
! 600:
! 601: base = F + i * tokensetsize;
! 602: fp3 = base + tokensetsize;
! 603:
! 604: rp = R[i];
! 605: if (rp) {
! 606: while ((j = *rp++) >= 0) {
! 607: if (INDEX[j] == 0)
! 608: traverse(j);
1.14 sthen 609:
1.15 ! tedu 610: if (INDEX[i] > INDEX[j])
! 611: INDEX[i] = INDEX[j];
1.1 deraadt 612:
1.15 ! tedu 613: fp1 = base;
! 614: fp2 = F + j * tokensetsize;
1.1 deraadt 615:
1.15 ! tedu 616: while (fp1 < fp3)
! 617: *fp1++ |= *fp2++;
! 618: }
1.1 deraadt 619: }
620:
1.15 ! tedu 621: if (INDEX[i] == height) {
! 622: for (;;) {
! 623: j = VERTICES[top--];
! 624: INDEX[j] = infinity;
1.1 deraadt 625:
1.15 ! tedu 626: if (i == j)
! 627: break;
1.1 deraadt 628:
1.15 ! tedu 629: fp1 = base;
! 630: fp2 = F + j * tokensetsize;
1.1 deraadt 631:
1.15 ! tedu 632: while (fp1 < fp3)
! 633: *fp2++ = *fp1++;
! 634: }
1.1 deraadt 635: }
636: }
![[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