y4.c

整理 unix v7 的 ya

#include "dextern.h"

#define a amem
#define mem mem0
#define pa indgo
#define yypact temp1
#define greed tystate

int * ggreed = lkst[0].lset;
int * pgo = wsets[0].ws.lset;
int *yy_pgo = &nontrst[0].tvalue;

int maxspr = 0;  /* maximum spread of any entry */
int maxoff = 0;  /* maximum offset into a array */
int *pmem = mem;
int *maxa;
#define NOMORE -1000

int nxdb = 0;
int adb = 0;

void callopt(void);
void gin(int i);
void stin(int i);
int  nxti(void);
void osummary(void);
void aoutput(void);
void arout(char * s, int *v, int n);
int  gtnm(void);

void callopt(void)
{

	register int i, *p, j, k, *q;

	/* read the arrays from tempfile and set parameters */

	if((finput=fopen(TEMPNAME,"r")) == NULL)
		error("optimizer cannot open tempfile");

	pgo[0] = 0;
	yypact[0] = 0;
	nstate = 0;
	nnonter = 0;
	for(;;){
		switch(gtnm()){

		case '\n':
			yypact[++nstate] = (--pmem) - mem;
		case ',':
			continue;

		case '$':
			break;

		default:
			error("bad tempfile");
		}
		break;
	}

	yypact[nstate] = yy_pgo[0] = (--pmem) - mem;

	for(;;){
		switch(gtnm()){

		case '\n':
			yy_pgo[++nnonter]= pmem-mem;
		case ',':
			continue;

		case EOF:
			break;

		default:
			error("bad tempfile");
		}
		break;
	}

	yy_pgo[nnonter--] = (--pmem) - mem;



	for(i=0; i<nstate; ++i){

		k = 32000;
		j = 0;
		q = mem + yypact[i+1];
		for(p = mem + yypact[i]; p<q ; p += 2){
			if(*p > j)
				j = *p;
			if(*p < k)
				k = *p;
		}
		if(k <= j){ /* nontrivial situation */
			/* temporarily, kill this for compatibility
			j -= k; j is now the range */
			if(k > maxoff)
				maxoff = k;
		}
		greed[i] = (yypact[i+1]-yypact[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 = mem + yy_pgo[i+1] -1;
		for(p = mem+yy_pgo[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 a array */

	for(i=0; i<ACTSIZE; ++i)
		a[i] = 0;
	maxa = a;

	for(i=0; i<nstate; ++i) {
		if(greed[i]==0 && adb>1)
			fprintf(ftable, "State %d: null\n", i);
		pa[i] = YYFLAG1;
	}

	while((i = nxti()) != NOMORE) {
		if(i >= 0)
			stin(i);
		else
			gin(-i);

	}

	if(adb>2){ /* print a array */
		for(p=a; p <= maxa; p += 10){
			fprintf(ftable, "%4d  ", p-a);
			for(i=0; i<10; ++i)
				fprintf(ftable, "%4d  ", p[i]);
			fprintf(ftable, "\n");
		}
	}
	/* write out the output appropriate to the language */

	aoutput();

	osummary();
	ZAPFILE(TEMPNAME);
}

void gin(int i)
{

	register int *p, *r, *s, *q1, *q2;

	/* enter gotos on nonterminal i into array a */

	ggreed[i] = 0;

	q2 = mem+ yy_pgo[i+1] - 1;
	q1 = mem + yy_pgo[i];

	/* now, find a place for it */

	for(p=a; p < &a[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) > &a[ACTSIZE])
					error("a array overflow");
			}
		}
		/* we have found a spot */

		*p = *q2;
		if(p > maxa){
			if((maxa=p) > &a[ACTSIZE])
				error("a array overflow");
		}
		for(r=q1; r<q2; r+=2){
			s = p + *r + 1;
			*s = r[1];
		}

		pgo[i] = p-a;
		if(adb>1)
			fprintf(ftable, "Nonterminal %d, entry at %d\n" , i, pgo[i]);
		goto nextgi;

		nextgp:  ;
	}

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

	nextgi:  ;
}

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

	greed[i] = 0;

	/* enter state i into the a array */

	q2 = mem+yypact[i+1];
	q1 = mem+yypact[i];
	/* find an acceptable place */

	for(n= -maxoff; n<ACTSIZE; ++n){

		flag = 0;
		for(r = q1; r < q2; r += 2){
			if((s = *r + n + a) < a)
				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(pa[j] == n) {
				if(flag)
					goto nextn;  /* we have some disagreement */
				if(yypact[j+1] + yypact[i] == yypact[j] + yypact[i+1]){
					/* states are equal */
					pa[i] = n;
					if(adb>1)
						fprintf(ftable, "State %d: entry at %d equals state %d\n",	i, n, j);
					return;
				}
				goto nextn;  /* we have some disagreement */
			}
		}

		for(r = q1; r < q2; r += 2){
			if((s = *r + n + a) >= &a[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-a, r[1]);
			*s = r[1];
		}
		pa[i] = n;
		if(adb>1)
			fprintf(ftable, "State %d: entry at %d\n", i, pa[i]);
		return;

	nextn:  ;
	}

	error("Error; failure to place state %d\n", i);

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

	max = 0;

	for(i=1; i<= nnonter; ++i)
		if(ggreed[i] >= max){
			max = ggreed[i];
			maxi = -i;
		}

	for(i=0; i<nstate; ++i)
		if(greed[i] >= max){
			max = greed[i];
			maxi = i;
		}

	if(nxdb)
		fprintf(ftable, "nxti = %d, max = %d\n", maxi, max);
	if(max==0)
		return(NOMORE);
	else
		return(maxi);
}
/*
 * write summary
 */
void osummary(void)
{


	register int i, *p;

	if(foutput == NULL)
		return;
	i=0;
	for(p=maxa; p>=a; --p) {
		if(*p == 0) 
			++i;
	}

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

}
/*
 * this version is for C
 */
void aoutput(void)
{

	/* write out the optimized parser */

	fprintf(ftable, "# define YYLAST %d\n", maxa-a+1);

	arout("yyact", a, (maxa-a)+1);
	arout("yypact", pa, nstate);
	arout("yypgo", pgo, nnonter+1);

}

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

	register int i;

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


int gtnm(void)
{
	register int s, val, c;

	/* read and convert an integer from the standard input */
	/* return the terminating character */
	/* blanks, tabs, and newlines are ignored */

	s = 1;
	val = 0;

	while((c=getc(finput)) != EOF){
		if(isdigit(c)){
			val = val * 10 + c - '0';
		}
		else if (c == '-')
			s = -1;
		else
			break;
	}

	*pmem++ = s*val;
	if(pmem > &mem[MEMSIZE])
		error("out of space");
	return(c);

}