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