xref: /titanic_51/usr/src/cmd/sgs/lex/common/sub2.c (revision a31148363f598def767ac48c5d82e1572e44b935)

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

#pragma ident	"%Z%%M%	%I%	%E% SMI"

#include "ldefs.h"

static void add(int **array, int n);
static void follow(int v);
static void first(int v);
static void nextstate(int s, int c);
static void packtrans(int st, CHR *tch, int *tst, int cnt, int tryit);
static void acompute(int s);
static void rprint(int *a, char *s, int n);
static void shiftr(int *a, int n);
static void upone(int *a, int n);
static void bprint(char *a, char *s, int n);
static int notin(int n);
static int member(int d, CHR *t);

#ifdef PP
static void padd(int **array, int n);
#endif

void
cfoll(int v)
{
	int i, j, k;
	CHR *p;
	i = name[v];
	if (!ISOPERATOR(i))
		i = 1;
	switch (i) {
		case 1: case RSTR: case RCCL: case RNCCL: case RNULLS:
			for (j = 0; j < tptr; j++)
				tmpstat[j] = FALSE;
			count = 0;
			follow(v);
#ifdef PP
			padd(foll, v); /* packing version */
#else
			add(foll, v); /* no packing version */
#endif
			if (i == RSTR)
				cfoll(left[v]);
			else if (i == RCCL || i == RNCCL) {
				for (j = 1; j < ncg; j++)
					symbol[j] = (i == RNCCL);
				p = (CHR *) left[v];
				while (*p)
					symbol[*p++] = (i == RCCL);
				p = pcptr;
				for (j = 1; j < ncg; j++)
					if (symbol[j]) {
						for (k = 0; p + k < pcptr; k++)
							if (cindex[j] ==
							    *(p + k))
								break;
						if (p + k >= pcptr)
							*pcptr++ = cindex[j];
					}
				*pcptr++ = 0;
				if (pcptr > pchar + pchlen)
					error(
					"Too many packed character classes");
				left[v] = (int)p;
				name[v] = RCCL;	/* RNCCL eliminated */
#ifdef DEBUG
				if (debug && *p) {
					(void) printf("ccl %d: %d", v, *p++);
					while (*p)
						(void) printf(", %d", *p++);
					(void) putchar('\n');
				}
#endif
			}
			break;
		case CARAT:
			cfoll(left[v]);
			break;

		/* XCU4: add RXSCON */
		case RXSCON:

		case STAR: case PLUS: case QUEST: case RSCON:
			cfoll(left[v]);
			break;
		case BAR: case RCAT: case DIV: case RNEWE:
			cfoll(left[v]);
			cfoll(right[v]);
			break;
#ifdef DEBUG
		case FINAL:
		case S1FINAL:
		case S2FINAL:
			break;
		default:
			warning("bad switch cfoll %d", v);
#endif
	}
}

#ifdef DEBUG
void
pfoll(void)
{
	int i, k, *p;
	int j;
	/* print sets of chars which may follow positions */
	(void) printf("pos\tchars\n");
	for (i = 0; i < tptr; i++)
		if (p = foll[i]) {
			j = *p++;
			if (j >= 1) {
				(void) printf("%d:\t%d", i, *p++);
				for (k = 2; k <= j; k++)
					(void) printf(", %d", *p++);
				(void) putchar('\n');
			}
		}
}
#endif

static void
add(int **array, int n)
{
	int i, *temp;
	CHR *ctemp;
	temp = nxtpos;
	ctemp = tmpstat;
	array[n] = nxtpos;	/* note no packing is done in positions */
	*temp++ = count;
	for (i = 0; i < tptr; i++)
		if (ctemp[i] == TRUE)
			*temp++ = i;
	nxtpos = temp;
	if (nxtpos >= positions+maxpos)
		error(
		"Too many positions %s",
		    (maxpos == MAXPOS ? "\nTry using %p num" : ""));
}

