regc_nfa.c

来自「A*算法 A*算法 A*算法 A*算法A*算法A*算法」· C语言 代码 · 共 1,583 行 · 第 1/3 页

int type;
{
	struct arc *a;

	assert(old != from);

	for (a = old->outs; a != NULL; a = a->outchain)
		newarc(nfa, type, a->co, from, to);
}

/*
 - delsub - delete a sub-NFA, updating subre pointers if necessary
 * This uses a recursive traversal of the sub-NFA, marking already-seen
 * states using their tmp pointer.
 ^ static VOID delsub(struct nfa *, struct state *, struct state *);
 */
static VOID
delsub(nfa, lp, rp)
struct nfa *nfa;
struct state *lp;	/* the sub-NFA goes from here... */
struct state *rp;	/* ...to here, *not* inclusive */
{
	assert(lp != rp);

	rp->tmp = rp;			/* mark end */

	deltraverse(nfa, lp, lp);
	assert(lp->nouts == 0 && rp->nins == 0);	/* did the job */
	assert(lp->no != FREESTATE && rp->no != FREESTATE);	/* no more */

	rp->tmp = NULL;			/* unmark end */
	lp->tmp = NULL;			/* and begin, marked by deltraverse */
}

/*
 - deltraverse - the recursive heart of delsub
 * This routine's basic job is to destroy all out-arcs of the state.
 ^ static VOID deltraverse(struct nfa *, struct state *, struct state *);
 */
static VOID
deltraverse(nfa, leftend, s)
struct nfa *nfa;
struct state *leftend;
struct state *s;
{
	struct arc *a;
	struct state *to;

	if (s->nouts == 0)
		return;			/* nothing to do */
	if (s->tmp != NULL)
		return;			/* already in progress */

	s->tmp = s;			/* mark as in progress */

	while ((a = s->outs) != NULL) {
		to = a->to;
		deltraverse(nfa, leftend, to);
		assert(to->nouts == 0 || to->tmp != NULL);
		freearc(nfa, a);
		if (to->nins == 0 && to->tmp == NULL) {
			assert(to->nouts == 0);
			freestate(nfa, to);
		}
	}

	assert(s->no != FREESTATE);	/* we're still here */
	assert(s == leftend || s->nins != 0);	/* and still reachable */
	assert(s->nouts == 0);		/* but have no outarcs */

	s->tmp = NULL;			/* we're done here */
}

/*
 - dupnfa - duplicate sub-NFA
 * Another recursive traversal, this time using tmp to point to duplicates
 * as well as mark already-seen states.  (You knew there was a reason why
 * it's a state pointer, didn't you? :-))
 ^ static VOID dupnfa(struct nfa *, struct state *, struct state *, 
 ^ 	struct state *, struct state *);
 */
static VOID
dupnfa(nfa, start, stop, from, to)
struct nfa *nfa;
struct state *start;		/* duplicate of subNFA starting here */
struct state *stop;		/* and stopping here */
struct state *from;		/* stringing duplicate from here */
struct state *to;		/* to here */
{
	if (start == stop) {
		newarc(nfa, EMPTY, 0, from, to);
		return;
	}

	stop->tmp = to;
	duptraverse(nfa, start, from);
	/* done, except for clearing out the tmp pointers */

	stop->tmp = NULL;
	cleartraverse(nfa, start);
}

/*
 - duptraverse - recursive heart of dupnfa
 ^ static VOID duptraverse(struct nfa *, struct state *, struct state *);
 */
static VOID
duptraverse(nfa, s, stmp)
struct nfa *nfa;
struct state *s;
struct state *stmp;		/* s's duplicate, or NULL */
{
	struct arc *a;

	if (s->tmp != NULL)
		return;		/* already done */

	s->tmp = (stmp == NULL) ? newstate(nfa) : stmp;
	if (s->tmp == NULL) {
		assert(NISERR());
		return;
	}

	for (a = s->outs; a != NULL && !NISERR(); a = a->outchain) {
		duptraverse(nfa, a->to, (struct state *)NULL);
		assert(a->to->tmp != NULL);
		cparc(nfa, a, s->tmp, a->to->tmp);
	}
}

