xref: /illumos-gate/usr/src/cmd/sgs/yacc/common/y1.c (revision caeaa75185132c7efab72ba0c9e7256bae1b9b95)

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (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 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

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

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

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;

int
main(int argc, char *argv[])
{
	(void) setlocale(LC_ALL, "");
#if !defined(TEXT_DOMAIN)	/* Should be defined by cc -D */
#define	TEXT_DOMAIN "SYS_TEST"	/* Use this only if it weren't */
#endif
	(void) textdomain(TEXT_DOMAIN);

	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 = (int *) malloc(sizeof (int) * new_actsize);
	psmem = (ITEM *) malloc(sizeof (ITEM) * new_pstsize);
	if ((psmem == NULL) || (amem == NULL))
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	This error happens when yacc could not allocate
 *	initial memory to be used for internal tables.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
		error(gettext(
		"couldn't allocate initial table"));
	zzmemsz = psmem;
	memp = amem;

	/*
	 * For lkst
	 */
#define	INIT_LSIZE	nnontersz * LKFACTOR

	tmp_lset = (int *)
	    calloc((size_t)(TBITSET * (INIT_LSIZE+1)), sizeof (int));
	if (tmp_lset == NULL)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	Yacc could not allocate memory for table named lookset.
 *	Do not translate 'lookset'.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
		error(gettext(
		"could not allocate lookset array"));
	lkst = (LOOKSETS *) 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 = (int *)
	    calloc((size_t)(TBITSET * (nnontersz+1)), sizeof (int));
	if (tmp_lset == NULL)
		error(gettext(
		"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 = (int *)malloc(sizeof (int)*TBITSET);
	tstates = (int *)malloc(sizeof (int)*(ntoksz + 1));
	ntstates = (int *)malloc(sizeof (int)*(nnontersz + 1));
	temp1 = (int *)malloc(sizeof (int)*size);
	pres = (int ***)malloc(sizeof (int **)*(nnontersz + 2));
	pfirst = (LOOKSETS **)malloc(sizeof (LOOKSETS *)*(nnontersz + 2));
	pempty = (int *)malloc(sizeof (int)*(nnontersz + 1));

	pstate = (ITEM **)malloc(sizeof (ITEM *)*(nstatesz+2));
	tystate = (int *)malloc(sizeof (int)*nstatesz);
	indgo = (int *)malloc(sizeof (int)*nstatesz);
	mstates = (int *)malloc(sizeof (int)*nstatesz);
	defact = (int *)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))
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	Do not translate mktbls(). It is a function name.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
			error(gettext(
			"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;
	int c, i, j;
	int tmpline;

	finput = fopen(parser, "r");
	if (finput == NULL)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	This error message is issued when yacc can not find
 *	the parser to be copied.
 */
		error(gettext(
		"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)
		(void) putwc(c, ftable);
	(void) fclose(fdebug);
	ZAPFILE(DEBUGNAME);

	if (gen_lines)
		(void) 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')
				(void) putwc(L'$', ftable);
			else { /* copy actions */
				tmpline++;
				faction = fopen(ACTNAME, "r");
				if (faction == NULL)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	This error is issued when yacc can not open a
 *	temporary file to be used. You do not need to
 *	use the word 'tempfile'. You can translate it to
 *	mean 'temporary file'.
 */
					error(gettext(
					"cannot open action tempfile"));
				while ((c = getwc(faction)) != EOF)
					(void) putwc(c, ftable);
				(void) fclose(faction);
				if (gen_lines)
					(void) fprintf(ftable,
					    "\n# line\t%d \"%s\"",
					    tmpline,
					    parser);
				ZAPFILE(ACTNAME);
				c = getwc(finput);
			}
		}
		(void) putwc(c, ftable);
	}
	(void) 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++) != L'\0')
		++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 = (wchar_t *)malloc(sizeof (wchar_t) * isize);
		if (sarr == NULL)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	This error is issued when yacc could not allocate
 *	memory for internally used array.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
			error(gettext(
			"could not allocate output string array"));
		for (i = 0; i < isize; ++i)
			sarr[i] = L' ';
	}
	for (p = pp; *p > 0; ++p) /* NULL */
		;
	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 = (wchar_t *)
			    realloc((char *)sarr, sizeof (*sarr) * isize);
			if (sarr == NULL)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	This error is issued when yacc could not allocate
 *	memory for internally used array.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
				error(gettext(
				    "cannot expand sarr arrays"));
			q = q - sarrbase + sarr;
		}
	}

	/* an item calling for a reduction */
	if ((i = *pp) < 0) {
		q = chcopy(q, L"    (");
		(void) wsprintf(q, "%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) {
		(void) fprintf(foutput,
		    "\n%d/%d terminals, %d/%d nonterminals\n",
		    ntokens, ntoksz, nnonter, nnontersz);
		(void) fprintf(foutput,
		    "%d/%d grammar rules, %d/%d states\n",
		    nprod, nprodsz, nstate, nstatesz);
		(void) fprintf(foutput,
		"%d shift/reduce, %d reduce/reduce conflicts reported\n",
		    zzsrconf, zzrrconf);
		(void) fprintf(foutput,
		    "%d/%d working sets used\n", zzcwp, wsetsz);
		(void) fprintf(foutput,
		    "memory: states,etc. %" PRIdPTR
		    "/%d, parser %" PRIdPTR "/%d\n",
		    mem-tracemem, new_memsize,
		    memp-amem, new_actsize);
		(void) fprintf(foutput,
		    "%d/%d distinct lookahead sets\n", nlset, lsetsize);
		(void) fprintf(foutput,
		    "%d extra closures\n", zzclose - 2*nstate);
		(void) fprintf(foutput,
		    "%d shift entries, %d exceptions\n", zzacent, zzexcp);
		(void) fprintf(foutput,
		    "%d goto entries\n", zzgoent);
		(void) fprintf(foutput,
		    "%d entries saved by goto default\n", zzgobest);
	}
	if (zzsrconf != 0 || zzrrconf != 0) {
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	You may just leave this message un-translated.
 *	This message only makes sense to those who knows
 *	how yacc works, and the person should know what
 *	this message means in English.
 */
		(void) fprintf(stderr, gettext(
		    "\nconflicts: "));
		if (zzsrconf)
			(void) fprintf(stderr, "%d shift/reduce", zzsrconf);
		if (zzsrconf && zzrrconf)
			(void) fprintf(stderr, ", ");
		if (zzrrconf)
			(void) fprintf(stderr, "%d reduce/reduce", zzrrconf);
		(void) fprintf(stderr, "\n");
	}

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

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

	va_start(ap, s);

	++nerrors;
	if (!lineno)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is a prefix to the error messages
 *	passed to error() function.
 */
		(void) fprintf(stderr, gettext(
		    "command line: fatal: "));
	else {
		(void) fprintf(stderr, "\"%s\", ", infile);
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is a prefix to the error messages
 *	passed to error() function.
 */
		(void) fprintf(stderr, gettext(
		    "line %d: fatal: "),
		    lineno);
	}
	(void) vfprintf(stderr, s, ap);
	(void) fprintf(stderr, "\n");
	va_end(ap);
	if (!fatfl)
		return;
	summary();
	exit(1);
}

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

	(void) fprintf(stderr, "\"%s\", ", infile);
	/*
	 * If flag, print lineno as well.
	 */
	if (flag == 0)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is a prefix to the warning messages
 *	passed to warning() function.
 */
		(void) fprintf(stderr, gettext(
		    "warning: "));
	else
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is a prefix to the warning messages
 *	passed to warning() function.
 */
		(void) fprintf(stderr, gettext(
		    "line %d: warning: "),
		    lineno);
	(void) vfprintf(stderr, s, ap);
	(void) 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(int *a, int *b)
{
	int i, x, sub;

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

static void
prlook(LOOKSETS *p)
{
	int j, *pp;
	pp = p->lset;
	if (pp == 0)
		(void) fprintf(foutput, "\tNULL");
	else {
		(void) fprintf(foutput, " { ");
		TLOOP(j) {
			if (BIT(pp, j))
				(void) fprintf(foutput, "%ws ", symnam(j));
		}
		(void) 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)
{
	int **ptrpy;
	int **pyield;
	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 = (int **) malloc(sizeof (int *) * nprodsz)) == NULL)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	This error is issued when yacc could not allocate
 *	memory for internally used array.
 *
 *	pyield is name of an array. You should not try to translate
 *	this word.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
		error(gettext(
		"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 */
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	Ask somebody who knows yacc how to translate nonterminal or
 *	look at translated yacc document.
 */
			error(gettext(
			"undefined nonterminal: %ws"),
			    nontrst[i].name);
		}
	}
	pres[i] = ptrpy;
	fatfl = 1;
	if (nerrors) {
		summary();
		exit(1);
	}
	if (ptrpy != &pyield[nprod])
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	This is an internal error message.
 *	Very little use to user. You may leave it
 *	un-translated.
 *
 *	pyied is name of an array. Do not translate it.
 */
		error(gettext(
		"internal Yacc error: pyield %d"),
		    ptrpy-&pyield[nprod]);
}