static void
follow(int v)
{
	int p;
	if (v >= tptr-1)
		return;
	p = parent[v];
	if (p == 0)
		return;
	switch (name[p]) {
	/* will not be CHAR RNULLS FINAL S1FINAL S2FINAL RCCL RNCCL */
	case RSTR:
		if (tmpstat[p] == FALSE) {
			count++;
			tmpstat[p] = TRUE;
		}
		break;
	case STAR: case PLUS:
		first(v);
		follow(p);
		break;
	case BAR: case QUEST: case RNEWE:
		follow(p);
		break;
	case RCAT: case DIV:
		if (v == left[p]) {
			if (nullstr[right[p]])
				follow(p);
			first(right[p]);
		}
		else
			follow(p);
		break;
	/* XCU4: add RXSCON */
	case RXSCON:
	case RSCON: case CARAT:
		follow(p);
		break;
#ifdef DEBUG
	default:
		warning("bad switch follow %d", p);
#endif
	}
}

/*
 * Check if I have a RXSCON in my upper node
 */
static int
check_me(int v)
{
	int tmp = parent[v];

	while (name[tmp] != RNEWE) {
		if (name[tmp] == RXSCON)
			return (1);
		tmp = parent[tmp];
	}
	return (0);
}

/* calculate set of positions with v as root which can be active initially */
static void
first(int v)
{
	int i;
	CHR *p;
	i = name[v];
	if (!ISOPERATOR(i))
		i = 1;
	switch (i) {
	case 1: case RCCL: case RNCCL:
	case RNULLS: case FINAL:
	case S1FINAL: case S2FINAL:
	/*
	 * XCU4: if we are working on an exclusive start state and
	 * the parent of this position is not RXSCON or RSTR this
	 * is not an active position.
	 *
	 * (There is a possibility that RSXCON appreas as the
	 *  (parent)* node. Check it by check_me().)
	 */
		if ((exclusive[stnum/2]) &&
		    ISOPERATOR(name[parent[v]]) &&
		    (name[parent[v]] != RXSCON) &&
		    (name[parent[v]] != RSTR) &&
		    (check_me(v) == 0)) {
				break;
		}
		if (tmpstat[v] == FALSE) {
			count++;
			tmpstat[v] = TRUE;
		}
		break;
	case BAR: case RNEWE:
		first(left[v]);
		first(right[v]);
		break;
	case CARAT:
		if (stnum % 2 == 1)
			first(left[v]);
		break;
	/* XCU4: add RXSCON */
	case RXSCON:
	case RSCON:
		i = stnum/2 +1;
		p = (CHR *) right[v];
		while (*p)
			if (*p++ == i) {
				first(left[v]);
				break;
			}
		break;
	case STAR: case QUEST:
	case PLUS:  case RSTR:
	/*
	 * XCU4: if we are working on an exclusive start state and
	 * the parent of this position is not RXSCON or RSTR this
	 * is not an active position.
	 *
	 * (There is a possibility that RSXCON appreas as the
	 *  (parent)* node. Check it by check_me().)
	 */
		if ((exclusive[stnum/2]) &&
		    ISOPERATOR(name[parent[v]]) &&
		    (name[parent[v]] != RXSCON) &&
		    (name[parent[v]] != RSTR) &&
		    (check_me(v) == 0)) {
				break;
		}
		first(left[v]);
		break;
	case RCAT: case DIV:
		first(left[v]);
		if (nullstr[left[v]])
			first(right[v]);
		break;
#ifdef DEBUG
	default:
		warning("bad switch first %d", v);
#endif
	}
}