/*
 - cleartraverse - recursive cleanup for algorithms that leave tmp ptrs set
 ^ static VOID cleartraverse(struct nfa *, struct state *);
 */
static VOID
cleartraverse(nfa, s)
struct nfa *nfa;
struct state *s;
{
	struct arc *a;

	if (s->tmp == NULL)
		return;
	s->tmp = NULL;

	for (a = s->outs; a != NULL; a = a->outchain)
		cleartraverse(nfa, a->to);
}

/*
 - specialcolors - fill in special colors for an NFA
 ^ static VOID specialcolors(struct nfa *);
 */
static VOID
specialcolors(nfa)
struct nfa *nfa;
{
	/* false colors for BOS, BOL, EOS, EOL */
	if (nfa->parent == NULL) {
		nfa->bos[0] = pseudocolor(nfa->cm);
		nfa->bos[1] = pseudocolor(nfa->cm);
		nfa->eos[0] = pseudocolor(nfa->cm);
		nfa->eos[1] = pseudocolor(nfa->cm);
	} else {
		assert(nfa->parent->bos[0] != COLORLESS);
		nfa->bos[0] = nfa->parent->bos[0];
		assert(nfa->parent->bos[1] != COLORLESS);
		nfa->bos[1] = nfa->parent->bos[1];
		assert(nfa->parent->eos[0] != COLORLESS);
		nfa->eos[0] = nfa->parent->eos[0];
		assert(nfa->parent->eos[1] != COLORLESS);
		nfa->eos[1] = nfa->parent->eos[1];
	}
}

/*
 - optimize - optimize an NFA
 ^ static long optimize(struct nfa *, FILE *);
 */
static long			/* re_info bits */
optimize(nfa, f)
struct nfa *nfa;
FILE *f;			/* for debug output; NULL none */
{
	int verbose = (f != NULL) ? 1 : 0;

	if (verbose)
		fprintf(f, "\ninitial cleanup:\n");
	cleanup(nfa);		/* may simplify situation */
	if (verbose)
		dumpnfa(nfa, f);
	if (verbose)
		fprintf(f, "\nempties:\n");
	fixempties(nfa, f);	/* get rid of EMPTY arcs */
	if (verbose)
		fprintf(f, "\nconstraints:\n");
	pullback(nfa, f);	/* pull back constraints backward */
	pushfwd(nfa, f);	/* push fwd constraints forward */
	if (verbose)
		fprintf(f, "\nfinal cleanup:\n");
	cleanup(nfa);		/* final tidying */
	return analyze(nfa);	/* and analysis */
}

/*
 - pullback - pull back constraints backward to (with luck) eliminate them
 ^ static VOID pullback(struct nfa *, FILE *);
 */
static VOID
pullback(nfa, f)
struct nfa *nfa;
FILE *f;			/* for debug output; NULL none */
{
	struct state *s;
	struct state *nexts;
	struct arc *a;
	struct arc *nexta;
	int progress;

	/* find and pull until there are no more */
	do {
		progress = 0;
		for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
			nexts = s->next;
			for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
				nexta = a->outchain;
				if (a->type == '^' || a->type == BEHIND)
					if (pull(nfa, a))
						progress = 1;
				assert(nexta == NULL || s->no != FREESTATE);
			}
		}
		if (progress && f != NULL)
			dumpnfa(nfa, f);
	} while (progress && !NISERR());
	if (NISERR())
		return;

	for (a = nfa->pre->outs; a != NULL; a = nexta) {
		nexta = a->outchain;
		if (a->type == '^') {
			assert(a->co == 0 || a->co == 1);
			newarc(nfa, PLAIN, nfa->bos[a->co], a->from, a->to);
			freearc(nfa, a);
		}
	}
}

/*
 - pull - pull a back constraint backward past its source state
 * A significant property of this function is that it deletes at most
 * one state -- the constraint's from state -- and only if the constraint
 * was that state's last outarc.
 ^ static int pull(struct nfa *, struct arc *);
 */
