[unix-history] / usr / src / old / awk / b.c

#ifndef lint
static char sccsid[] = "@(#)b.c	4.3 %G%";
#endif

#include "awk.def"
#include "stdio.h"
#include "awk.h"

extern node *op2();
extern struct fa *cgotofn();
#define MAXLIN 256
#define NCHARS 128
#define NSTATES 256

#define type(v)	v->nobj
#define left(v)	v->narg[0]
#define right(v)	v->narg[1]
#define parent(v)	v->nnext

#define LEAF	case CCL: case NCCL: case CHAR: case DOT:
#define UNARY	case FINAL: case STAR: case PLUS: case QUEST:

/* encoding in tree nodes:
	leaf (CCL, NCCL, CHAR, DOT): left is index, right contains value or pointer to value
	unary (FINAL, STAR, PLUS, QUEST): left is child, right is null
	binary (CAT, OR): left and right are children
	parent contains pointer to parent
*/

struct fa {
	int cch;
	struct fa *st;
};

int	*state[NSTATES];
int	*foll[MAXLIN];
char	chars[MAXLIN];
int	setvec[MAXLIN];
node	*point[MAXLIN];

int	setcnt;
int	line;
int	maxfoll;  /* index of highest foll[] entry set by cfoll() */


struct fa *makedfa(p)	/* returns dfa for tree pointed to by p */
node *p;
{
	node *p1;
	struct fa *fap;
	p1 = op2(CAT, op2(STAR, op2(DOT, (node *) 0, (node *) 0), (node *) 0), p);
		/* put DOT STAR in front of reg. exp. */
	p1 = op2(FINAL, p1, (node *) 0);		/* install FINAL node */

	line = 0;
	penter(p1);	/* enter parent pointers and leaf indices */
	point[line] = p1;	/* FINAL node */
	setvec[0] = 1;		/* for initial DOT STAR */
	cfoll(p1);	/* set up follow sets */
	fap = cgotofn();
	freetr(p1);	/* add this when alloc works */
	return(fap);
}

penter(p)	/* set up parent pointers and leaf indices */
node *p;
{
	switch(type(p)) {
		LEAF
			left(p) = (node *) line;
			point[line++] = p;
			break;
		UNARY
			penter(left(p));
			parent(left(p)) = p;
			break;
		case CAT:
		case OR:
			penter(left(p));
			penter(right(p));
			parent(left(p)) = p;
			parent(right(p)) = p;
			break;
		default:
			error(FATAL, "unknown type %d in penter\n", type(p));
			break;
	}
}

freetr(p)	/* free parse tree and follow sets */
node *p;
{
	switch(type(p)) {
		LEAF
			foll_free((int) left(p));
			xfree(p);
			break;
		UNARY
			freetr(left(p));
			xfree(p);
			break;
		case CAT:
		case OR:
			freetr(left(p));
			freetr(right(p));
			xfree(p);
			break;
		default:
			error(FATAL, "unknown type %d in freetr", type(p));
			break;
	}
}
char *cclenter(p)
register char *p;
{
	register i, c;
	char *op;

	op = p;
	i = 0;
	while ((c = *p++) != 0) {
		if (c == '-' && i > 0 && chars[i-1] != 0) {
			if (*p != 0) {
				c = chars[i-1];
				while (c < *p) {
					if (i >= MAXLIN)
						overflo();
					chars[i++] = ++c;
				}
				p++;
				continue;
			}
		}
		if (i >= MAXLIN)
			overflo();
		chars[i++] = c;
	}
	chars[i++] = '\0';
	dprintf("cclenter: in = |%s|, out = |%s|\n", op, chars, NULL);
	xfree(op);
	return(tostring(chars));
}

overflo()
{
	error(FATAL, "regular expression too long\n");
}

cfoll(v)		/* enter follow set of each leaf of vertex v into foll[leaf] */
register node *v;
{
	register i;
	int prev;
	int *add();

	maxfoll = -1;
	switch(type(v)) {
		LEAF
			setcnt = 0;
			for (i=1; i<=line; i++)
				setvec[i] = 0;
			follow(v);
			if (notin(foll, ( (int) left(v))-1, &prev)) {
				foll[(int) left(v)] = add(setcnt);
			}
			else
				foll[ (int) left(v)] = foll[prev];
			if ((int)left(v) > maxfoll)
				maxfoll = (int)left(v);
			break;
		UNARY
			cfoll(left(v));
			break;
		case CAT:
		case OR:
			cfoll(left(v));
			cfoll(right(v));
			break;
		default:
			error(FATAL, "unknown type %d in cfoll", type(v));
	}
}

