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

#ifndef lint
static char sccsid[] = "@(#)b.c	4.2 %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;


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
			xfree(foll[(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();

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