static int			/* 0 couldn't, 1 could */
pull(nfa, con)
struct nfa *nfa;
struct arc *con;
{
	struct state *from = con->from;
	struct state *to = con->to;
	struct arc *a;
	struct arc *nexta;
	struct state *s;

	if (from == to) {	/* circular constraint is pointless */
		freearc(nfa, con);
		return 1;
	}
	if (from->flag)		/* can't pull back beyond start */
		return 0;
	if (from->nins == 0) {	/* unreachable */
		freearc(nfa, con);
		return 1;
	}

	/* first, clone from state if necessary to avoid other outarcs */
	if (from->nouts > 1) {
		s = newstate(nfa);
		if (NISERR())
			return 0;
		assert(to != from);		/* con is not an inarc */
		copyins(nfa, from, s);		/* duplicate inarcs */
		cparc(nfa, con, s, to);		/* move constraint arc */
		freearc(nfa, con);
		from = s;
		con = from->outs;
	}
	assert(from->nouts == 1);

	/* propagate the constraint into the from state's inarcs */
	for (a = from->ins; a != NULL; a = nexta) {
		nexta = a->inchain;
		switch (combine(con, a)) {
		case INCOMPATIBLE:	/* destroy the arc */
			freearc(nfa, a);
			break;
		case SATISFIED:		/* no action needed */
			break;
		case COMPATIBLE:	/* swap the two arcs, more or less */
			s = newstate(nfa);
			if (NISERR())
				return 0;
			cparc(nfa, a, s, to);		/* anticipate move */
			cparc(nfa, con, a->from, s);
			if (NISERR())
				return 0;
			freearc(nfa, a);
			break;
		default:
			assert(NOTREACHED);
			break;
		}
	}

	/* remaining inarcs, if any, incorporate the constraint */
	moveins(nfa, from, to);
	dropstate(nfa, from);		/* will free the constraint */
	return 1;
}

/*
 - pushfwd - push forward constraints forward to (with luck) eliminate them
 ^ static VOID pushfwd(struct nfa *, FILE *);
 */
static VOID
pushfwd(nfa, f)
struct nfa *nfa;
FILE *f;			/* for debug output; NULL none */
{
	struct state *s;
	struct state *nexts;
	struct arc *a;
	struct arc *nexta;
	int progress;

	/* find and push until there are no more */
	do {
		progress = 0;
		for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
			nexts = s->next;
			for (a = s->ins; a != NULL && !NISERR(); a = nexta) {
				nexta = a->inchain;
				if (a->type == '$' || a->type == AHEAD)
					if (push(nfa, a))
						progress = 1;
				assert(nexta == NULL || s->no != FREESTATE);
			}
		}
		if (progress && f != NULL)
			dumpnfa(nfa, f);
	} while (progress && !NISERR());
	if (NISERR())
		return;

	for (a = nfa->post->ins; a != NULL; a = nexta) {
		nexta = a->inchain;
		if (a->type == '$') {
			assert(a->co == 0 || a->co == 1);
			newarc(nfa, PLAIN, nfa->eos[a->co], a->from, a->to);
			freearc(nfa, a);
		}
	}
}

/*
 - push - push a forward constraint forward past its destination state
 * A significant property of this function is that it deletes at most
 * one state -- the constraint's to state -- and only if the constraint
 * was that state's last inarc.
 ^ static int push(struct nfa *, struct arc *);
 */
static int			/* 0 couldn't, 1 could */
push(nfa, con)
struct nfa *nfa;
struct arc *con;
{
	struct state *from = con->from;
	struct state *to = con->to;
	struct arc *a;
	struct arc *nexta;
	struct state *s;

	if (to == from) {	/* circular constraint is pointless */
		freearc(nfa, con);
		return 1;
	}
	if (to->flag)		/* can't push forward beyond end */
		return 0;
	if (to->nouts == 0) {	/* dead end */
		freearc(nfa, con);
		return 1;
	}

