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