yacc.c

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

		}
		wract(i);
	}

	if(fdebug)
		Bprint(fdebug, "};\n");
	Bprint(ftable, "};\n");
	Bprint(ftable, "#define	YYNPROD	%d\n", nprod);
	Bprint(ftable, "#define	YYPRIVATE %d\n", PRIVATE);
	if(yydebug)
		Bprint(ftable, "#define	yydebug	%s\n", yydebug);
}

/*
 * pack state i from temp1 into amem
 */
int
apack(int *p, int n)
{
	int *pp, *qq, *rr, off, *q, *r;

	/* we don't need to worry about checking because
	 * we will only look at entries known to be there...
	 * eliminate leading and trailing 0's
	 */

	q = p+n;
	for(pp = p, off = 0; *pp == 0 && pp <= q; ++pp, --off)
		;
 	/* no actions */
	if(pp > q)
		return 0;
	p = pp;

	/* now, find a place for the elements from p to q, inclusive */
	r = &amem[ACTSIZE-1];
	for(rr = amem; rr <= r; rr++, off++) {
		for(qq = rr, pp = p; pp <= q; pp++, qq++)
			if(*pp != 0)
				if(*pp != *qq && *qq != 0)
					goto nextk;

		/* we have found an acceptable k */
		if(pkdebug && foutput != 0)
			Bprint(foutput, "off = %d, k = %d\n", off, (int)(rr-amem));
		for(qq = rr, pp = p; pp <= q; pp++, qq++)
			if(*pp) {
				if(qq > r)
					error("action table overflow");
				if(qq > memp)
					memp = qq;
				*qq = *pp;
			}
		if(pkdebug && foutput != 0)
			for(pp = amem; pp <= memp; pp += 10) {
				Bprint(foutput, "\t");
				for(qq = pp; qq <= pp+9; qq++)
					Bprint(foutput, "%d ", *qq);
				Bprint(foutput, "\n");
			}
		return(off);
	nextk:;
	}
	error("no space in action table");
	return 0;
}

/*
 * output the gotos for the nontermninals
 */
void
go2out(void)
{
	int i, j, k, best, count, cbest, times;

	/* mark begining of gotos */
	Bprint(ftemp, "$\n");
	for(i = 1; i <= nnonter; i++) {
		go2gen(i);

		/* find the best one to make default */
		best = -1;
		times = 0;

		/* is j the most frequent */
		for(j = 0; j <= nstate; j++) {
			if(tystate[j] == 0)
				continue;
			if(tystate[j] == best)
				continue;

			/* is tystate[j] the most frequent */
			count = 0;
			cbest = tystate[j];
			for(k = j; k <= nstate; k++)
				if(tystate[k] == cbest)
					count++;
			if(count > times) {
				best = cbest;
				times = count;
			}
		}

		/* best is now the default entry */
		zzgobest += times-1;
		for(j = 0; j <= nstate; j++)
			if(tystate[j] != 0 && tystate[j] != best) {
				Bprint(ftemp, "%d,%d,", j, tystate[j]);
				zzgoent++;
			}

		/* now, the default */
		if(best == -1)
			best = 0;
		zzgoent++;
		Bprint(ftemp, "%d\n", best);
	}
}

/*
 * output the gotos for nonterminal c
 */
