/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 1990 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/* Copyright (c) 1988 AT&T */
/* All Rights Reserved */

/*	from OpenSolaris "y1.c	6.27	05/06/08 SMI"	*/

/*
 * Portions Copyright (c) 2005 Gunnar Ritter, Freiburg i. Br., Germany
 *
 * Sccsid @(#)y1.c	1.7 (gritter) 11/26/05
 */

#include "dextern"
#include <sys/param.h>
#include <errno.h>
#include <unistd.h>
#include <locale.h>
#include <stdarg.h>	/* For error() */
#include <wchar.h>

static void mktbls(void);
static void others(void);
static void summary(void);
static wchar_t *chcopy(wchar_t *, wchar_t *);
static int setunion(int *, int *);
static void prlook(LOOKSETS *);
static void cpres(void);
static void cpfir(void);
static void cempty(void);
static void stagen(void);
static LOOKSETS *flset(LOOKSETS *);
static void exp_lkst(void);
static void exp_wsets(void);
static void exp_states(void);
static void exp_psmem(void);

	/* lookahead computations */

int TBITSET;
static int tbitset;	/* size of lookahead sets */
LOOKSETS *lkst;
static int lsetsize;

static int nlset = 0; 	/* next lookahead set index */
int nolook = 0; 	/* flag to suppress lookahead computations */
static LOOKSETS clset;  /* temporary storage for lookahead computations */

static ITEM *psmem, *zzmemsz;
static int new_pstsize = PSTSIZE;

	/* working set computations */

WSET *wsets;
int cwp;
static int wsetsz = 0;		/* number of WSET items in wsets block */

	/* state information */

int nstate = 0;			/* number of states */
static int nstatesz = NSTATES;	/* number of state space allocated	*/
ITEM **pstate;			/* ptr to descriptions of the states	*/
int *tystate;			/* contains type info about the states	*/
int *indgo;			/* index to the stored goto table	*/
static int *tmp_lset;
static int *tstates;		/* states generated by terminal gotos	*/
static int *ntstates;		/* states generated by non-term gotos	*/
static int *mstates;		/* chain of overflows of term/nonterm	*/
				/* generation lists			*/

	/* storage for the actions in the parser */

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

	/* other storage areas */

int *temp1;		/* temp storate, indexed by terms+ntokens or states */
int lineno = 0;		/* current input line number */
int size;
static int fatfl = 1;  	/* if on, error is fatal */
static int nerrors = 0;	/* number of errors */

	/* storage for information about the nonterminals */

static int ***pres;		/* vector of pointers to productions	*/
				/* yielding each nonterminal		*/
static LOOKSETS **pfirst;	/* vector of pointers to first sets for	*/
				/* each nonterminal			*/
static int *pempty;		/* vector of nonterminals nontrivially	*/
				/* deriving e				*/
extern int nprodsz;

static char *sav_argv0;
char run_directory[MAXPATHLEN];
char current_work_directory[MAXPATHLEN];

int 
main(int argc, char *argv[])
{
	setlocale(LC_CTYPE, "");

	sav_argv0 = argv[0];
	setup(argc, argv); 		/* initialize and read productions */
	TBITSET = NWORDS(ntoksz*LKFACTOR);
	tbitset = NWORDS(ntokens*LKFACTOR);
	mktbls();
	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();
	return 0;
}


