![[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] / researchv10dc / cmd / picasso|
Return to y1.c CVS log | Up to [Research Unix] / researchv10dc / cmd / picasso |
1.1 root 1: #ident "@(#)/usr/src/cmd/yacc/y1.c 1.3 6/6/85 02:44:08 - Amdahl/UTS"
2: /* @(#)y1.c 1.6 */
3: # include "dextern"
4:
5: /* variables used locally */
6:
7: /* lookahead computations */
8:
9: int tbitset; /* size of lookahead sets */
10: struct looksets lkst [ LSETSIZE ];
11: int nlset = 0; /* next lookahead set index */
12: int nolook = 0; /* flag to suppress lookahead computations */
13: struct looksets clset; /* temporary storage for lookahead computations */
14:
15: /* working set computations */
16:
17: struct wset wsets[ WSETSIZE ];
18: struct wset *cwp;
19:
20: /* state information */
21:
22: int nstate = 0; /* number of states */
23: struct item *pstate[NSTATES+2]; /* pointers to the descriptions of the states */
24: int tystate[NSTATES]; /* contains type information about the states */
25: int indgo[NSTATES]; /* index to the stored goto table */
26: int tstates[ NTERMS ]; /* states generated by terminal gotos */
27: int ntstates[ NNONTERM ]; /* states generated by nonterminal gotos */
28: int mstates[ NSTATES ]; /* chain of overflows of term/nonterm generation lists */
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:
50: setup(argc,argv); /* initialize and read productions */
51: tbitset = NWORDS(ntokens);
52: cpres(); /* make table of which productions yield a given nonterminal */
53: cempty(); /* make a table of which nonterminals can match the empty string */
54: cpfir(); /* make a table of firsts of nonterminals */
55: stagen(); /* generate the states */
56: output(); /* write the states and the tables */
57: go2out();
58: hideprod();
59: summary();
60: callopt();
61: others();
62: exit(0);
63: }
64:
65: others(){ /* put out other arrays, copy the parsers */
66: register c, i, j;
67:
68: finput = fopen( PARSER, "r" );
69: if( finput == NULL ) error( "cannot find parser %s", PARSER );
70:
71: warray( "yyr1", levprd, nprod );
72:
73: aryfil( temp1, nprod, 0 );
74: /* had_act[i] is either 1 or 0 */
75: PLOOP(1,i)temp1[i] = ((prdptr[i+1]-prdptr[i]-2) << 1) | had_act[i];
76: warray( "yyr2", temp1, nprod );
77:
78: aryfil( temp1, nstate, -1000 );
79: TLOOP(i){
80: for( j=tstates[i]; j!=0; j=mstates[j] ){
81: temp1[j] = tokset[i].value;
82: }
83: }
84: NTLOOP(i){
85: for( j=ntstates[i]; j!=0; j=mstates[j] ){
86: temp1[j] = -i;
87: }
88: }
89: warray( "yychk", temp1, nstate );
90:
91: warray( "yydef", defact, nstate );
92:
93: fdebug = fopen( DEBUGNAME, "r" );
94: if ( fdebug == NULL ) error( "cannot re-open yacc.debug" );
95: while ( ( c = getc( fdebug ) ) != EOF )
96: putc( c, ftable );
97: fclose( fdebug );
98: ZAPFILE( DEBUGNAME );
99: /* copy parser text */
100:
101: while( (c=getc(finput) ) != EOF ){
102: if( c == '$' ){
103: if( (c=getc(finput)) != 'A' ) putc( '$', ftable );
104: else { /* copy actions */
105: faction = fopen( ACTNAME, "r" );
106: if( faction == NULL ) error( "cannot reopen action tempfile" );
107: while( (c=getc(faction) ) != EOF ) putc( c, ftable );
108: fclose(faction);
109: ZAPFILE(ACTNAME);
110: c = getc(finput);
111: }
112: }
113: putc( c, ftable );
114: }
115:
116: fclose( ftable );
117: }
118:
119: char *chcopy( p, q ) char *p, *q; {
120: /* copies string q into p, returning next free char ptr */
121: while( *p = *q++ ) ++p;
122: return( p );
123: }
124:
125: # define ISIZE 400
126: char *writem(pp) int *pp; { /* creates output string for item pointed to by pp */
127: int i,*p;
128: static char sarr[ISIZE];
129: char *q;
130:
131: for( p=pp; *p>0 ; ++p ) ;
132: p = prdptr[-*p];
133: q = chcopy( sarr, nontrst[*p-NTBASE].name );
134: q = chcopy( q, " : " );
135:
136: for(;;){
137: *q++ = ++p==pp ? '_' : ' ';
138: *q = '\0';
139: if((i = *p) <= 0) break;
140: q = chcopy( q, symnam(i) );
141: if( q> &sarr[ISIZE-30] ) error( "item too big" );
142: }
143:
144: if( (i = *pp) < 0 ){ /* an item calling for a reduction */
145: q = chcopy( q, " (" );
146: sprintf( q, "%d)", -i );
147: }
148:
149: return( sarr );
150: }
151:
152: char *symnam(i){ /* return a pointer to the name of symbol i */
153: char *cp;
154:
155: cp = (i>=NTBASE) ? nontrst[i-NTBASE].name : tokset[i].name ;
156: if( *cp == ' ' ) ++cp;
157: return( cp );
158: }
159:
160: struct wset *zzcwp = wsets;
161: int zzgoent = 0;
162: int zzgobest = 0;
163: int zzacent = 0;
164: int zzexcp = 0;
165: int zzclose = 0;
166: int zzsrconf = 0;
167: int * zzmemsz = mem0;
168: int zzrrconf = 0;
169:
170: summary(){ /* output the summary on the tty */
171:
172: if( foutput!=NULL ){
173: fprintf( foutput, "\n%d/%d terminals, %d/%d nonterminals\n", ntokens, NTERMS,
174: nnonter, NNONTERM );
175: fprintf( foutput, "%d/%d grammar rules, %d/%d states\n", nprod, NPROD, nstate, NSTATES );
176: fprintf( foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n", zzsrconf, zzrrconf );
177: fprintf( foutput, "%d/%d working sets used\n", zzcwp-wsets, WSETSIZE );
178: fprintf( foutput, "memory: states,etc. %d/%d, parser %d/%d\n", zzmemsz-mem0, MEMSIZE,
179: memp-amem, ACTSIZE );
180: fprintf( foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE );
181: fprintf( foutput, "%d extra closures\n", zzclose - 2*nstate );
182: fprintf( foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp );
183: fprintf( foutput, "%d goto entries\n", zzgoent );
184: fprintf( foutput, "%d entries saved by goto default\n", zzgobest );
185: }
186: if( zzsrconf!=0 || zzrrconf!=0 ){
187: fprintf( stderr,"\nconflicts: ");
188: if( zzsrconf )fprintf( stderr, "%d shift/reduce" , zzsrconf );
189: if( zzsrconf && zzrrconf )fprintf( stderr, ", " );
190: if( zzrrconf )fprintf( stderr, "%d reduce/reduce" , zzrrconf );
191: fprintf( stderr, "\n" );
192: }
193:
194: if( ftemp != NULL ) fclose( ftemp );
195: if( fdefine != NULL ) fclose( fdefine );
196: }
197:
198: /* VARARGS1 */
199: error(s,a1) char *s; { /* write out error comment */
200:
201: ++nerrors;
202: fprintf( stderr, "\n fatal error: ");
203: fprintf( stderr, s,a1);
204: fprintf( stderr, ", line %d\n", lineno );
205: if( !fatfl ) return;
206: summary();
207: exit(1);
208: }
209:
210: aryfil( v, n, c ) int *v,n,c; { /* set elements 0 through n-1 to c */
211: int i;
212: for( i=0; i<n; ++i ) v[i] = c;
213: }
214:
215: setunion( a, b ) register *a, *b; {
216: /* set a to the union of a and b */
217: /* return 1 if b is not a subset of a, 0 otherwise */
218: register i, x, sub;
219:
220: sub = 0;
221: SETLOOP(i){
222: *a = (x = *a)|*b++;
223: if( *a++ != x ) sub = 1;
224: }
225: return( sub );
226: }
227:
228: prlook( p ) struct looksets *p;{
229: register j, *pp;
230: pp = p->lset;
231: if( pp == 0 ) fprintf( foutput, "\tNULL");
232: else {
233: fprintf( foutput, " { " );
234: TLOOP(j) {
235: if( BIT(pp,j) ) fprintf( foutput, "%s ", symnam(j) );
236: }
237: fprintf( foutput, "}" );
238: }
239: }
240:
241: cpres(){ /* compute an array with the beginnings of productions yielding given nonterminals
242: The array pres points to these lists */
243: /* the array pyield has the lists: the total size is only NPROD+1 */
244: register **pmem;
245: register c, j, i;
246: static int * pyield[NPROD];
247:
248: pmem = pyield;
249:
250: NTLOOP(i){
251: c = i+NTBASE;
252: pres[i] = pmem;
253: fatfl = 0; /* make undefined symbols nonfatal */
254: PLOOP(0,j){
255: if (*prdptr[j] == c) *pmem++ = prdptr[j]+1;
256: }
257: if(pres[i] == pmem){
258: error("nonterminal %s not defined!", nontrst[i].name);
259: }
260: }
261: pres[i] = pmem;
262: fatfl = 1;
263: if( nerrors ){
264: summary();
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: exit(1);
440: }
441:
442: /* now, compute the pempty array, to see which nonterminals derive the empty string */
443:
444: /* set pempty to WHOKNOWS */
445:
446: aryfil( pempty, nnonter+1, WHOKNOWS );
447:
448: /* loop as long as we keep finding empty nonterminals */
449:
450: again:
451: PLOOP(1,i){
452: if( pempty[ *prdptr[i]-NTBASE ]==WHOKNOWS ){ /* not known to be empty */
453: for( p=prdptr[i]+1; *p>=NTBASE && pempty[*p-NTBASE]==EMPTY ; ++p ) ;
454: if( *p < 0 ){ /* we have a nontrivially empty nonterminal */
455: pempty[*prdptr[i]-NTBASE] = EMPTY;
456: goto again; /* got one ... try for another */
457: }
458: }
459: }
460:
461: }
462:
463: int gsdebug = 0;
464: stagen(){ /* generate the states */
465:
466: int i, j;
467: register c;
468: register struct wset *p, *q;
469:
470: /* initialize */
471:
472: nstate = 0;
473: /* THIS IS FUNNY from the standpoint of portability */
474: /* it represents the magic moment when the mem0 array, which has
475: /* been holding the productions, starts to hold item pointers, of a
476: /* different type... */
477: /* someday, alloc should be used to allocate all this stuff... for now, we
478: /* accept that if pointers don't fit in integers, there is a problem... */
479:
480: pstate[0] = pstate[1] = (struct item *)mem;
481: aryfil( clset.lset, tbitset, 0 );
482: putitem( prdptr[0]+1, &clset );
483: tystate[0] = MUSTDO;
484: nstate = 1;
485: pstate[2] = pstate[1];
486:
487: aryfil( amem, ACTSIZE, 0 );
488:
489: /* now, the main state generation loop */
490:
491: more:
492: SLOOP(i){
493: if( tystate[i] != MUSTDO ) continue;
494: tystate[i] = DONE;
495: aryfil( temp1, nnonter+1, 0 );
496: /* take state i, close it, and do gotos */
497: closure(i);
498: WSLOOP(wsets,p){ /* generate goto's */
499: if( p->flag ) continue;
500: p->flag = 1;
501: c = *(p->pitem);
502: if( c <= 1 ) {
503: if( pstate[i+1]-pstate[i] <= p-wsets ) tystate[i] = MUSTLOOKAHEAD;
504: continue;
505: }
506: /* do a goto on c */
507: WSLOOP(p,q){
508: if( c == *(q->pitem) ){ /* this item contributes to the goto */
509: putitem( q->pitem + 1, &q->ws );
510: q->flag = 1;
511: }
512: }
513: if( c < NTBASE ) {
514: state(c); /* register new state */
515: }
516: else {
517: temp1[c-NTBASE] = state(c);
518: }
519: }
520: if( gsdebug && (foutput!=NULL) ){
521: fprintf( foutput, "%d: ", i );
522: NTLOOP(j) {
523: if( temp1[j] ) fprintf( foutput, "%s %d, ", nontrst[j].name, temp1[j] );
524: }
525: fprintf( foutput, "\n");
526: }
527: indgo[i] = apack( &temp1[1], nnonter-1 ) - 1;
528: goto more; /* we have done one goto; do some more */
529: }
530: /* no more to do... stop */
531: }
532:
533: int cldebug = 0; /* debugging flag for closure */
534: closure(i){ /* generate the closure of state i */
535:
536: int c, ch, work, k;
537: register struct wset *u, *v;
538: int *pi;
539: int **s, **t;
540: struct item *q;
541: register struct item *p;
542:
543: ++zzclose;
544:
545: /* first, copy kernel of state i to wsets */
546:
547: cwp = wsets;
548: ITMLOOP(i,p,q){
549: cwp->pitem = p->pitem;
550: cwp->flag = 1; /* this item must get closed */
551: SETLOOP(k) cwp->ws.lset[k] = p->look->lset[k];
552: WSBUMP(cwp);
553: }
554:
555: /* now, go through the loop, closing each item */
556:
557: work = 1;
558: while( work ){
559: work = 0;
560: WSLOOP(wsets,u){
561:
562: if( u->flag == 0 ) continue;
563: c = *(u->pitem); /* dot is before c */
564:
565: if( c < NTBASE ){
566: u->flag = 0;
567: continue; /* only interesting case is where . is before nonterminal */
568: }
569:
570: /* compute the lookahead */
571: aryfil( clset.lset, tbitset, 0 );
572:
573: /* find items involving c */
574:
575: WSLOOP(u,v){
576: if( v->flag == 1 && *(pi=v->pitem) == c ){
577: v->flag = 0;
578: if( nolook ) continue;
579: while( (ch= *++pi)>0 ){
580: if( ch < NTBASE ){ /* terminal symbol */
581: SETBIT( clset.lset, ch );
582: break;
583: }
584: /* nonterminal symbol */
585: setunion( clset.lset, pfirst[ch-NTBASE]->lset );
586: if( !pempty[ch-NTBASE] ) break;
587: }
588: if( ch<=0 ) setunion( clset.lset, v->ws.lset );
589: }
590: }
591:
592: /* now loop over productions derived from c */
593:
594: c -= NTBASE; /* c is now nonterminal number */
595:
596: t = pres[c+1];
597: for( s=pres[c]; s<t; ++s ){
598: /* put these items into the closure */
599: WSLOOP(wsets,v){ /* is the item there */
600: if( v->pitem == *s ){ /* yes, it is there */
601: if( nolook ) goto nexts;
602: if( setunion( v->ws.lset, clset.lset ) ) v->flag = work = 1;
603: goto nexts;
604: }
605: }
606:
607: /* not there; make a new entry */
608: if( cwp-wsets+1 >= WSETSIZE ) error( "working set overflow" );
609: cwp->pitem = *s;
610: cwp->flag = 1;
611: if( !nolook ){
612: work = 1;
613: SETLOOP(k) cwp->ws.lset[k] = clset.lset[k];
614: }
615: WSBUMP(cwp);
616:
617: nexts: ;
618: }
619:
620: }
621: }
622:
623: /* have computed closure; flags are reset; return */
624:
625: if( cwp > zzcwp ) zzcwp = cwp;
626: if( cldebug && (foutput!=NULL) ){
627: fprintf( foutput, "\nState %d, nolook = %d\n", i, nolook );
628: WSLOOP(wsets,u){
629: if( u->flag ) fprintf( foutput, "flag set!\n");
630: u->flag = 0;
631: fprintf( foutput, "\t%s", writem(u->pitem));
632: prlook( &u->ws );
633: fprintf( foutput, "\n" );
634: }
635: }
636: }
637:
638: struct looksets *flset( p ) struct looksets *p; {
639: /* decide if the lookahead set pointed to by p is known */
640: /* return pointer to a perminent location for the set */
641:
642: register struct looksets *q;
643: int j, *w;
644: register *u, *v;
645:
646: for( q = &lkst[nlset]; q-- > lkst; ){
647: u = p->lset;
648: v = q->lset;
649: w = & v[tbitset];
650: while( v<w) if( *u++ != *v++ ) goto more;
651: /* we have matched */
652: return( q );
653: more: ;
654: }
655: /* add a new one */
656: q = &lkst[nlset++];
657: if( nlset >= LSETSIZE )error("too many lookahead sets" );
658: SETLOOP(j){
659: q->lset[j] = p->lset[j];
660: }
661: return( q );
662: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.