void
cgoto(void)
{
	int i, j;
	static int s;
	int npos, curpos, n;
	int tryit;
	CHR tch[MAXNCG];
	int tst[MAXNCG];
	CHR *q;
	/* generate initial state, for each start condition */
	if (ratfor) {
		(void) fprintf(fout, "blockdata\n");
		(void) fprintf(fout, "common /Lvstop/ vstop\n");
		(void) fprintf(fout, "define Svstop %d\n", nstates+1);
		(void) fprintf(fout, "integer vstop(Svstop)\n");
	} else
		(void) fprintf(fout, "int yyvstop[] = {\n0,\n");
	while (stnum < 2 || stnum/2 < sptr) {
		for (i = 0; i < tptr; i++)
			tmpstat[i] = 0;
		count = 0;
		if (tptr > 0)
			first(tptr-1);
		add(state, stnum);
#ifdef DEBUG
		if (debug) {
			if (stnum > 1)
				(void) printf("%ws:\n", sname[stnum/2]);
			pstate(stnum);
		}
#endif
		stnum++;
	}
	stnum--;
	/* even stnum = might not be at line begin */
	/* odd stnum  = must be at line begin */
	/* even states can occur anywhere, odd states only at line begin */
	for (s = 0; s <= stnum; s++) {
		tryit = FALSE;
		cpackflg[s] = FALSE;
		sfall[s] = -1;
		acompute(s);
		for (i = 0; i < ncg; i++)
			symbol[i] = 0;
		npos = *state[s];
		for (i = 1; i <= npos; i++) {
			curpos = *(state[s]+i);
			if (!ISOPERATOR(name[curpos]))
				symbol[name[curpos]] = TRUE;
			else {
				switch (name[curpos]) {
				case RCCL:
					tryit = TRUE;
					q = (CHR *)left[curpos];
					while (*q) {
						for (j = 1; j < ncg; j++)
							if (cindex[j] == *q)
								symbol[j] =
								    TRUE;
						q++;
					}
					break;
				case RSTR:
					symbol[right[curpos]] = TRUE;
					break;
#ifdef DEBUG
				case RNULLS:
				case FINAL:
				case S1FINAL:
				case S2FINAL:
					break;
				default:
					warning(
					"bad switch cgoto %d state %d",
					    curpos, s);
					break;
#endif
				}
			}
		}
#ifdef DEBUG
		if (debug) {
			printf("State %d transitions on char-group {", s);
			charc = 0;
			for (i = 1; i < ncg; i++) {
				if (symbol[i]) {
					printf("%d,", i);
				}
				if (i == ncg-1)
					printf("}\n");
				if (charc > LINESIZE/4) {
					charc = 0;
					printf("\n\t");
				}
			}
		}
#endif
		/* for each char, calculate next state */
		n = 0;
		for (i = 1; i < ncg; i++) {
			if (symbol[i]) {
				/* executed for each state, transition pair */
				nextstate(s, i);
				xstate = notin(stnum);
				if (xstate == -2)
					warning("bad state  %d %o", s, i);
				else if (xstate == -1) {
					if (stnum+1 >= nstates) {
						stnum++;
						error("Too many states %s",
						    (nstates == NSTATES ?
						    "\nTry using %n num":""));
					}
					add(state, ++stnum);
#ifdef DEBUG
					if (debug)
						pstate(stnum);
#endif
					tch[n] = i;
					tst[n++] = stnum;
				} else { /* xstate >= 0 ==> state exists */
					tch[n] = i;
					tst[n++] = xstate;
				}
			}
		}
		tch[n] = 0;
		tst[n] = -1;
		/* pack transitions into permanent array */
		if (n > 0)
			packtrans(s, tch, tst, n, tryit);
		else
			gotof[s] = -1;
	}
	(void) (ratfor ? fprintf(fout, "end\n") : fprintf(fout, "0};\n"));
}

/*
 * Beware -- 70% of total CPU time is spent in this subroutine -
 * if you don't believe me - try it yourself !
 */
static void
nextstate(int s, int c)
{
	int j, *newpos;
	CHR *temp, *tz;
	int *pos, i, *f, num, curpos, number;
	/* state to goto from state s on char c */
	num = *state[s];
	temp = tmpstat;
	pos = state[s] + 1;
	for (i = 0; i < num; i++) {
		curpos = *pos++;
		j = name[curpos];
		if ((!ISOPERATOR(j)) && j == c ||
		    j == RSTR && c == right[curpos] ||
		    j == RCCL && member(c, (CHR *) left[curpos])) {
			f = foll[curpos];
			number = *f;
			newpos = f+1;
			for (j = 0; j < number; j++)
				temp[*newpos++] = 2;
		}
	}
	j = 0;
	tz = temp + tptr;
	while (temp < tz) {
		if (*temp == 2) {
			j++;
			*temp++ = 1;
		}
		else
			*temp++ = 0;
	}
	count = j;
}

static int
notin(int n)
{	/* see if tmpstat occurs previously */
	int *j, k;
	CHR *temp;
	int i;
	if (count == 0)
		return (-2);
	temp = tmpstat;
	for (i = n; i >= 0; i--) { /* for each state */
		j = state[i];
		if (count == *j++) {
			for (k = 0; k < count; k++)
				if (!temp[*j++])
					break;
			if (k >= count)
				return (i);
		}
	}
	return (-1);
}