static void 
mktbls(void)
{
	int i;

	size = ntoksz + nnontersz +1;
	if (size < nstatesz)
		size = nstatesz;
	if (size < new_memsize)
		size = new_memsize;

	amem = malloc(sizeof (int) * new_actsize);
	psmem = malloc(sizeof (ITEM) * new_pstsize);
	if ((psmem == NULL) || (amem == NULL))
		error("couldn't allocate initial table");
	zzmemsz = psmem;
	memp = amem;

	/*
	 * For lkst
	 */
#define	INIT_LSIZE	nnontersz*LKFACTOR
	tmp_lset = calloc((size_t)(TBITSET * (INIT_LSIZE+1)), sizeof (int));
	if (tmp_lset == NULL)
		error("could not allocate lookset array");
	lkst = malloc(sizeof (LOOKSETS) * (INIT_LSIZE + 1));
	for (i = 0; i <= INIT_LSIZE; ++i)
		lkst[i].lset = tmp_lset + TBITSET * i;
	tmp_lset = NULL;

	/*
	 * For wsets
	 */
	tmp_lset = calloc((size_t)(TBITSET * (nnontersz+1)), sizeof (int));
	if (tmp_lset == NULL)
		error("could not allocate lookset array");
	wsets = (WSET *) malloc(sizeof (WSET) * (nnontersz + 1));
	for (i = 0; i <= nnontersz; ++i)
		wsets[i].ws.lset = tmp_lset + TBITSET * i;
	tmp_lset = NULL;

	clset.lset = malloc(sizeof (int)*TBITSET);
	tstates = malloc(sizeof (int)*(ntoksz + 1));
	ntstates = malloc(sizeof (int)*(nnontersz + 1));
	temp1 = malloc(sizeof (int)*size);
	pres = malloc(sizeof (int **)*(nnontersz + 2));
	pfirst = malloc(sizeof (LOOKSETS *)*(nnontersz + 2));
	pempty = malloc(sizeof (int)*(nnontersz + 1));

	pstate = malloc(sizeof (ITEM *)*(nstatesz+2));
	tystate = malloc(sizeof (int)*nstatesz);
	indgo = malloc(sizeof (int)*nstatesz);
	mstates = malloc(sizeof (int)*nstatesz);
	defact = malloc(sizeof (int)*nstatesz);

	if ((lkst == NULL) || (wsets == NULL) || (tstates == NULL) ||
	    (ntstates == NULL) || (temp1 == NULL) || (pres == NULL) ||
	    (pfirst == NULL) || (pempty == NULL) || (pstate == NULL) ||
	    (tystate == NULL) || (indgo == NULL) || (mstates == NULL) ||
	    (defact == NULL) || (clset.lset == NULL))
			error("cannot allocate tables in mktbls()");

	aryfil(ntstates, nnontersz+1, 0);
	aryfil(tstates, ntoksz+1, 0);
	wsetsz = nnontersz + 1;
	lsetsize = INIT_LSIZE + 1;
}

/* put out other arrays, copy the parsers */
static void 
others(void)
{
	extern int gen_lines;
	register int c, i, j;
	int tmpline;

	/* This  routine has been "stolen" from the driver */
	if (parser == NULL)
		parser = PARSER;

	finput = fopen(parser, "r");
	if (finput == NULL)
		error("cannot find parser %s", parser);

	warray(L"yyr1", levprd, nprod);

	aryfil(temp1, nprod, 0);
					/* had_act[i] is either 1 or 0 */
	PLOOP(1, i)
		temp1[i] = ((prdptr[i+1] - prdptr[i]-2) << 1) | had_act[i];
	warray(L"yyr2", temp1, nprod);

	aryfil(temp1, nstate, -10000000);
	TLOOP(i)
		for (j = tstates[i]; j != 0; j = mstates[j])
			temp1[j] = tokset[i].value;
	NTLOOP(i)
		for (j = ntstates[i]; j != 0; j = mstates[j])
			temp1[j] = -i;
	warray(L"yychk", temp1, nstate);

	warray(L"yydef", defact, nstate);

	if ((fdebug = fopen(DEBUGNAME, "r")) == NULL)
		error("cannot open yacc.debug");
	while ((c = getwc(fdebug)) != EOF)
		putwc(c, ftable);
	fclose(fdebug);
	ZAPFILE(DEBUGNAME);

	if (gen_lines)
		fprintf(ftable, "# line\t1 \"%s\"\n", parser);
	tmpline = 1;
	/* copy parser text */
	while ((c = getwc(finput)) != EOF) {
		if (c == '\n')
			tmpline++;
		if (c == L'$') {
			if ((c = getwc(finput)) != L'A')
				putwc(L'$', ftable);
			else { /* copy actions */
				tmpline++;
				faction = fopen(ACTNAME, "r");
				if (faction == NULL)
					error("cannot open action tempfile");
				while ((c = getwc(faction)) != EOF)
					putwc(c, ftable);
				fclose(faction);
				if (gen_lines)
					fprintf(ftable,
						"\n# line\t%d \"%s\"",
						tmpline,
						parser);
				ZAPFILE(ACTNAME);
				c = getwc(finput);
			}
		}
		putwc(c, ftable);
	}
	fclose(ftable);
}


