/* (c) 1979 Regents of the University of California */ # include "ey.h" cpres(){ /* conpute an array with the beginnings of productions yielding given nonterminals The array pres points to these lists */ int i,j,c; pres = yalloc(nnonter+1); for(i=0;i<=nnonter;i++){ c = i+NTBASE; pres[i] = mem; fatfl = 0; /* make undefined symbols nonfatal */ for(j=0;j 0 ; ++p ) { if( ch < NTBASE ) { wsets[i].ws[ch>>4] |= (1 << (ch&017) ); break; } else if( !pempty[ch-NTBASE] ) break; } } } /* now, reflect transitivity */ changes = 1; while( changes ){ changes = 0; for( i=0; i<=nnonter; ++i ){ t = pres[i+1]; for( s=pres[i]; s= 0; ++p ) { changes |= UNION( wsets[i].ws, wsets[i].ws, wsets[ch].ws ); if( !pempty[ch] ) break; } } } } for( i=0; i<=nnonter; i++ ) pfirst[i] = flset( wsets[i].ws ); if( !indebug ) return; settty(); for( i=0; i<=nnonter; i++ ){ fprintf( cout , "\n%s: ", nontrst[i].name ); prlook( pfirst[i] ); fprintf( cout , " %d\n", pempty[i] ); } } state(c){ /* sorts last state,and sees if it equals earlier ones. returns state number */ int s,size1,size2; _REGISTER i; struct item *p1, *p2, *k, *l, *q1, *q2; p1 = pstate[nstate]; p2 = pstate[nstate+1]; if(p1==p2) return(0); /* null state */ /* sort the items */ for(k=p2-1;k>p1;k--) { /* make k the biggest */ for(l=k-1;l>=p1;--l)if( l->pitem > k->pitem ){ s = k->pitem; k->pitem = l->pitem; l->pitem = s; s = k->look; k->look = l->look; l->look = s; } } size1 = p2 - p1; /* size of state */ for( i= (c>=NTBASE)?ntstates[c-NTBASE]:tstates[c]; i != 0; i = mstates[i] ) { /* get ith state */ q1 = pstate[i]; q2 = pstate[i+1]; size2 = q2 - q1; if (size1 != size2) continue; k=p1; for(l=q1;lpitem != k->pitem ) break; ++k; } if (l != q2) continue; /* found it */ pstate[nstate+1] = pstate[nstate]; /* delete last state */ /* fix up lookaheads */ k=p1; for( l=q1; llook->lset, k->look->lset ) ) { tystate[i] = 1; /* register the new set */ l->look = flset( &clset ); } ++k; } return (i); } /* state is new */ pstate[nstate+2] = p2; if(nstate+1 >= stsize) error("too many states"); if( c >= NTBASE ){ mstates[ nstate ] = ntstates[ c-NTBASE ]; ntstates[ c-NTBASE ] = nstate; } else { mstates[ nstate ] = tstates[ c ]; tstates[ c ] = nstate; } tystate[nstate]=1; return(nstate++); } int pidebug = 0; /* debugging flag for putitem */ putitem ( ptr, lptr ) int *ptr; struct looksets *lptr;{ int *jip, k; struct item *i, *j; if( pidebug ) { settty(); fprintf( cout , "putitem(%s), state %d\n", writem(&ptr), nstate ); } /* see if it's there */ j = pstate[nstate+1]; for( i=pstate[nstate]; ipitem == ptr) { error("yacc error--duplicate item"); } /* not there */ j->pitem = ptr; j->look = flset( lptr ); pstate[nstate+1] = ++j; jip = j; if(jip-mem0 >= memsiz) error("out of state space"); } cempty(){ /* mark nonterminals which derive the empty string */ int i, *p; /* set pempty to 0 */ pempty = yalloc( nnonter ); aryfil( pempty, nnonter+1, 0 ); for( i=1; i=NTBASE && pempty[*p-NTBASE]!=0 ; ++p ) ; if( *p < 0 ){ /* we have a nontrivially empty nonterminal */ pempty[*prdptr[i]-NTBASE] = 1; goto again; /* got one ... try for another */ } } } } int gsdebug = 0; stagen(){ /* generate the states */ int i, j, k, c; /* initialize */ nstate = 0; pstate[0] = pstate[1] = mem; aryfil( clset.lset, tbitset, 0 ); putitem( prdptr[0]+1, &clset ); tystate[0] = 1; nstate = 1; pstate[2] = pstate[1]; memact = 0; aryfil( amem, actsiz, 0 ); /* now, the main state generation loop */ more: for( i=0; ipitem; wsets[cwset].flag = 1; /* this item must get closed */ for( k=0; klook->lset[k]; ++cwset; } /* now, go through the loop, closing each item */ work = 1; while( work ){ work = 0; for( j=0; j0 ){ if( ch < NTBASE ){ /* terminal symbol */ clset.lset[ch>>4] |= (1<<(ch&017)); break; } /* nonterminal symbol */ UNION( clset.lset, clset.lset, pfirst[ch-NTBASE] ); if( !pempty[ch-NTBASE] ) break; } if( ch<=0 ) UNION( clset.lset, clset.lset, wsets[k].ws ); } } /* now loop over productions derived from c */ c -= NTBASE; /* c is now nonterminal number */ t = pres[c+1]; for( s=pres[c]; s= wssize ) error( "working set overflow" ); wsets[cwset].pitem = *s; wsets[cwset].flag = 1; if( nolook ){ cwset++; goto nexts; } work = 1; for( k=0; k zzcwset ) zzcwset = cwset; if( !cldebug ) return; settty(); fprintf( cout , "\nState %d, nolook = %d\n", i, nolook ); for( j=0; jlset; v = lkst[i].lset; w = & v[tbitset]; while( v= lsetsz )error("too many lookahead sets"); for( j=0; jlset[j]; } return( & lkst[nlset++]); }