static void
packtrans(int st, CHR *tch, int *tst, int cnt, int tryit)
{
	/*
	 * pack transitions into nchar, nexts
	 * nchar is terminated by '\0', nexts uses cnt, followed by elements
	 * gotof[st] = index into nchr, nexts for state st
	 * sfall[st] =  t implies t is fall back state for st
	 * == -1 implies no fall back
	 */

	int cmin, cval, tcnt, diff, p, *ast;
	int i, j, k;
	CHR *ach;
	int go[MAXNCG], temp[MAXNCG], index, c;
	int swork[MAXNCG];
	CHR cwork[MAXNCG];
	int upper;

	rcount += (long)cnt;
	cmin = -1;
	cval = ncg;
	ast = tst;
	ach = tch;
	/* try to pack transitions using ccl's */
	if (!optim)
		goto nopack; /* skip all compaction */
	if (tryit) { /* ccl's used */
		for (i = 1; i < ncg; i++) {
			go[i] = temp[i] = -1;
			symbol[i] = 1;
		}
		for (i = 0; i < cnt; i++) {
			index = (unsigned char) tch[i];
			if ((index >= 0) && (index < NCH)) {
				go[index] = tst[i];
				symbol[index] = 0;
			} else {
				(void) fprintf(stderr,
"lex`sub2`packtran: tch[%d] out of bounds (%d)\n",
				    i, (int)tch[i]);
			}
		}
		for (i = 0; i < cnt; i++) {
			c = match[tch[i]];
			if (go[c] != tst[i] || c == tch[i])
				temp[tch[i]] = tst[i];
		}
		/* fill in error entries */
		for (i = 1; i < ncg; i++)
			if (symbol[i])
				temp[i] = -2;	/* error trans */
		/* count them */
		k = 0;
		for (i = 1; i < ncg; i++)
			if (temp[i] != -1)
				k++;
		if (k < cnt) { /* compress by char */
#ifdef DEBUG
			if (debug)
				(void) printf(
				"use compression  %d,  %d vs %d\n", st, k, cnt);
#endif
			k = 0;
			for (i = 1; i < ncg; i++)
				if (temp[i] != -1) {
					cwork[k] = i;
					swork[k++] =
					    (temp[i] == -2 ? -1 : temp[i]);
				}
			cwork[k] = 0;
#ifdef PC
			ach = cwork;
			ast = swork;
			cnt = k;
			cpackflg[st] = TRUE;
#endif
		}
	}
	/*
	 * get most similar state
	 * reject state with more transitions,
	 * state already represented by a third state,
	 * and state which is compressed by char if ours is not to be
	 */
	for (i = 0; i < st; i++) {
		if (sfall[i] != -1)
			continue;
		if (cpackflg[st] == 1)
			if (!(cpackflg[i] == 1))
				continue;
		p = gotof[i];
		if (p == -1) /* no transitions */
			continue;
		tcnt = nexts[p];
		if (tcnt > cnt)
			continue;
		diff = 0;
		k = 0;
		j = 0;
		upper = p + tcnt;
		while (ach[j] && p < upper) {
			while (ach[j] < nchar[p] && ach[j]) {
				diff++;
				j++;
			}
			if (ach[j] == 0)
				break;
			if (ach[j] > nchar[p]) {
				diff = ncg;
				break;
			}
			/* ach[j] == nchar[p] */
			if (ast[j] != nexts[++p] ||
			    ast[j] == -1 ||
			    (cpackflg[st] && ach[j] != match[ach[j]]))
				diff++;
			j++;
		}
		while (ach[j]) {
			diff++;
			j++;
		}
		if (p < upper)
			diff = ncg;
		if (diff < cval && diff < tcnt) {
			cval = diff;
			cmin = i;
			if (cval == 0)
				break;
		}
	}
	/* cmin = state "most like" state st */
#ifdef DEBUG
	if (debug)
		(void) printf("select st %d for st %d diff %d\n",
		    cmin, st, cval);
#endif
#ifdef PS
	if (cmin != -1) { /* if we can use st cmin */
		gotof[st] = nptr;
		k = 0;
		sfall[st] = cmin;
		p = gotof[cmin] + 1;
		j = 0;
		while (ach[j]) {
			/* if cmin has a transition on c, then so will st */
			/* st may be "larger" than cmin, however */
			while (ach[j] < nchar[p-1] && ach[j]) {
				k++;
				nchar[nptr] = ach[j];
				nexts[++nptr] = ast[j];
				j++;
			}
			if (nchar[p-1] == 0)
				break;
			if (ach[j] > nchar[p-1]) {
				warning("bad transition %d %d", st, cmin);
				goto nopack;
			}
			/* ach[j] == nchar[p-1] */
			if (ast[j] != nexts[p] ||
			    ast[j] == -1 ||
			    (cpackflg[st] && ach[j] != match[ach[j]])) {
				k++;
				nchar[nptr] = ach[j];
				nexts[++nptr] = ast[j];
			}
			p++;
			j++;
		}
		while (ach[j]) {
			nchar[nptr] = ach[j];
			nexts[++nptr] = ast[j++];
			k++;
		}
		nexts[gotof[st]] = cnt = k;
		nchar[nptr++] = 0;
	} else {
#endif
nopack:
	/* stick it in */
		gotof[st] = nptr;
		nexts[nptr] = cnt;
		for (i = 0; i < cnt; i++) {
			nchar[nptr] = ach[i];
			nexts[++nptr] = ast[i];
		}
		nchar[nptr++] = 0;
#ifdef PS
	}
#endif
	if (cnt < 1) {
		gotof[st] = -1;
		nptr--;
	} else
		if (nptr > ntrans)
			error(
			"Too many transitions %s",
			    (ntrans == NTRANS ? "\nTry using %a num" : ""));
}

