sub2.c

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

		}
	}
	for(i=0; i<st; i++){	/* get most similar state */
				/* reject state with more transitions, state already represented by a third state,
					and state which is compressed by char if ours is not to be */
		if(sfall[i] != -1) continue;
		if(cpackflg[st] == 1) if(!(cpackflg[i] == 1)) continue;
		p = gotof[i];
		if(p == -1) /* no transitions */ continue;
		tcnt = nexts[p];
		if(tcnt > cnt) continue;
		diff = 0;
		j = 0;
		upper = p + tcnt;
		while(ach[j] && p < upper){
			while(ach[j] < nchar[p] && ach[j]){diff++; j++; }
			if(ach[j] == 0)break;
			if(ach[j] > nchar[p]){diff=NCH;break;}
			/* ach[j] == nchar[p] */
			if(ast[j] != nexts[++p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]]))diff++;
			j++;
		}
		while(ach[j]){
			diff++;
			j++;
		}
		if(p < upper)diff = NCH;
		if(diff < cval && diff < tcnt){
			cval = diff;
			cmin = i;
			if(cval == 0)break;
		}
	}
	/* cmin = state "most like" state st */
# ifdef DEBUG
	if(debug)print("select st %d for st %d diff %d\n",cmin,st,cval);
# endif
# ifdef PS
	if(cmin != -1){ /* if we can use st cmin */
		gotof[st] = nptr;
		k = 0;
		sfall[st] = cmin;
		p = gotof[cmin]+1;
		j = 0;
		while(ach[j]){
			/* if cmin has a transition on c, then so will st */
			/* st may be "larger" than cmin, however */
			while(ach[j] < nchar[p-1] && ach[j]){
				k++;
				nchar[nptr] = ach[j];
				nexts[++nptr] = ast[j];
				j++;
			}
			if(nchar[p-1] == 0)break;
			if(ach[j] > nchar[p-1]){
				warning("bad transition %d %d",st,cmin);
				goto nopack;
			}
			/* ach[j] == nchar[p-1] */
			if(ast[j] != nexts[p] || ast[j] == -1 || (cpackflg[st] && ach[j] != match[ach[j]])){
				k++;
				nchar[nptr] = ach[j];
				nexts[++nptr] = ast[j];
			}
			p++;
			j++;
		}
		while(ach[j]){
			nchar[nptr] = ach[j];
			nexts[++nptr] = ast[j++];
			k++;
		}
		nexts[gotof[st]] = cnt = k;
		nchar[nptr++] = 0;
	} else {
# endif
nopack:
	/* stick it in */
		gotof[st] = nptr;
		nexts[nptr] = cnt;
		for(i=0;i<cnt;i++){
			nchar[nptr] = ach[i];
			nexts[++nptr] = ast[i];
		}
		nchar[nptr++] = 0;
# ifdef PS
	}
# endif
	if(cnt < 1){
		gotof[st] = -1;
		nptr--;
	} else
		if(nptr > ntrans)
			error("Too many transitions %s",(ntrans==NTRANS?"\nTry using %a num":""));
}

# ifdef DEBUG
void
pstate(int s)
{
	int *p,i,j;
	print("State %d:\n",s);
	p = state[s];
	i = *p++;
	if(i == 0) return;
	print("%4d",*p++);
	for(j = 1; j<i; j++){
		print(", %4d",*p++);
		if(j%30 == 0)print("\n");
	}
	print("\n");
	return;
}
# endif

int
member(int d, uchar *t)
{
	int c;
	uchar *s;

	c = d;
	s = t;
	c = cindex[c];
	while(*s)
		if(*s++ == c) return(1);
	return(0);
}

# ifdef DEBUG
void
stprt(int i)
{
	int p, t;

	print("State %d:",i);
	/* print actions, if any */
	t = atable[i];
	if(t != -1)print(" final");
	print("\n");
	if(cpackflg[i] == TRUE)print("backup char in use\n");
	if(sfall[i] != -1)print("fall back state %d\n",sfall[i]);
	p = gotof[i];
	if(p == -1) return;
	print("(%d transitions)\n",nexts[p]);
	while(nchar[p]){
		charc = 0;
		if(nexts[p+1] >= 0)
			print("%d\t",nexts[p+1]);
		else print("err\t");
		allprint(nchar[p++]);
		while(nexts[p] == nexts[p+1] && nchar[p]){
			if(charc > LINESIZE){
				charc = 0;
				print("\n\t");
			}
			allprint(nchar[p++]);
		}
		print("\n");
	}
	print("\n");
}
# endif