/* copies string q into p, returning next free char ptr */
static wchar_t *
chcopy(wchar_t *p, wchar_t *q)
{
	while (*p = *q++)
		++p;
	return (p);
}

#define	ISIZE 400
/* creates output string for item pointed to by pp */
wchar_t *
writem(int *pp)
{
	int i, *p;
	static int isize = ISIZE;
	static wchar_t *sarr = NULL;
	wchar_t *q;

	if (sarr == NULL) {
		sarr = malloc(sizeof (wchar_t) * isize);
		if (sarr == NULL)
			error("could not allocate output string array");
		for (i = 0; i < isize; ++i)
			sarr[i] = L' ';
	}
	for (p = pp; *p > 0; ++p) /* EMPTY */;
	p = prdptr[-*p];
	q = chcopy(sarr, nontrst[*p-NTBASE].name);
	q = chcopy(q, L" : ");

	for (;;) {
		*q++ = ++p == pp ? L'_' : L' ';
		*q = 0;
		if ((i = *p) <= 0)
			break;
		q = chcopy(q, symnam(i));
		while (q > &sarr[isize-30]) {
			static wchar_t *sarrbase;

			sarrbase = sarr;
			isize += ISIZE;
			sarr = realloc(sarr, sizeof (*sarr) * isize);
			if (sarr == NULL)
				error("cannot expand sarr arrays");
			q = q - sarrbase + sarr;
		}
	}

	/* an item calling for a reduction */
	if ((i = *pp) < 0) {
		q = chcopy(q, L"    (");
		swprintf(q, q + isize - sarr, L"%d)", -i);
	}
	return (sarr);
}

/* return a pointer to the name of symbol i */
wchar_t *
symnam(int i)
{
	wchar_t *cp;

	cp = (i >= NTBASE) ? nontrst[i-NTBASE].name : tokset[i].name;
	if (*cp == L' ')
		++cp;
	return (cp);
}

static int zzcwp = 0;
static int zzclose = 0;
int zzgoent = 0;
int zzgobest = 0;
int zzacent = 0;
int zzexcp = 0;
int zzsrconf = 0;
int zzrrconf = 0;

/* output the summary on the tty */
static void 
summary(void)
{
	if (foutput != NULL) {
		fprintf(foutput,
			"\n%d/%d terminals, %d/%d nonterminals\n",
			ntokens, ntoksz, nnonter, nnontersz);
		fprintf(foutput,
			"%d/%d grammar rules, %d/%d states\n",
			nprod, nprodsz, nstate, nstatesz);
		fprintf(foutput,
		"%d shift/reduce, %d reduce/reduce conflicts reported\n",
			zzsrconf, zzrrconf);
		fprintf(foutput,
			"%d/%d working sets used\n", zzcwp, wsetsz);
		fprintf(foutput,
			"memory: states,etc. %d/%d, parser %d/%d\n",
			mem-tracemem, new_memsize, memp-amem, new_actsize);
		fprintf(foutput,
			"%d/%d distinct lookahead sets\n", nlset, lsetsize);
		fprintf(foutput,
			"%d extra closures\n", zzclose - 2*nstate);
		fprintf(foutput,
			"%d shift entries, %d exceptions\n", zzacent, zzexcp);
		fprintf(foutput,
			"%d goto entries\n", zzgoent);
		fprintf(foutput,
			"%d entries saved by goto default\n", zzgobest);
	}
	if (zzsrconf != 0 || zzrrconf != 0) {
		fprintf(stderr, "\nconflicts: ");
		if (zzsrconf)
			fprintf(stderr, "%d shift/reduce", zzsrconf);
		if (zzsrconf && zzrrconf)
			fprintf(stderr, ", ");
		if (zzrrconf)
			fprintf(stderr, "%d reduce/reduce", zzrrconf);
		fprintf(stderr, "\n");
	}

	if (ftemp != NULL)
		fclose(ftemp);
	if (fdefine != NULL)
		fclose(fdefine);
}