#ifdef DEBUG
void
pstate(int s)
{
	int *p, i, j;
	(void) printf("State %d:\n", s);
	p = state[s];
	i = *p++;
	if (i == 0)
		return;
	(void) printf("%4d", *p++);
	for (j = 1; j < i; j++) {
		(void) printf(", %4d", *p++);
		if (j%30 == 0)
			(void) putchar('\n');
	}
	(void) putchar('\n');
}
#endif

static int
member(int d, CHR *t)
{
	int c;
	CHR *s;
	c = d;
	s = t;
	c = cindex[c];
	while (*s)
		if (*s++ == c)
			return (1);
	return (0);
}

#ifdef DEBUG
void
stprt(int i)
{
	int p, t;
	(void) printf("State %d:", i);
	/* print actions, if any */
	t = atable[i];
	if (t != -1)
		(void) printf(" final");
	(void) putchar('\n');
	if (cpackflg[i] == TRUE)
		(void) printf("backup char in use\n");
	if (sfall[i] != -1)
		(void) printf("fall back state %d\n", sfall[i]);
	p = gotof[i];
	if (p == -1)
		return;
	(void) printf("(%d transitions)\n", nexts[p]);
	while (nchar[p]) {
		charc = 0;
		if (nexts[p+1] >= 0)
			(void) printf("%d\t", nexts[p+1]);
		else
			(void) printf("err\t");
		allprint(nchar[p++]);
		while (nexts[p] == nexts[p+1] && nchar[p]) {
			if (charc > LINESIZE) {
				charc = 0;
				(void) printf("\n\t");
			}
			allprint(nchar[p++]);
		}
		(void) putchar('\n');
	}
	(void) putchar('\n');
}
#endif