void
acompute(int s)	/* compute action list = set of poss. actions */
{
	int *p, i, j;
	int cnt, m;
	int temp[300], k, neg[300], n;

	k = 0;
	n = 0;
	p = state[s];
	cnt = *p++;
	if(cnt > 300)
		error("Too many positions for one state - acompute");
	for(i=0;i<cnt;i++){
		if(name[*p] == FINAL)temp[k++] = left[*p];
		else if(name[*p] == S1FINAL){temp[k++] = left[*p];
			if (left[*p] >= NACTIONS) error("Too many right contexts");
			extra[left[*p]] = 1;
		} else if(name[*p] == S2FINAL)neg[n++] = left[*p];
		p++;
	}
	atable[s] = -1;
	if(k < 1 && n < 1) return;
# ifdef DEBUG
	if(debug) print("final %d actions:",s);
# endif
	/* sort action list */
	for(i=0; i<k; i++)
		for(j=i+1;j<k;j++)
			if(temp[j] < temp[i]){
				m = temp[j];
				temp[j] = temp[i];
				temp[i] = m;
			}
	/* remove dups */
	for(i=0;i<k-1;i++)
		if(temp[i] == temp[i+1]) temp[i] = 0;
	/* copy to permanent quarters */
	atable[s] = aptr;
# ifdef DEBUG
	Bprint(&fout,"/* actions for state %d */",s);
# endif
	Bputc(&fout, '\n');
	for(i=0;i<k;i++)
		if(temp[i] != 0){
			Bprint(&fout,"%d,\n",temp[i]);
# ifdef DEBUG
			if(debug)
				print("%d ",temp[i]);
# endif
			aptr++;
		}
	for(i=0;i<n;i++){		/* copy fall back actions - all neg */
		Bprint(&fout,"%d,\n",neg[i]);
		aptr++;
# ifdef DEBUG
		if(debug)print("%d ",neg[i]);
# endif
	}
# ifdef DEBUG
	if(debug)print("\n");
# endif
	Bprint(&fout,"0,\n");
	aptr++;
	return;
}

# ifdef DEBUG
void
pccl(void) {
	/* print character class sets */
	int i, j;

	print("char class intersection\n");
	for(i=0; i< ccount; i++){
		charc = 0;
		print("class %d:\n\t",i);
		for(j=1;j<NCH;j++)
			if(cindex[j] == i){
				allprint(j);
				if(charc > LINESIZE){
					print("\n\t");
					charc = 0;
				}
			}
		print("\n");
	}
	charc = 0;
	print("match:\n");
	for(i=0;i<NCH;i++){
		allprint(match[i]);
		if(charc > LINESIZE){
			print("\n");
			charc = 0;
		}
	}
	print("\n");
	return;
}
# endif

void
mkmatch(void)
{
	int i;
	uchar tab[NCH];

	for(i=0; i<ccount; i++)
		tab[i] = 0;
	for(i=1;i<NCH;i++)
		if(tab[cindex[i]] == 0)
			tab[cindex[i]] = i;
	/* tab[i] = principal char for new ccl i */
	for(i = 1; i<NCH; i++)
		match[i] = tab[cindex[i]];
	return;
}

