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