void
go2gen(int c)
{
	int i, work, cc;
	Item *p, *q;


	/* first, find nonterminals with gotos on c */
	aryfil(temp1, nnonter+1, 0);
	temp1[c] = 1;
	work = 1;
	while(work) {
		work = 0;
		PLOOP(0, i)

			/* cc is a nonterminal */
			if((cc=prdptr[i][1]-NTBASE) >= 0)
				/* cc has a goto on c */
				if(temp1[cc] != 0) {

					/* thus, the left side of production i does too */
					cc = *prdptr[i]-NTBASE;
					if(temp1[cc] == 0) {
						  work = 1;
						  temp1[cc] = 1;
					}
				}
	}

	/* now, we have temp1[c] = 1 if a goto on c in closure of cc */
	if(g2debug && foutput != 0) {
		Bprint(foutput, "%s: gotos on ", nontrst[c].name);
		NTLOOP(i)
			if(temp1[i])
				Bprint(foutput, "%s ", nontrst[i].name);
		Bprint(foutput, "\n");
	}

	/* now, go through and put gotos into tystate */
	aryfil(tystate, nstate, 0);
	SLOOP(i)
		ITMLOOP(i, p, q)
			if((cc = *p->pitem) >= NTBASE)
				/* goto on c is possible */
				if(temp1[cc-NTBASE]) {
					tystate[i] = amem[indgo[i]+c];
					break;
				}
}

/*
 * decide a shift/reduce conflict by precedence.
 * r is a rule number, t a token number
 * the conflict is in state s
 * temp1[t] is changed to reflect the action
 */
void
precftn(int r, int t, int s)
{
	int lp, lt, action;

	lp = levprd[r];
	lt = toklev[t];
	if(PLEVEL(lt) == 0 || PLEVEL(lp) == 0) {

		/* conflict */
		if(foutput != 0)
			Bprint(foutput,
				"\n%d: shift/reduce conflict (shift %d(%d), red'n %d(%d)) on %s",
				s, temp1[t], PLEVEL(lt), r, PLEVEL(lp), symnam(t));
		zzsrconf++;
		return;
	}
	if(PLEVEL(lt) == PLEVEL(lp))
		action = ASSOC(lt);
	else
		if(PLEVEL(lt) > PLEVEL(lp))
			action = RASC;  /* shift */
		else
			action = LASC;  /* reduce */
	switch(action) {
	case BASC:  /* error action */
		temp1[t] = ERRCODE;
		break;
	case LASC:  /* reduce */
		temp1[t] = -r;
		break;
	}
}

/*
 * output state i
 * temp1 has the actions, lastred the default
 */
void
wract(int i)
{
	int p, p0, p1, ntimes, tred, count, j, flag;

	/* find the best choice for lastred */
	lastred = 0;
	ntimes = 0;
	TLOOP(j) {
		if(temp1[j] >= 0)
			continue;
		if(temp1[j]+lastred == 0)
			continue;
		/* count the number of appearances of temp1[j] */
		count = 0;
		tred = -temp1[j];
		levprd[tred] |= REDFLAG;
		TLOOP(p)
			if(temp1[p]+tred == 0)
				count++;
		if(count > ntimes) {
			lastred = tred;
			ntimes = count;
		}
	}

	/*
	 * for error recovery, arrange that, if there is a shift on the
	 * error recovery token, `error', that the default be the error action
	 */
	if(temp1[2] > 0)
		lastred = 0;

	/* clear out entries in temp1 which equal lastred */
	TLOOP(p)
		if(temp1[p]+lastred == 0)
			temp1[p] = 0;

	wrstate(i);
	defact[i] = lastred;
	flag = 0;
	TLOOP(p0)
		if((p1=temp1[p0]) != 0) {
			if(p1 < 0) {
				p1 = -p1;
				goto exc;
			}
			if(p1 == ACCEPTCODE) {
				p1 = -1;
				goto exc;
			}
			if(p1 == ERRCODE) {
				p1 = 0;
			exc:
				if(flag++ == 0)
					Bprint(ftable, "-1, %d,\n", i);
				Bprint(ftable, "\t%d, %d,\n", p0, p1);
				zzexcp++;
				continue;
			}
			Bprint(ftemp, "%d,%d,", p0, p1);
			zzacent++;
		}
	if(flag) {
		defact[i] = -2;
		Bprint(ftable, "\t-2, %d,\n", lastred);
	}
	Bprint(ftemp, "\n");
}

/*
 * writes state i
 */