void
layout(void)
{
	/* format and output final program's tables */
	int i, j, k;
	int  top, bot, startup, omin;

	for(i=0; i<outsize;i++)
		verify[i] = advance[i] = 0;
	omin = 0;
	yytop = 0;
	for(i=0; i<= stnum; i++){	/* for each state */
		j = gotof[i];
		if(j == -1){
			stoff[i] = 0;
			continue;
			}
		bot = j;
		while(nchar[j])j++;
		top = j - 1;
# ifdef DEBUG
		if (debug) {
			print("State %d: (layout)\n", i);
			for(j=bot; j<=top;j++) {
				print("  %o", nchar[j]);
				if (j%10==0) print("\n");
			}
			print("\n");
		}
# endif
		while(verify[omin+NCH]) omin++;
		startup = omin;
# ifdef DEBUG
		if (debug) print("bot,top %d, %d startup begins %d\n",bot,top,startup);
# endif
		do {
			startup += 1;
			if(startup > outsize - NCH)
				error("output table overflow");
			for(j = bot; j<= top; j++){
				k = startup + nchar[j];
				if(verify[k])break;
			}
		} while (j <= top);
		/* have found place */
# ifdef DEBUG
		if (debug) print(" startup going to be %d\n", startup);
# endif
		for(j = bot; j<= top; j++){
			k = startup + nchar[j];
			verify[k] = i+1;			/* state number + 1*/
			advance[k] = nexts[j+1]+1;		/* state number + 1*/
			if(yytop < k) yytop = k;
		}
		stoff[i] = startup;
	}

	/* stoff[i] = offset into verify, advance for trans for state i */
	/* put out yywork */
	Bprint(&fout,"# define YYTYPE %s\n",stnum+1 >= NCH ? "int" : "Uchar");
	Bprint(&fout,"struct yywork { YYTYPE verify, advance; } yycrank[] = {\n");
	for(i=0;i<=yytop;i+=4){
		for(j=0;j<4;j++){
			k = i+j;
			if(verify[k])
				Bprint(&fout,"%d,%d,\t",verify[k],advance[k]);
			else
				Bprint(&fout,"0,0,\t");
		}
		Bputc(&fout, '\n');
	}
	Bprint(&fout,"0,0};\n");

	/* put out yysvec */

	Bprint(&fout,"struct yysvf yysvec[] = {\n");
	Bprint(&fout,"0,\t0,\t0,\n");
	for(i=0;i<=stnum;i++){	/* for each state */
		if(cpackflg[i])stoff[i] = -stoff[i];
		Bprint(&fout,"yycrank+%d,\t",stoff[i]);
		if(sfall[i] != -1)
			Bprint(&fout,"yysvec+%d,\t", sfall[i]+1);	/* state + 1 */
		else Bprint(&fout,"0,\t\t");
		if(atable[i] != -1)
			Bprint(&fout,"yyvstop+%d,",atable[i]);
		else Bprint(&fout,"0,\t");
# ifdef DEBUG
		Bprint(&fout,"\t\t/* state %d */",i);
# endif
		Bputc(&fout, '\n');
	}
	Bprint(&fout,"0,\t0,\t0};\n");

	/* put out yymatch */
	
	Bprint(&fout,"struct yywork *yytop = yycrank+%d;\n",yytop);
	Bprint(&fout,"struct yysvf *yybgin = yysvec+1;\n");
	Bprint(&fout,"Uchar yymatch[] = {\n");
	for(i=0; i<NCH; i+=8){
		for(j=0; j<8; j++){
			int fbch;
			fbch = match[i+j];
			if(isprint(fbch) && fbch != '\'' && fbch != '\\')
				Bprint(&fout,"'%c' ,",fbch);
			else Bprint(&fout,"0%-3o,",fbch);
		}
		Bputc(&fout, '\n');
	}
	Bprint(&fout,"0};\n");
	/* put out yyextra */
	Bprint(&fout,"Uchar yyextra[] = {\n");
	for(i=0;i<casecount;i+=8){
		for(j=0;j<8;j++)
			Bprint(&fout, "%d,", i+j<NACTIONS ?
				extra[i+j] : 0);
		Bputc(&fout, '\n');
	}
	Bprint(&fout,"0};\n");
}

# ifdef PP
void
padd(int **array, int n)
{
	int i, *j, k;

	array[n] = nxtpos;
	if(count == 0){
		*nxtpos++ = 0;
		return;
	}
	for(i=tptr-1;i>=0;i--){
		j = array[i];
		if(j && *j++ == count){
			for(k=0;k<count;k++)
				if(!tmpstat[*j++])break;
			if(k >= count){
				array[n] = array[i];
				return;
			}
		}
	}
	add(array,n);
}
# endif