/* Create the first states. */	num_start_states = lastsc * 2;	for ( i = 1; i <= num_start_states; ++i )		{		numstates = 1;		/* For each start condition, make one state for the case when		 * we're at the beginning of the line (the '^' operator) and		 * one for the case when we're not.		 */		if ( i % 2 == 1 )			nset[numstates] = scset[(i / 2) + 1];		else			nset[numstates] =				mkbranch( scbol[i / 2], scset[i / 2] );		nset = epsclosure( nset, &numstates, accset, &nacc, &hashval );		if ( snstods( nset, numstates, accset, nacc, hashval, &ds ) )			{			numas += nacc;			totnst += numstates;			++todo_next;			if ( variable_trailing_context_rules && nacc > 0 )				check_trailing_context( nset, numstates,							accset, nacc );			}		}	if ( ! fullspd )		{		if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) )			flexfatal(			_( "could not create unique end-of-buffer state" ) );		++numas;		++num_start_states;		++todo_next;		}	while ( todo_head < todo_next )		{		targptr = 0;		totaltrans = 0;		for ( i = 1; i <= numecs; ++i )			state[i] = 0;		ds = ++todo_head;		dset = dss[ds];		dsize = dfasiz[ds];		if ( trace )			fprintf( stderr, _( "state # %d:\n" ), ds );		sympartition( dset, dsize, symlist, duplist );		for ( sym = 1; sym <= numecs; ++sym )			{			if ( symlist[sym] )				{				symlist[sym] = 0;				if ( duplist[sym] == NIL )					{					/* Symbol has unique out-transitions. */					numstates = symfollowset( dset, dsize,								sym, nset );					nset = epsclosure( nset, &numstates,						accset, &nacc, &hashval );					if ( snstods( nset, numstates, accset,						nacc, hashval, &newds ) )						{						totnst = totnst + numstates;						++todo_next;						numas += nacc;						if (					variable_trailing_context_rules &&							nacc > 0 )							check_trailing_context(								nset, numstates,								accset, nacc );						}					state[sym] = newds;					if ( trace )						fprintf( stderr, "\t%d\t%d\n",							sym, newds );					targfreq[++targptr] = 1;					targstate[targptr] = newds;					++numuniq;					}				else					{					/* sym's equivalence class has the same					 * transitions as duplist(sym)'s					 * equivalence class.					 */					targ = state[duplist[sym]];					state[sym] = targ;					if ( trace )						fprintf( stderr, "\t%d\t%d\n",							sym, targ );					/* Update frequency count for					 * destination state.					 */					i = 0;					while ( targstate[++i] != targ )						;					++targfreq[i];					++numdup;					}				++totaltrans;				duplist[sym] = NIL;				}			}		if ( caseins && ! useecs )			{			register int j;			for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j )				{				if ( state[i] == 0 && state[j] != 0 )					/* We're adding a transition. */					++totaltrans;				else if ( state[i] != 0 && state[j] == 0 )					/* We're taking away a transition. */					--totaltrans;				state[i] = state[j];				}			}		numsnpairs += totaltrans;		if ( ds > num_start_states )			check_for_backing_up( ds, state );		if ( nultrans )			{			nultrans[ds] = state[NUL_ec];			state[NUL_ec] = 0;	/* remove transition */			}		if ( fulltbl )			{			outn( "    {" );			/* Supply array's 0-element. */			if ( ds == end_of_buffer_state )				mk2data( -end_of_buffer_state );			else				mk2data( end_of_buffer_state );			for ( i = 1; i < num_full_table_rows; ++i )				/* Jams are marked by negative of state				 * number.				 */				mk2data( state[i] ? state[i] : -ds );			dataflush();			outn( "    },\n" );			}		else if ( fullspd )			place_state( state, ds, totaltrans );		else if ( ds == end_of_buffer_state )			/* Special case this state to make sure it does what			 * it's supposed to, i.e., jam on end-of-buffer.			 */			stack1( ds, 0, 0, JAMSTATE );		else /* normal, compressed state */			{			/* Determine which destination state is the most			 * common, and how many transitions to it there are.			 */			comfreq = 0;			comstate = 0;			for ( i = 1; i <= targptr; ++i )				if ( targfreq[i] > comfreq )					{					comfreq = targfreq[i];					comstate = targstate[i];					}			bldtbl( state, ds, totaltrans, comstate, comfreq );			}		}	if ( fulltbl )		dataend();	else if ( ! fullspd )		{		cmptmps();  /* create compressed template entries */		/* Create tables for all the states with only one		 * out-transition.		 */		while ( onesp > 0 )			{			mk1tbl( onestate[onesp], onesym[onesp], onenext[onesp],			onedef[onesp] );			--onesp;			}		mkdeftbl();		}	flex_free( (void *) accset );	flex_free( (void *) nset );	}/* snstods - converts a set of ndfa states into a dfa state * * synopsis *    is_new_state = snstods( int sns[numstates], int numstates, *				int accset[num_rules+1], int nacc, *				int hashval, int *newds_addr ); * * On return, the dfa state number is in newds. */int snstods( sns, numstates, accset, nacc, hashval, newds_addr )int sns[], numstates, accset[], nacc, hashval, *newds_addr;	{	int didsort = 0;	register int i, j;	int newds, *oldsns;	for ( i = 1; i <= lastdfa; ++i )		if ( hashval == dhash[i] )			{			if ( numstates == dfasiz[i] )				{				oldsns = dss[i];				if ( ! didsort )					{					/* We sort the states in sns so we					 * can compare it to oldsns quickly.					 * We use bubble because there probably					 * aren't very many states.					 */					bubble( sns, numstates );					didsort = 1;					}				for ( j = 1; j <= numstates; ++j )					if ( sns[j] != oldsns[j] )						break;				if ( j > numstates )					{					++dfaeql;					*newds_addr = i;					return 0;					}				++hshcol;				}			else				++hshsave;			}	/* Make a new dfa. */	if ( ++lastdfa >= current_max_dfas )		increase_max_dfas();	newds = lastdfa;	dss[newds] = allocate_integer_array( numstates + 1 );	/* If we haven't already sorted the states in sns, we do so now,	 * so that future comparisons with it can be made quickly.	 */	if ( ! didsort )		bubble( sns, numstates );	for ( i = 1; i <= numstates; ++i )		dss[newds][i] = sns[i];	dfasiz[newds] = numstates;	dhash[newds] = hashval;	if ( nacc == 0 )		{		if ( reject )			dfaacc[newds].dfaacc_set = (int *) 0;		else			dfaacc[newds].dfaacc_state = 0;		accsiz[newds] = 0;		}	else if ( reject )		{		/* We sort the accepting set in increasing order so the		 * disambiguating rule that the first rule listed is considered		 * match in the event of ties will work.  We use a bubble		 * sort since the list is probably quite small.		 */		bubble( accset, nacc );		dfaacc[newds].dfaacc_set = allocate_integer_array( nacc + 1 );		/* Save the accepting set for later */		for ( i = 1; i <= nacc; ++i )			{			dfaacc[newds].dfaacc_set[i] = accset[i];			if ( accset[i] <= num_rules )				/* Who knows, perhaps a REJECT can yield				 * this rule.				 */				rule_useful[accset[i]] = true;			}		accsiz[newds] = nacc;		}	else		{		/* Find lowest numbered rule so the disambiguating rule		 * will work.		 */		j = num_rules + 1;		for ( i = 1; i <= nacc; ++i )			if ( accset[i] < j )				j = accset[i];		dfaacc[newds].dfaacc_state = j;		if ( j <= num_rules )			rule_useful[j] = true;		}	*newds_addr = newds;	return 1;	}/* symfollowset - follow the symbol transitions one step * * synopsis *    numstates = symfollowset( int ds[current_max_dfa_size], int dsize, *				int transsym, int nset[current_max_dfa_size] ); */int symfollowset( ds, dsize, transsym, nset )int ds[], dsize, transsym, nset[];	{	int ns, tsp, sym, i, j, lenccl, ch, numstates, ccllist;	numstates = 0;	for ( i = 1; i <= dsize; ++i )		{ /* for each nfa state ns in the state set of ds */		ns = ds[i];		sym = transchar[ns];		tsp = trans1[ns];		if ( sym < 0 )			{ /* it's a character class */			sym = -sym;			ccllist = cclmap[sym];			lenccl = ccllen[sym];			if ( cclng[sym] )				{				for ( j = 0; j < lenccl; ++j )					{					/* Loop through negated character					 * class.					 */					ch = ccltbl[ccllist + j];					if ( ch == 0 )						ch = NUL_ec;					if ( ch > transsym )						/* Transsym isn't in negated						 * ccl.						 */						break;					else if ( ch == transsym )						/* next 2 */ goto bottom;					}				/* Didn't find transsym in ccl. */				nset[++numstates] = tsp;				}			else				for ( j = 0; j < lenccl; ++j )					{					ch = ccltbl[ccllist + j];					if ( ch == 0 )						ch = NUL_ec;					if ( ch > transsym )						break;					else if ( ch == transsym )						{						nset[++numstates] = tsp;						break;						}					}			}		else if ( sym >= 'A' && sym <= 'Z' && caseins )			flexfatal(			_( "consistency check failed in symfollowset" ) );		else if ( sym == SYM_EPSILON )			{ /* do nothing */			}		else if ( ABS( ecgroup[sym] ) == transsym )			nset[++numstates] = tsp;		bottom: ;		}	return numstates;	}/* sympartition - partition characters with same out-transitions * * synopsis *    sympartition( int ds[current_max_dfa_size], int numstates, *			int symlist[numecs], int duplist[numecs] ); */void sympartition( ds, numstates, symlist, duplist )int ds[], numstates;int symlist[], duplist[];	{	int tch, i, j, k, ns, dupfwd[CSIZE + 1], lenccl, cclp, ich;	/* Partitioning is done by creating equivalence classes for those	 * characters which have out-transitions from the given state.  Thus	 * we are really creating equivalence classes of equivalence classes.	 */	for ( i = 1; i <= numecs; ++i )		{ /* initialize equivalence class list */		duplist[i] = i - 1;		dupfwd[i] = i + 1;		}	duplist[1] = NIL;	dupfwd[numecs] = NIL;	for ( i = 1; i <= numstates; ++i )		{		ns = ds[i];		tch = transchar[ns];		if ( tch != SYM_EPSILON )			{			if ( tch < -lastccl || tch >= csize )				{				flexfatal(		_( "bad transition character detected in sympartition()" ) );				}			if ( tch >= 0 )				{ /* character transition */				int ec = ecgroup[tch];				mkechar( ec, dupfwd, duplist );				symlist[ec] = 1;				}			else				{ /* character class */				tch = -tch;				lenccl = ccllen[tch];				cclp = cclmap[tch];				mkeccl( ccltbl + cclp, lenccl, dupfwd,					duplist, numecs, NUL_ec );				if ( cclng[tch] )					{					j = 0;					for ( k = 0; k < lenccl; ++k )						{						ich = ccltbl[cclp + k];						if ( ich == 0 )							ich = NUL_ec;						for ( ++j; j < ich; ++j )							symlist[j] = 1;						}					for ( ++j; j <= numecs; ++j )						symlist[j] = 1;					}				else					for ( k = 0; k < lenccl; ++k )						{						ich = ccltbl[cclp + k];						if ( ich == 0 )							ich = NUL_ec;						symlist[ich] = 1;						}				}			}		}	}