Subversion Repositories planix.SVN

#include <u.h>

#include <libc.h>

#include <bio.h>

#include <ctype.h>

#define	Bungetrune	Bungetc		/* ok for now. */

/*

 * all these are 32 bit

 */

#define TBITSET		((32+NTERMS)/32)	/* BOTCH?? +31 */

#define BIT(a,i)	((a)[(i)>>5] & (1<<((i)&037)))

#define SETBIT(a,i)	((a)[(i)>>5] |= (1<<((i)&037)))

#define NWORDS(n)	(((n)+32)/32)

#define PARSER		"/sys/lib/yaccpar"

#define PARSERS		"/sys/lib/yaccpars"

#define TEMPNAME	"y.tmp.XXXXXX"

#define ACTNAME		"y.acts.XXXXXX"

#define OFILE		"tab.c"

#define FILEU		"output"

#define FILED		"tab.h"

#define FILEDEBUG	"debug"

enum

{

/*

 * the following are adjustable

 * according to memory size

 */

	ACTSIZE		= 40000,

	MEMSIZE		= 40000,

	NSTATES		= 2000,

	NTERMS		= 511,

	NPROD		= 1600,

	NNONTERM	= 600,

	TEMPSIZE	= 2000,

	CNAMSZ		= 10000,

	LSETSIZE	= 2400,

	WSETSIZE	= 350,

	NAMESIZE	= 50,

	NTYPES		= 63,

	ISIZE		= 400,

	PRIVATE		= 0xE000,	/* unicode private use */

	/* relationships which must hold:

		TBITSET ints must hold NTERMS+1 bits...

		WSETSIZE >= NNONTERM

		LSETSIZE >= NNONTERM

		TEMPSIZE >= NTERMS + NNONTERM + 1

		TEMPSIZE >= NSTATES

	*/

	NTBASE		= 010000,

	ERRCODE		= 8190,

	ACCEPTCODE	= 8191,

	NOASC		= 0,	/* no assoc. */

	LASC		= 1,	/* left assoc. */

	RASC		= 2,	/* right assoc. */

	BASC		= 3,	/* binary assoc. */

	/* flags for state generation */

	DONE		= 0,

	MUSTDO		= 1,

	MUSTLOOKAHEAD	= 2,

	/* flags for a rule having an action, and being reduced */

	ACTFLAG		= 04,

	REDFLAG		= 010,

	/* output parser flags */

	YYFLAG1		= -1000,

	/* parse tokens */

	IDENTIFIER	= PRIVATE,

	MARK,

	TERM,

	LEFT,

	RIGHT,

	BINARY,

	PREC,

	LCURLY,

	IDENTCOLON,

	NUMBER,

	START,

	TYPEDEF,

	TYPENAME,

	UNION,

	ENDFILE		= 0,

	EMPTY		= 1,

	WHOKNOWS	= 0,

	OK		= 1,

	NOMORE		= -1000,

};

	/* macros for getting associativity and precedence levels */

#define ASSOC(i)	((i)&03)

#define PLEVEL(i)	(((i)>>4)&077)

#define TYPE(i)		(((i)>>10)&077)

	/* macros for setting associativity and precedence levels */

#define SETASC(i,j)	i |= j

#define SETPLEV(i,j)	i |= (j<<4)

#define SETTYPE(i,j)	i |= (j<<10)

	/* looping macros */

#define TLOOP(i)	for(i=1; i<=ntokens; i++)

#define NTLOOP(i)	for(i=0; i<=nnonter; i++)

#define PLOOP(s,i)	for(i=s; i<nprod; i++)

#define SLOOP(i)	for(i=0; i<nstate; i++)

#define WSBUMP(x)	x++

#define WSLOOP(s,j)	for(j=s; j<cwp; j++)

#define ITMLOOP(i,p,q)	for(q=pstate[i+1], p=pstate[i]; p<q; p++)

#define SETLOOP(i)	for(i=0; i<tbitset; i++)

	/* command to clobber tempfiles after use */

#define	ZAPFILE(x)	if(x) remove(x)

	/* I/O descriptors */

Biobuf*	faction;	/* file for saving actions */

Biobuf*	fdefine;	/* file for #defines */

Biobuf*	fdebug;		/* y.debug for strings for debugging */

Biobuf*	ftable;		/* y.tab.c file */

