projects / unix-history / blob
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
file reorg, pathnames.h, paths.h
[unix-history] / usr / src / old / yacc / y1.c
#ifndef lint
static char sccsid[] = "@(#)y1.c 4.2 (Berkeley) %G%";
#endif not lint
# include "dextern"
# include "pathnames.h"
/* variables used locally */
/* lookahead computations */
int tbitset; /* size of lookahead sets */
struct looksets lkst [ LSETSIZE ];
int nlset = 0; /* next lookahead set index */
int nolook = 0; /* flag to suppress lookahead computations */
struct looksets clset; /* temporary storage for lookahead computations */
/* working set computations */
struct wset wsets[ WSETSIZE ];
struct wset *cwp;
/* state information */
int nstate = 0; /* number of states */
struct item *pstate[NSTATES+2]; /* pointers to the descriptions of the states */
int tystate[NSTATES]; /* contains type information about the states */
int indgo[NSTATES]; /* index to the stored goto table */
int tstates[ NTERMS ]; /* states generated by terminal gotos */
int ntstates[ NNONTERM ]; /* states generated by nonterminal gotos */
int mstates[ NSTATES ]; /* chain of overflows of term/nonterm generation lists */
/* storage for the actions in the parser */
int amem[ACTSIZE]; /* action table storage */
int *memp = amem; /* next free action table position */
/* other storage areas */
int temp1[TEMPSIZE]; /* temporary storage, indexed by terms + ntokens or states */
int lineno= 1; /* current input line number */
int fatfl = 1; /* if on, error is fatal */
int nerrors = 0; /* number of errors */
/* storage for information about the nonterminals */
int **pres[NNONTERM+2]; /* vector of pointers to productions yielding each nonterminal */
struct looksets *pfirst[NNONTERM+2]; /* vector of pointers to first sets for each nonterminal */
int pempty[NNONTERM+1]; /* vector of nonterminals nontrivially deriving e */
main(argc,argv) int argc; char *argv[]; {
setup(argc,argv); /* initialize and read productions */
tbitset = NWORDS(ntokens);
cpres(); /* make table of which productions yield a given nonterminal */
cempty(); /* make a table of which nonterminals can match the empty string */
cpfir(); /* make a table of firsts of nonterminals */
stagen(); /* generate the states */
output(); /* write the states and the tables */
go2out();
hideprod();
summary();
callopt();
others();
exit(0);
}
others(){ /* put out other arrays, copy the parsers */
register c, i, j;
finput = fopen( _PATH_PARSER, "r" );
if( finput == NULL ) error( "cannot find parser %s", _PATH_PARSER);
warray( "yyr1", levprd, nprod );
aryfil( temp1, nprod, 0 );
PLOOP(1,i)temp1[i] = prdptr[i+1]-prdptr[i]-2;
warray( "yyr2", temp1, nprod );
aryfil( temp1, nstate, -1000 );
TLOOP(i){
for( j=tstates[i]; j!=0; j=mstates[j] ){
temp1[j] = tokset[i].value;
}
}
NTLOOP(i){
for( j=ntstates[i]; j!=0; j=mstates[j] ){
temp1[j] = -i;
}
}
warray( "yychk", temp1, nstate );
warray( "yydef", defact, nstate );
/* copy parser text */
while( (c=getc(finput) ) != EOF ){
if( c == '$' ){
if( (c=getc(finput)) != 'A' ) putc( '$', ftable );
else { /* copy actions */
faction = fopen( ACTNAME, "r" );
if( faction == NULL ) error( "cannot reopen action tempfile" );
while( (c=getc(faction) ) != EOF ) putc( c, ftable );
fclose(faction);
ZAPFILE(ACTNAME);
c = getc(finput);
}
}
putc( c, ftable );
}
fclose( ftable );
}
char *chcopy( p, q ) char *p, *q; {
/* copies string q into p, returning next free char ptr */
while( *p = *q++ ) ++p;
return( p );
}
# define ISIZE 400
char *writem(pp) int *pp; { /* creates output string for item pointed to by pp */
int i,*p;
static char sarr[ISIZE];
char *q;
for( p=pp; *p>0 ; ++p ) ;
p = prdptr[-*p];
q = chcopy( sarr, nontrst[*p-NTBASE].name );
q = chcopy( q, " : " );
for(;;){
*q++ = ++p==pp ? '_' : ' ';
*q = '\0';
if((i = *p) <= 0) break;
q = chcopy( q, symnam(i) );
if( q> &sarr[ISIZE-30] ) error( "item too big" );
}
if( (i = *pp) < 0 ){ /* an item calling for a reduction */
q = chcopy( q, " (" );
sprintf( q, "%d)", -i );
}
return( sarr );
}
char *symnam(i){ /* return a pointer to the name of symbol i */
char *cp;
cp = (i>=NTBASE) ? nontrst[i-NTBASE].name : tokset[i].name ;
if( *cp == ' ' ) ++cp;
return( cp );
}
struct wset *zzcwp = wsets;
int zzgoent = 0;
int zzgobest = 0;
int zzacent = 0;
int zzexcp = 0;
int zzclose = 0;
int zzsrconf = 0;
int * zzmemsz = mem0;
int zzrrconf = 0;
summary(){ /* output the summary on the tty */
if( foutput!=NULL ){
fprintf( foutput, "\n%d/%d terminals, %d/%d nonterminals\n", ntokens, NTERMS,
nnonter, NNONTERM );
fprintf( foutput, "%d/%d grammar rules, %d/%d states\n", nprod, NPROD, nstate, NSTATES );
fprintf( foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n", zzsrconf, zzrrconf );
fprintf( foutput, "%d/%d working sets used\n", zzcwp-wsets, WSETSIZE );
fprintf( foutput, "memory: states,etc. %d/%d, parser %d/%d\n", zzmemsz-mem0, MEMSIZE,
memp-amem, ACTSIZE );
fprintf( foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE );
fprintf( foutput, "%d extra closures\n", zzclose - 2*nstate );
fprintf( foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp );
fprintf( foutput, "%d goto entries\n", zzgoent );
fprintf( foutput, "%d entries saved by goto default\n", zzgobest );
}
if( zzsrconf!=0 || zzrrconf!=0 ){
fprintf( stdout,"\nconflicts: ");
if( zzsrconf )fprintf( stdout, "%d shift/reduce" , zzsrconf );
if( zzsrconf && zzrrconf )fprintf( stdout, ", " );
if( zzrrconf )fprintf( stdout, "%d reduce/reduce" , zzrrconf );
fprintf( stdout, "\n" );
}
fclose( ftemp );
if( fdefine != NULL ) fclose( fdefine );
}
/* VARARGS1 */
error(s,a1) char *s; { /* write out error comment */
++nerrors;
fprintf( stderr, "\n fatal error: ");
fprintf( stderr, s,a1);
fprintf( stderr, ", line %d\n", lineno );
if( !fatfl ) return;
summary();
exit(1);
}
aryfil( v, n, c ) int *v,n,c; { /* set elements 0 through n-1 to c */
int i;
for( i=0; i<n; ++i ) v[i] = c;
}
setunion( a, b ) register *a, *b; {
/* set a to the union of a and b */
/* return 1 if b is not a subset of a, 0 otherwise */
register i, x, sub;
sub = 0;
SETLOOP(i){
*a = (x = *a)|*b++;
if( *a++ != x ) sub = 1;
}
return( sub );
}
prlook( p ) struct looksets *p;{
register j, *pp;
pp = p->lset;
if( pp == 0 ) fprintf( foutput, "\tNULL");
else {
fprintf( foutput, " { " );
TLOOP(j) {
if( BIT(pp,j) ) fprintf( foutput, "%s ", symnam(j) );
}
fprintf( foutput, "}" );
}
}
cpres(){ /* compute an array with the beginnings of productions yielding given nonterminals
The array pres points to these lists */
/* the array pyield has the lists: the total size is only NPROD+1 */
register **pmem;
register c, j, i;
static int * pyield[NPROD];
pmem = pyield;
NTLOOP(i){
c = i+NTBASE;
pres[i] = pmem;
fatfl = 0; /* make undefined symbols nonfatal */
PLOOP(0,j){
if (*prdptr[j] == c) *pmem++ = prdptr[j]+1;
}
if(pres[i] == pmem){
error("nonterminal %s not defined!", nontrst[i].name);
}
}
pres[i] = pmem;
fatfl = 1;
if( nerrors ){
summary();
exit(1);
}
if( pmem != &pyield[nprod] ) error( "internal Yacc error: pyield %d", pmem-&pyield[nprod] );
}
int indebug = 0;
cpfir() {
/* compute an array with the first of nonterminals */
register *p, **s, i, **t, ch, changes;
zzcwp = &wsets[nnonter];
NTLOOP(i){
aryfil( wsets[i].ws.lset, tbitset, 0 );
t = pres[i+1];
for( s=pres[i]; s<t; ++s ){ /* initially fill the sets */
for( p = *s; (ch = *p) > 0 ; ++p ) {
if( ch < NTBASE ) {
SETBIT( wsets[i].ws.lset, ch );
break;
}
else if( !pempty[ch-NTBASE] ) break;
}
}
}
/* now, reflect transitivity */
changes = 1;
while( changes ){
changes = 0;
NTLOOP(i){
t = pres[i+1];
for( s=pres[i]; s<t; ++s ){
for( p = *s; ( ch = (*p-NTBASE) ) >= 0; ++p ) {
changes |= setunion( wsets[i].ws.lset, wsets[ch].ws.lset );
if( !pempty[ch] ) break;
}
}
}
}
NTLOOP(i) pfirst[i] = flset( &wsets[i].ws );
if( !indebug ) return;
if( (foutput!=NULL) ){
NTLOOP(i) {
fprintf( foutput, "\n%s: ", nontrst[i].name );
prlook( pfirst[i] );
fprintf( foutput, " %d\n", pempty[i] );
}
}
}
state(c){ /* sorts last state,and sees if it equals earlier ones. returns state number */
int 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 ){
int *s;
struct looksets *ss;
s = k->pitem;
k->pitem = l->pitem;
l->pitem = s;
ss = k->look;
k->look = l->look;
l->look = ss;
}
}
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;l<q2;l++) {
if( l->pitem != k->pitem ) break;
++k;
}
if (l != q2) continue;
/* found it */
pstate[nstate+1] = pstate[nstate]; /* delete last state */
/* fix up lookaheads */
if( nolook ) return(i);
for( l=q1,k=p1; l<q2; ++l,++k ){
int s;
SETLOOP(s) clset.lset[s] = l->look->lset[s];
if( setunion( clset.lset, k->look->lset ) ) {
tystate[i] = MUSTDO;
/* register the new set */
l->look = flset( &clset );
}
}
return (i);
}
/* state is new */
if( nolook ) error( "yacc state/nolook error" );
pstate[nstate+2] = p2;
if(nstate+1 >= NSTATES) 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]=MUSTDO;
return(nstate++);
}
int pidebug = 0; /* debugging flag for putitem */
putitem( ptr, lptr ) int *ptr; struct looksets *lptr; {
register struct item *j;
if( pidebug && (foutput!=NULL) ) {
fprintf( foutput, "putitem(%s), state %d\n", writem(ptr), nstate );
}
j = pstate[nstate+1];
j->pitem = ptr;
if( !nolook ) j->look = flset( lptr );
pstate[nstate+1] = ++j;
if( (int *)j > zzmemsz ){
zzmemsz = (int *)j;
if( zzmemsz >= &mem0[MEMSIZE] ) error( "out of state space" );
}
}
cempty(){ /* mark nonterminals which derive the empty string */
/* also, look for nonterminals which don't derive any token strings */
# define EMPTY 1
# define WHOKNOWS 0
# define OK 1
register i, *p;
/* first, use the array pempty to detect productions that can never be reduced */
/* set pempty to WHONOWS */
aryfil( pempty, nnonter+1, WHOKNOWS );
/* now, look at productions, marking nonterminals which derive something */
more:
PLOOP(0,i){
if( pempty[ *prdptr[i] - NTBASE ] ) continue;
for( p=prdptr[i]+1; *p>=0; ++p ){
if( *p>=NTBASE && pempty[ *p-NTBASE ] == WHOKNOWS ) break;
}
if( *p < 0 ){ /* production can be derived */
pempty[ *prdptr[i]-NTBASE ] = OK;
goto more;
}
}
/* now, look at the nonterminals, to see if they are all OK */
NTLOOP(i){
/* the added production rises or falls as the start symbol ... */
if( i == 0 ) continue;
if( pempty[ i ] != OK ) {
fatfl = 0;
error( "nonterminal %s never derives any token string", nontrst[i].name );
}
}
if( nerrors ){
summary();
exit(1);
}
/* now, compute the pempty array, to see which nonterminals derive the empty string */
/* set pempty to WHOKNOWS */
aryfil( pempty, nnonter+1, WHOKNOWS );
/* loop as long as we keep finding empty nonterminals */
again:
PLOOP(1,i){
if( pempty[ *prdptr[i]-NTBASE ]==WHOKNOWS ){ /* not known to be empty */
for( p=prdptr[i]+1; *p>=NTBASE && pempty[*p-NTBASE]==EMPTY ; ++p ) ;
if( *p < 0 ){ /* we have a nontrivially empty nonterminal */
pempty[*prdptr[i]-NTBASE] = EMPTY;
goto again; /* got one ... try for another */
}
}
}
}
int gsdebug = 0;
stagen(){ /* generate the states */
int i, j;
register c;
register struct wset *p, *q;
/* initialize */
nstate = 0;
/* THIS IS FUNNY from the standpoint of portability */
/* it represents the magic moment when the mem0 array, which has
/* been holding the productions, starts to hold item pointers, of a
/* different type... */
/* someday, alloc should be used to allocate all this stuff... for now, we
/* accept that if pointers don't fit in integers, there is a problem... */
pstate[0] = pstate[1] = (struct item *)mem;
aryfil( clset.lset, tbitset, 0 );
putitem( prdptr[0]+1, &clset );
tystate[0] = MUSTDO;
nstate = 1;
pstate[2] = pstate[1];
aryfil( amem, ACTSIZE, 0 );
/* now, the main state generation loop */
more:
SLOOP(i){
if( tystate[i] != MUSTDO ) continue;
tystate[i] = DONE;
aryfil( temp1, nnonter+1, 0 );
/* take state i, close it, and do gotos */
closure(i);
WSLOOP(wsets,p){ /* generate goto's */
if( p->flag ) continue;
p->flag = 1;
c = *(p->pitem);
if( c <= 1 ) {
if( pstate[i+1]-pstate[i] <= p-wsets ) tystate[i] = MUSTLOOKAHEAD;
continue;
}
/* do a goto on c */
WSLOOP(p,q){
if( c == *(q->pitem) ){ /* this item contributes to the goto */
putitem( q->pitem + 1, &q->ws );
q->flag = 1;
}
}
if( c < NTBASE ) {
state(c); /* register new state */
}
else {
temp1[c-NTBASE] = state(c);
}
}
if( gsdebug && (foutput!=NULL) ){
fprintf( foutput, "%d: ", i );
NTLOOP(j) {
if( temp1[j] ) fprintf( foutput, "%s %d, ", nontrst[j].name, temp1[j] );
}
fprintf( foutput, "\n");
}
indgo[i] = apack( &temp1[1], nnonter-1 ) - 1;
goto more; /* we have done one goto; do some more */
}
/* no more to do... stop */
}
int cldebug = 0; /* debugging flag for closure */
closure(i){ /* generate the closure of state i */
int c, ch, work, k;
register struct wset *u, *v;
int *pi;
int **s, **t;
struct item *q;
register struct item *p;
++zzclose;
/* first, copy kernel of state i to wsets */
cwp = wsets;
ITMLOOP(i,p,q){
cwp->pitem = p->pitem;
cwp->flag = 1; /* this item must get closed */
SETLOOP(k) cwp->ws.lset[k] = p->look->lset[k];
WSBUMP(cwp);
}
/* now, go through the loop, closing each item */
work = 1;
while( work ){
work = 0;
WSLOOP(wsets,u){
if( u->flag == 0 ) continue;
c = *(u->pitem); /* dot is before c */
if( c < NTBASE ){
u->flag = 0;
continue; /* only interesting case is where . is before nonterminal */
}
/* compute the lookahead */
aryfil( clset.lset, tbitset, 0 );
/* find items involving c */
WSLOOP(u,v){
if( v->flag == 1 && *(pi=v->pitem) == c ){
v->flag = 0;
if( nolook ) continue;
while( (ch= *++pi)>0 ){
if( ch < NTBASE ){ /* terminal symbol */
SETBIT( clset.lset, ch );
break;
}
/* nonterminal symbol */
setunion( clset.lset, pfirst[ch-NTBASE]->lset );
if( !pempty[ch-NTBASE] ) break;
}
if( ch<=0 ) setunion( clset.lset, v->ws.lset );
}
}
/* now loop over productions derived from c */
c -= NTBASE; /* c is now nonterminal number */
t = pres[c+1];
for( s=pres[c]; s<t; ++s ){
/* put these items into the closure */
WSLOOP(wsets,v){ /* is the item there */
if( v->pitem == *s ){ /* yes, it is there */
if( nolook ) goto nexts;
if( setunion( v->ws.lset, clset.lset ) ) v->flag = work = 1;
goto nexts;
}
}
/* not there; make a new entry */
if( cwp-wsets+1 >= WSETSIZE ) error( "working set overflow" );
cwp->pitem = *s;
cwp->flag = 1;
if( !nolook ){
work = 1;
SETLOOP(k) cwp->ws.lset[k] = clset.lset[k];
}
WSBUMP(cwp);
nexts: ;
}
}
}
/* have computed closure; flags are reset; return */
if( cwp > zzcwp ) zzcwp = cwp;
if( cldebug && (foutput!=NULL) ){
fprintf( foutput, "\nState %d, nolook = %d\n", i, nolook );
WSLOOP(wsets,u){
if( u->flag ) fprintf( foutput, "flag set!\n");
u->flag = 0;
fprintf( foutput, "\t%s", writem(u->pitem));
prlook( &u->ws );
fprintf( foutput, "\n" );
}
}
}
struct looksets *flset( p ) struct looksets *p; {
/* decide if the lookahead set pointed to by p is known */
/* return pointer to a perminent location for the set */
register struct looksets *q;
int j, *w;
register *u, *v;
for( q = &lkst[nlset]; q-- > lkst; ){
u = p->lset;
v = q->lset;
w = & v[tbitset];
while( v<w) if( *u++ != *v++ ) goto more;
/* we have matched */
return( q );
more: ;
}
/* add a new one */
q = &lkst[nlset++];
if( nlset >= LSETSIZE )error("too many lookahead sets" );
SETLOOP(j){
q->lset[j] = p->lset[j];
}
return( q );
}
Continuous source code history from original PDP-7 UNIX to FreeBSD 2, the first fully unencumbered FreeBSD release.