/* compute action list = set of poss. actions */
static void
acompute(int s)
{
	int *p, i, j;
	int q, r;
	int cnt, m;
	int temp[MAXPOSSTATE], k, neg[MAXPOSSTATE], n;
	k = 0;
	n = 0;
	p = state[s];
	cnt = *p++;
	if (cnt > MAXPOSSTATE)
		error("Too many positions for one state - acompute");
	for (i = 0; i < cnt; i++) {
		q = *p;
		if (name[q] == FINAL)
			temp[k++] = left[q];
		else if (name[q] == S1FINAL) {
			temp[k++] = left[q];
			if ((r = left[q]) >= NACTIONS)
				error(
				"INTERNAL ERROR:left[%d]==%d>=NACTIONS", q, r);
			extra[r] = 1;
		} else if (name[q] == S2FINAL)
			neg[n++] = left[q];
		p++;
	}
	atable[s] = -1;
	if (k < 1 && n < 1)
		return;
#ifdef DEBUG
	if (debug)
		(void) printf("final %d actions:", s);
#endif
	/* sort action list */
	for (i = 0; i < k; i++)
		for (j = i+1; j < k; j++)
			if (temp[j] < temp[i]) {
				m = temp[j];
				temp[j] = temp[i];
				temp[i] = m;
			}
	/* remove dups */
	for (i = 0; i < k-1; i++)
		if (temp[i] == temp[i+1])
			temp[i] = 0;
	/* copy to permanent quarters */
	atable[s] = aptr;
#ifdef DEBUG
	if (!ratfor)
		(void) fprintf(fout, "/* actions for state %d */", s);
#endif
	(void) putc('\n', fout);
	for (i = 0; i < k; i++)
		if (temp[i] != 0) {
			(void) (ratfor ?
			    fprintf(fout, "data vstop(%d)/%d/\n",
			    aptr, temp[i]) :
			    fprintf(fout, "%d,\n", temp[i]));
#ifdef DEBUG
			if (debug)
				(void) printf("%d ", temp[i]);
#endif
			aptr++;
		}
	for (i = 0; i < n; i++) { /* copy fall back actions - all neg */
		ratfor ?
		    (void) fprintf(fout, "data vstop(%d)/%d/\n", aptr, neg[i]) :
		    (void) fprintf(fout, "%d,\n", neg[i]);
		aptr++;
#ifdef DEBUG
		if (debug)
			(void) printf("%d ", neg[i]);
#endif
		}
#ifdef DEBUG
	if (debug)
		(void) putchar('\n');
#endif
	(void) (ratfor ? fprintf(fout, "data vstop (%d)/0/\n", aptr) :
	    fprintf(fout, "0, \n"));
	aptr++;
}

#ifdef DEBUG
void
pccl(void)
{
	/* print character class sets */
	int i, j;
	(void) printf("char class intersection\n");
	for (i = 0; i < ccount; i++) {
		charc = 0;
		(void) printf("class %d:\n\t", i);
		for (j = 1; j < ncg; j++)
			if (cindex[j] == i) {
				allprint(j);
				if (charc > LINESIZE) {
					(void) printf("\n\t");
					charc = 0;
				}
			}
		(void) putchar('\n');
	}
	charc = 0;
	(void) printf("match:\n");
	for (i = 0; i < ncg; i++) {
		allprint(match[i]);
		if (charc > LINESIZE) {
			(void) putchar('\n');
			charc = 0;
		}
	}
	(void) putchar('\n');
}
#endif

void
mkmatch(void)
{
	int i;
	CHR tab[MAXNCG];
	for (i = 0; i < ccount; i++)
		tab[i] = 0;
	for (i = 1; i < ncg; i++)
		if (tab[cindex[i]] == 0)
			tab[cindex[i]] = i;
	/* tab[i] = principal char for new ccl i */
	for (i = 1; i < ncg; i++)
		match[i] = tab[cindex[i]];
}

