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