Biobuf*	ftemp;		/* tempfile to pass 2 */

Biobuf*	finput;		/* input file */

Biobuf*	foutput;	/* y.output file */

	/* communication variables between various I/O routines */

char*	infile;			/* input file name */

int	numbval;		/* value of an input number */

char	tokname[NAMESIZE+UTFmax+1]; /* input token name, slop for runes and 0 */

	/* structure declarations */

typedef

struct

{

	int	lset[TBITSET];

} Lkset;

typedef

struct

{

	int*	pitem;

	Lkset*	look;

} Item;

typedef

struct

{

	char*	name;

	int	value;

} Symb;

typedef

struct

{

	int*	pitem;

	int	flag;

	Lkset	ws;

} Wset;

	/* storage of names */

char	cnames[CNAMSZ];		/* place where token and nonterminal names are stored */

int	cnamsz = CNAMSZ;	/* size of cnames */

char*	cnamp = cnames;		/* place where next name is to be put in */

int	ndefout = 4;		/* number of defined symbols output */

char*	tempname;

char*	actname;

char	ttempname[] = TEMPNAME;

char	tactname[] = ACTNAME;

char*	parser = PARSER;

char*	yydebug;

	/* storage of types */

int	ntypes;			/* number of types defined */

char*	typeset[NTYPES];	/* pointers to type tags */

	/* token information */

int	ntokens = 0 ;		/* number of tokens */

Symb	tokset[NTERMS];

int	toklev[NTERMS];		/* vector with the precedence of the terminals */

	/* nonterminal information */

int	nnonter = -1;		/* the number of nonterminals */

Symb	nontrst[NNONTERM];

int	start;			/* start symbol */

	/* assigned token type values */

int	extval = 0;

char*	ytabc = OFILE;	/* name of y.tab.c */

	/* grammar rule information */

int	mem0[MEMSIZE] ;		/* production storage */

int*	mem = mem0;

int	nprod = 1;		/* number of productions */

int*	prdptr[NPROD];		/* pointers to descriptions of productions */

int	levprd[NPROD];		/* precedence levels for the productions */

int	rlines[NPROD];		/* line number for this rule */

	/* state information */

int	nstate = 0;		/* number of states */

Item*	pstate[NSTATES+2];	/* pointers to the descriptions of the states */

int	tystate[NSTATES];	/* contains type information about the states */

int	defact[NSTATES];	/* the default actions of states */

int	tstates[NTERMS];	/* states generated by terminal gotos */

int	ntstates[NNONTERM]; 	/* states generated by nonterminal gotos */

int	mstates[NSTATES];	/* chain of overflows of term/nonterm generation lists  */

int	lastred; 		/* the number of the last reduction of a state */

	/* lookahead set information */

Lkset	lkst[LSETSIZE];

int	nolook;			/* flag to turn off lookahead computations */

int	tbitset;		/* size of lookahead sets */

int	nlset = 0;		/* next lookahead set index */

int	nolook = 0;		/* flag to suppress lookahead computations */

Lkset	clset;  		/* temporary storage for lookahead computations */

	/* working set information */

Wset	wsets[WSETSIZE];

Wset*	cwp;

	/* storage for action table */

int	amem[ACTSIZE];		/* action table storage */

int*	memp = amem;		/* next free action table position */

int	indgo[NSTATES];		/* index to the stored goto table */

	/* temporary vector, indexable by states, terms, or ntokens */

int	temp1[TEMPSIZE];	/* temporary storage, indexed by terms + ntokens or states */

int	lineno = 1;		/* current input line number */

int	fatfl = 1;  		/* if on, error is fatal */

int	nerrors = 0;		/* number of errors */

	/* statistics collection variables */

int	zzgoent;

int	zzgobest;

int	zzacent;

int	zzexcp;

int	zzclose;

int	zzrrconf;

int	zzsrconf;

int*	ggreed = lkst[0].lset;

int*	pgo = wsets[0].ws.lset;

int*	yypgo = &nontrst[0].value;

int	maxspr = 0;  		/* maximum spread of any entry */

int	maxoff = 0;  		/* maximum offset into a array */

int*	pmem = mem0;

int*	maxa;

int	nxdb = 0;

int	adb = 0;

	/* storage for information about the nonterminals */

int**	pres[NNONTERM+2];  	/* vector of pointers to productions yielding each nonterminal */

