![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to y1.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / yacc|
Return to y1.c CVS log | Up to [Research Unix] / researchv10no / cmd / yacc |
1.1 root 1: # include "dextern"
2: # include <signal.h>
3:
4: /* variables used locally */
5:
6: /* lookahead computations */
7:
8: int tbitset; /* size of lookahead sets */
9: struct looksets lkst [ LSETSIZE ];
10: int nlset = 0; /* next lookahead set index */
11: int nolook = 0; /* flag to suppress lookahead computations */
12: struct looksets clset; /* temporary storage for lookahead computations */
13:
14: /* working set computations */
15:
16: struct wset wsets[ WSETSIZE ];
17: struct wset *cwp;
18:
19: /* state information */
20:
21: int nstate = 0; /* number of states */
22: struct item *pstate[NSTATES+2]; /* pointers to the descriptions of the states */
23: int tystate[NSTATES]; /* contains type information about the states */
24: int indgo[NSTATES]; /* index to the stored goto table */
25: int tstates[ NTERMS ]; /* states generated by terminal gotos */
26: int ntstates[ NNONTERM ]; /* states generated by nonterminal gotos */
27: int mstates[ NSTATES ]; /* chain of overflows of term/nonterm generation lists */
28: int rlines[ NPROD ]; /* line number for this rule */
29:
30: /* storage for the actions in the parser */
31:
32: int amem[ACTSIZE]; /* action table storage */
33: int *memp = amem; /* next free action table position */
34:
35: /* other storage areas */
36:
37: int temp1[TEMPSIZE]; /* temporary storage, indexed by terms + ntokens or states */
38: int lineno= 1; /* current input line number */
39: int fatfl = 1; /* if on, error is fatal */
40: int nerrors = 0; /* number of errors */
41:
42: /* storage for information about the nonterminals */
43:
44: int **pres[NNONTERM+2]; /* vector of pointers to productions yielding each nonterminal */
45: struct looksets *pfirst[NNONTERM+2]; /* vector of pointers to first sets for each nonterminal */
46: int pempty[NNONTERM+1]; /* vector of nonterminals nontrivially deriving e */
47:
48: main(argc,argv) int argc; char *argv[]; {
49: extern intr();
50:
51: if (signal(SIGINT, SIG_IGN) != SIG_IGN)
52: signal(SIGINT, intr);
53: if (signal(SIGHUP, SIG_IGN) != SIG_IGN)
54: signal(SIGHUP, intr);
55: setup(argc,argv); /* initialize and read productions */
56: tbitset = NWORDS(ntokens);
57: cpres(); /* make table of which productions yield a given nonterminal */
58: cempty(); /* make a table of which nonterminals can match the empty string */
59: cpfir(); /* make a table of firsts of nonterminals */
60: stagen(); /* generate the states */
61: output(); /* write the states and the tables */
62: go2out();
63: hideprod();
64: summary();
65: callopt();
66: others();
67: exit(0);
68: }
69:
70: others(){ /* put out other arrays, copy the parsers */
71: register c, i, j;
72:
73: finput = fopen( PARSER, "r" );
74: if( finput == NULL ) error( "cannot find parser %s", PARSER );
75:
76: warray( "yyr1", levprd, nprod );
77:
78: aryfil( temp1, nprod, 0 );
79: PLOOP(1,i)temp1[i] = prdptr[i+1]-prdptr[i]-2;
80: warray( "yyr2", temp1, nprod );
81:
82: aryfil( temp1, nstate, -1000 );
83: TLOOP(i){
84: for( j=tstates[i]; j!=0; j=mstates[j] ){
85: temp1[j] = tokset[i].value;
86: }
87: }
88: NTLOOP(i){
89: for( j=ntstates[i]; j!=0; j=mstates[j] ){
90: temp1[j] = -i;
91: }
92: }
93: warray( "yychk", temp1, nstate );
94:
95: warray( "yydef", defact, nstate );
96:
97: /* copy parser text */
98:
99: while( (c=getc(finput) ) != EOF ){
100: if( c == '$' ){
101: if( (c=getc(finput)) != 'A' ) putc( '$', ftable );
102: else { /* copy actions */
103: faction = fopen( actname, "r" );
104: if( faction == NULL ) error( "cannot reopen action tempfile" );
105: while( (c=getc(faction) ) != EOF ) putc( c, ftable );
106: fclose(faction);
107: ZAPFILE(actname);
108: c = getc(finput);
109: }
110: }
111: putc( c, ftable );
112: }
113:
114: fclose( ftable );
115: }
116:
117: char *chcopy( p, q ) char *p, *q; {
118: /* copies string q into p, returning next free char ptr */
119: while( *p = *q++ ) ++p;
120: return( p );
121: }
122:
123: # define ISIZE 400
124: char *writem(pp) int *pp; { /* creates output string for item pointed to by pp */
125: int i,*p;
126: static char sarr[ISIZE];
127: char *q;
128:
129: for( p=pp; *p>0 ; ++p ) ;
130: p = prdptr[-*p];
131: q = chcopy( sarr, nontrst[*p-NTBASE].name );
132: q = chcopy( q, " : " );
133:
134: for(;;){
135: *q++ = ++p==pp ? '.' : ' ';
136: *q = '\0';
137: if((i = *p) <= 0) break;
138: q = chcopy( q, symnam(i) );
139: if( q> &sarr[ISIZE-30] ) error( "item too big" );
140: }
141:
142: if( (i = *pp) < 0 ){ /* an item calling for a reduction */
143: q = chcopy( q, " (" );
144: sprintf( q, "%d)", -i );
145: }
146:
147: return( sarr );
148: }
149:
150: char *symnam(i){ /* return a pointer to the name of symbol i */
151: char *cp;
152:
153: cp = (i>=NTBASE) ? nontrst[i-NTBASE].name : tokset[i].name ;
154: if( *cp == ' ' ) ++cp;
155: return( cp );
156: }
157:
158: struct wset *zzcwp = wsets;
159: int zzgoent = 0;
160: int zzgobest = 0;
161: int zzacent = 0;
162: int zzexcp = 0;
163: int zzclose = 0;
164: int zzsrconf = 0;
165: int * zzmemsz = mem0;
166: int zzrrconf = 0;
167:
168: summary(){ /* output the summary on y.output */
169:
170: if( foutput!=NULL ){
171: fprintf( foutput, "\n%d/%d terminals, %d/%d nonterminals\n", ntokens, NTERMS,
172: nnonter, NNONTERM );
173: fprintf( foutput, "%d/%d grammar rules, %d/%d states\n", nprod, NPROD, nstate, NSTATES );
174: fprintf( foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n", zzsrconf, zzrrconf );
175: fprintf( foutput, "%d/%d working sets used\n", zzcwp-wsets, WSETSIZE );
176: fprintf( foutput, "memory: states,etc. %d/%d, parser %d/%d\n", zzmemsz-mem0, MEMSIZE,
177: memp-amem, ACTSIZE );
178: fprintf( foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE );
179: fprintf( foutput, "%d extra closures\n", zzclose - 2*nstate );
180: fprintf( foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp );
181: fprintf( foutput, "%d goto entries\n", zzgoent );
182: fprintf( foutput, "%d entries saved by goto default\n", zzgobest );
183: }
184: if( zzsrconf!=0 || zzrrconf!=0 ){
185: fprintf( stdout,"\nconflicts: ");
186: if( zzsrconf )fprintf( stdout, "%d shift/reduce" , zzsrconf );
187: if( zzsrconf && zzrrconf )fprintf( stdout, ", " );
188: if( zzrrconf )fprintf( stdout, "%d reduce/reduce" , zzrrconf );
189: fprintf( stdout, "\n" );
190: }
191:
192: if( ftemp != NULL ) fclose( ftemp );
193: if( fdefine != NULL ) fclose( fdefine );
194: }
195:
196: /* VARARGS1 */
197: error(s,a1) char *s; { /* write out error comment */
198:
199: ++nerrors;
200: fprintf( stderr, "\n fatal error: ");
201: fprintf( stderr, s,a1);
202: fprintf( stderr, ", line %d\n", lineno );
203: if( !fatfl ) return;
204: summary();
205: cleantmp();
206: exit(1);
207: }
208:
209: aryfil( v, n, c ) int *v,n,c; { /* set elements 0 through n-1 to c */
210: int i;
211: for( i=0; i<n; ++i ) v[i] = c;
212: }
213:
214: setunion( a, b ) register *a, *b; {
215: /* set a to the union of a and b */
216: /* return 1 if b is not a subset of a, 0 otherwise */
217: register i, x, sub;
218:
219: sub = 0;
220: SETLOOP(i){
221: *a = (x = *a)|*b++;
222: if( *a++ != x ) sub = 1;
223: }
224: return( sub );
225: }
226:
227: prlook( p ) struct looksets *p;{
228: register j, *pp;
229: pp = p->lset;
230: if( pp == 0 ) fprintf( foutput, "\tNULL");
231: else {
232: fprintf( foutput, " { " );
233: TLOOP(j) {
234: if( BIT(pp,j) ) fprintf( foutput, "%s ", symnam(j) );
235: }
236: fprintf( foutput, "}" );
237: }
238: }
239:
240: cpres(){ /* compute an array with the beginnings of productions yielding given nonterminals
241: The array pres points to these lists */
242: /* the array pyield has the lists: the total size is only NPROD+1 */
243: register **pmem;
244: register c, j, i;
245: static int * pyield[NPROD];
246:
247: pmem = pyield;
248:
249: NTLOOP(i){
250: c = i+NTBASE;
251: pres[i] = pmem;
252: fatfl = 0; /* make undefined symbols nonfatal */
253: PLOOP(0,j){
254: if (*prdptr[j] == c) *pmem++ = prdptr[j]+1;
255: }
256: if(pres[i] == pmem){
257: error("nonterminal %s not defined!", nontrst[i].name);
258: }
259: }
260: pres[i] = pmem;
261: fatfl = 1;
262: if( nerrors ){
263: summary();
264: cleantmp();
265: exit(1);
266: }
267: if( pmem != &pyield[nprod] ) error( "internal Yacc error: pyield %d", pmem-&pyield[nprod] );
268: }
269:
270: int indebug = 0;
271: cpfir() {
272: /* compute an array with the first of nonterminals */
273: register *p, **s, i, **t, ch, changes;
274:
275: zzcwp = &wsets[nnonter];
276: NTLOOP(i){
277: aryfil( wsets[i].ws.lset, tbitset, 0 );
278: t = pres[i+1];
279: for( s=pres[i]; s<t; ++s ){ /* initially fill the sets */
280: for( p = *s; (ch = *p) > 0 ; ++p ) {
281: if( ch < NTBASE ) {
282: SETBIT( wsets[i].ws.lset, ch );
283: break;
284: }
285: else if( !pempty[ch-NTBASE] ) break;
286: }
287: }
288: }
289:
290: /* now, reflect transitivity */
291:
292: changes = 1;
293: while( changes ){
294: changes = 0;
295: NTLOOP(i){
296: t = pres[i+1];
297: for( s=pres[i]; s<t; ++s ){
298: for( p = *s; ( ch = (*p-NTBASE) ) >= 0; ++p ) {
299: changes |= setunion( wsets[i].ws.lset, wsets[ch].ws.lset );
300: if( !pempty[ch] ) break;
301: }
302: }
303: }
304: }
305:
306: NTLOOP(i) pfirst[i] = flset( &wsets[i].ws );
307: if( !indebug ) return;
308: if( (foutput!=NULL) ){
309: NTLOOP(i) {
310: fprintf( foutput, "\n%s: ", nontrst[i].name );
311: prlook( pfirst[i] );
312: fprintf( foutput, " %d\n", pempty[i] );
313: }
314: }
315: }
316:
317: state(c){ /* sorts last state,and sees if it equals earlier ones. returns state number */
318: int size1,size2;
319: register i;
320: struct item *p1, *p2, *k, *l, *q1, *q2;
321: p1 = pstate[nstate];
322: p2 = pstate[nstate+1];
323: if(p1==p2) return(0); /* null state */
324: /* sort the items */
325: for(k=p2-1;k>p1;k--) { /* make k the biggest */
326: for(l=k-1;l>=p1;--l)if( l->pitem > k->pitem ){
327: int *s;
328: struct looksets *ss;
329: s = k->pitem;
330: k->pitem = l->pitem;
331: l->pitem = s;
332: ss = k->look;
333: k->look = l->look;
334: l->look = ss;
335: }
336: }
337: size1 = p2 - p1; /* size of state */
338:
339: for( i= (c>=NTBASE)?ntstates[c-NTBASE]:tstates[c]; i != 0; i = mstates[i] ) {
340: /* get ith state */
341: q1 = pstate[i];
342: q2 = pstate[i+1];
343: size2 = q2 - q1;
344: if (size1 != size2) continue;
345: k=p1;
346: for(l=q1;l<q2;l++) {
347: if( l->pitem != k->pitem ) break;
348: ++k;
349: }
350: if (l != q2) continue;
351: /* found it */
352: pstate[nstate+1] = pstate[nstate]; /* delete last state */
353: /* fix up lookaheads */
354: if( nolook ) return(i);
355: for( l=q1,k=p1; l<q2; ++l,++k ){
356: int s;
357: SETLOOP(s) clset.lset[s] = l->look->lset[s];
358: if( setunion( clset.lset, k->look->lset ) ) {
359: tystate[i] = MUSTDO;
360: /* register the new set */
361: l->look = flset( &clset );
362: }
363: }
364: return (i);
365: }
366: /* state is new */
367: if( nolook ) error( "yacc state/nolook error" );
368: pstate[nstate+2] = p2;
369: if(nstate+1 >= NSTATES) error("too many states" );
370: if( c >= NTBASE ){
371: mstates[ nstate ] = ntstates[ c-NTBASE ];
372: ntstates[ c-NTBASE ] = nstate;
373: }
374: else {
375: mstates[ nstate ] = tstates[ c ];
376: tstates[ c ] = nstate;
377: }
378: tystate[nstate]=MUSTDO;
379: return(nstate++);
380: }
381:
382: int pidebug = 0; /* debugging flag for putitem */
383: putitem( ptr, lptr ) int *ptr; struct looksets *lptr; {
384: register struct item *j;
385:
386: if( pidebug && (foutput!=NULL) ) {
387: fprintf( foutput, "putitem(%s), state %d\n", writem(ptr), nstate );
388: }
389: j = pstate[nstate+1];
390: j->pitem = ptr;
391: if( !nolook ) j->look = flset( lptr );
392: pstate[nstate+1] = ++j;
393: if( (int *)j > zzmemsz ){
394: zzmemsz = (int *)j;
395: if( zzmemsz >= &mem0[MEMSIZE] ) error( "out of state space" );
396: }
397: }
398:
399: cempty(){ /* mark nonterminals which derive the empty string */
400: /* also, look for nonterminals which don't derive any token strings */
401:
402: # define EMPTY 1
403: # define WHOKNOWS 0
404: # define OK 1
405:
406: register i, *p;
407:
408: /* first, use the array pempty to detect productions that can never be reduced */
409: /* set pempty to WHONOWS */
410: aryfil( pempty, nnonter+1, WHOKNOWS );
411:
412: /* now, look at productions, marking nonterminals which derive something */
413:
414: more:
415: PLOOP(0,i){
416: if( pempty[ *prdptr[i] - NTBASE ] ) continue;
417: for( p=prdptr[i]+1; *p>=0; ++p ){
418: if( *p>=NTBASE && pempty[ *p-NTBASE ] == WHOKNOWS ) break;
419: }
420: if( *p < 0 ){ /* production can be derived */
421: pempty[ *prdptr[i]-NTBASE ] = OK;
422: goto more;
423: }
424: }
425:
426: /* now, look at the nonterminals, to see if they are all OK */
427:
428: NTLOOP(i){
429: /* the added production rises or falls as the start symbol ... */
430: if( i == 0 ) continue;
431: if( pempty[ i ] != OK ) {
432: fatfl = 0;
433: error( "nonterminal %s never derives any token string", nontrst[i].name );
434: }
435: }
436:
437: if( nerrors ){
438: summary();
439: cleantmp();
440: exit(1);
441: }
442:
443: /* now, compute the pempty array, to see which nonterminals derive the empty string */
444:
445: /* set pempty to WHOKNOWS */
446:
447: aryfil( pempty, nnonter+1, WHOKNOWS );
448:
449: /* loop as long as we keep finding empty nonterminals */
450:
451: again:
452: PLOOP(1,i){
453: if( pempty[ *prdptr[i]-NTBASE ]==WHOKNOWS ){ /* not known to be empty */
454: for( p=prdptr[i]+1; *p>=NTBASE && pempty[*p-NTBASE]==EMPTY ; ++p ) ;
455: if( *p < 0 ){ /* we have a nontrivially empty nonterminal */
456: pempty[*prdptr[i]-NTBASE] = EMPTY;
457: goto again; /* got one ... try for another */
458: }
459: }
460: }
461:
462: }
463:
464: int gsdebug = 0;
465: stagen(){ /* generate the states */
466:
467: int i, j;
468: register c;
469: register struct wset *p, *q;
470:
471: /* initialize */
472:
473: nstate = 0;
474: /* THIS IS FUNNY from the standpoint of portability */
475: /* it represents the magic moment when the mem0 array, which has
476: /* been holding the productions, starts to hold item pointers, of a
477: /* different type... */
478: /* someday, alloc should be used to allocate all this stuff... for now, we
479: /* accept that if pointers don't fit in integers, there is a problem... */
480:
481: pstate[0] = pstate[1] = (struct item *)mem;
482: aryfil( clset.lset, tbitset, 0 );
483: putitem( prdptr[0]+1, &clset );
484: tystate[0] = MUSTDO;
485: nstate = 1;
486: pstate[2] = pstate[1];
487:
488: aryfil( amem, ACTSIZE, 0 );
489:
490: /* now, the main state generation loop */
491:
492: more:
493: SLOOP(i){
494: if( tystate[i] != MUSTDO ) continue;
495: tystate[i] = DONE;
496: aryfil( temp1, nnonter+1, 0 );
497: /* take state i, close it, and do gotos */
498: closure(i);
499: WSLOOP(wsets,p){ /* generate goto's */
500: if( p->flag ) continue;
501: p->flag = 1;
502: c = *(p->pitem);
503: if( c <= 1 ) {
504: if( pstate[i+1]-pstate[i] <= p-wsets ) tystate[i] = MUSTLOOKAHEAD;
505: continue;
506: }
507: /* do a goto on c */
508: WSLOOP(p,q){
509: if( c == *(q->pitem) ){ /* this item contributes to the goto */
510: putitem( q->pitem + 1, &q->ws );
511: q->flag = 1;
512: }
513: }
514: if( c < NTBASE ) {
515: state(c); /* register new state */
516: }
517: else {
518: temp1[c-NTBASE] = state(c);
519: }
520: }
521: if( gsdebug && (foutput!=NULL) ){
522: fprintf( foutput, "%d: ", i );
523: NTLOOP(j) {
524: if( temp1[j] ) fprintf( foutput, "%s %d, ", nontrst[j].name, temp1[j] );
525: }
526: fprintf( foutput, "\n");
527: }
528: indgo[i] = apack( &temp1[1], nnonter-1 ) - 1;
529: goto more; /* we have done one goto; do some more */
530: }
531: /* no more to do... stop */
532: }
533:
534: int cldebug = 0; /* debugging flag for closure */
535: closure(i){ /* generate the closure of state i */
536:
537: int c, ch, work, k;
538: register struct wset *u, *v;
539: int *pi;
540: int **s, **t;
541: struct item *q;
542: register struct item *p;
543:
544: ++zzclose;
545:
546: /* first, copy kernel of state i to wsets */
547:
548: cwp = wsets;
549: ITMLOOP(i,p,q){
550: cwp->pitem = p->pitem;
551: cwp->flag = 1; /* this item must get closed */
552: SETLOOP(k) cwp->ws.lset[k] = p->look->lset[k];
553: WSBUMP(cwp);
554: }
555:
556: /* now, go through the loop, closing each item */
557:
558: work = 1;
559: while( work ){
560: work = 0;
561: WSLOOP(wsets,u){
562:
563: if( u->flag == 0 ) continue;
564: c = *(u->pitem); /* dot is before c */
565:
566: if( c < NTBASE ){
567: u->flag = 0;
568: continue; /* only interesting case is where . is before nonterminal */
569: }
570:
571: /* compute the lookahead */
572: aryfil( clset.lset, tbitset, 0 );
573:
574: /* find items involving c */
575:
576: WSLOOP(u,v){
577: if( v->flag == 1 && *(pi=v->pitem) == c ){
578: v->flag = 0;
579: if( nolook ) continue;
580: while( (ch= *++pi)>0 ){
581: if( ch < NTBASE ){ /* terminal symbol */
582: SETBIT( clset.lset, ch );
583: break;
584: }
585: /* nonterminal symbol */
586: setunion( clset.lset, pfirst[ch-NTBASE]->lset );
587: if( !pempty[ch-NTBASE] ) break;
588: }
589: if( ch<=0 ) setunion( clset.lset, v->ws.lset );
590: }
591: }
592:
593: /* now loop over productions derived from c */
594:
595: c -= NTBASE; /* c is now nonterminal number */
596:
597: t = pres[c+1];
598: for( s=pres[c]; s<t; ++s ){
599: /* put these items into the closure */
600: WSLOOP(wsets,v){ /* is the item there */
601: if( v->pitem == *s ){ /* yes, it is there */
602: if( nolook ) goto nexts;
603: if( setunion( v->ws.lset, clset.lset ) ) v->flag = work = 1;
604: goto nexts;
605: }
606: }
607:
608: /* not there; make a new entry */
609: if( cwp-wsets+1 >= WSETSIZE ) error( "working set overflow" );
610: cwp->pitem = *s;
611: cwp->flag = 1;
612: if( !nolook ){
613: work = 1;
614: SETLOOP(k) cwp->ws.lset[k] = clset.lset[k];
615: }
616: WSBUMP(cwp);
617:
618: nexts: ;
619: }
620:
621: }
622: }
623:
624: /* have computed closure; flags are reset; return */
625:
626: if( cwp > zzcwp ) zzcwp = cwp;
627: if( cldebug && (foutput!=NULL) ){
628: fprintf( foutput, "\nState %d, nolook = %d\n", i, nolook );
629: WSLOOP(wsets,u){
630: if( u->flag ) fprintf( foutput, "flag set!\n");
631: u->flag = 0;
632: fprintf( foutput, "\t%s", writem(u->pitem));
633: prlook( &u->ws );
634: fprintf( foutput, "\n" );
635: }
636: }
637: }
638:
639: struct looksets *flset( p ) struct looksets *p; {
640: /* decide if the lookahead set pointed to by p is known */
641: /* return pointer to a perminent location for the set */
642:
643: register struct looksets *q;
644: int j, *w;
645: register *u, *v;
646:
647: for( q = &lkst[nlset]; q-- > lkst; ){
648: u = p->lset;
649: v = q->lset;
650: w = & v[tbitset];
651: while( v<w) if( *u++ != *v++ ) goto more;
652: /* we have matched */
653: return( q );
654: more: ;
655: }
656: /* add a new one */
657: q = &lkst[nlset++];
658: if( nlset >= LSETSIZE )error("too many lookahead sets" );
659: SETLOOP(j){
660: q->lset[j] = p->lset[j];
661: }
662: return( q );
663: }
664:
665: cleantmp()
666: {
667: ZAPFILE(actname);
668: ZAPFILE(tempname);
669: }
670:
671: intr()
672: {
673: cleantmp();
674: exit(1);
675: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.