sub2.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

# include "ldefs.h"
void
cfoll(int v)
{
	int i,j,k;
	uchar *p;
	i = name[v];
	if(i < NCH) i = 1;	/* character */
	switch(i){
		case 1: case RSTR: case RCCL: case RNCCL: case RNULLS:
			for(j=0;j<tptr;j++)
				tmpstat[j] = FALSE;
			count = 0;
			follow(v);
# ifdef PP
			padd(foll,v);		/* packing version */
# endif
# ifndef PP
			add(foll,v);		/* no packing version */
# endif
			if(i == RSTR) cfoll(left[v]);
			else if(i == RCCL || i == RNCCL){	/* compress ccl list */
				for(j=1; j<NCH;j++)
					symbol[j] = (i==RNCCL);
				p = ptr[v];
				while(*p)
					symbol[*p++] = (i == RCCL);
				p = pcptr;
				for(j=1;j<NCH;j++)
					if(symbol[j]){
						for(k=0;p+k < pcptr; k++)
							if(cindex[j] == *(p+k))
								break;
						if(p+k >= pcptr)*pcptr++ = cindex[j];
					}
				*pcptr++ = 0;
				if(pcptr > pchar + pchlen)
					error("Too many packed character classes");
				ptr[v] = p;
				name[v] = RCCL;	/* RNCCL eliminated */
# ifdef DEBUG
				if(debug && *p){
					print("ccl %d: %d",v,*p++);
					while(*p)
						print(", %d",*p++);
					print("\n");
				}
# endif
			}
			break;
		case CARAT:
			cfoll(left[v]);
			break;
		case STAR: case PLUS: case QUEST: case RSCON: 
			cfoll(left[v]);
			break;
		case BAR: case RCAT: case DIV: case RNEWE:
			cfoll(left[v]);
			cfoll(right[v]);
			break;
# ifdef DEBUG
		case FINAL:
		case S1FINAL:
		case S2FINAL:
			break;
		default:
			warning("bad switch cfoll %d",v);
# endif
	}
}

# ifdef DEBUG
void
pfoll(void)
	{
	int i,k,*p;
	int j;
	/* print sets of chars which may follow positions */
	print("pos\tchars\n");
	for(i=0;i<tptr;i++)
		if(p=foll[i]){
			j = *p++;
			if(j >= 1){
				print("%d:\t%d",i,*p++);
				for(k=2;k<=j;k++)
					print(", %d",*p++);
				print("\n");
			}
		}
}
# endif

void
add(int **array, int n)
{
	int i, *temp;
	uchar *ctemp;

	temp = nxtpos;
	ctemp = tmpstat;
	array[n] = nxtpos;		/* note no packing is done in positions */
	*temp++ = count;
	for(i=0;i<tptr;i++)
		if(ctemp[i] == TRUE)
			*temp++ = i;
	nxtpos = temp;
	if(nxtpos >= positions+maxpos)
		error("Too many positions %s",(maxpos== MAXPOS?"\nTry using %p num":""));
	return;
}