first(p)			/* collects initially active leaves of p into setvec */
register node *p;		/* returns 0 or 1 depending on whether p matches empty string */
{
	register b;

	switch(type(p)) {
		LEAF
			if (setvec[(int) left(p)] != 1) {
				setvec[(int) left(p)] = 1;
				setcnt++;
			}
			if (type(p) == CCL && (*(char *) right(p)) == '\0')
				return(0);		/* empty CCL */
			else return(1);
		case FINAL:
		case PLUS:
			if (first(left(p)) == 0) return(0);
			return(1);
		case STAR:
		case QUEST:
			first(left(p));
			return(0);
		case CAT:
			if (first(left(p)) == 0 && first(right(p)) == 0) return(0);
			return(1);
		case OR:
			b = first(right(p));
			if (first(left(p)) == 0 || b == 0) return(0);
			return(1);
	}
	error(FATAL, "unknown type %d in first\n", type(p));
	return(-1);
}

follow(v)
node *v;		/* collects leaves that can follow v into setvec */
{
	node *p;

	if (type(v) == FINAL)
		return;
	p = parent(v);
	switch (type(p)) {
		case STAR:
		case PLUS:	first(v);
				follow(p);
				return;

		case OR:
		case QUEST:	follow(p);
				return;

		case CAT:	if (v == left(p)) {	/* v is left child of p */
					if (first(right(p)) == 0) {
						follow(p);
						return;
					}
				}
				else		/* v is right child */
					follow(p);
				return;
		case FINAL:	if (setvec[line] != 1) {
					setvec[line] = 1;
					setcnt++;
				}
				return;
	}
}

member(c, s)	/* is c in s? */
register char c, *s;
{
	while (*s)
		if (c == *s++)
			return(1);
	return(0);
}

notin(array, n, prev)		/* is setvec in array[0] thru array[n]? */
int **array;
int *prev; {
	register i, j;
	int *ptr;
	for (i=0; i<=n; i++) {
		ptr = array[i];
		if (*ptr == setcnt) {
			for (j=0; j < setcnt; j++)
				if (setvec[*(++ptr)] != 1) goto nxt;
			*prev = i;
			return(0);
		}
		nxt: ;
	}
	return(1);
}

int *add(n) {		/* remember setvec */
	int *ptr, *p;
	register i;
	if ((p = ptr = (int *) malloc((n+1)*sizeof(int))) == NULL)
		overflo();
	*ptr = n;
	dprintf("add(%d)\n", n, NULL, NULL);
	for (i=1; i <= line; i++)
		if (setvec[i] == 1) {
			*(++ptr) = i;
			dprintf("  ptr = %o, *ptr = %d, i = %d\n", ptr, *ptr, i);
		}
	dprintf("\n", NULL, NULL, NULL);
	return(p);
}

struct fa *cgotofn()
{
	register i, k;
	register int *ptr;
	char c;
	char *p;
	node *cp;
	int j, n, s, ind, numtrans;
	int finflg;
	int curpos, num, prev;
	struct fa *where[NSTATES];

	int fatab[257];
	struct fa *pfa;

	char index[MAXLIN];
	char iposns[MAXLIN];
	int sposns[MAXLIN];
	int spmax, spinit;

	char symbol[NCHARS];
	char isyms[NCHARS];
	char ssyms[NCHARS];
	int ssmax, ssinit;

