y1.c

整理 unix v7 的 ya

		}
	}
}
/*
 * sorts last state,and sees if it equals earlier ones. returns state number
 */
int state(int c)
{
	int size1,size2;
	register int 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 */
void putitem(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");
	}
}
 
/* 
 * mark nonterminals which derive the empty string
 * also, look for nonterminals which don't derive any token strings
 */
void cempty(void)
{
#define EMPTY 1
#define WHOKNOWS 0
#define OK 1

	register int 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();
		ZAPFILE(ACTNAME);
		ZAPFILE(TEMPNAME);
		ZAPFILE(OFILE);
		if (fdefine != NULL)
			ZAPFILE(FILED);
		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;
/*
 * generate the states
 */
void stagen(void)
{ 

	int i, j;
	register int 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 */
/*
 * generate the closure of state i
 */
void closure(int 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");
		}
	}
}
/*
 * decide if the lookahead set pointed to by p is known
 * return pointer to a perminent location for the set
 */
struct looksets *flset(struct looksets *p)
{
	register struct looksets *q;
	int j, *w;
	register int *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);
}