Lkset*	pfirst[NNONTERM+2];	/* vector of pointers to first sets for each nonterminal */

int	pempty[NNONTERM+1];	/* vector of nonterminals nontrivially deriving e */

	/* random stuff picked out from between functions */

int	indebug = 0;

Wset*	zzcwp = wsets;

int	zzgoent = 0;

int	zzgobest = 0;

int	zzacent = 0;

int	zzexcp = 0;

int	zzclose = 0;

int	zzsrconf = 0;

int*	zzmemsz = mem0;

int	zzrrconf = 0;

int	pidebug = 0;		/* debugging flag for putitem */

int	gsdebug = 0;

int	cldebug = 0;		/* debugging flag for closure */

int	pkdebug = 0;

int	g2debug = 0;

struct

{

	char*	name;

	long	value;

} resrv[] =

{

	"binary",	BINARY,

	"left",		LEFT,

	"nonassoc",	BINARY,

	"prec",		PREC,

	"right",	RIGHT,

	"start",	START,

	"term",		TERM,

	"token",	TERM,

	"type",		TYPEDEF,

	"union",	UNION,

	0,

};

	/* define functions */

void	main(int, char**);

void	others(void);

char*	chcopy(char*, char*);

char*	writem(int*);

char*	symnam(int);

void	summary(void);

void	error(char*, ...);

void	aryfil(int*, int, int);

int	setunion(int*, int*);

void	prlook(Lkset*);

void	cpres(void);

void	cpfir(void);

int	state(int);

void	putitem(int*, Lkset*);

void	cempty(void);

void	stagen(void);

void	closure(int);

Lkset*	flset(Lkset*);

void	cleantmp(void);

void	intr(void);

void	setup(int, char**);

void	finact(void);

int	defin(int, char*);

void	defout(int);

char*	cstash(char*);

long	gettok(void);

int	fdtype(int);

int	chfind(int, char*);

void	cpyunion(void);

void	cpycode(void);

int	skipcom(void);

void	cpyact(int);

void	openup(char*, int, int, int, char*);

void	output(void);

int	apack(int*, int);

void	go2out(void);

void	go2gen(int);

void	precftn(int, int, int);

void	wract(int);

void	wrstate(int);

void	warray(char*, int*, int);

void	hideprod(void);

void	callopt(void);

void	gin(int);

void	stin(int);

int	nxti(void);

void	osummary(void);

void	aoutput(void);

void	arout(char*, int*, int);

int	gtnm(void);

void

main(int argc, char *argv[])

{

	setup(argc, argv);	/* initialize and read productions */

	tbitset = NWORDS(ntokens);

	cpres();		/* make table of which productions yield a given nonterminal */

	cempty();		/* make a table of which nonterminals can match the empty string */

	cpfir();		/* make a table of firsts of nonterminals */

	stagen();		/* generate the states */

	output();		/* write the states and the tables */

	go2out();

	hideprod();

	summary();

	callopt();

	others();

	exits(0);

}

/*

 * put out other arrays, copy the parsers

 */

void

others(void)