void
layout(void)
{
	/* format and output final program's tables */
	int i, j, k;
	int  top, bot, startup, omin;
	startup = 0;
	for (i = 0; i < outsize; i++)
		verify[i] = advance[i] = 0;
	omin = 0;
	yytop = 0;
	for (i = 0; i <= stnum; i++) { /* for each state */
		j = gotof[i];
		if (j == -1) {
			stoff[i] = 0;
			continue;
		}
		bot = j;
		while (nchar[j])
			j++;
		top = j - 1;
#if DEBUG
		if (debug) {
			(void) printf("State %d: (layout)\n", i);
			for (j = bot; j <= top; j++) {
				(void) printf("  %o", nchar[j]);
				if (j % 10 == 0)
					(void) putchar('\n');
			}
			(void) putchar('\n');
		}
#endif
		while (verify[omin+ZCH])
			omin++;
		startup = omin;
#if DEBUG
		if (debug)
			(void) printf(
			"bot,top %d, %d startup begins %d\n",
			    bot, top, startup);
#endif
		if (chset) {
			do {
				startup += 1;
				if (startup > outsize - ZCH)
					error("output table overflow");
				for (j = bot; j <= top; j++) {
					k = startup+ctable[nchar[j]];
					if (verify[k])
						break;
				}
			} while (j <= top);
#if DEBUG
			if (debug)
				(void) printf(" startup will be %d\n",
				    startup);
#endif
			/* have found place */
			for (j = bot; j <= top; j++) {
				k = startup + ctable[nchar[j]];
				if (ctable[nchar[j]] <= 0)
					(void) printf(
					"j %d nchar %d ctable.nch %d\n",
					    j, (int)nchar[j], ctable[nchar[k]]);
				verify[k] = i + 1;	/* state number + 1 */
				advance[k] = nexts[j+1]+1;
				if (yytop < k)
					yytop = k;
			}
		} else {
			do {
				startup += 1;
				if (startup > outsize - ZCH)
					error("output table overflow");
				for (j = bot; j <= top; j++) {
					k = startup + nchar[j];
					if (verify[k])
						break;
				}
			} while (j <= top);
			/* have found place */
#if DEBUG
	if (debug)
		(void) printf(" startup going to be %d\n", startup);
#endif
			for (j = bot; j <= top; j++) {
				k = startup + nchar[j];
				verify[k] = i+1; /* state number + 1 */
				advance[k] = nexts[j+1] + 1;
				if (yytop < k)
					yytop = k;
			}
		}
		stoff[i] = startup;
	}

	/* stoff[i] = offset into verify, advance for trans for state i */
	/* put out yywork */
	if (ratfor) {
		(void) fprintf(fout, "define YYTOPVAL %d\n", yytop);
		rprint(verify, "verif", yytop+1);
		rprint(advance, "advan", yytop+1);
		shiftr(stoff, stnum);
		rprint(stoff, "stoff", stnum+1);
		shiftr(sfall, stnum);
		upone(sfall, stnum+1);
		rprint(sfall, "fall", stnum+1);
		bprint(extra, "extra", casecount+1);
		bprint((char *)match, "match", ncg);
		shiftr(atable, stnum);
		rprint(atable, "atable", stnum+1);
	}
	(void) fprintf(fout,
	"# define YYTYPE %s\n", stnum+1 >= NCH ? "int" : "unsigned char");
	(void) fprintf(fout,
	"struct yywork { YYTYPE verify, advance; } yycrank[] = {\n");
	for (i = 0; i <= yytop; i += 4) {
		for (j = 0; j < 4; j++) {
			k = i+j;
			if (verify[k])
				(void) fprintf(fout,
				"%d,%d,\t", verify[k], advance[k]);
			else
				(void) fprintf(fout, "0,0,\t");
		}
		(void) putc('\n', fout);
	}
	(void) fprintf(fout, "0,0};\n");

	/* put out yysvec */

	(void) fprintf(fout, "struct yysvf yysvec[] = {\n");
	(void) fprintf(fout, "0,\t0,\t0,\n");
	for (i = 0; i <= stnum; i++) {	/* for each state */
		if (cpackflg[i])
			stoff[i] = -stoff[i];
		(void) fprintf(fout, "yycrank+%d,\t", stoff[i]);
		if (sfall[i] != -1)
			(void) fprintf(fout,
			"yysvec+%d,\t", sfall[i]+1); /* state + 1 */
		else
			(void) fprintf(fout, "0,\t\t");
		if (atable[i] != -1)
			(void) fprintf(fout, "yyvstop+%d,", atable[i]);
		else
			(void) fprintf(fout, "0,\t");
#ifdef DEBUG
		(void) fprintf(fout, "\t\t/* state %d */", i);
#endif
		(void) putc('\n', fout);
	}
	(void) fprintf(fout, "0,\t0,\t0};\n");

	/* put out yymatch */

	(void) fprintf(fout, "struct yywork *yytop = yycrank+%d;\n", yytop);
	(void) fprintf(fout, "struct yysvf *yybgin = yysvec+1;\n");
	if (optim) {
		if (handleeuc) {
			(void) fprintf(fout, "int yymatch[] = {\n");
		} else {
			(void) fprintf(fout, "char yymatch[] = {\n");
		}
		if (chset == 0) { /* no chset, put out in normal order */
			for (i = 0; i < ncg; i += 8) {
				for (j = 0; j < 8; j++) {
					int fbch;
					fbch = match[i+j];
					(void) fprintf(fout, "%3d, ", fbch);
				}
				(void) putc('\n', fout);
			}
		} else {
			int *fbarr;
			/*LINTED: E_BAD_PTR_CAST_ALIGN*/
			fbarr = (int *)myalloc(2*MAXNCG, sizeof (*fbarr));
			if (fbarr == 0)
				error("No space for char table reverse", 0);
			for (i = 0; i < MAXNCG; i++)
				fbarr[i] = 0;
			for (i = 0; i < ncg; i++)
				fbarr[ctable[i]] = ctable[match[i]];
			for (i = 0; i < ncg; i += 8) {
				for (j = 0; j < 8; j++)
					(void) fprintf(fout, "0%-3o,",
					    fbarr[i+j]);
				(void) putc('\n', fout);
			}
			free(fbarr);
		}
		(void) fprintf(fout, "0};\n");
	}
	/* put out yyextra */
	(void) fprintf(fout, "char yyextra[] = {\n");
	for (i = 0; i < casecount; i += 8) {
		for (j = 0; j < 8; j++)
			(void) fprintf(fout, "%d,", i+j < NACTIONS ?
			    extra[i+j] : 0);
		(void) putc('\n', fout);
	}
	(void) fprintf(fout, "0};\n");
	if (handleeuc) {
		/* Put out yycgidtbl */
		(void) fprintf(fout, "#define YYNCGIDTBL %d\n", ncgidtbl);
		(void) fprintf(fout, "\tunsigned long yycgidtbl[]={");
		/*
		 * Use "unsigned long" instead of "lchar" to minimize
		 * the name-space polution for the application program.
		 */
		for (i = 0; i < ncgidtbl; ++i) {
			if (i%8 == 0)
				(void) fprintf(fout, "\n\t\t");
			(void) fprintf(fout, "0x%08x, ",  (int)yycgidtbl[i]);
		}
		(void) fprintf(fout, "\n\t0};\n");
	}
}