void
wrstate(int i)
{
	int j0, j1;
	Item *pp, *qq;
	Wset *u;

	if(fdebug) {
		if(lastred) {
			Bprint(fdebug, "	0, /*%d*/\n", i);
		} else {
			Bprint(fdebug, "	\"");
			ITMLOOP(i, pp, qq)
				Bprint(fdebug, "%s\\n", writem(pp->pitem));
			if(tystate[i] == MUSTLOOKAHEAD)
				WSLOOP(wsets + (pstate[i+1] - pstate[i]), u)
					if(*u->pitem < 0)
						Bprint(fdebug, "%s\\n", writem(u->pitem));
			Bprint(fdebug, "\", /*%d*/\n", i);
		}
	}
	if(foutput == 0)
		return;
	Bprint(foutput, "\nstate %d\n", i);
	ITMLOOP(i, pp, qq)
		Bprint(foutput, "\t%s\n", writem(pp->pitem));
	if(tystate[i] == MUSTLOOKAHEAD)
		/* print out empty productions in closure */
		WSLOOP(wsets+(pstate[i+1]-pstate[i]), u)
			if(*u->pitem < 0)
				Bprint(foutput, "\t%s\n", writem(u->pitem));

	/* check for state equal to another */
	TLOOP(j0)
		if((j1=temp1[j0]) != 0) {
			Bprint(foutput, "\n\t%s  ", symnam(j0));
			/* shift, error, or accept */
			if(j1 > 0) {
				if(j1 == ACCEPTCODE)
					Bprint(foutput,  "accept");
				else
					if(j1 == ERRCODE)
						Bprint(foutput, "error");
					else
						Bprint(foutput, "shift %d", j1);
			} else
				Bprint(foutput, "reduce %d (src line %d)", -j1, rlines[-j1]);
		}

	/* output the final production */
	if(lastred)
		Bprint(foutput, "\n\t.  reduce %d (src line %d)\n\n",
			lastred, rlines[lastred]);
	else
		Bprint(foutput, "\n\t.  error\n\n");

	/* now, output nonterminal actions */
	j1 = ntokens;
	for(j0 = 1; j0 <= nnonter; j0++) {
		j1++;
		if(temp1[j1])
			Bprint(foutput, "\t%s  goto %d\n", symnam(j0+NTBASE), temp1[j1]);
	}
}

void
warray(char *s, int *v, int n)
{
	int i;

	Bprint(ftable, "short	%s[] =\n{", s);
	for(i=0;;) {
		if(i%10 == 0)
			Bprint(ftable, "\n");
		Bprint(ftable, "%4d", v[i]);
		i++;
		if(i >= n) {
			Bprint(ftable, "\n};\n");
			break;
		}
		Bprint(ftable, ",");
	}
}

/*
 * in order to free up the mem and amem arrays for the optimizer,
 * and still be able to output yyr1, etc., after the sizes of
 * the action array is known, we hide the nonterminals
 * derived by productions in levprd.
 */

void
hideprod(void)
{
	int i, j;

	j = 0;
	levprd[0] = 0;
	PLOOP(1, i) {
		if(!(levprd[i] & REDFLAG)) {
			j++;
			if(foutput != 0)
				Bprint(foutput, "Rule not reduced:   %s\n", writem(prdptr[i]));
		}
		levprd[i] = *prdptr[i] - NTBASE;
	}
	if(j)
		print("%d rules never reduced\n", j);
}