/* write out error comment */
void
error(char *s, ...)
{
	extern char *infile;
	va_list	ap;

	va_start(ap, s);

	++nerrors;
	if (!lineno)
		fprintf(stderr, "command line: fatal: ");
	else {
		fprintf(stderr, "\"%s\", ", infile);
		fprintf(stderr, "line %d: fatal: ", lineno);
	}
	vfprintf(stderr, s, ap);
	fprintf(stderr, "\n");
	va_end(ap);
	if (!fatfl)
		return;
	summary();
	exit(1);
}

/*
 * Print out a warning message.
 */
void
warning(int flag, char *s, ...)
{
	extern char *infile;
	va_list	ap;
	va_start(ap, s);

	fprintf(stderr, "\"%s\", ", infile);
	/*
	 * If flag, print lineno as well.
	 */
	if (flag == 0)
		fprintf(stderr, "warning: ");
	else
		fprintf(stderr, "line %d: warning: ", lineno);
	vfprintf(stderr, s, ap);
	fprintf(stderr, "\n");
	va_end(ap);
}

/* 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 */
static int
setunion(register int *a, register int *b)
{
	register int i, x, sub;

	sub = 0;
	SETLOOP(i) {
		*a = (x = *a) | *b++;
		if (*a++ != x)
			sub = 1;
	}
	return (sub);
}