	for (i=0; i<=line; i++) index[i] = iposns[i] = setvec[i] = 0;
	for (i=0; i<NCHARS; i++)  isyms[i] = symbol[i] = 0;
	setcnt = 0;
	/* compute initial positions and symbols of state 0 */
	ssmax = 0;
	ptr = state[0] = foll[0];
	spinit = *ptr;
	for (i=0; i<spinit; i++) {
		curpos = *(++ptr);
		sposns[i] = curpos;
		iposns[curpos] = 1;
		cp = point[curpos];
		dprintf("i = %d, spinit = %d, curpos = %d\n", i, spinit, curpos);
		switch (type(cp)) {
			case CHAR:
				k = (int) right(cp);
				if (isyms[k] != 1) {
					isyms[k] = 1;
					ssyms[ssmax++] = k;
				}
				break;
			case DOT:
				for (k=1; k<NCHARS; k++) {
					if (k != HAT) {
						if (isyms[k] != 1) {
							isyms[k] = 1;
							ssyms[ssmax++] = k;
						}
					}
				}
				break;
			case CCL:
				for (p = (char *) right(cp); *p; p++) {
					if (*p != HAT) {
						if (isyms[*p] != 1) {
							isyms[*p] = 1;
							ssyms[ssmax++] = *p;
						}
					}
				}
				break;
			case NCCL:
				for (k=1; k<NCHARS; k++) {
					if (k != HAT && !member(k, (char *) right(cp))) {
						if (isyms[k] != 1) {
							isyms[k] = 1;
							ssyms[ssmax++] = k;
						}
					}
				}
		}
	}
	ssinit = ssmax;
	n = 0;
	for (s=0; s<=n; s++)  {
	dprintf("s = %d\n", s, NULL, NULL);
		ind = 0;
		numtrans = 0;
		finflg = 0;
		if (*(state[s] + *state[s]) == line) {		/* s final? */
			finflg = 1;
			goto tenter;
		}
		spmax = spinit;
		ssmax = ssinit;
		ptr = state[s];
		num = *ptr;
		for (i=0; i<num; i++) {
			curpos = *(++ptr);
			if (iposns[curpos] != 1 && index[curpos] != 1) {
				index[curpos] = 1;
				sposns[spmax++] = curpos;
			}
			cp = point[curpos];
			switch (type(cp)) {
				case CHAR:
					k = (int) right(cp);
					if (isyms[k] == 0 && symbol[k] == 0) {
						symbol[k] = 1;
						ssyms[ssmax++] = k;
					}
					break;
				case DOT:
					for (k=1; k<NCHARS; k++) {
						if (k != HAT) {
							if (isyms[k] == 0 && symbol[k] == 0) {
								symbol[k] = 1;
								ssyms[ssmax++] = k;
							}
						}
					}
					break;
				case CCL:
					for (p = (char *) right(cp); *p; p++) {
						if (*p != HAT) {
							if (isyms[*p] == 0 && symbol[*p] == 0) {
								symbol[*p] = 1;
								ssyms[ssmax++] = *p;
							}
						}
					}
					break;
				case NCCL:
					for (k=1; k<NCHARS; k++) {
						if (k != HAT && !member(k, (char *) right(cp))) {
							if (isyms[k] == 0 && symbol[k] == 0) {
								symbol[k] = 1;
								ssyms[ssmax++] = k;
							}
						}
					}
			}
		}
		for (j=0; j<ssmax; j++) {	/* nextstate(s, ssyms[j]) */
			c = ssyms[j];
			symbol[c] = 0;
			setcnt = 0;
			for (k=0; k<=line; k++) setvec[k] = 0;
			for (i=0; i<spmax; i++) {
				index[sposns[i]] = 0;
				cp = point[sposns[i]];
				if ((k = type(cp)) != FINAL)
					if (k == CHAR && c == (int) right(cp)
					 || k == DOT
					 || k == CCL && member(c, (char *) right(cp))
					 || k == NCCL && !member(c, (char *) right(cp))) {
						ptr = foll[sposns[i]];
						num = *ptr;
						for (k=0; k<num; k++) {
							if (setvec[*(++ptr)] != 1
								&& iposns[*ptr] != 1) {
								setvec[*ptr] = 1;
								setcnt++;
							}
						}
					}
			} /* end nextstate */
			if (notin(state, n, &prev)) {
				if (n >= NSTATES) {
					dprintf("cgotofn: notin; state = %d, n = %d\n", state, n, NULL);
					overflo();
				}
				state[++n] = add(setcnt);
				dprintf("	delta(%d,%o) = %d", s,c,n);
				dprintf(", ind = %d\n", ind+1, NULL, NULL);
				fatab[++ind] = c;
				fatab[++ind] = n;
				numtrans++;
			}
			else {
				if (prev != 0) {
					dprintf("	delta(%d,%o) = %d", s,c,prev);
					dprintf(", ind = %d\n", ind+1, NULL, NULL);
					fatab[++ind] = c;
					fatab[++ind] = prev;
					numtrans++;
				}
			}
		}
	tenter:
		if ((pfa = (struct fa *) malloc((numtrans + 1) * sizeof(struct fa))) == NULL)
			overflo();
		where[s] = pfa;
		if (finflg)
			pfa->cch = -1;		/* s is a final state */
		else
			pfa->cch = numtrans;
		pfa->st = 0;
		for (i=1, pfa += 1; i<=numtrans; i++, pfa++) {
			pfa->cch = fatab[2*i-1];
			pfa->st = (struct fa *) fatab[2*i];
		}
	}
	for (i=0; i<=n; i++) {
		/* N.b. state[0] == foll[0], not separately allocated */
		if (i>0)
			xfree(state[i]);       /* free state[i] */
		pfa = where[i];
		pfa->st = where[0];
		dprintf("state %d: (%o)\n", i, pfa, NULL);
		dprintf("	numtrans = %d,	default = %o\n", pfa->cch, pfa->st, NULL);
		for (k=1; k<=pfa->cch; k++) {
			(pfa+k)->st = where[ (int) (pfa+k)->st];
			dprintf("	char = %o,	nextstate = %o\n",(pfa+k)->cch, (pfa+k)->st, NULL);
		}
	}
	pfa = where[0];
	if ((num = pfa->cch) < 0)
		return(where[0]);
	for (pfa += num; num; num--, pfa--)
		if (pfa->cch == HAT) {
			return(pfa->st);
		}
	return(where[0]);
}