void
callopt(void)
{
	int i, *p, j, k, *q;

	/* read the arrays from tempfile and set parameters */
	finput = Bopen(tempname, OREAD);
	if(finput == 0)
		error("optimizer cannot open tempfile");

	pgo[0] = 0;
	temp1[0] = 0;
	nstate = 0;
	nnonter = 0;
	for(;;) {
		switch(gtnm()) {
		case '\n':
			nstate++;
			pmem--;
			temp1[nstate] = pmem - mem0;
		case ',':
			continue;
		case '$':
			break;
		default:
			error("bad tempfile");
		}
		break;
	}

	pmem--;
	temp1[nstate] = yypgo[0] = pmem - mem0;
	for(;;) {
		switch(gtnm()) {
		case '\n':
			nnonter++;
			yypgo[nnonter] = pmem-mem0;
		case ',':
			continue;
		case -1:
			break;
		default:
			error("bad tempfile");
		}
		break;
	}
	pmem--;
	yypgo[nnonter--] = pmem - mem0;
	for(i = 0; i < nstate; i++) {
		k = 32000;
		j = 0;
		q = mem0 + temp1[i+1];
		for(p = mem0 + temp1[i]; p < q ; p += 2) {
			if(*p > j)
				j = *p;
			if(*p < k)
				k = *p;
		}
		/* nontrivial situation */
		if(k <= j) {
			/* j is now the range */
/*			j -= k;			/* call scj */
			if(k > maxoff)
				maxoff = k;
		}
		tystate[i] = (temp1[i+1]-temp1[i]) + 2*j;
		if(j > maxspr)
			maxspr = j;
	}

	/* initialize ggreed table */
	for(i = 1; i <= nnonter; i++) {
		ggreed[i] = 1;
		j = 0;

		/* minimum entry index is always 0 */
		q = mem0 + yypgo[i+1] - 1;
		for(p = mem0+yypgo[i]; p < q ; p += 2) {
			ggreed[i] += 2;
			if(*p > j)
				j = *p;
		}
		ggreed[i] = ggreed[i] + 2*j;
		if(j > maxoff)
			maxoff = j;
	}

	/* now, prepare to put the shift actions into the amem array */
	for(i = 0; i < ACTSIZE; i++)
		amem[i] = 0;
	maxa = amem;
	for(i = 0; i < nstate; i++) {
		if(tystate[i] == 0 && adb > 1)
			Bprint(ftable, "State %d: null\n", i);
		indgo[i] = YYFLAG1;
	}
	while((i = nxti()) != NOMORE)
		if(i >= 0)
			stin(i);
		else
			gin(-i);

	/* print amem array */
	if(adb > 2 )
		for(p = amem; p <= maxa; p += 10) {
			Bprint(ftable, "%4d  ", (int)(p-amem));
			for(i = 0; i < 10; ++i)
				Bprint(ftable, "%4d  ", p[i]);
			Bprint(ftable, "\n");
		}

	/* write out the output appropriate to the language */
	aoutput();
	osummary();
	ZAPFILE(tempname);
}

void
gin(int i)
{
	int *p, *r, *s, *q1, *q2;

	/* enter gotos on nonterminal i into array amem */
	ggreed[i] = 0;

	q2 = mem0+ yypgo[i+1] - 1;
	q1 = mem0 + yypgo[i];

	/* now, find amem place for it */
	for(p = amem; p < &amem[ACTSIZE]; p++) {
		if(*p)
			continue;
		for(r = q1; r < q2; r += 2) {
			s = p + *r + 1;
			if(*s)
				goto nextgp;
			if(s > maxa)
				if((maxa = s) > &amem[ACTSIZE])
					error("a array overflow");
		}
		/* we have found amem spot */
		*p = *q2;
		if(p > maxa)
			if((maxa = p) > &amem[ACTSIZE])
				error("a array overflow");
		for(r = q1; r < q2; r += 2) {
			s = p + *r + 1;
			*s = r[1];
		}
		pgo[i] = p-amem;
		if(adb > 1)
			Bprint(ftable, "Nonterminal %d, entry at %d\n", i, pgo[i]);
		return;

	nextgp:;
	}
	error("cannot place goto %d\n", i);
}

