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