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