void
stin(int i)
{
	int *r, *s, n, flag, j, *q1, *q2;

	tystate[i] = 0;

	/* enter state i into the amem array */
	q2 = mem0+temp1[i+1];
	q1 = mem0+temp1[i];
	/* find an acceptable place */
	for(n = -maxoff; n < ACTSIZE; n++) {
		flag = 0;
		for(r = q1; r < q2; r += 2) {
			if((s = *r + n + amem) < amem)
				goto nextn;
			if(*s == 0)
				flag++;
			else
				if(*s != r[1])
					goto nextn;
		}

		/* check that the position equals another only if the states are identical */
		for(j=0; j<nstate; j++) {
			if(indgo[j] == n) {

				/* we have some disagreement */
				if(flag)
					goto nextn;
				if(temp1[j+1]+temp1[i] == temp1[j]+temp1[i+1]) {

					/* states are equal */
					indgo[i] = n;
					if(adb > 1)
						Bprint(ftable,
						"State %d: entry at %d equals state %d\n",
						i, n, j);
					return;
				}

				/* we have some disagreement */
				goto nextn;
			}
		}

		for(r = q1; r < q2; r += 2) {
			if((s = *r+n+amem) >= &amem[ACTSIZE])
				error("out of space in optimizer a array");
			if(s > maxa)
				maxa = s;
			if(*s != 0 && *s != r[1])
				error("clobber of a array, pos'n %d, by %d", s-amem, r[1]);
			*s = r[1];
		}
		indgo[i] = n;
		if(adb > 1)
			Bprint(ftable, "State %d: entry at %d\n", i, indgo[i]);
		return;
	nextn:;
	}
	error("Error; failure to place state %d\n", i);
}

/*
 * finds the next i
 */
int
nxti(void)
{
	int i, max, maxi;

	max = 0;
	maxi = 0;
	for(i = 1; i <= nnonter; i++)
		if(ggreed[i] >= max) {
			max = ggreed[i];
			maxi = -i;
		}
	for(i = 0; i < nstate; ++i)
		if(tystate[i] >= max) {
			max = tystate[i];
			maxi = i;
		}
	if(nxdb)
		Bprint(ftable, "nxti = %d, max = %d\n", maxi, max);
	if(max == 0)
		return NOMORE;
	return maxi;
}

/*
 * write summary
 */
void
osummary(void)
{

	int i, *p;

	if(foutput == 0)
		return;
	i = 0;
	for(p = maxa; p >= amem; p--)
		if(*p == 0)
			i++;

	Bprint(foutput, "Optimizer space used: input %d/%d, output %d/%d\n",
		(int)(pmem-mem0+1), MEMSIZE, (int)(maxa-amem+1), ACTSIZE);
	Bprint(foutput, "%d table entries, %d zero\n", (int)(maxa-amem+1), i);
	Bprint(foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff);
}

/*
 * this version is for C
 * write out the optimized parser
 */
void
aoutput(void)
{
	Bprint(ftable, "#define\tYYLAST\t%d\n", (int)(maxa-amem+1));
	arout("yyact", amem, (maxa-amem)+1);
	arout("yypact", indgo, nstate);
	arout("yypgo", pgo, nnonter+1);
}

void
arout(char *s, int *v, int n)
{
	int i;

	Bprint(ftable, "short	%s[] =\n{", s);
	for(i = 0; i < n;) {
		if(i%10 == 0)
			Bprint(ftable, "\n");
		Bprint(ftable, "%4d", v[i]);
		i++;
		if(i == n)
			Bprint(ftable, "\n};\n");
		else
			Bprint(ftable, ",");
	}
}

/*
 * read and convert an integer from the standard input
 * return the terminating character
 * blanks, tabs, and newlines are ignored
 */
int
gtnm(void)
{
	int sign, val, c;

	sign = 0;
	val = 0;
	while((c=Bgetrune(finput)) != Beof) {
		if(isdigit(c)) {
			val = val*10 + c-'0';
			continue;
		}
		if(c == '-') {
			sign = 1;
			continue;
		}
		break;
	}
	if(sign)
		val = -val;
	*pmem++ = val;
	if(pmem >= &mem0[MEMSIZE])
		error("out of space");
	return c;
}