{

	int c, i, j;

	finput = Bopen(parser, OREAD);

	if(finput == 0)

		error("cannot find parser %s", parser);

	warray("yyr1", levprd, nprod);

	aryfil(temp1, nprod, 0);

	PLOOP(1, i)

		temp1[i] = prdptr[i+1]-prdptr[i]-2;

	warray("yyr2", temp1, nprod);

	aryfil(temp1, nstate, -1000);

	TLOOP(i)

		for(j=tstates[i]; j!=0; j=mstates[j])

			temp1[j] = i;

	NTLOOP(i)

		for(j=ntstates[i]; j!=0; j=mstates[j])

			temp1[j] = -i;

	warray("yychk", temp1, nstate);

	warray("yydef", defact, nstate);

	/* put out token translation tables */

	/* table 1 has 0-256 */

	aryfil(temp1, 256, 0);

	c = 0;

	TLOOP(i) {

		j = tokset[i].value;

		if(j >= 0 && j < 256) {

			if(temp1[j]) {

				print("yacc bug -- cant have 2 different Ts with same value\n");

				print("	%s and %s\n", tokset[i].name, tokset[temp1[j]].name);

				nerrors++;

			}

			temp1[j] = i;

			if(j > c)

				c = j;

		}

	}

	warray("yytok1", temp1, c+1);

	/* table 2 has PRIVATE-PRIVATE+256 */

	aryfil(temp1, 256, 0);

	c = 0;

	TLOOP(i) {

		j = tokset[i].value - PRIVATE;

		if(j >= 0 && j < 256) {

			if(temp1[j]) {

				print("yacc bug -- cant have 2 different Ts with same value\n");

				print("	%s and %s\n", tokset[i].name, tokset[temp1[j]].name);

				nerrors++;

			}

			temp1[j] = i;

			if(j > c)

				c = j;

		}

	}

	warray("yytok2", temp1, c+1);

	/* table 3 has everything else */

	Bprint(ftable, "long	yytok3[] =\n{\n");

	c = 0;

	TLOOP(i) {

		j = tokset[i].value;

		if(j >= 0 && j < 256)

			continue;

		if(j >= PRIVATE && j < 256+PRIVATE)

			continue;

		Bprint(ftable, "%4d,%4d,", j, i);

		c++;

		if(c%5 == 0)

			Bprint(ftable, "\n");

	}

	Bprint(ftable, "%4d\n};\n", 0);

	/* copy parser text */

	while((c=Bgetrune(finput)) != Beof) {

		if(c == '$') {

			if((c = Bgetrune(finput)) != 'A')

				Bputrune(ftable, '$');

			else { /* copy actions */

				faction = Bopen(actname, OREAD);

				if(faction == 0)

					error("cannot reopen action tempfile");

				while((c=Bgetrune(faction)) != Beof)

					Bputrune(ftable, c);

				Bterm(faction);

				ZAPFILE(actname);

				c = Bgetrune(finput);

			}

		}

		Bputrune(ftable, c);

	}

	Bterm(ftable);

}

/*

 * copies string q into p, returning next free char ptr

 */

char*

chcopy(char* p, char* q)

{

	int c;

	while(c = *q) {

		if(c == '"')

			*p++ = '\\';

		*p++ = c;

		q++;

	}

	*p = 0;

	return p;

}

/*

 * creates output string for item pointed to by pp

 */

char*

writem(int *pp)

{

	int i,*p;

	static char sarr[ISIZE];

	char* q;

	for(p=pp; *p>0; p++)

		;

	p = prdptr[-*p];

	q = chcopy(sarr, nontrst[*p-NTBASE].name);

	q = chcopy(q, ": ");

	for(;;) {

		*q = ' ';

		p++;

		if(p == pp)

			*q = '.';

		q++;

		*q = '\0';

		i = *p;

		if(i <= 0)

			break;

		q = chcopy(q, symnam(i));

		if(q > &sarr[ISIZE-30])

			error("item too big");

	}

	/* an item calling for a reduction */

	i = *pp;

	if(i < 0 ) {

		q = chcopy(q, "    (");

		sprint(q, "%d)", -i);

	}

	return sarr;

}

/*

 * return a pointer to the name of symbol i

 */

char*

symnam(int i)

{

	char* cp;

	cp = (i >= NTBASE)? nontrst[i-NTBASE].name: tokset[i].name;

	if(*cp == ' ')

		cp++;

	return cp;

}

/*

 * output the summary on y.output

 */

void

summary(void)

{

	if(foutput != 0) {

		Bprint(foutput, "\n%d/%d terminals, %d/%d nonterminals\n",

			ntokens, NTERMS, nnonter, NNONTERM);

		Bprint(foutput, "%d/%d grammar rules, %d/%d states\n",

			nprod, NPROD, nstate, NSTATES);

		Bprint(foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n",

			zzsrconf, zzrrconf);

		Bprint(foutput, "%d/%d working sets used\n",

			(int)(zzcwp-wsets), WSETSIZE);

		Bprint(foutput, "memory: states,etc. %d/%d, parser %d/%d\n",

			(int)(zzmemsz-mem0), MEMSIZE, (int)(memp-amem), ACTSIZE);

		Bprint(foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE);

		Bprint(foutput, "%d extra closures\n", zzclose - 2*nstate);

		Bprint(foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp);

		Bprint(foutput, "%d goto entries\n", zzgoent);

		Bprint(foutput, "%d entries saved by goto default\n", zzgobest);

	}

	if(zzsrconf != 0 || zzrrconf != 0) {

		print("\nconflicts: ");

		if(zzsrconf)

			print("%d shift/reduce", zzsrconf);

		if(zzsrconf && zzrrconf)

			print(", ");

		if(zzrrconf)

			print("%d reduce/reduce", zzrrconf);

		print("\n");

	}

	if(ftemp != 0) {

		Bterm(ftemp);

		ftemp = 0;

	}

	if(fdefine != 0) {

		Bterm(fdefine);

		fdefine = 0;

	}

}