	/* first, clone to state if necessary to avoid other inarcs */
	if (to->nins > 1) {
		s = newstate(nfa);
		if (NISERR())
			return 0;
		copyouts(nfa, to, s);		/* duplicate outarcs */
		cparc(nfa, con, from, s);	/* move constraint */
		freearc(nfa, con);
		to = s;
		con = to->ins;
	}
	assert(to->nins == 1);

	/* propagate the constraint into the to state's outarcs */
	for (a = to->outs; a != NULL; a = nexta) {
		nexta = a->outchain;
		switch (combine(con, a)) {
		case INCOMPATIBLE:	/* destroy the arc */
			freearc(nfa, a);
			break;
		case SATISFIED:		/* no action needed */
			break;
		case COMPATIBLE:	/* swap the two arcs, more or less */
			s = newstate(nfa);
			if (NISERR())
				return 0;
			cparc(nfa, con, s, a->to);	/* anticipate move */
			cparc(nfa, a, from, s);
			if (NISERR())
				return 0;
			freearc(nfa, a);
			break;
		default:
			assert(NOTREACHED);
			break;
		}
	}

	/* remaining outarcs, if any, incorporate the constraint */
	moveouts(nfa, to, from);
	dropstate(nfa, to);		/* will free the constraint */
	return 1;
}

/*
 - combine - constraint lands on an arc, what happens?
 ^ #def	INCOMPATIBLE	1	// destroys arc
 ^ #def	SATISFIED	2	// constraint satisfied
 ^ #def	COMPATIBLE	3	// compatible but not satisfied yet
 ^ static int combine(struct arc *, struct arc *);
 */
 
/* FIXME Required for CW 8 on Mac since it's not in limits.h */
#ifndef __CHAR_BIT__
#define __CHAR_BIT__ 8
#endif

 
static int
combine(con, a)
struct arc *con;
struct arc *a;
{
#	define	CA(ct,at)	(((ct)<<CHAR_BIT) | (at))

	switch (CA(con->type, a->type)) {
	case CA('^', PLAIN):		/* newlines are handled separately */
	case CA('$', PLAIN):
		return INCOMPATIBLE;
		break;
	case CA(AHEAD, PLAIN):		/* color constraints meet colors */
	case CA(BEHIND, PLAIN):
		if (con->co == a->co)
			return SATISFIED;
		return INCOMPATIBLE;
		break;
	case CA('^', '^'):		/* collision, similar constraints */
	case CA('$', '$'):
	case CA(AHEAD, AHEAD):
	case CA(BEHIND, BEHIND):
		if (con->co == a->co)		/* true duplication */
			return SATISFIED;
		return INCOMPATIBLE;
		break;
	case CA('^', BEHIND):		/* collision, dissimilar constraints */
	case CA(BEHIND, '^'):
	case CA('$', AHEAD):
	case CA(AHEAD, '$'):
		return INCOMPATIBLE;
		break;
	case CA('^', '$'):		/* constraints passing each other */
	case CA('^', AHEAD):
	case CA(BEHIND, '$'):
	case CA(BEHIND, AHEAD):
	case CA('$', '^'):
	case CA('$', BEHIND):
	case CA(AHEAD, '^'):
	case CA(AHEAD, BEHIND):
	case CA('^', LACON):
	case CA(BEHIND, LACON):
	case CA('$', LACON):
	case CA(AHEAD, LACON):
		return COMPATIBLE;
		break;
	}
	assert(NOTREACHED);
	return INCOMPATIBLE;		/* for benefit of blind compilers */
}

/*
 - fixempties - get rid of EMPTY arcs
 ^ static VOID fixempties(struct nfa *, FILE *);
 */
static VOID
fixempties(nfa, f)
struct nfa *nfa;
FILE *f;			/* for debug output; NULL none */
{
	struct state *s;
	struct state *nexts;
	struct arc *a;
	struct arc *nexta;
	int progress;

	/* find and eliminate empties until there are no more */
	do {
		progress = 0;
		for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
			nexts = s->next;
			for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
				nexta = a->outchain;
				if (a->type == EMPTY && unempty(nfa, a))
					progress = 1;