static int indebug = 0;
/* compute an array with the first of nonterminals */
static void
cpfir(void)
{
	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) {
			(void) fprintf(foutput, "\n%ws: ", nontrst[i].name);
			prlook(pfirst[i]);
			(void) 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;
	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)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	You may leave this untranslated. Leave
 *	state/nolook un-translated.
 */
		error(gettext(
		"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))
		(void) fprintf(foutput,
		    "putitem(%ws), 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
	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;
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	Ask somebody who knows yacc how to translate nonterminal or
 *	look at translated yacc document. Check how 'derive' is
 *	translated in these documents also.
 */
			error(gettext(
			"nonterminal %ws 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;
	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)
				(void) state(c);  /* register new state */
			else temp1[c-NTBASE] = state(c);
		}
		if (gsdebug && (foutput != NULL)) {
			(void) fprintf(foutput,  "%d: ", i);
			NTLOOP(j) {
				if (temp1[j])
					(void) fprintf(foutput,
					    "%ws %d, ", nontrst[j].name,
					    temp1[j]);
			}
			(void) 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 */
						(void) setunion(clset.lset,
						    pfirst[ch-NTBASE]->lset);
						if (!pempty[ch-NTBASE])
							break;
					}
					if (ch <= 0)
						(void) 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)) {
		(void) fprintf(foutput, "\nState %d, nolook = %d\n", i, nolook);
		WSLOOP(wsets, u) {
			if (u->flag)
				(void) fprintf(foutput, "flag set!\n");
			u->flag = 0;
			(void) fprintf(foutput, "\t%ws", writem(u->pitem));
			prlook(&u->ws);
			(void) 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;
	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 = (int *)
	    calloc((size_t)(TBITSET * (lsetsize-LSETSIZE)), sizeof (int));
	if (tmp_lset == NULL)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	Memory allocation error. Do not translate lookset.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
		error(gettext(
		"could not expand lookset array"));
	lkst = (LOOKSETS *) realloc((char *)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)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	Memory allocation error. Do not translate lookset.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
		error(gettext(
		"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 = (int *)
	    calloc((size_t)(TBITSET * (wsetsz-WSETSIZE)), sizeof (int));
	if (tmp_lset == NULL)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	Memory allocation error. Do not translate lookset.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
		error(gettext(
		"could not expand lookset array"));
	wsets = (WSET *) realloc((char *)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)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	Memory allocation error. You may just transltate
 *	this as 'Could not allocate internally used memory.'
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
		error(gettext(
		"could not expand working sets"));
}

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

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

	if ((*pstate == NULL) || (tystate == NULL) || (defact == NULL) ||
	    (indgo == NULL) || (mstates == NULL))
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	Memory allocation error.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
		error(gettext(
		"cannot expand table of states"));
}

static void
exp_psmem(void)
{
	int i;

	new_pstsize += PSTSIZE;
	psmem = (ITEM *) realloc((char *)psmem, sizeof (ITEM) * new_pstsize);
	if (psmem == NULL)
/*
 * TRANSLATION_NOTE  -- This is a message from yacc.
 *	This message is passed to error() function.
 *	Memory allocation error.
 *
 *	You may just translate this as:
 *	'Could not allocate internally used memory.'
 */
		error(gettext(
		"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;
}