![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to y3.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / d / bin / yacc|
Return to y3.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin / yacc |
1.1 root 1: /*
2: * LALR-1 parser generator
3: * generation of lookahead sets
4: * the algorithm is thanks to Frank D. Remer & Thomas J Pennello,
5: * "Efficient computation of LALR(1) lookahead sets",
6: * SIGPLAN conference 1979.
7: */
8:
9: #include "yacc.h"
10: #include <assert.h>
11:
12: /* the size of SMAX must be related to the amount of space available
13: on the runtime stack for recursive calls to traverse.
14: (on systems which do not dynamically allocate the stack like RSX)
15: on RSX traverse takes up about 18 bytes per call which means that
16: with a 1024 byte stack we can probably make 50-55 levels of recursion
17: */
18: #define SMAX 100
19:
20: #define INFINITY 10000 /* infinity is small for a mathematician */
21: #define INITCODE 1
22: #define COPYCODE 2
23: #define UNIONCODE 3
24: #define EOFCODE 4
25: static struct
26: {
27: int s_last;
28: int s_vals[SMAX];
29: } stk; /* stack for digraph */
30:
31: static struct trans *transp; /* temporary vector for traverse */
32: static struct lset *lsetp, *fsetp;
33: static int nttrans;
34: int rread(), rincl();
35: struct lset *getset();
36:
37: genlook()
38: {
39: int code = EOFCODE;
40: rewopt();
41: cttrans();
42: transp = (struct trans *)yalloc(nttrans, sizeof *transp);
43: cdread();
44: rread(0);
45: rread(1);
46: digraph();
47: free(transp->t_trans->ng_rel);
48: rincl(0);
49: rincl(1);
50: digraph();
51: free(transp->t_trans->ng_rel);
52: free(transp);
53: fwrite(&code, sizeof code, 1, optout);
54: execute();
55: lookback();
56: }
57:
58: cdread()
59: {
60: register i, j, k;
61: struct state *stp, *stp1;
62: struct ntgo *ntp;
63: struct lset lset;
64: int code = INITCODE;
65:
66: for(i=0; i<nstates; i++) {
67: stp = &states[i];
68: for(j=0; j<stp->s_ntgo; j++) {
69: zerolset(&lset);
70: ntp = &stp->s_ntgos[j];
71: stp1 = &states[ntp->ng_st];
72: for(k=0; k<stp1->s_tgo; k++)
73: setbit(&lset, stp1->s_tgos[k].tg_trm);
74: fwrite(&code, sizeof code, 1, optout);
75: fwrite(&ntp, sizeof ntp, 1, optout);
76: fwrite(lset.l_bits, sizeof lset.l_bits, 1, optout);
77: }
78: }
79: }
80:
81:
82:
83: cttrans()
84: {
85: /* count number of nonterminal transations in automaton */
86: register i;
87:
88: nttrans = 0;
89: for(i=0; i<nstates; i++)
90: nttrans += states[i].s_ntgo;
91: }
92:
93: digraph()
94: {
95: register i;
96: stk.s_last = 0;
97: zerolev();
98: for(i=0; i<nttrans; i++)
99: if( transp[i].t_level==0 )
100: traverse(i);
101: }
102:
103: traverse(x)
104: register int x;
105: {
106: register i, y;
107: int k;
108: struct ntgo *ntp;
109: int code = UNIONCODE;
110:
111: if( stk.s_last>= (SMAX-1) )
112: yyerror(FATAL|NLNO, "internal stack overflow - SMAX");
113: stk.s_vals[++stk.s_last] = x;
114: k = stk.s_last;
115: transp[x].t_level = k;
116: ntp = transp[x].t_trans;
117:
118: for(i=0; i<ntp->ng_rel->r_count; i++) {
119: y = ntp->ng_rel->r_list[i];
120: if( transp[y].t_level==0 )
121: traverse(y);
122: if( transp[y].t_level < transp[x].t_level )
123: transp[x].t_level = transp[y].t_level;
124: fwrite(&code, sizeof code, 1, optout);
125: fwrite(&ntp, sizeof ntp, 1, optout);
126: fwrite(&transp[y].t_trans, sizeof ntp, 1, optout);
127: }
128:
129: code = COPYCODE;
130: if( transp[x].t_level == k ) {
131: transp[x].t_level = INFINITY;
132: while( (y = stk.s_vals[stk.s_last--]) != x ) {
133: transp[y].t_level = INFINITY;
134: fwrite(&code, sizeof code, 1, optout);
135: fwrite(&transp[y].t_trans, sizeof ntp, 1, optout);
136: fwrite(&ntp, sizeof ntp, 1, optout);
137: }
138: }
139: }
140:
141: /*
142: * form the set unions of the read sets and the follow sets, following
143: * the codes left in temp file by digraph
144: */
145: execute()
146: {
147: int code;
148: struct ntgo *ntp1, *ntp2;
149: register struct lset *csetp;
150:
151: rewopt();
152: csetp = lsetp = (struct lset *)yalloc(nttrans, sizeof *lsetp);
153: fsetp = NULL;
154: for(;;) {
155: if( fread(&code, sizeof code, 1, optout) != 1 )
156: yyerror(NLNO|FATAL, "eof on tempfile in execute");
157: switch( code ) {
158: case INITCODE:
159: fread(&ntp1, sizeof ntp1, 1, optout);
160: assert( csetp < &lsetp[nttrans] );
161: fread(csetp->l_bits, sizeof csetp->l_bits, 1, optout);
162: /*
163: fprintf(listout, "init: "); ptrans(ntp1);
164: prlset(csetp); fprintf(listout,"\n");
165: */
166: ntp1->ng_lset = csetp++;
167: break;
168:
169: case UNIONCODE:
170: fread(&ntp1, sizeof ntp1, 1, optout);
171: fread(&ntp2, sizeof ntp2, 1, optout);
172: /*
173: fprintf(listout, "union "); ptrans(ntp1); fprintf(listout," |=");
174: ptrans(ntp2);
175: */
176: setunion(ntp1->ng_lset, ntp2->ng_lset);
177: /*
178: prlset(ntp1->ng_lset); fprintf(listout, "\n");
179: */
180: break;
181:
182: case COPYCODE:
183: fread(&ntp1, sizeof ntp1, 1, optout);
184: fread(&ntp2, sizeof ntp2, 1, optout);
185: xxx("copy", ntp1, ntp2);
186: freeset(ntp1->ng_lset);
187: ntp1->ng_lset = getset();
188: copylset(ntp1->ng_lset, ntp2->ng_lset);
189: break;
190:
191: case EOFCODE:
192: return;
193: default:
194: yyerror(NLNO|FATAL, "bad temp file; code %o\n", code);
195: }
196: }
197: }
198:
199: lookback()
200: {
201: register i;
202:
203: for(i=0; i<nprod; i++)
204: reduce(prdptr[i]);
205:
206: }
207:
208: reduce(pp)
209: register struct prod *pp;
210: {
211: register nt, i;
212: struct sym *sp;
213: struct redn *rdp;
214: struct state *stp, *stp1;
215: int j, sno, sno1;
216: struct ntgo *ntp;
217:
218: nt = -pp->p_left;
219: sp = ntrmptr[nt-NTBASE];
220: for(j=0; j<sp->s_nstates; j++) {
221: stp = &states[sno = sp->s_states[j]];
222: for(i=0; i<stp->s_ntgo; i++) {
223: ntp = &stp->s_ntgos[i];
224: if( ntp->ng_nt == nt )
225: break;
226: }
227: assert(pp->p_prodno==0 || i<stp->s_ntgo);
228: sno1 = go2star(sno, pp->p_right, pp->p_right+prodl(pp));
229: stp1 = &states[sno1];
230: if( stp1->s_reds == (struct redn *)NULL ) { /* MWC DSC */
231: stp1->s_reds = (struct redn *)yalloc(stp1->s_nred, sizeof *stp1->s_reds);
232: stp1->s_nred = 0;
233: }
234: rdp = stp1->s_reds;
235: for(i=0; i<stp1->s_nred; i++,rdp++)
236: if( rdp->rd_prod==pp )
237: break;
238: if( yydebug ) {
239: fprintf(listout, "(%d, pdn %d) ", sno1, pp->p_prodno);
240: prlset(ntp->ng_lset);
241: fprintf(listout, "\n");
242: }
243: if( i==stp1->s_nred ) {
244: rdp->rd_prod = pp;
245: rdp->rd_lset = getset();
246: if( pp->p_prodno!=0 ) {
247: copylset(rdp->rd_lset, ntp->ng_lset);
248: } else {
249: zerolset(rdp->rd_lset);
250: setbit(rdp->rd_lset, EOFNO);
251: }
252: stp1->s_nred++;
253: } else {
254: setunion(rdp->rd_lset, ntp->ng_lset);
255: }
256: }
257: }
258:
259: go2star(sno, ip, fin)
260: register *ip;
261: int *fin;
262: {
263: register i;
264: register struct state *stp;
265:
266: while( ip!=fin ) {
267: stp = &states[sno];
268: if( *ip>=NTBASE ) {
269: for(i=0; i<stp->s_ntgo; i++)
270: if( stp->s_ntgos[i].ng_nt == *ip )
271: break;
272: assert(i<stp->s_ntgo);
273: sno = stp->s_ntgos[i].ng_st;
274: } else {
275: for(i=0; i<stp->s_tgo; i++)
276: if( stp->s_tgos[i].tg_trm == *ip )
277: break;
278: assert(i<stp->s_tgo);
279: sno = stp->s_tgos[i].tg_st;
280: }
281: ip++;
282: }
283: return(sno);
284: }
285:
286: rread(todo)
287: {
288: struct state *stp;
289: register struct sym *sp;
290: register i, j;
291: int p;
292: struct ntgo *ntp;
293:
294: if( todo )
295: zerolev();
296: else
297: startcount();
298:
299: for(i=0; i<nttrans; i++) {
300: stp = &states[transp[i].t_trans->ng_st];
301: for(j=0; j<stp->s_ntgo; j++) {
302: ntp = &stp->s_ntgos[j];
303: sp = ntrmptr[ntp->ng_nt-NTBASE];
304: if( sp->s_flags&DERIV ) {
305: p = transp[i].t_level++;
306: if( todo ) {
307: transp[i].t_trans->ng_rel->r_list[p] =
308: rsearch(ntp);
309: xxx("reads",transp[i].t_trans,ntp);
310: }
311: break;
312: }
313: }
314: }
315: if( !todo )
316: endcount();
317: }
318:
319: rincl(todo)
320: {
321: register i, j;
322: int *pb, *pe, k, p, sno, sno1, ind, nt;
323: struct state *stp;
324: struct prod *pp;
325: struct ntgo *ntp;
326: struct sym *sp;
327:
328: if( todo )
329: zerolev();
330: else
331: startcount();
332: for(i=0; i<nttrans; i++) {
333: sno = ssearch(transp[i].t_trans);
334: sp = ntrmptr[transp[i].t_trans->ng_nt-NTBASE];
335: for(j=0; j<sp->s_nprods; j++) {
336: pp = sp->s_prods[j];
337: pb = pp->p_right;
338: pe = pb + prodl(pp);
339: while( pb <= --pe && (nt = *pe) >= NTBASE ) {
340: sno1 = go2star(sno, pb, pe);
341: stp = &states[sno1];
342: for(k=0; k<stp->s_ntgo; k++)
343: if( stp->s_ntgos[k].ng_nt==nt )
344: break;
345: assert(k<stp->s_ntgo);
346: ind = rsearch(&stp->s_ntgos[k]);
347: p = transp[ind].t_level++;
348: if( todo ) {
349: ntp = transp[ind].t_trans;
350: xxx("includes", ntp, transp[i].t_trans);
351: ntp->ng_rel->r_list[p] = i;
352: }
353: if( (ntrmptr[nt-NTBASE]->s_flags&DERIV)==0 )
354: break;
355: }
356: }
357: }
358: if( !todo )
359: endcount();
360: }
361:
362: endcount()
363: {
364: register i, k, *relp; /* relp must be integer pointer */
365: struct ntgo *ntp;
366: k = 0;
367: for(i=0; i<nttrans; i++)
368: {
369: k += transp[i].t_level+1; /* include 1 for count */
370: }
371: relp = (int *)yalloc(k, sizeof *relp);
372: for(i=0; i<nttrans; i++) {
373: ntp = transp[i].t_trans;
374: ntp->ng_rel = relp;
375: ntp->ng_rel->r_count = transp[i].t_level;
376: relp += transp[i].t_level+1;
377: }
378: }
379:
380: startcount()
381: {
382: register i, j, k;
383: struct state *stp;
384:
385: k = 0;
386: for(i=0; i<nstates; i++) {
387: stp = &states[i];
388: for(j=0; j<stp->s_ntgo; j++) {
389: transp[k].t_trans = &stp->s_ntgos[j];
390: transp[k].t_level = 0;
391: k++;
392: }
393: }
394: }
395:
396: zerolev()
397: {
398: register i;
399: for(i=0; i<nttrans; i++)
400: transp[i].t_level = 0;
401: }
402:
403: rsearch(ntp)
404: struct ntgo *ntp;
405: {
406: register lb, nb;
407: register struct ntgo *el;
408: int ub;
409:
410: lb = 0;
411: ub = nttrans-1;
412: do {
413: nb = (ub+lb)/2;
414: if( (el = transp[nb].t_trans) < ntp )
415: lb = nb+1;
416: else if( el > ntp )
417: ub = nb-1;
418: else
419: return(nb);
420: } while( lb<=ub );
421: yyerror(NLNO|FATAL, "oops in rsearch");
422: }
423:
424: ssearch(ntp)
425: struct ntgo *ntp;
426: {
427: register lb, nb;
428: register struct ntgo *el;
429: int ub;
430:
431: lb = 0;
432: ub = nstates-1;
433:
434: do {
435: nb = (ub+lb) / 2;
436: el = states[nb].s_ntgos;
437: if( ntp < el )
438: ub = nb-1;
439: else if( ntp >= &el[states[nb].s_ntgo] )
440: lb = nb+1;
441: else
442: return(nb);
443: } while( lb<=ub );
444: yyerror(NLNO|FATAL, "oops in ssearch");
445: }
446:
447: prodl(pp)
448: register struct prod *pp;
449: {
450: register *ip;
451:
452: ip = pp->p_right;
453: while( *ip++ != -1 );
454: return( ip-pp->p_right-1 ); /* BONZO OR NO??? */
455: }
456:
457: struct lset *
458: getset()
459: {
460: register struct lset *lp;
461: if( fsetp ) {
462: lp = fsetp;
463: fsetp = fsetp->l_next;
464: return(lp);
465: }
466: lp = (struct lset *)yalloc(1, sizeof *lp);
467: return(lp);
468: }
469:
470: freeset(lp)
471: struct lset *lp;
472: {
473: lp->l_next = fsetp;
474: fsetp = lp;
475: }
476:
477: frlset()
478: {
479: register struct state *stp;
480: register i, j;
481: struct lset *lp, *lp1;
482:
483: free(states[0].s_tgos);
484: free(states[0].s_ntgos);
485: for(i=0; i<nstates; i++) {
486: stp = &states[i];
487: for(j=0; j<stp->s_nred; j++)
488: freeset(stp->s_reds[j].rd_lset);
489: if( stp->s_reds != (struct redn *)NULL ) /* MWC DSC */
490: free(stp->s_reds);
491: for(j=0; j<stp->s_ntgo; j++)
492: freeset(stp->s_ntgos[j].ng_lset);
493: }
494: lp = fsetp;
495: while( lp ) {
496: lp1 = lp->l_next;
497: if( lp<&lsetp[0] || lp>=&lsetp[nttrans] )
498: free(lp);
499: lp = lp1;
500: }
501: free(lsetp);
502: }
503:
504: xxx(s, ntp1, ntp2)
505: char *s;
506: struct ntgo *ntp1, *ntp2;
507: {
508: if( !yydebug )
509: return;
510: ptrans(ntp1); fprintf(listout, " %s ", s); ptrans(ntp2);
511: fprintf(listout, "\n");
512: }
513: ptrans(ntp)
514: struct ntgo *ntp;
515: {
516: int sno;
517: sno = ssearch(ntp);
518: fprintf(listout, "(%d, %s)", sno, ptosym(ntp->ng_nt));
519: }
520:
521: prlset(ls)
522: struct lset *ls;
523: {
524: register i, once;
525: fprintf(listout, "[");
526: once = 0;
527: for(i=first(ls); i>=0; i=next(ls,i)) {
528: if( once++ ) fprintf(listout, ",");
529: fprintf(listout, "%s", trmptr[i]->s_name);
530: }
531: fprintf(listout, "]");
532: }
533:
534:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.