hbase

y1.c (24864B)

---

 /*
  * 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;
 }