static void 
prlook(LOOKSETS *p)
{
	register int j, *pp;
	pp = p->lset;
	if (pp == 0)
		fprintf(foutput, "\tNULL");
	else {
		fprintf(foutput, " { ");
		TLOOP(j) {
			if (BIT(pp, j))
				fprintf(foutput,  "%ls ", symnam(j));
		}
		fprintf(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
 */
static void 
cpres(void)
{
	register int **ptrpy;
	int **pyield;
	register int c, j, i;

	/*
	 * 2/29/88 -
	 * nprodsz is the size of the tables describing the productions.
	 * Normally this will be NPROD unless the production tables have
	 * been expanded, in which case the tables will be NPROD * N(where
	 * N is the number of times the tables had to be expanded.)
	 */
	if ((pyield = malloc(sizeof (int *) * nprodsz)) == NULL)
		error("cannot allocate space for pyield array");

	ptrpy = pyield;

	NTLOOP(i) {
		c = i+NTBASE;
		pres[i] = ptrpy;
		fatfl = 0;  /* make undefined  symbols  nonfatal */
		PLOOP(0, j) {
			if (*prdptr[j] == c)  	/* linear search for all c's */
				*ptrpy++ =  prdptr[j] + 1;
		}
		if (pres[i] == ptrpy) { 		/* c not found */
			error("undefined nonterminal: %ls", nontrst[i].name);
		}
	}
	pres[i] = ptrpy;
	fatfl = 1;
	if (nerrors) {
		summary();
		exit(1);
	}
	if (ptrpy != &pyield[nprod])
		error("internal Yacc error: pyield %d", ptrpy-&pyield[nprod]);
}

static int indebug = 0;
/* compute an array with the first of nonterminals */
static void 
cpfir(void)
{
	register int *p, **s, i, **t, ch, changes;

	zzcwp = 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) {
			/* check if ch is non-terminal */
			for (p = *s; (ch = *p) > 0; ++p) {
				if (ch < NTBASE) { 	/* should be token */
					SETBIT(wsets[i].ws.lset, ch);
					break;
				} else 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 != NULL)) {
		NTLOOP(i) {
			fprintf(foutput, "\n%ls: ", nontrst[i].name);
			prlook(pfirst[i]);
			fprintf(foutput, " %d\n", pempty[i]);
		}
	}
}

/* sorts last state,and sees if it equals earlier ones. returns state number */
int
state(int c)
{
	int size1, size2;
	register int i;
	ITEM *p1, *p2, *k, *l, *q1, *q2;
	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;
				LOOKSETS *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 >= nstatesz)
		exp_states();
	if (c >= NTBASE) {
		mstates[nstate] = ntstates[c - NTBASE];
		ntstates[c - NTBASE] = nstate;
	} else {
		mstates[nstate] = tstates[c];
		tstates[c] = nstate;
	}
	tystate[nstate] = MUSTDO;
	return (nstate++);
}

static int pidebug = 0;

void 
putitem(int *ptr, LOOKSETS *lptr)
{
	register ITEM *j;

	if (pidebug && (foutput != NULL))
		fprintf(foutput,
			"putitem(%ls), state %d\n", writem(ptr), nstate);
	j = pstate[nstate+1];
	j->pitem = ptr;
	if (!nolook)
		j->look = flset(lptr);
	pstate[nstate+1] = ++j;
	if (j > zzmemsz) {
		zzmemsz = j;
		if (zzmemsz >=  &psmem[new_pstsize])
			exp_psmem();
			/* error("out of state space"); */
	}
}

/*
 * mark nonterminals which derive the empty string
 * also, look for nonterminals which don't derive any token strings
 */
static void 
cempty(void)
{
#define	EMPTY 1
#define	WHOKNOWS 0
#define	OK 1
	register int i, *p;

	/*
	 * first, use the array pempty to detect productions
	 * that can never be reduced
	 */

	/* set pempty to WHONOWS */
	aryfil(pempty, nnonter+1, WHOKNOWS);

	/*
	 * now, look at productions, marking nonterminals which
	 * derive something
	 */
	more:
	PLOOP(0, i) {
		if (pempty[*prdptr[i] - NTBASE])
			continue;
		for (p = prdptr[i] + 1; *p >= 0; ++p)
			if (*p >= NTBASE && pempty[*p-NTBASE] == WHOKNOWS)
				break;
		if (*p < 0) { /* production can be derived */
			pempty[*prdptr[i]-NTBASE] = OK;
			goto more;
		}
	}

	/* now, look at the nonterminals, to see if they are all OK */

	NTLOOP(i) {
		/*
		 * the added production rises or falls as the
		 * start symbol ...
		 */
		if (i == 0)
			continue;
		if (pempty[i] != OK) {
			fatfl = 0;
			error("nonterminal %ls never derives any token string",
			nontrst[i].name);
		}
	}

	if (nerrors) {
		summary();
		exit(1);
	}

	/*
	 * now, compute the pempty array, to see which nonterminals
	 * derive the empty string
	 */

	/* set pempty to WHOKNOWS */

	aryfil(pempty, nnonter+1, WHOKNOWS);

	/* loop as long as we keep finding empty nonterminals */

again:
	PLOOP(1, i) {
		/* not known to be empty */
		if (pempty[*prdptr[i]-NTBASE] == WHOKNOWS) {
			for (p = prdptr[i]+1;
				*p >= NTBASE && pempty[*p-NTBASE] == EMPTY;
				++p);
			/* we have a nontrivially empty nonterminal */
			if (*p < 0) {
				pempty[*prdptr[i]-NTBASE] = EMPTY;
				goto again; /* got one ... try for another */
			}
		}
	}
}

/* generate the states */
static int gsdebug = 0;
static void 
stagen(void)
{
	int i, j;
	register int c;
	register WSET *p, *q;

	/* initialize */

	nstate = 0;

	pstate[0] = pstate[1] = psmem;
	aryfil(clset.lset, tbitset, 0);
	putitem(prdptr[0] + 1, &clset);
	tystate[0] = MUSTDO;
	nstate = 1;
	pstate[2] = pstate[1];

	aryfil(amem, new_actsize, 0);

	/* now, the main state generation loop */

	more:
	SLOOP(i) {
		if (tystate[i] != MUSTDO)
			continue;
		tystate[i] = DONE;
		aryfil(temp1, nnonter + 1, 0);
		/* take state i, close it, and do gotos */
		closure(i);
		WSLOOP(wsets, p) { /* generate goto's */
			if (p->flag)
				continue;
			p->flag = 1;
			c = *(p->pitem);
			if (c <= 1) {
				if (pstate[i+1]-pstate[i] <= p-wsets)
					tystate[i] = MUSTLOOKAHEAD;
				continue;
			}
			/* do a goto on c */
			WSLOOP(p, q) {
				/* this item contributes to the goto */
				if (c == *(q->pitem)) {
					putitem(q->pitem + 1, &q->ws);
					q->flag = 1;
				}
			}
			if (c < NTBASE)
				state(c);  /* register new state */
			else temp1[c-NTBASE] = state(c);
		}
		if (gsdebug && (foutput != NULL)) {
			fprintf(foutput,  "%d: ", i);
			NTLOOP(j) {
				if (temp1[j])
					fprintf(foutput,
						"%ls %d, ", nontrst[j].name,
						temp1[j]);
			}
			fprintf(foutput, "\n");
		}
		indgo[i] = apack(&temp1[1], nnonter - 1) - 1;
		goto more; /* we have done one goto; do some more */
	}
	/* no more to do... stop */
}

/* generate the closure of state i */
static int cldebug = 0; /* debugging flag for closure */
void 
closure(int i)
{
	int c, ch, work, k;
	register WSET *u, *v;
	int *pi;
	int **s, **t;
	ITEM *q;
	register ITEM *p;
	int idx1 = 0;

	++zzclose;

	/* first, copy kernel of state i to wsets */
	cwp = 0;
	ITMLOOP(i, p, q) {
		wsets[cwp].pitem = p->pitem;
		wsets[cwp].flag = 1;    /* this item must get closed */
		SETLOOP(k)
			wsets[cwp].ws.lset[k] = p->look->lset[k];
		WSBUMP(cwp);
	}

	/* now, go through the loop, closing each item */

	work = 1;
	while (work) {
		work = 0;
		/*
		 * WSLOOP(wsets, u) {
		 */
		for (idx1 = 0; idx1 < cwp; idx1++) {
			u = &wsets[idx1];
			if (u->flag == 0)
				continue;
			c = *(u->pitem);  /* dot is before c */
			if (c < NTBASE) {
				u->flag = 0;
				/*
				 * only interesting case is where . is
				 * before nonterminal
				 */
				continue;
			}

			/* compute the lookahead */
			aryfil(clset.lset, tbitset, 0);

			/* find items involving c */

			WSLOOP(u, v) {
				if (v->flag == 1 && *(pi = v->pitem) == c) {
					v->flag = 0;
					if (nolook)
						continue;
					while ((ch = *++pi) > 0) {
						/* terminal symbol */
						if (ch < NTBASE) {
							SETBIT(clset.lset, ch);
							break;
						}
						/* nonterminal symbol */
						setunion(clset.lset,
						pfirst[ch-NTBASE]->lset);
						if (!pempty[ch-NTBASE])
							break;
					}
					if (ch <= 0)
						setunion(clset.lset,
								v->ws.lset);
				}
			}

			/*  now loop over productions derived from c */

			c -= NTBASE; /* c is now nonterminal number */

			t = pres[c+1];
			for (s = pres[c]; s < t; ++s) {
				/* put these items into the closure */
				WSLOOP(wsets, v) { /* is the item there */
					/* yes, it is there */
					if (v->pitem == *s) {
						if (nolook)
							goto nexts;
						if (setunion(v->ws.lset,
							clset.lset))
							v->flag = work = 1;
						goto nexts;
					}
				}

				/*  not there; make a new entry */
				if (cwp + 1 >= wsetsz)
					exp_wsets();

				wsets[cwp].pitem = *s;
				wsets[cwp].flag = 1;
				if (!nolook) {
					work = 1;
					SETLOOP(k)
						wsets[cwp].ws.lset[k] =
							clset.lset[k];
				}
				WSBUMP(cwp);
				nexts:;
			}
		}
	}

	/* have computed closure; flags are reset; return */

	if (&wsets[cwp] > &wsets[zzcwp])
		zzcwp = cwp;
	if (cldebug && (foutput != NULL)) {
		fprintf(foutput, "\nState %d, nolook = %d\n", i, nolook);
		WSLOOP(wsets, u) {
			if (u->flag)
				fprintf(foutput, "flag set!\n");
			u->flag = 0;
			fprintf(foutput, "\t%ls", writem(u->pitem));
			prlook(&u->ws);
			fprintf(foutput,  "\n");
		}
	}
}

static LOOKSETS *
flset(LOOKSETS *p)
{
	/* decide if the lookahead set pointed to by p is known */
	/* return pointer to a perminent location for the set */

	int j, *w;
	register int *u, *v;
	register LOOKSETS *q;

	for (q = &lkst[nlset]; q-- > lkst; ) {
		u = p->lset;
		v = q->lset;
		w = & v[tbitset];
		while (v < w)
			if (*u++ != *v++)
				goto more;
		/* we have matched */
		return (q);
		more:;
	}
	/* add a new one */
	q = &lkst[nlset++];
	if (nlset >= lsetsize) {
		exp_lkst();
		q = &lkst[nlset++];
	}
	SETLOOP(j) q->lset[j] = p->lset[j];
	return (q);
}

static void 
exp_lkst(void)
{
	int i, j;
	static LOOKSETS *lookbase;

	lookbase = lkst;
	lsetsize += LSETSIZE;
	tmp_lset = calloc(TBITSET * (lsetsize-LSETSIZE), sizeof (int));
	if (tmp_lset == NULL)
		error("could not expand lookset array");
	lkst = realloc(lkst, sizeof (LOOKSETS) * lsetsize);
	for (i = lsetsize-LSETSIZE, j = 0; i < lsetsize; ++i, ++j)
		lkst[i].lset = tmp_lset + TBITSET * j;
	tmp_lset = NULL;
	if (lkst == NULL)
		error("could not expand lookahead sets");
	for (i = 0; i <= nnonter; ++i)
		pfirst[i] = pfirst[i] - lookbase + lkst;
	for (i = 0; i <= nstate+1; ++i) {
		if (psmem[i].look)
			psmem[i].look = psmem[i].look - lookbase + lkst;
		if (pstate[i]->look)
			pstate[i]->look = pstate[i]->look - lookbase + lkst;
	}
}

static void 
exp_wsets(void)
{
	int i, j;

	wsetsz += WSETSIZE;
	tmp_lset = calloc(TBITSET * (wsetsz-WSETSIZE), sizeof (int));
	if (tmp_lset == NULL)
		error("could not expand lookset array");
	wsets = realloc(wsets, sizeof (WSET) * wsetsz);
	for (i = wsetsz-WSETSIZE, j = 0; i < wsetsz; ++i, ++j)
		wsets[i].ws.lset = tmp_lset + TBITSET * j;
	tmp_lset = NULL;
	if (wsets == NULL)
		error("could not expand working sets");
}

static void 
exp_states(void)
{
	nstatesz += NSTATES;

	pstate = realloc(pstate, sizeof (ITEM *)*(nstatesz+2));
	mstates = realloc(mstates, sizeof (int)*nstatesz);
	defact = realloc(defact, sizeof (int)*nstatesz);
	tystate = realloc(tystate, sizeof (int)*nstatesz);
	indgo = realloc(indgo, sizeof (int)*nstatesz);

	if ((*pstate == NULL) || (tystate == NULL) || (defact == NULL) ||
		(indgo == NULL) || (mstates == NULL))
		error("cannot expand table of states");
}

static void 
exp_psmem(void)
{
	int i;

	new_pstsize += PSTSIZE;
	psmem = realloc(psmem, sizeof (ITEM) * new_pstsize);
	if (psmem == NULL)
		error("cannot expand pstate memory");

	zzmemsz = zzmemsz - pstate[0] + psmem;
	for (i = 1; i <= nstate+1; ++i)
		pstate[i] = pstate[i] - pstate[0] + psmem;
	pstate[0] = psmem;
}
