![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to lalr.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / bison|
Return to lalr.c CVS log | Up to [Apple XNU] / GNUtools / bison |
1.1 root 1: /* Compute look-ahead criteria for bison,
2: Copyright (C) 1984, 1986, 1989 Free Software Foundation, Inc.
3:
4: This file is part of Bison, the GNU Compiler Compiler.
5:
6: Bison is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 2, or (at your option)
9: any later version.
10:
11: Bison is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with Bison; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: /* Compute how to make the finite state machine deterministic;
22: find which rules need lookahead in each state, and which lookahead tokens they accept.
23:
24: lalr(), the entry point, builds these data structures:
25:
26: goto_map, from_state and to_state
27: record each shift transition which accepts a variable (a nonterminal).
28: ngotos is the number of such transitions.
29: from_state[t] is the state number which a transition leads from
30: and to_state[t] is the state number it leads to.
31: All the transitions that accept a particular variable are grouped together and
32: goto_map[i - ntokens] is the index in from_state and to_state of the first of them.
33:
34: consistent[s] is nonzero if no lookahead is needed to decide what to do in state s.
35:
36: LAruleno is a vector which records the rules that need lookahead in various states.
37: The elements of LAruleno that apply to state s are those from
38: lookaheads[s] through lookaheads[s+1]-1.
39: Each element of LAruleno is a rule number.
40:
41: If lr is the length of LAruleno, then a number from 0 to lr-1
42: can specify both a rule and a state where the rule might be applied.
43:
44: LA is a lr by ntokens matrix of bits.
45: LA[l, i] is 1 if the rule LAruleno[l] is applicable in the appropriate state
46: when the next token is symbol i.
47: If LA[l, i] and LA[l, j] are both 1 for i != j, it is a conflict.
48: */
49:
50: #include <stdio.h>
51: #include "system.h"
52: #include "machine.h"
53: #include "types.h"
54: #include "state.h"
55: #include "new.h"
56: #include "gram.h"
57:
58:
59: extern short **derives;
60: extern char *nullable;
61:
62:
63: int tokensetsize;
64: short *lookaheads;
65: short *LAruleno;
66: unsigned *LA;
67: short *accessing_symbol;
68: char *consistent;
69: core **state_table;
70: shifts **shift_table;
71: reductions **reduction_table;
72: short *goto_map;
73: short *from_state;
74: short *to_state;
75:
76: short **transpose();
77: void set_state_table();
78: void set_accessing_symbol();
79: void set_shift_table();
80: void set_reduction_table();
81: void set_maxrhs();
82: void initialize_LA();
83: void set_goto_map();
84: void initialize_F();
85: void build_relations();
86: void add_lookback_edge();
87: void compute_FOLLOWS();
88: void compute_lookaheads();
89: void digraph();
90: void traverse();
91:
92: extern void toomany();
93: extern void berror();
94:
95: static int infinity;
96: static int maxrhs;
97: static int ngotos;
98: static unsigned *F;
99: static short **includes;
100: static shorts **lookback;
101: static short **R;
102: static short *INDEX;
103: static short *VERTICES;
104: static int top;
105:
106:
107: void
108: lalr()
109: {
110: tokensetsize = WORDSIZE(ntokens);
111:
112: set_state_table();
113: set_accessing_symbol();
114: set_shift_table();
115: set_reduction_table();
116: set_maxrhs();
117: initialize_LA();
118: set_goto_map();
119: initialize_F();
120: build_relations();
121: compute_FOLLOWS();
122: compute_lookaheads();
123: }
124:
125:
126: void
127: set_state_table()
128: {
129: register core *sp;
130:
131: state_table = NEW2(nstates, core *);
132:
133: for (sp = first_state; sp; sp = sp->next)
134: state_table[sp->number] = sp;
135: }
136:
137:
138: void
139: set_accessing_symbol()
140: {
141: register core *sp;
142:
143: accessing_symbol = NEW2(nstates, short);
144:
145: for (sp = first_state; sp; sp = sp->next)
146: accessing_symbol[sp->number] = sp->accessing_symbol;
147: }
148:
149:
150: void
151: set_shift_table()
152: {
153: register shifts *sp;
154:
155: shift_table = NEW2(nstates, shifts *);
156:
157: for (sp = first_shift; sp; sp = sp->next)
158: shift_table[sp->number] = sp;
159: }
160:
161:
162: void
163: set_reduction_table()
164: {
165: register reductions *rp;
166:
167: reduction_table = NEW2(nstates, reductions *);
168:
169: for (rp = first_reduction; rp; rp = rp->next)
170: reduction_table[rp->number] = rp;
171: }
172:
173:
174: void
175: set_maxrhs()
176: {
177: register short *itemp;
178: register int length;
179: register int max;
180:
181: length = 0;
182: max = 0;
183: for (itemp = ritem; *itemp; itemp++)
184: {
185: if (*itemp > 0)
186: {
187: length++;
188: }
189: else
190: {
191: if (length > max) max = length;
192: length = 0;
193: }
194: }
195:
196: maxrhs = max;
197: }
198:
199:
200: void
201: initialize_LA()
202: {
203: register int i;
204: register int j;
205: register int count;
206: register reductions *rp;
207: register shifts *sp;
208: register short *np;
209:
210: consistent = NEW2(nstates, char);
211: lookaheads = NEW2(nstates + 1, short);
212:
213: count = 0;
214: for (i = 0; i < nstates; i++)
215: {
216: register int k;
217:
218: lookaheads[i] = count;
219:
220: rp = reduction_table[i];
221: sp = shift_table[i];
222: if (rp && (rp->nreds > 1
223: || (sp && ! ISVAR(accessing_symbol[sp->shifts[0]]))))
224: count += rp->nreds;
225: else
226: consistent[i] = 1;
227:
228: if (sp)
229: for (k = 0; k < sp->nshifts; k++)
230: {
231: if (accessing_symbol[sp->shifts[k]] == error_token_number)
232: {
233: consistent[i] = 0;
234: break;
235: }
236: }
237: }
238:
239: lookaheads[nstates] = count;
240:
241: if (count == 0)
242: {
243: LA = NEW2(1 * tokensetsize, unsigned);
244: LAruleno = NEW2(1, short);
245: lookback = NEW2(1, shorts *);
246: }
247: else
248: {
249: LA = NEW2(count * tokensetsize, unsigned);
250: LAruleno = NEW2(count, short);
251: lookback = NEW2(count, shorts *);
252: }
253:
254: np = LAruleno;
255: for (i = 0; i < nstates; i++)
256: {
257: if (!consistent[i])
258: {
259: if (rp = reduction_table[i])
260: for (j = 0; j < rp->nreds; j++)
261: *np++ = rp->rules[j];
262: }
263: }
264: }
265:
266:
267: void
268: set_goto_map()
269: {
270: register shifts *sp;
271: register int i;
272: register int symbol;
273: register int k;
274: register short *temp_map;
275: register int state2;
276: register int state1;
277:
278: goto_map = NEW2(nvars + 1, short) - ntokens;
279: temp_map = NEW2(nvars + 1, short) - ntokens;
280:
281: ngotos = 0;
282: for (sp = first_shift; sp; sp = sp->next)
283: {
284: for (i = sp->nshifts - 1; i >= 0; i--)
285: {
286: symbol = accessing_symbol[sp->shifts[i]];
287:
288: if (ISTOKEN(symbol)) break;
289:
290: if (ngotos == MAXSHORT)
291: toomany("gotos");
292:
293: ngotos++;
294: goto_map[symbol]++;
295: }
296: }
297:
298: k = 0;
299: for (i = ntokens; i < nsyms; i++)
300: {
301: temp_map[i] = k;
302: k += goto_map[i];
303: }
304:
305: for (i = ntokens; i < nsyms; i++)
306: goto_map[i] = temp_map[i];
307:
308: goto_map[nsyms] = ngotos;
309: temp_map[nsyms] = ngotos;
310:
311: from_state = NEW2(ngotos, short);
312: to_state = NEW2(ngotos, short);
313:
314: for (sp = first_shift; sp; sp = sp->next)
315: {
316: state1 = sp->number;
317: for (i = sp->nshifts - 1; i >= 0; i--)
318: {
319: state2 = sp->shifts[i];
320: symbol = accessing_symbol[state2];
321:
322: if (ISTOKEN(symbol)) break;
323:
324: k = temp_map[symbol]++;
325: from_state[k] = state1;
326: to_state[k] = state2;
327: }
328: }
329:
330: FREE(temp_map + ntokens);
331: }
332:
333:
334:
335: /* Map_goto maps a state/symbol pair into its numeric representation. */
336:
337: int
338: map_goto(state, symbol)
339: int state;
340: int symbol;
341: {
342: register int high;
343: register int low;
344: register int middle;
345: register int s;
346:
347: low = goto_map[symbol];
348: high = goto_map[symbol + 1] - 1;
349:
350: while (low <= high)
351: {
352: middle = (low + high) / 2;
353: s = from_state[middle];
354: if (s == state)
355: return (middle);
356: else if (s < state)
357: low = middle + 1;
358: else
359: high = middle - 1;
360: }
361:
362: berror("map_goto");
363: /* NOTREACHED */
364: return 0;
365: }
366:
367:
368: void
369: initialize_F()
370: {
371: register int i;
372: register int j;
373: register int k;
374: register shifts *sp;
375: register short *edge;
376: register unsigned *rowp;
377: register short *rp;
378: register short **reads;
379: register int nedges;
380: register int stateno;
381: register int symbol;
382: register int nwords;
383:
384: nwords = ngotos * tokensetsize;
385: F = NEW2(nwords, unsigned);
386:
387: reads = NEW2(ngotos, short *);
388: edge = NEW2(ngotos + 1, short);
389: nedges = 0;
390:
391: rowp = F;
392: for (i = 0; i < ngotos; i++)
393: {
394: stateno = to_state[i];
395: sp = shift_table[stateno];
396:
397: if (sp)
398: {
399: k = sp->nshifts;
400:
401: for (j = 0; j < k; j++)
402: {
403: symbol = accessing_symbol[sp->shifts[j]];
404: if (ISVAR(symbol))
405: break;
406: SETBIT(rowp, symbol);
407: }
408:
409: for (; j < k; j++)
410: {
411: symbol = accessing_symbol[sp->shifts[j]];
412: if (nullable[symbol])
413: edge[nedges++] = map_goto(stateno, symbol);
414: }
415:
416: if (nedges)
417: {
418: reads[i] = rp = NEW2(nedges + 1, short);
419:
420: for (j = 0; j < nedges; j++)
421: rp[j] = edge[j];
422:
423: rp[nedges] = -1;
424: nedges = 0;
425: }
426: }
427:
428: rowp += tokensetsize;
429: }
430:
431: digraph(reads);
432:
433: for (i = 0; i < ngotos; i++)
434: {
435: if (reads[i])
436: FREE(reads[i]);
437: }
438:
439: FREE(reads);
440: FREE(edge);
441: }
442:
443:
444: void
445: build_relations()
446: {
447: register int i;
448: register int j;
449: register int k;
450: register short *rulep;
451: register short *rp;
452: register shifts *sp;
453: register int length;
454: register int nedges;
455: register int done;
456: register int state1;
457: register int stateno;
458: register int symbol1;
459: register int symbol2;
460: register short *shortp;
461: register short *edge;
462: register short *states;
463: register short **new_includes;
464:
465: includes = NEW2(ngotos, short *);
466: edge = NEW2(ngotos + 1, short);
467: states = NEW2(maxrhs + 1, short);
468:
469: for (i = 0; i < ngotos; i++)
470: {
471: nedges = 0;
472: state1 = from_state[i];
473: symbol1 = accessing_symbol[to_state[i]];
474:
475: for (rulep = derives[symbol1]; *rulep > 0; rulep++)
476: {
477: length = 1;
478: states[0] = state1;
479: stateno = state1;
480:
481: for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
482: {
483: symbol2 = *rp;
484: sp = shift_table[stateno];
485: k = sp->nshifts;
486:
487: for (j = 0; j < k; j++)
488: {
489: stateno = sp->shifts[j];
490: if (accessing_symbol[stateno] == symbol2) break;
491: }
492:
493: states[length++] = stateno;
494: }
495:
496: if (!consistent[stateno])
497: add_lookback_edge(stateno, *rulep, i);
498:
499: length--;
500: done = 0;
501: while (!done)
502: {
503: done = 1;
504: rp--;
505: /* JF added rp>=ritem && I hope to god its right! */
506: if (rp>=ritem && ISVAR(*rp))
507: {
508: stateno = states[--length];
509: edge[nedges++] = map_goto(stateno, *rp);
510: if (nullable[*rp]) done = 0;
511: }
512: }
513: }
514:
515: if (nedges)
516: {
517: includes[i] = shortp = NEW2(nedges + 1, short);
518: for (j = 0; j < nedges; j++)
519: shortp[j] = edge[j];
520: shortp[nedges] = -1;
521: }
522: }
523:
524: new_includes = transpose(includes, ngotos);
525:
526: for (i = 0; i < ngotos; i++)
527: if (includes[i])
528: FREE(includes[i]);
529:
530: FREE(includes);
531:
532: includes = new_includes;
533:
534: FREE(edge);
535: FREE(states);
536: }
537:
538:
539: void
540: add_lookback_edge(stateno, ruleno, gotono)
541: int stateno;
542: int ruleno;
543: int gotono;
544: {
545: register int i;
546: register int k;
547: register int found;
548: register shorts *sp;
549:
550: i = lookaheads[stateno];
551: k = lookaheads[stateno + 1];
552: found = 0;
553: while (!found && i < k)
554: {
555: if (LAruleno[i] == ruleno)
556: found = 1;
557: else
558: i++;
559: }
560:
561: if (found == 0)
562: berror("add_lookback_edge");
563:
564: sp = NEW(shorts);
565: sp->next = lookback[i];
566: sp->value = gotono;
567: lookback[i] = sp;
568: }
569:
570:
571:
572: short **
573: transpose(R_arg, n)
574: short **R_arg;
575: int n;
576: {
577: register short **new_R;
578: register short **temp_R;
579: register short *nedges;
580: register short *sp;
581: register int i;
582: register int k;
583:
584: nedges = NEW2(n, short);
585:
586: for (i = 0; i < n; i++)
587: {
588: sp = R_arg[i];
589: if (sp)
590: {
591: while (*sp >= 0)
592: nedges[*sp++]++;
593: }
594: }
595:
596: new_R = NEW2(n, short *);
597: temp_R = NEW2(n, short *);
598:
599: for (i = 0; i < n; i++)
600: {
601: k = nedges[i];
602: if (k > 0)
603: {
604: sp = NEW2(k + 1, short);
605: new_R[i] = sp;
606: temp_R[i] = sp;
607: sp[k] = -1;
608: }
609: }
610:
611: FREE(nedges);
612:
613: for (i = 0; i < n; i++)
614: {
615: sp = R_arg[i];
616: if (sp)
617: {
618: while (*sp >= 0)
619: *temp_R[*sp++]++ = i;
620: }
621: }
622:
623: FREE(temp_R);
624:
625: return (new_R);
626: }
627:
628:
629: void
630: compute_FOLLOWS()
631: {
632: register int i;
633:
634: digraph(includes);
635:
636: for (i = 0; i < ngotos; i++)
637: {
638: if (includes[i]) FREE(includes[i]);
639: }
640:
641: FREE(includes);
642: }
643:
644:
645: void
646: compute_lookaheads()
647: {
648: register int i;
649: register int n;
650: register unsigned *fp1;
651: register unsigned *fp2;
652: register unsigned *fp3;
653: register shorts *sp;
654: register unsigned *rowp;
655: /* register short *rulep; JF unused */
656: /* register int count; JF unused */
657: register shorts *sptmp;/* JF */
658:
659: rowp = LA;
660: n = lookaheads[nstates];
661: for (i = 0; i < n; i++)
662: {
663: fp3 = rowp + tokensetsize;
664: for (sp = lookback[i]; sp; sp = sp->next)
665: {
666: fp1 = rowp;
667: fp2 = F + tokensetsize * sp->value;
668: while (fp1 < fp3)
669: *fp1++ |= *fp2++;
670: }
671:
672: rowp = fp3;
673: }
674:
675: for (i = 0; i < n; i++)
676: {/* JF removed ref to freed storage */
677: for (sp = lookback[i]; sp; sp = sptmp) {
678: sptmp=sp->next;
679: FREE(sp);
680: }
681: }
682:
683: FREE(lookback);
684: FREE(F);
685: }
686:
687:
688: void
689: digraph(relation)
690: short **relation;
691: {
692: register int i;
693:
694: infinity = ngotos + 2;
695: INDEX = NEW2(ngotos + 1, short);
696: VERTICES = NEW2(ngotos + 1, short);
697: top = 0;
698:
699: R = relation;
700:
701: for (i = 0; i < ngotos; i++)
702: INDEX[i] = 0;
703:
704: for (i = 0; i < ngotos; i++)
705: {
706: if (INDEX[i] == 0 && R[i])
707: traverse(i);
708: }
709:
710: FREE(INDEX);
711: FREE(VERTICES);
712: }
713:
714:
715: void
716: traverse(i)
717: register int i;
718: {
719: register unsigned *fp1;
720: register unsigned *fp2;
721: register unsigned *fp3;
722: register int j;
723: register short *rp;
724:
725: int height;
726: unsigned *base;
727:
728: VERTICES[++top] = i;
729: INDEX[i] = height = top;
730:
731: base = F + i * tokensetsize;
732: fp3 = base + tokensetsize;
733:
734: rp = R[i];
735: if (rp)
736: {
737: while ((j = *rp++) >= 0)
738: {
739: if (INDEX[j] == 0)
740: traverse(j);
741:
742: if (INDEX[i] > INDEX[j])
743: INDEX[i] = INDEX[j];
744:
745: fp1 = base;
746: fp2 = F + j * tokensetsize;
747:
748: while (fp1 < fp3)
749: *fp1++ |= *fp2++;
750: }
751: }
752:
753: if (INDEX[i] == height)
754: {
755: for (;;)
756: {
757: j = VERTICES[top--];
758: INDEX[j] = infinity;
759:
760: if (i == j)
761: break;
762:
763: fp1 = base;
764: fp2 = F + j * tokensetsize;
765:
766: while (fp1 < fp3)
767: *fp2++ = *fp1++;
768: }
769: }
770: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.