match(pfa, p)
register struct fa *pfa;
register char *p;
{
	register count;
	char c;
	if (p == 0) return(0);
	if (pfa->cch == 1) {		/* fast test for first character, if possible */
		c = (++pfa)->cch;
		do
			if (c == *p) {
				p++;
				pfa = pfa->st;
				goto adv;
			}
		while (*p++ != 0);
		return(0);
	}
   adv: if ((count = pfa->cch) < 0) return(1);
	do {
		for (pfa += count; count; count--, pfa--)
			if (pfa->cch == *p) {
				break;
			}
		pfa = pfa->st;
		if ((count = pfa->cch) < 0) return(1);
	} while(*p++ != 0);
	return(0);
}

/*
 * Free foll[i], taking into account identical foll[] entries.
 * This is necessary because cfoll() uses the same physical follow set for
 * several foll[] entries when the set is identical.  Called by freetr().
 */
foll_free(i)
int i;
{
	register int j;
	int *p = foll[i];
	if (p==NULL) return;
	for (j=0; j<=maxfoll; j++) 
		if (foll[j]==p) foll[j]=NULL;
	xfree(p);
}
Commit	Line	Data
b803c326	1	#ifndef lint
39a6c341	2	static char sccsid[] = "@(#)b.c 4.3 %G%";
b803c326	3	#endif
8351eafd KM	4
	5	#include "awk.def"
	6	#include "stdio.h"
	7	#include "awk.h"
	8
	9	extern node *op2();
	10	extern struct fa *cgotofn();
	11	#define MAXLIN 256
	12	#define NCHARS 128
	13	#define NSTATES 256
	14
	15	#define type(v) v->nobj
	16	#define left(v) v->narg[0]
	17	#define right(v) v->narg[1]
	18	#define parent(v) v->nnext
	19
	20	#define LEAF case CCL: case NCCL: case CHAR: case DOT:
	21	#define UNARY case FINAL: case STAR: case PLUS: case QUEST:
	22
	23	/* encoding in tree nodes:
	24	leaf (CCL, NCCL, CHAR, DOT): left is index, right contains value or pointer to value
	25	unary (FINAL, STAR, PLUS, QUEST): left is child, right is null
	26	binary (CAT, OR): left and right are children
	27	parent contains pointer to parent
	28	*/
	29
	30	struct fa {
	31	int cch;
	32	struct fa *st;
	33	};
	34
	35	int *state[NSTATES];
	36	int *foll[MAXLIN];
	37	char chars[MAXLIN];
	38	int setvec[MAXLIN];
	39	node *point[MAXLIN];
	40
	41	int setcnt;
	42	int line;