/*

 * write out error comment -- NEEDS WORK

 */

void

error(char *s, ...)

{

	nerrors++;

	fprint(2, "\n fatal error:");

	fprint(2, s, (&s)[1]);

	fprint(2, ", %s:%d\n", infile, lineno);

	if(!fatfl)

		return;

	summary();

	cleantmp();

	exits("error");

}

/*

 * set elements 0 through n-1 to c

 */

void

aryfil(int *v, int n, int c)

{

	int i;

	for(i=0; i<n; i++)

		v[i] = c;

}

/*

 * set a to the union of a and b

 * return 1 if b is not a subset of a, 0 otherwise

 */

int

setunion(int *a, int *b)

{

	int i, x, sub;

	sub = 0;

	SETLOOP(i) {

		x = *a;

		*a |= *b;

		if(*a != x)

			sub = 1;

		a++;

		b++;

	}

	return sub;

}

void

prlook(Lkset* p)

{

	int j, *pp;

	pp = p->lset;

	if(pp == 0)

		Bprint(foutput, "\tNULL");

	else {

		Bprint(foutput, " { ");

		TLOOP(j)

			if(BIT(pp,j))

				Bprint(foutput, "%s ", symnam(j));

		Bprint(foutput, "}");

	}

}

/*

 * compute an array with the beginnings of  productions yielding given nonterminals

 * The array pres points to these lists

 * the array pyield has the lists: the total size is only NPROD+1

 */

void

cpres(void)

{

	int c, j, i, **pmem;

	static int *pyield[NPROD];

	pmem = pyield;

	NTLOOP(i) {

		c = i+NTBASE;

		pres[i] = pmem;

		fatfl = 0;  	/* make undefined  symbols  nonfatal */

		PLOOP(0, j)

			if(*prdptr[j] == c)

				*pmem++ =  prdptr[j]+1;

		if(pres[i] == pmem)

			error("nonterminal %s not defined!", nontrst[i].name);

	}

	pres[i] = pmem;

	fatfl = 1;

	if(nerrors) {

		summary();

		cleantmp();

		exits("error");

	}

	if(pmem != &pyield[nprod])

		error("internal Yacc error: pyield %d", pmem-&pyield[nprod]);

}

/*

 * compute an array with the first of nonterminals

 */

void

cpfir(void)

{

	int *p, **s, i, **t, ch, changes;

	zzcwp = &wsets[nnonter];

	NTLOOP(i) {

		aryfil(wsets[i].ws.lset, tbitset, 0);

		t = pres[i+1];

		/* initially fill the sets */

		for(s=pres[i]; s<t; ++s)

			for(p = *s; (ch = *p) > 0; ++p) {

				if(ch < NTBASE) {

					SETBIT(wsets[i].ws.lset, ch);

					break;

				}

				if(!pempty[ch-NTBASE])

					break;

			}

	}

	/* now, reflect transitivity */

	changes = 1;

	while(changes) {

		changes = 0;

		NTLOOP(i) {

			t = pres[i+1];

			for(s = pres[i]; s < t; ++s)

				for(p = *s; (ch = (*p-NTBASE)) >= 0; ++p) {

					changes |= setunion(wsets[i].ws.lset, wsets[ch].ws.lset);

					if(!pempty[ch])

						break;

				}

		}

	}

	NTLOOP(i)

		pfirst[i] = flset(&wsets[i].ws);

	if(!indebug)

		return;

	if(foutput != 0)

		NTLOOP(i) {

			Bprint(foutput, "\n%s: ", nontrst[i].name);

			prlook(pfirst[i]);

			Bprint(foutput, " %d\n", pempty[i]);

		}

}

/*

 * sorts last state,and sees if it equals earlier ones. returns state number

 */

int

state(int c)

{

	Item *p1, *p2, *k, *l, *q1, *q2;

	int size1, size2, i;

	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;

				Lkset *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;