![[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 / b / bin / yacc|
Return to y3.c CVS log | Up to [MW Coherent from dump] / coherent / b / 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: #include "yacc.h"
9: #include <assert.h>
10:
11: /* the size of SMAX must be related to the amount of space available
12: on the runtime stack for recursive calls to traverse.
13: (on systems which do not dynamically allocate the stack like RSX)
14: on RSX traverse takes up about 18 bytes per call which means that
15: with a 1024 byte stack we can probably make 50-55 levels of recursion
16: */
17: #define SMAX 300
18:
19: #define INFINITY 10000 /* infinity is small for a mathematician */
20: #define INITCODE 1
21: #define COPYCODE 2
22: #define UNIONCODE 3
23: #define EOFCODE 4
24: static struct
25: {
26: int s_last;
27: int s_vals[SMAX];
28: } stk; /* stack for digraph */
29:
30: static struct trans *transp; /* temporary vector for traverse */
31: static struct lset *lsetp, *fsetp;
32: static int nttrans;
33: int rread(), rincl();
34: struct lset *getset();
35:
36: genlook()
37: {
38: int code = EOFCODE;
39: rewopt();
40: cttrans();
41: transp = (struct trans *)yalloc(nttrans, sizeof *transp);
42: cdread();
43: rread(0);
44: rread(1);
45: digraph();
46: free(transp->t_trans->ng_rel);
47: rincl(0);
48: rincl(1);
49: digraph();
50: free(transp->t_trans->ng_rel);
51: free(transp);
52: fwrite(&code, sizeof code, 1, optout);
53: execute();
54: lookback();
55: }
56:
57: cdread()
58: {
59: register i, j, k;
60: struct state *stp, *stp1;
61: struct ntgo *ntp;
62: struct lset lset;
63: int code = INITCODE;
64:
65: for(i=0; i<nstates; i++) {
66: stp = &states[i];
67: for(j=0; j<stp->s_ntgo; j++) {
68: zerolset(&lset);
69: ntp = &stp->s_ntgos[j];
70: stp1 = &states[ntp->ng_st];
71: for(k=0; k<stp1->s_tgo; k++)
72: setbit(&lset, stp1->s_tgos[k].tg_trm);
73: fwrite(&code, sizeof code, 1, optout);
74: fwrite(&ntp, sizeof ntp, 1, optout);
75: fwrite(lset.l_bits, sizeof lset.l_bits, 1, optout);
76: }
77: }
78: }
79:
80:
81:
82: cttrans()
83: {
84: /* count number of nonterminal transations in automaton */
85: register i;
86:
87: nttrans = 0;
88: for(i=0; i<nstates; i++)
89: nttrans += states[i].s_ntgo;
90: }
91:
92: digraph()
93: {
94: register i;
95: stk.s_last = 0;
96: zerolev();
97: for(i=0; i<nttrans; i++)
98: if( transp[i].t_level==0 )
99: traverse(i);
100: }
101:
102: traverse(x)
103: register int x;
104: {
105: register i, y;
106: int k;
107: struct ntgo *ntp;
108: int code = UNIONCODE;
109:
110: if( stk.s_last>= (SMAX-1) )
111: yyerror(FATAL|NLNO, "internal stack overflow - SMAX");
112: stk.s_vals[++stk.s_last] = x;
113: k = stk.s_last;
114: transp[x].t_level = k;
115: ntp = transp[x].t_trans;
116:
117: for(i=0; i<ntp->ng_rel->r_count; i++) {
118: y = ntp->ng_rel->r_list[i];
119: if( transp[y].t_level==0 )
120: traverse(y);
121: if( transp[y].t_level < transp[x].t_level )
122: transp[x].t_level = transp[y].t_level;
123: fwrite(&code, sizeof code, 1, optout);
124: fwrite(&ntp, sizeof ntp, 1, optout);
125: fwrite(&transp[y].t_trans, sizeof ntp, 1, optout);
126: }
127:
128: code = COPYCODE;
129: if( transp[x].t_level == k ) {
130: transp[x].t_level = INFINITY;
131: while( (y = stk.s_vals[stk.s_last--]) != x ) {
132: transp[y].t_level = INFINITY;
133: fwrite(&code, sizeof code, 1, optout);
134: fwrite(&transp[y].t_trans, sizeof ntp, 1, optout);
135: fwrite(&ntp, sizeof ntp, 1, optout);
136: }
137: }
138: }
139:
140: /*
141: * form the set unions of the read sets and the follow sets, following
142: * the codes left in temp file by digraph
143: */
144: execute()
145: {
146: int code;
147: struct ntgo *ntp1, *ntp2;
148: register struct lset *csetp;
149:
150: rewopt();
151: csetp = lsetp = (struct lset *)yalloc(nttrans, sizeof *lsetp);
152: fsetp = NULL;
153: for(;;) {
154: if( fread(&code, sizeof code, 1, optout) != 1 )
155: yyerror(NLNO|FATAL, "eof on tempfile in execute");
156: switch( code ) {
157: case INITCODE:
158: fread(&ntp1, sizeof ntp1, 1, optout);
159: assert( csetp < &lsetp[nttrans] );
160: fread(csetp->l_bits, sizeof csetp->l_bits, 1, optout);
161: /*
162: fprintf(listout, "init: "); ptrans(ntp1);
163: prlset(csetp); fprintf(listout,"\n");
164: */
165: ntp1->ng_lset = csetp++;
166: break;
167:
168: case UNIONCODE:
169: fread(&ntp1, sizeof ntp1, 1, optout);
170: fread(&ntp2, sizeof ntp2, 1, optout);
171: /*
172: fprintf(listout, "union "); ptrans(ntp1); fprintf(listout," |=");
173: ptrans(ntp2);
174: */
175: setunion(ntp1->ng_lset, ntp2->ng_lset);
176: /*
177: prlset(ntp1->ng_lset); fprintf(listout, "\n");
178: */
179: break;
180:
181: case COPYCODE:
182: fread(&ntp1, sizeof ntp1, 1, optout);
183: fread(&ntp2, sizeof ntp2, 1, optout);
184: xxx("copy", ntp1, ntp2);
185: freeset(ntp1->ng_lset);
186: ntp1->ng_lset = getset();
187: copylset(ntp1->ng_lset, ntp2->ng_lset);
188: break;
189:
190: case EOFCODE:
191: return;
192: default:
193: yyerror(NLNO|FATAL, "bad temp file; code %o\n", code);
194: }
195: }
196: }
197:
198: lookback()
199: {
200: register i;
201:
202: for(i=0; i<nprod; i++)
203: reduce(prdptr[i]);
204:
205: }
206:
207: reduce(pp)
208: register struct prod *pp;
209: {
210: register nt, i;
211: struct sym *sp;
212: struct redn *rdp;
213: struct state *stp, *stp1;
214: int j, sno, sno1;
215: struct ntgo *ntp;
216:
217: nt = -pp->p_left;
218: sp = ntrmptr[nt-NTBASE];
219: for(j=0; j<sp->s_nstates; j++) {
220: stp = &states[sno = sp->s_states[j]];
221: for(i=0; i<stp->s_ntgo; i++) {
222: ntp = &stp->s_ntgos[i];
223: if( ntp->ng_nt == nt )
224: break;
225: }
226: assert(pp->p_prodno==0 || i<stp->s_ntgo);
227: sno1 = go2star(sno, PROD_RIGHT (pp),
228: PROD_RIGHT (pp) + 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 = PROD_RIGHT (pp);
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;
365: struct ntgo *ntp;
366: char * alloc;
367:
368: k = 0;
369: for(i = 0 ; i < nttrans ; i ++)
370: k += REL_TOTAL_SIZE (transp [i].t_level);
371:
372: alloc = yalloc (1, k);
373:
374: for(i=0; i<nttrans; i++) {
375: ntp = transp[i].t_trans;
376: ntp->ng_rel = (struct rel *) alloc;
377: REL_EXTRA_INIT (ntp->ng_rel);
378: ntp->ng_rel->r_count = transp[i].t_level;
379:
380: alloc += REL_TOTAL_SIZE (transp[i].t_level);
381: }
382: }
383:
384: startcount()
385: {
386: register i, j, k;
387: struct state *stp;
388:
389: k = 0;
390: for(i=0; i<nstates; i++) {
391: stp = &states[i];
392: for(j=0; j<stp->s_ntgo; j++) {
393: transp[k].t_trans = &stp->s_ntgos[j];
394: transp[k].t_level = 0;
395: k++;
396: }
397: }
398: }
399:
400: zerolev()
401: {
402: register i;
403: for(i=0; i<nttrans; i++)
404: transp[i].t_level = 0;
405: }
406:
407: rsearch(ntp)
408: struct ntgo *ntp;
409: {
410: register lb, nb;
411: register struct ntgo *el;
412: int ub;
413:
414: lb = 0;
415: ub = nttrans-1;
416: do {
417: nb = (ub+lb)/2;
418: if( (el = transp[nb].t_trans) < ntp )
419: lb = nb+1;
420: else if( el > ntp )
421: ub = nb-1;
422: else
423: return(nb);
424: } while( lb<=ub );
425: yyerror(NLNO|FATAL, "oops in rsearch");
426: }
427:
428: ssearch(ntp)
429: struct ntgo *ntp;
430: {
431: register lb, nb;
432: register struct ntgo *el;
433: int ub;
434:
435: lb = 0;
436: ub = nstates-1;
437:
438: do {
439: nb = (ub+lb) / 2;
440: el = states[nb].s_ntgos;
441: if( ntp < el )
442: ub = nb-1;
443: else if( ntp >= &el[states[nb].s_ntgo] )
444: lb = nb+1;
445: else
446: return(nb);
447: } while( lb<=ub );
448: yyerror(NLNO|FATAL, "oops in ssearch");
449: }
450:
451: prodl(pp)
452: register struct prod *pp;
453: {
454: register *ip;
455:
456: ip = PROD_RIGHT (pp);
457: while (* ip ++ != -1)
458: /* DO NOTHING */;
459: return ip - PROD_RIGHT (pp) - 1; /* BONZO OR NO??? */
460: }
461:
462: struct lset *
463: getset()
464: {
465: register struct lset *lp;
466: if( fsetp ) {
467: lp = fsetp;
468: fsetp = fsetp->l_next;
469: return(lp);
470: }
471: lp = (struct lset *)yalloc(1, sizeof *lp);
472: return(lp);
473: }
474:
475: freeset(lp)
476: struct lset *lp;
477: {
478: lp->l_next = fsetp;
479: fsetp = lp;
480: }
481:
482: frlset()
483: {
484: register struct state *stp;
485: register i, j;
486: struct lset *lp, *lp1;
487:
488: free(states[0].s_tgos);
489: free(states[0].s_ntgos);
490: for(i=0; i<nstates; i++) {
491: stp = &states[i];
492: for(j=0; j<stp->s_nred; j++)
493: freeset(stp->s_reds[j].rd_lset);
494: if( stp->s_reds != (struct redn *)NULL ) /* MWC DSC */
495: free(stp->s_reds);
496: for(j=0; j<stp->s_ntgo; j++)
497: freeset(stp->s_ntgos[j].ng_lset);
498: }
499: lp = fsetp;
500: while( lp ) {
501: lp1 = lp->l_next;
502: if( lp<&lsetp[0] || lp>=&lsetp[nttrans] )
503: free(lp);
504: lp = lp1;
505: }
506: free(lsetp);
507: }
508:
509: xxx(s, ntp1, ntp2)
510: char *s;
511: struct ntgo *ntp1, *ntp2;
512: {
513: if( !yydebug )
514: return;
515: ptrans(ntp1); fprintf(listout, " %s ", s); ptrans(ntp2);
516: fprintf(listout, "\n");
517: }
518: ptrans(ntp)
519: struct ntgo *ntp;
520: {
521: int sno;
522: sno = ssearch(ntp);
523: fprintf(listout, "(%d, %s)", sno, ptosym(ntp->ng_nt));
524: }
525:
526: prlset(ls)
527: struct lset *ls;
528: {
529: register i, once;
530: fprintf(listout, "[");
531: once = 0;
532: for(i=first(ls); i>=0; i=next(ls,i)) {
533: if( once++ ) fprintf(listout, ",");
534: fprintf(listout, "%s", trmptr[i]->s_name);
535: }
536: fprintf(listout, "]");
537: }
538:
539:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.