void
follow(int v)
{
	int p;
	if(v >= tptr-1)return;
	p = parent[v];
	if(p == 0) return;
	switch(name[p]){
			/* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
		case RSTR:
			if(tmpstat[p] == FALSE){
				count++;
				tmpstat[p] = TRUE;
			}
			break;
		case STAR: case PLUS:
			first(v);
			follow(p);
			break;
		case BAR: case QUEST: case RNEWE:
			follow(p);
			break;
		case RCAT: case DIV: 
			if(v == left[p]){
				if(nullstr[right[p]])
					follow(p);
				first(right[p]);
			}
			else follow(p);
			break;
		case RSCON: case CARAT: 
			follow(p);
			break;
# ifdef DEBUG
		default:
			warning("bad switch follow %d",p);
# endif
	}
}

void
first(int v)	/* calculate set of positions with v as root which can be active initially */
{
	int i;
	uchar *p;
	i = name[v];
	if(i < NCH)i = 1;
	switch(i){
		case 1: case RCCL: case RNCCL: case RNULLS: case FINAL: case S1FINAL: case S2FINAL:
			if(tmpstat[v] == FALSE){
				count++;
				tmpstat[v] = TRUE;
			}
			break;
		case BAR: case RNEWE:
			first(left[v]);
			first(right[v]);
			break;
		case CARAT:
			if(stnum % 2 == 1)
				first(left[v]);
			break;
		case RSCON:
			i = stnum/2 +1;
			p = (uchar *)right[v];
			while(*p)
				if(*p++ == i){
					first(left[v]);
					break;
				}
			break;
		case STAR: case QUEST: case PLUS:  case RSTR:
			first(left[v]);
			break;
		case RCAT: case DIV:
			first(left[v]);
			if(nullstr[left[v]])
				first(right[v]);
			break;
# ifdef DEBUG
		default:
			warning("bad switch first %d",v);
# endif
	}
}

void
cgoto(void)
{
	int i, j, s;
	int npos, curpos, n;
	int tryit;
	uchar tch[NCH];
	int tst[NCH];
	uchar *q;

	/* generate initial state, for each start condition */
	Bprint(&fout,"int yyvstop[] = {\n0,\n");
	while(stnum < 2 || stnum/2 < sptr){
		for(i = 0; i<tptr; i++) tmpstat[i] = 0;
		count = 0;
		if(tptr > 0)first(tptr-1);
		add(state,stnum);
# ifdef DEBUG
		if(debug){
			if(stnum > 1)
				print("%s:\n",sname[stnum/2]);
			pstate(stnum);
		}
# endif
		stnum++;
	}
	stnum--;
	/* even stnum = might not be at line begin */
	/* odd stnum  = must be at line begin */
	/* even states can occur anywhere, odd states only at line begin */
	for(s = 0; s <= stnum; s++){
		tryit = FALSE;
		cpackflg[s] = FALSE;
		sfall[s] = -1;
		acompute(s);
		for(i=0;i<NCH;i++) symbol[i] = 0;
		npos = *state[s];
		for(i = 1; i<=npos; i++){
			curpos = *(state[s]+i);
			if(name[curpos] < NCH) symbol[name[curpos]] = TRUE;
			else switch(name[curpos]){
			case RCCL:
				tryit = TRUE;
				q = ptr[curpos];
				while(*q){
					for(j=1;j<NCH;j++)
						if(cindex[j] == *q)
							symbol[j] = TRUE;
					q++;
				}
				break;
			case RSTR:
				symbol[right[curpos]] = TRUE;
				break;
# ifdef DEBUG
			case RNULLS:
			case FINAL:
			case S1FINAL:
			case S2FINAL:
				break;
			default:
				warning("bad switch cgoto %d state %d",curpos,s);
				break;
# endif
			}
		}
# ifdef DEBUG
		if(debug){
			print("State %d transitions on:\n\t",s);
			charc = 0;
			for(i = 1; i<NCH; i++){
				if(symbol[i]) allprint(i);
				if(charc > LINESIZE){
					charc = 0;
					print("\n\t");
				}
			}
			print("\n");
		}
# endif
		/* for each char, calculate next state */
		n = 0;
		for(i = 1; i<NCH; i++){
			if(symbol[i]){
				nextstate(s,i);		/* executed for each state, transition pair */
				xstate = notin(stnum);
				if(xstate == -2) warning("bad state  %d %o",s,i);
				else if(xstate == -1){
					if(stnum >= nstates)
						error("Too many states %s",(nstates == NSTATES ? "\nTry using %n num":""));
					add(state,++stnum);
# ifdef DEBUG
					if(debug)pstate(stnum);
# endif
					tch[n] = i;
					tst[n++] = stnum;
				} else {		/* xstate >= 0 ==> state exists */
					tch[n] = i;
					tst[n++] = xstate;
				}
			}
		}
		tch[n] = 0;
		tst[n] = -1;
		/* pack transitions into permanent array */
		if(n > 0) packtrans(s,tch,tst,n,tryit);
		else gotof[s] = -1;
	}
	Bprint(&fout,"0};\n");
}

/*	Beware -- 70% of total CPU time is spent in this subroutine -
	if you don't believe me - try it yourself ! */
void
nextstate(int s, int c)
{
	int j, *newpos;
	uchar *temp, *tz;
	int *pos, i, *f, num, curpos, number;
	/* state to goto from state s on char c */
	num = *state[s];
	temp = tmpstat;
	pos = state[s] + 1;
	for(i = 0; i<num; i++){
		curpos = *pos++;
		j = name[curpos];
		if(j < NCH && j == c
		|| j == RSTR && c == right[curpos]
		|| j == RCCL && member(c, ptr[curpos])){
			f = foll[curpos];
			number = *f;
			newpos = f+1;
			for(j=0;j<number;j++)
				temp[*newpos++] = 2;
		}
	}
	j = 0;
	tz = temp + tptr;
	while(temp < tz){
		if(*temp == 2){
			j++;
			*temp++ = 1;
		}
		else *temp++ = 0;
	}
	count = j;
}

int
notin(int n)
{	/* see if tmpstat occurs previously */
	int *j,k;
	uchar *temp;
	int i;

	if(count == 0)
		return(-2);
	temp = tmpstat;
	for(i=n;i>=0;i--){	/* for each state */
		j = state[i];
		if(count == *j++){
			for(k=0;k<count;k++)
				if(!temp[*j++])break;
			if(k >= count)
				return(i);
		}
	}
	return(-1);
}

void
packtrans(int st, uchar *tch, int *tst, int cnt, int tryit)
{
	/* pack transitions into nchar, nexts */
	/* nchar is terminated by '\0', nexts uses cnt, followed by elements */
	/* gotof[st] = index into nchr, nexts for state st */

	/* sfall[st] =  t implies t is fall back state for st */
	/*	        == -1 implies no fall back */

	int i,j,k;
	int cmin, cval, tcnt, diff, p, *ast;
	uchar *ach;
	int go[NCH], temp[NCH], c;
	int swork[NCH];
	uchar cwork[NCH];
	int upper;

	rcount += cnt;
	cmin = -1;
	cval = NCH;
	ast = tst;
	ach = tch;
	/* try to pack transitions using ccl's */
	if(tryit){	/* ccl's used */
		for(i=1;i<NCH;i++){
			go[i] = temp[i] = -1;
			symbol[i] = 1;
		}
		for(i=0;i<cnt;i++){
			go[tch[i]] = tst[i];
			symbol[tch[i]] = 0;
		}
		for(i=0; i<cnt;i++){
			c = match[tch[i]];
			if(go[c] != tst[i] || c == tch[i])
				temp[tch[i]] = tst[i];
		}
		/* fill in error entries */
		for(i=1;i<NCH;i++)
			if(symbol[i]) temp[i] = -2;	/* error trans */
		/* count them */
		k = 0;
		for(i=1;i<NCH;i++)
			if(temp[i] != -1)k++;
		if(k <cnt){	/* compress by char */
# ifdef DEBUG
			if(debug) print("use compression  %d,  %d vs %d\n",st,k,cnt);
# endif
			k = 0;
			for(i=1;i<NCH;i++)
				if(temp[i] != -1){
					cwork[k] = i;
					swork[k++] = (temp[i] == -2 ? -1 : temp[i]);
				}
			cwork[k] = 0;
# ifdef PC
			ach = cwork;
			ast = swork;
			cnt = k;
			cpackflg[st] = TRUE;
# endif