![[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 [Research Unix] / researchv10dc / cmd / bison|
Return to lalr.c CVS log | Up to [Research Unix] / researchv10dc / cmd / bison |
1.1 root 1: /* Compute look-ahead criteria for bison,
2: Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
3:
4: BISON is distributed in the hope that it will be useful, but WITHOUT ANY
5: WARRANTY. No author or distributor accepts responsibility to anyone
6: for the consequences of using it or for whether it serves any
7: particular purpose or works at all, unless he says so in writing.
8: Refer to the BISON General Public License for full details.
9:
10: Everyone is granted permission to copy, modify and redistribute BISON,
11: but only under the conditions described in the BISON General Public
12: License. A copy of this license is supposed to have been given to you
13: along with BISON so you can know your rights and responsibilities. It
14: should be in a file named COPYING. Among other things, the copyright
15: notice and this notice must be preserved on all copies.
16:
17: In other words, you are welcome to use, share and improve this program.
18: You are forbidden to forbid anyone else to use, share and improve
19: what you give them. Help stamp out software-hoarding! */
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 "machine.h"
52: #include "types.h"
53: #include "state.h"
54: #include "new.h"
55: #include "gram.h"
56:
57:
58: extern short **derives;
59: extern char *nullable;
60:
61:
62: int tokensetsize;
63: short *lookaheads;
64: short *LAruleno;
65: unsigned *LA;
66: short *accessing_symbol;
67: char *consistent;
68: core **state_table;
69: shifts **shift_table;
70: reductions **reduction_table;
71: short *goto_map;
72: short *from_state;
73: short *to_state;
74:
75: short **transpose();
76:
77:
78: static int infinity;
79: static int maxrhs;
80: static int ngotos;
81: static unsigned *F;
82: static short **includes;
83: static shorts **lookback;
84: static short **R;
85: static short *INDEX;
86: static short *VERTICES;
87: static int top;
88:
89:
90:
91: lalr()
92: {
93: tokensetsize = WORDSIZE(ntokens);
94:
95: set_state_table();
96: set_accessing_symbol();
97: set_shift_table();
98: set_reduction_table();
99: set_maxrhs();
100: initialize_LA();
101: set_goto_map();
102: initialize_F();
103: build_relations();
104: compute_FOLLOWS();
105: compute_lookaheads();
106: }
107:
108:
109:
110: set_state_table()
111: {
112: register core *sp;
113:
114: state_table = NEW2(nstates, core *);
115:
116: for (sp = first_state; sp; sp = sp->next)
117: state_table[sp->number] = sp;
118: }
119:
120:
121:
122: set_accessing_symbol()
123: {
124: register core *sp;
125:
126: accessing_symbol = NEW2(nstates, short);
127:
128: for (sp = first_state; sp; sp = sp->next)
129: accessing_symbol[sp->number] = sp->accessing_symbol;
130: }
131:
132:
133:
134: set_shift_table()
135: {
136: register shifts *sp;
137:
138: shift_table = NEW2(nstates, shifts *);
139:
140: for (sp = first_shift; sp; sp = sp->next)
141: shift_table[sp->number] = sp;
142: }
143:
144:
145:
146: set_reduction_table()
147: {
148: register reductions *rp;
149:
150: reduction_table = NEW2(nstates, reductions *);
151:
152: for (rp = first_reduction; rp; rp = rp->next)
153: reduction_table[rp->number] = rp;
154: }
155:
156:
157:
158: set_maxrhs()
159: {
160: register short *itemp;
161: register int length;
162: register int max;
163:
164: length = 0;
165: max = 0;
166: for (itemp = ritem; *itemp; itemp++)
167: {
168: if (*itemp > 0)
169: {
170: length++;
171: }
172: else
173: {
174: if (length > max) max = length;
175: length = 0;
176: }
177: }
178:
179: maxrhs = max;
180: }
181:
182:
183:
184: initialize_LA()
185: {
186: register int i;
187: register int j;
188: register int count;
189: register reductions *rp;
190: register shifts *sp;
191: register short *np;
192:
193: consistent = NEW2(nstates, char);
194: lookaheads = NEW2(nstates + 1, short);
195:
196: count = 0;
197: for (i = 0; i < nstates; i++)
198: {
199: register int j;
200:
201: lookaheads[i] = count;
202:
203: rp = reduction_table[i];
204: sp = shift_table[i];
205: if (rp && (rp->nreds > 1
206: || (sp && ! ISVAR(accessing_symbol[sp->shifts[0]]))))
207: count += rp->nreds;
208: else
209: consistent[i] = 1;
210:
211: if (sp)
212: for (j = 0; j < sp->nshifts; j++)
213: {
214: if (accessing_symbol[sp->shifts[j]] == error_token_number)
215: {
216: consistent[i] = 0;
217: break;
218: }
219: }
220: }
221:
222: lookaheads[nstates] = count;
223:
224: LA = NEW2(count * tokensetsize, unsigned);
225: LAruleno = NEW2(count, short);
226: lookback = NEW2(count, shorts *);
227:
228: np = LAruleno;
229: for (i = 0; i < nstates; i++)
230: {
231: if (!consistent[i])
232: {
233: if (rp = reduction_table[i])
234: for (j = 0; j < rp->nreds; j++)
235: *np++ = rp->rules[j];
236: }
237: }
238: }
239:
240:
241:
242: set_goto_map()
243: {
244: register shifts *sp;
245: register int i;
246: register int symbol;
247: register int k;
248: register short *temp_map;
249: register int state2;
250: register int state1;
251:
252: goto_map = NEW2(nvars + 1, short) - ntokens;
253: temp_map = NEW2(nvars + 1, short) - ntokens;
254:
255: ngotos = 0;
256: for (sp = first_shift; sp; sp = sp->next)
257: {
258: for (i = sp->nshifts - 1; i >= 0; i--)
259: {
260: symbol = accessing_symbol[sp->shifts[i]];
261:
262: if (ISTOKEN(symbol)) break;
263:
264: if (ngotos == MAXSHORT)
265: toomany("gotos");
266:
267: ngotos++;
268: goto_map[symbol]++;
269: }
270: }
271:
272: k = 0;
273: for (i = ntokens; i < nsyms; i++)
274: {
275: temp_map[i] = k;
276: k += goto_map[i];
277: }
278:
279: for (i = ntokens; i < nsyms; i++)
280: goto_map[i] = temp_map[i];
281:
282: goto_map[nsyms] = ngotos;
283: temp_map[nsyms] = ngotos;
284:
285: from_state = NEW2(ngotos, short);
286: to_state = NEW2(ngotos, short);
287:
288: for (sp = first_shift; sp; sp = sp->next)
289: {
290: state1 = sp->number;
291: for (i = sp->nshifts - 1; i >= 0; i--)
292: {
293: state2 = sp->shifts[i];
294: symbol = accessing_symbol[state2];
295:
296: if (ISTOKEN(symbol)) break;
297:
298: k = temp_map[symbol]++;
299: from_state[k] = state1;
300: to_state[k] = state2;
301: }
302: }
303:
304: FREE(temp_map + ntokens);
305: }
306:
307:
308:
309: /* Map_goto maps a state/symbol pair into its numeric representation. */
310:
311: int
312: map_goto(state, symbol)
313: int state;
314: int symbol;
315: {
316: register int high;
317: register int low;
318: register int middle;
319: register int s;
320:
321: low = goto_map[symbol];
322: high = goto_map[symbol + 1];
323:
324: while (low <= high)
325: {
326: middle = (low + high) / 2;
327: s = from_state[middle];
328: if (s == state)
329: return (middle);
330: else if (s < state)
331: low = middle + 1;
332: else
333: high = middle - 1;
334: }
335:
336: berror("map_goto");
337:
338: /* NOTREACHED */
339: }
340:
341:
342:
343: initialize_F()
344: {
345: register int i;
346: register int j;
347: register int k;
348: register shifts *sp;
349: register short *edge;
350: register unsigned *rowp;
351: register short *rp;
352: register short **reads;
353: register int nedges;
354: register int stateno;
355: register int symbol;
356: register int nwords;
357:
358: nwords = ngotos * tokensetsize;
359: F = NEW2(nwords, unsigned);
360:
361: reads = NEW2(ngotos, short *);
362: edge = NEW2(ngotos + 1, short);
363: nedges = 0;
364:
365: rowp = F;
366: for (i = 0; i < ngotos; i++)
367: {
368: stateno = to_state[i];
369: sp = shift_table[stateno];
370:
371: if (sp)
372: {
373: k = sp->nshifts;
374:
375: for (j = 0; j < k; j++)
376: {
377: symbol = accessing_symbol[sp->shifts[j]];
378: if (ISVAR(symbol))
379: break;
380: SETBIT(rowp, symbol);
381: }
382:
383: for (; j < k; j++)
384: {
385: symbol = accessing_symbol[sp->shifts[j]];
386: if (nullable[symbol])
387: edge[nedges++] = map_goto(stateno, symbol);
388: }
389:
390: if (nedges)
391: {
392: reads[i] = rp = NEW2(nedges + 1, short);
393:
394: for (j = 0; j < nedges; j++)
395: rp[j] = edge[j];
396:
397: rp[nedges] = -1;
398: nedges = 0;
399: }
400: }
401:
402: rowp += tokensetsize;
403: }
404:
405: digraph(reads);
406:
407: for (i = 0; i < ngotos; i++)
408: {
409: if (reads[i])
410: FREE(reads[i]);
411: }
412:
413: FREE(reads);
414: FREE(edge);
415: }
416:
417:
418:
419: build_relations()
420: {
421: register int i;
422: register int j;
423: register int k;
424: register short *rulep;
425: register short *rp;
426: register shifts *sp;
427: register int length;
428: register int nedges;
429: register int done;
430: register int state1;
431: register int stateno;
432: register int symbol1;
433: register int symbol2;
434: register short *shortp;
435: register short *edge;
436: register short *states;
437: register short **new_includes;
438:
439: includes = NEW2(ngotos, short *);
440: edge = NEW2(ngotos + 1, short);
441: states = NEW2(maxrhs + 1, short);
442:
443: for (i = 0; i < ngotos; i++)
444: {
445: nedges = 0;
446: state1 = from_state[i];
447: symbol1 = accessing_symbol[to_state[i]];
448:
449: for (rulep = derives[symbol1]; *rulep > 0; rulep++)
450: {
451: length = 1;
452: states[0] = state1;
453: stateno = state1;
454:
455: for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
456: {
457: symbol2 = *rp;
458: sp = shift_table[stateno];
459: k = sp->nshifts;
460:
461: for (j = 0; j < k; j++)
462: {
463: stateno = sp->shifts[j];
464: if (accessing_symbol[stateno] == symbol2) break;
465: }
466:
467: states[length++] = stateno;
468: }
469:
470: if (!consistent[stateno])
471: add_lookback_edge(stateno, *rulep, i);
472:
473: length--;
474: done = 0;
475: while (!done)
476: {
477: done = 1;
478: rp--;
479: /* JF added rp>=ritem && I hope to god its right! */
480: if (rp>=ritem && ISVAR(*rp))
481: {
482: stateno = states[--length];
483: edge[nedges++] = map_goto(stateno, *rp);
484: if (nullable[*rp]) done = 0;
485: }
486: }
487: }
488:
489: if (nedges)
490: {
491: includes[i] = shortp = NEW2(nedges + 1, short);
492: for (j = 0; j < nedges; j++)
493: shortp[j] = edge[j];
494: shortp[nedges] = -1;
495: }
496: }
497:
498: new_includes = transpose(includes, ngotos);
499:
500: for (i = 0; i < ngotos; i++)
501: if (includes[i])
502: FREE(includes[i]);
503:
504: FREE(includes);
505:
506: includes = new_includes;
507:
508: FREE(edge);
509: FREE(states);
510: }
511:
512:
513:
514: add_lookback_edge(stateno, ruleno, gotono)
515: int stateno;
516: int ruleno;
517: int gotono;
518: {
519: register int i;
520: register int k;
521: register int found;
522: register shorts *sp;
523:
524: i = lookaheads[stateno];
525: k = lookaheads[stateno + 1];
526: found = 0;
527: while (!found && i < k)
528: {
529: if (LAruleno[i] == ruleno)
530: found = 1;
531: else
532: i++;
533: }
534:
535: if (found == 0)
536: berror("add_lookback_edge");
537:
538: sp = NEW(shorts);
539: sp->next = lookback[i];
540: sp->value = gotono;
541: lookback[i] = sp;
542: }
543:
544:
545:
546: short **
547: transpose(R, n)
548: short **R;
549: int n;
550: {
551: register short **new_R;
552: register short **temp_R;
553: register short *nedges;
554: register short *sp;
555: register int i;
556: register int k;
557:
558: nedges = NEW2(n, short);
559:
560: for (i = 0; i < n; i++)
561: {
562: sp = R[i];
563: if (sp)
564: {
565: while (*sp >= 0)
566: nedges[*sp++]++;
567: }
568: }
569:
570: new_R = NEW2(n, short *);
571: temp_R = NEW2(n, short *);
572:
573: for (i = 0; i < n; i++)
574: {
575: k = nedges[i];
576: if (k > 0)
577: {
578: sp = NEW2(k + 1, short);
579: new_R[i] = sp;
580: temp_R[i] = sp;
581: sp[k] = -1;
582: }
583: }
584:
585: FREE(nedges);
586:
587: for (i = 0; i < n; i++)
588: {
589: sp = R[i];
590: if (sp)
591: {
592: while (*sp >= 0)
593: *temp_R[*sp++]++ = i;
594: }
595: }
596:
597: FREE(temp_R);
598:
599: return (new_R);
600: }
601:
602:
603:
604: compute_FOLLOWS()
605: {
606: register int i;
607:
608: digraph(includes);
609:
610: for (i = 0; i < ngotos; i++)
611: {
612: if (includes[i]) FREE(includes[i]);
613: }
614:
615: FREE(includes);
616: }
617:
618:
619:
620: compute_lookaheads()
621: {
622: register int i;
623: register int n;
624: register unsigned *fp1;
625: register unsigned *fp2;
626: register unsigned *fp3;
627: register shorts *sp;
628: register unsigned *rowp;
629: /* register short *rulep; JF unused */
630: /* register int count; JF unused */
631: register shorts *sptmp;/* JF */
632:
633: rowp = LA;
634: n = lookaheads[nstates];
635: for (i = 0; i < n; i++)
636: {
637: fp3 = rowp + tokensetsize;
638: for (sp = lookback[i]; sp; sp = sp->next)
639: {
640: fp1 = rowp;
641: fp2 = F + tokensetsize * sp->value;
642: while (fp1 < fp3)
643: *fp1++ |= *fp2++;
644: }
645:
646: rowp = fp3;
647: }
648:
649: for (i = 0; i < n; i++)
650: {/* JF removed ref to freed storage */
651: for (sp = lookback[i]; sp; sp = sptmp) {
652: sptmp=sp->next;
653: FREE(sp);
654: }
655: }
656:
657: FREE(lookback);
658: FREE(F);
659: }
660:
661:
662:
663: digraph(relation)
664: short **relation;
665: {
666: register int i;
667:
668: infinity = ngotos + 2;
669: INDEX = NEW2(ngotos + 1, short);
670: VERTICES = NEW2(ngotos + 1, short);
671: top = 0;
672:
673: R = relation;
674:
675: for (i = 0; i < ngotos; i++)
676: INDEX[i] = 0;
677:
678: for (i = 0; i < ngotos; i++)
679: {
680: if (INDEX[i] == 0 && R[i])
681: traverse(i);
682: }
683:
684: FREE(INDEX);
685: FREE(VERTICES);
686: }
687:
688:
689:
690: traverse(i)
691: register int i;
692: {
693: register unsigned *fp1;
694: register unsigned *fp2;
695: register unsigned *fp3;
696: register int j;
697: register short *rp;
698:
699: int height;
700: unsigned *base;
701:
702: VERTICES[++top] = i;
703: INDEX[i] = height = top;
704:
705: base = F + i * tokensetsize;
706: fp3 = base + tokensetsize;
707:
708: rp = R[i];
709: if (rp)
710: {
711: while ((j = *rp++) >= 0)
712: {
713: if (INDEX[j] == 0)
714: traverse(j);
715:
716: if (INDEX[i] > INDEX[j])
717: INDEX[i] = INDEX[j];
718:
719: fp1 = base;
720: fp2 = F + j * tokensetsize;
721:
722: while (fp1 < fp3)
723: *fp1++ |= *fp2++;
724: }
725: }
726:
727: if (INDEX[i] == height)
728: {
729: for (;;)
730: {
731: j = VERTICES[top--];
732: INDEX[j] = infinity;
733:
734: if (i == j)
735: break;
736:
737: fp1 = base;
738: fp2 = F + j * tokensetsize;
739:
740: while (fp1 < fp3)
741: *fp2++ = *fp1++;
742: }
743: }
744: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.