39a6c341	43	int maxfoll; /* index of highest foll[] entry set by cfoll() */
8351eafd KM	44
	45
	46	struct fa makedfa(p) / returns dfa for tree pointed to by p */
	47	node *p;
	48	{
	49	node *p1;
	50	struct fa *fap;
	51	p1 = op2(CAT, op2(STAR, op2(DOT, (node ) 0, (node ) 0), (node *) 0), p);
	52	/* put DOT STAR in front of reg. exp. */
	53	p1 = op2(FINAL, p1, (node ) 0); / install FINAL node */
	54
	55	line = 0;
	56	penter(p1); /* enter parent pointers and leaf indices */
	57	point[line] = p1; /* FINAL node */
	58	setvec[0] = 1; /* for initial DOT STAR */
	59	cfoll(p1); /* set up follow sets */
	60	fap = cgotofn();
	61	freetr(p1); /* add this when alloc works */
	62	return(fap);
	63	}
	64
	65	penter(p) /* set up parent pointers and leaf indices */
	66	node *p;
	67	{
	68	switch(type(p)) {
	69	LEAF
	70	left(p) = (node *) line;
	71	point[line++] = p;
	72	break;
	73	UNARY
	74	penter(left(p));
	75	parent(left(p)) = p;
	76	break;
	77	case CAT:
	78	case OR:
	79	penter(left(p));
	80	penter(right(p));
	81	parent(left(p)) = p;
	82	parent(right(p)) = p;
	83	break;
	84	default:
	85	error(FATAL, "unknown type %d in penter\n", type(p));
	86	break;
	87	}
	88	}
	89
	90	freetr(p) /* free parse tree and follow sets */
	91	node *p;
	92	{
	93	switch(type(p)) {
	94	LEAF
39a6c341	95	foll_free((int) left(p));
8351eafd KM	96	xfree(p);
	97	break;
	98	UNARY
	99	freetr(left(p));
	100	xfree(p);
	101	break;
	102	case CAT:
	103	case OR:
	104	freetr(left(p));
	105	freetr(right(p));
	106	xfree(p);
	107	break;
	108	default:
	109	error(FATAL, "unknown type %d in freetr", type(p));
	110	break;
	111	}
	112	}
	113	char *cclenter(p)
	114	register char *p;
	115	{
	116	register i, c;
	117	char *op;
	118
	119	op = p;
	120	i = 0;
	121	while ((c = *p++) != 0) {
	122	if (c == '-' && i > 0 && chars[i-1] != 0) {
	123	if (*p != 0) {
	124	c = chars[i-1];
	125	while (c < *p) {
	126	if (i >= MAXLIN)
	127	overflo();
	128	chars[i++] = ++c;
	129	}
	130	p++;
	131	continue;
	132	}
	133	}
	134	if (i >= MAXLIN)
	135	overflo();
	136	chars[i++] = c;
	137	}
	138	chars[i++] = '\0';
	139	dprintf("cclenter: in = \|%s\|, out = \|%s\|\n", op, chars, NULL);
	140	xfree(op);
	141	return(tostring(chars));
	142	}
	143
	144	overflo()
	145	{
	146	error(FATAL, "regular expression too long\n");
	147	}
	148
	149	cfoll(v) /* enter follow set of each leaf of vertex v into foll[leaf] */
	150	register node *v;
	151	{
	152	register i;
	153	int prev;
	154	int *add();
	155
39a6c341	156	maxfoll = -1;
8351eafd KM	157	switch(type(v)) {
	158	LEAF
	159	setcnt = 0;
	160	for (i=1; i<=line; i++)
	161	setvec[i] = 0;
	162	follow(v);
	163	if (notin(foll, ( (int) left(v))-1, &prev)) {
	164	foll[(int) left(v)] = add(setcnt);
	165	}
	166	else
	167	foll[ (int) left(v)] = foll[prev];
39a6c341 KM	168	if ((int)left(v) > maxfoll)
39a6c341 KM	169	maxfoll = (int)left(v);
8351eafd KM	170	break;
	171	UNARY
	172	cfoll(left(v));
	173	break;
	174	case CAT:
	175	case OR:
	176	cfoll(left(v));
	177	cfoll(right(v));
	178	break;
	179	default:
	180	error(FATAL, "unknown type %d in cfoll", type(v));
	181	}
	182	}
	183
	184	first(p) /* collects initially active leaves of p into setvec */
	185	register node p; / returns 0 or 1 depending on whether p matches empty string */
	186	{
	187	register b;
	188
	189	switch(type(p)) {
	190	LEAF
	191	if (setvec[(int) left(p)] != 1) {
	192	setvec[(int) left(p)] = 1;
	193	setcnt++;
	194	}
	195	if (type(p) == CCL && ((char ) right(p)) == '\0')
	196	return(0); /* empty CCL */
	197	else return(1);
	198	case FINAL:
	199	case PLUS:
	200	if (first(left(p)) == 0) return(0);
	201	return(1);
	202	case STAR:
	203	case QUEST:
	204	first(left(p));
	205	return(0);
	206	case CAT:
	207	if (first(left(p)) == 0 && first(right(p)) == 0) return(0);
	208	return(1);
	209	case OR:
	210	b = first(right(p));
	211	if (first(left(p)) == 0 \|\| b == 0) return(0);
	212	return(1);
	213	}
	214	error(FATAL, "unknown type %d in first\n", type(p));
	215	return(-1);
	216	}
	217
	218	follow(v)
	219	node v; / collects leaves that can follow v into setvec */
	220	{
	221	node *p;
	222
	223	if (type(v) == FINAL)
	224	return;
	225	p = parent(v);
	226	switch (type(p)) {
	227	case STAR:
	228	case PLUS: first(v);
	229	follow(p);
	230	return;
	231
	232	case OR:
	233	case QUEST: follow(p);
234	return;
235
236	case CAT: if (v == left(p)) { /* v is left child of p */
237	if (first(right(p)) == 0) {
238	follow(p);
239	return;
240	}
241	}
242	else /* v is right child */
243	follow(p);
244	return;
245	case FINAL: if (setvec[line] != 1) {
246	setvec[line] = 1;
247	setcnt++;
248	}
249	return;
250	}
251	}
252
253	member(c, s) /* is c in s? */
254	register char c, *s;
255	{
256	while (*s)
257	if (c == *s++)
258	return(1);
259	return(0);
260	}
261
262	notin(array, n, prev) /* is setvec in array[0] thru array[n]? */
263	int **array;
264	int *prev; {
265	register i, j;
266	int *ptr;
267	for (i=0; i<=n; i++) {
268	ptr = array[i];
269	if (*ptr == setcnt) {
270	for (j=0; j < setcnt; j++)
271	if (setvec[*(++ptr)] != 1) goto nxt;
272	*prev = i;
273	return(0);
274	}
275	nxt: ;
276	}
277	return(1);
278	}
279
280	int add(n) { / remember setvec */
281	int ptr, p;
282	register i;
283	if ((p = ptr = (int ) malloc((n+1)sizeof(int))) == NULL)
284	overflo();
285	*ptr = n;
286	dprintf("add(%d)\n", n, NULL, NULL);
287	for (i=1; i <= line; i++)
288	if (setvec[i] == 1) {
289	*(++ptr) = i;
290	dprintf(" ptr = %o, ptr = %d, i = %d\n", ptr, ptr, i);
291	}
292	dprintf("\n", NULL, NULL, NULL);
293	return(p);
294	}
295
296	struct fa *cgotofn()
297	{
298	register i, k;
299	register int *ptr;
300	char c;
301	char *p;
302	node *cp;
303	int j, n, s, ind, numtrans;
304	int finflg;
305	int curpos, num, prev;
306	struct fa *where[NSTATES];
307
308	int fatab[257];
309	struct fa *pfa;
310
311	char index[MAXLIN];
312	char iposns[MAXLIN];
313	int sposns[MAXLIN];
314	int spmax, spinit;
315
316	char symbol[NCHARS];
317	char isyms[NCHARS];
318	char ssyms[NCHARS];
319	int ssmax, ssinit;
320
321	for (i=0; i<=line; i++) index[i] = iposns[i] = setvec[i] = 0;
322	for (i=0; i<NCHARS; i++) isyms[i] = symbol[i] = 0;
323	setcnt = 0;
324	/* compute initial positions and symbols of state 0 */
325	ssmax = 0;
326	ptr = state[0] = foll[0];
327	spinit = *ptr;
328	for (i=0; i<spinit; i++) {
329	curpos = *(++ptr);
330	sposns[i] = curpos;
331	iposns[curpos] = 1;
332	cp = point[curpos];
333	dprintf("i = %d, spinit = %d, curpos = %d\n", i, spinit, curpos);
334	switch (type(cp)) {
335	case CHAR:
336	k = (int) right(cp);
337	if (isyms[k] != 1) {
338	isyms[k] = 1;
339	ssyms[ssmax++] = k;
340	}
341	break;
342	case DOT:
343	for (k=1; k<NCHARS; k++) {
344	if (k != HAT) {
345	if (isyms[k] != 1) {
346	isyms[k] = 1;
347	ssyms[ssmax++] = k;
348	}
349	}
350	}
351	break;
352	case CCL:
353	for (p = (char ) right(cp); p; p++) {
354	if (*p != HAT) {
355	if (isyms[*p] != 1) {
356	isyms[*p] = 1;
357	ssyms[ssmax++] = *p;
358	}
359	}
360	}
361	break;
362	case NCCL:
363	for (k=1; k<NCHARS; k++) {
364	if (k != HAT && !member(k, (char *) right(cp))) {
365	if (isyms[k] != 1) {
366	isyms[k] = 1;
367	ssyms[ssmax++] = k;
368	}
369	}
370	}
371	}
372	}
373	ssinit = ssmax;
374	n = 0;
375	for (s=0; s<=n; s++) {
376	dprintf("s = %d\n", s, NULL, NULL);
377	ind = 0;
378	numtrans = 0;
379	finflg = 0;
380	if ((state[s] + state[s]) == line) { /* s final? */
381	finflg = 1;
382	goto tenter;
383	}
384	spmax = spinit;
385	ssmax = ssinit;
386	ptr = state[s];
387	num = *ptr;
388	for (i=0; i<num; i++) {
389	curpos = *(++ptr);
390	if (iposns[curpos] != 1 && index[curpos] != 1) {
391	index[curpos] = 1;
392	sposns[spmax++] = curpos;
393	}
394	cp = point[curpos];
395	switch (type(cp)) {
396	case CHAR:
397	k = (int) right(cp);
398	if (isyms[k] == 0 && symbol[k] == 0) {
399	symbol[k] = 1;
400	ssyms[ssmax++] = k;
401	}
402	break;
403	case DOT:
404	for (k=1; k<NCHARS; k++) {
405	if (k != HAT) {
406	if (isyms[k] == 0 && symbol[k] == 0) {
407	symbol[k] = 1;
408	ssyms[ssmax++] = k;
409	}
410	}
411	}
412	break;
413	case CCL:
414	for (p = (char ) right(cp); p; p++) {
415	if (*p != HAT) {
416	if (isyms[p] == 0 && symbol[p] == 0) {
417	symbol[*p] = 1;
418	ssyms[ssmax++] = *p;
419	}
420	}
421	}
422	break;
423	case NCCL:
424	for (k=1; k<NCHARS; k++) {
425	if (k != HAT && !member(k, (char *) right(cp))) {
426	if (isyms[k] == 0 && symbol[k] == 0) {
427	symbol[k] = 1;
428	ssyms[ssmax++] = k;
429	}
430	}
431	}
432	}
433	}
434	for (j=0; j<ssmax; j++) { /* nextstate(s, ssyms[j]) */
435	c = ssyms[j];
436	symbol[c] = 0;
437	setcnt = 0;
438	for (k=0; k<=line; k++) setvec[k] = 0;
439	for (i=0; i<spmax; i++) {
440	index[sposns[i]] = 0;
441	cp = point[sposns[i]];
442	if ((k = type(cp)) != FINAL)
443	if (k == CHAR && c == (int) right(cp)
444	\|\| k == DOT
445	\|\| k == CCL && member(c, (char *) right(cp))
446	\|\| k == NCCL && !member(c, (char *) right(cp))) {
447	ptr = foll[sposns[i]];
448	num = *ptr;
449	for (k=0; k<num; k++) {
450	if (setvec[*(++ptr)] != 1
451	&& iposns[*ptr] != 1) {
452	setvec[*ptr] = 1;
453	setcnt++;
454	}
455	}
456	}
457	} /* end nextstate */
458	if (notin(state, n, &prev)) {
459	if (n >= NSTATES) {
460	dprintf("cgotofn: notin; state = %d, n = %d\n", state, n, NULL);
461	overflo();
462	}
463	state[++n] = add(setcnt);
464	dprintf(" delta(%d,%o) = %d", s,c,n);
465	dprintf(", ind = %d\n", ind+1, NULL, NULL);
466	fatab[++ind] = c;
467	fatab[++ind] = n;
468	numtrans++;
469	}
470	else {
471	if (prev != 0) {
472	dprintf(" delta(%d,%o) = %d", s,c,prev);
473	dprintf(", ind = %d\n", ind+1, NULL, NULL);
474	fatab[++ind] = c;
475	fatab[++ind] = prev;
476	numtrans++;
477	}
478	}
479	}
480	tenter:
481	if ((pfa = (struct fa ) malloc((numtrans + 1) sizeof(struct fa))) == NULL)
482	overflo();
483	where[s] = pfa;
484	if (finflg)
485	pfa->cch = -1; /* s is a final state */
486	else
487	pfa->cch = numtrans;
488	pfa->st = 0;
489	for (i=1, pfa += 1; i<=numtrans; i++, pfa++) {
490	pfa->cch = fatab[2*i-1];
491	pfa->st = (struct fa ) fatab[2i];
492	}
493	}
494	for (i=0; i<=n; i++) {
39a6c341 KM	495	/* N.b. state[0] == foll[0], not separately allocated */
	496	if (i>0)
	497	xfree(state[i]); /* free state[i] */
8351eafd KM	498	pfa = where[i];
	499	pfa->st = where[0];
	500	dprintf("state %d: (%o)\n", i, pfa, NULL);
	501	dprintf(" numtrans = %d, default = %o\n", pfa->cch, pfa->st, NULL);
	502	for (k=1; k<=pfa->cch; k++) {
	503	(pfa+k)->st = where[ (int) (pfa+k)->st];
	504	dprintf(" char = %o, nextstate = %o\n",(pfa+k)->cch, (pfa+k)->st, NULL);
	505	}
	506	}
	507	pfa = where[0];
	508	if ((num = pfa->cch) < 0)
	509	return(where[0]);
	510	for (pfa += num; num; num--, pfa--)
	511	if (pfa->cch == HAT) {
	512	return(pfa->st);
	513	}
	514	return(where[0]);
	515	}
	516
	517	match(pfa, p)
	518	register struct fa *pfa;
	519	register char *p;
	520	{
	521	register count;
	522	char c;
	523	if (p == 0) return(0);
	524	if (pfa->cch == 1) { /* fast test for first character, if possible */
	525	c = (++pfa)->cch;
	526	do
	527	if (c == *p) {
	528	p++;
	529	pfa = pfa->st;
	530	goto adv;
	531	}
	532	while (*p++ != 0);
	533	return(0);
	534	}
	535	adv: if ((count = pfa->cch) < 0) return(1);
	536	do {
	537	for (pfa += count; count; count--, pfa--)
	538	if (pfa->cch == *p) {
	539	break;
	540	}
	541	pfa = pfa->st;
	542	if ((count = pfa->cch) < 0) return(1);
	543	} while(*p++ != 0);
	544	return(0);
	545	}
39a6c341 KM	546
	547	/*
	548	* Free foll[i], taking into account identical foll[] entries.
	549	* This is necessary because cfoll() uses the same physical follow set for
	550	* several foll[] entries when the set is identical. Called by freetr().
	551	*/
	552	foll_free(i)
	553	int i;
	554	{
	555	register int j;
	556	int *p = foll[i];
	557	if (p==NULL) return;
	558	for (j=0; j<=maxfoll; j++)
	559	if (foll[j]==p) foll[j]=NULL;
	560	xfree(p);
	561	}