static void
rprint(int *a, char *s, int n)
{
	int i;
	(void) fprintf(fout, "block data\n");
	(void) fprintf(fout, "common /L%s/ %s\n", s, s);
	(void) fprintf(fout, "define S%s %d\n", s, n);
	(void) fprintf(fout, "integer %s (S%s)\n", s, s);
	for (i = 1; i <= n; i++) {
		if (i%8 == 1)
			(void) fprintf(fout, "data ");
		(void) fprintf(fout, "%s (%d)/%d/", s, i, a[i]);
		(void) fprintf(fout, (i%8 && i < n) ? ", " : "\n");
	}
	(void) fprintf(fout, "end\n");
}

static void
shiftr(int *a, int n)
{
	int i;
	for (i = n; i >= 0; i--)
		a[i+1] = a[i];
}

static void
upone(int *a, int n)
{
	int i;
	for (i = 0; i <= n; i++)
		a[i]++;
}

static void
bprint(char *a, char *s, int n)
{
	int i, j, k;
	(void) fprintf(fout, "block data\n");
	(void) fprintf(fout, "common /L%s/ %s\n", s, s);
	(void) fprintf(fout, "define S%s %d\n", s, n);
	(void) fprintf(fout, "integer %s (S%s)\n", s, s);
	for (i = 1; i < n; i += 8) {
		(void) fprintf(fout, "data %s (%d)/%d/", s, i, a[i]);
		for (j = 1; j < 8; j++) {
			k = i+j;
			if (k < n)
				(void) fprintf(fout,
				    ", %s (%d)/%d/", s, k, a[k]);
		}
		(void) putc('\n', fout);
	}
	(void) fprintf(fout, "end\n");
}

#ifdef PP
static void
padd(int **array, int n)
{
	int i, *j, k;
	array[n] = nxtpos;
	if (count == 0) {
		*nxtpos++ = 0;
		return;
	}
	for (i = tptr-1; i >= 0; i--) {
		j = array[i];
		if (j && *j++ == count) {
			for (k = 0; k < count; k++)
				if (!tmpstat[*j++])
					break;
			if (k >= count) {
				array[n] = array[i];
				return;
			}
		}
	}
	add(array, n);
}
#endif