dfa.c

操作系统源代码

	     */
	    num_full_table_rows = numecs + 1;

	/* declare it "short" because it's a real long-shot that that
	 * won't be large enough.
	 */
	printf( "static short int yy_nxt[][%d] =\n    {\n",
		/* '}' so vi doesn't get too confused */
		num_full_table_rows );

	/* generate 0 entries for state #0 */
	for ( i = 0; i < num_full_table_rows; ++i )
	    mk2data( 0 );

	/* force ',' and dataflush() next call to mk2data */
	datapos = NUMDATAITEMS;

	/* force extra blank line next dataflush() */
	dataline = NUMDATALINES;
	}

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

	numsnpairs = numsnpairs + totaltrans;

	if ( caseins && ! useecs )
	    {
	    register int j;

	    for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j )
		state[i] = state[j];
	    }

	if ( ds > num_start_states )
	    check_for_backtracking( ds, state );

	if ( nultrans )
	    {
	    nultrans[ds] = state[NUL_ec];
	    state[NUL_ec] = 0;	/* remove transition */
	    }

	if ( fulltbl )
	    {
	    /* 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 );

	    /* force ',' and dataflush() next call to mk2data */
	    datapos = NUMDATAITEMS;

	    /* force extra blank line next dataflush() */
	    dataline = NUMDATALINES;
	    }

        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();
	}
    }


/* snstods - converts a set of ndfa states into a dfa state
 *
 * synopsis
 *    int sns[numstates], numstates, newds, accset[num_rules + 1], nacc, hashval;
 *    int snstods();
 *    is_new_state = snstods( sns, numstates, accset, nacc, hashval, &newds );
 *
 * 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] = (int *) malloc( (unsigned) ((numstates + 1) * sizeof( int )) );

    if ( ! dss[newds] )
	flexfatal( "dynamic memory failure in snstods()" );

    /* 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 =
	    (int *) malloc( (unsigned) ((nacc + 1) * sizeof( int )) );

	if ( ! dfaacc[newds].dfaacc_set )
	    flexfatal( "dynamic memory failure in snstods()" );

	/* save the accepting set for later */
	for ( i = 1; i <= nacc; ++i )
	    dfaacc[newds].dfaacc_set[i] = accset[i];

	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;
	}

    *newds_addr = newds;

    return ( 1 );
    }


/* symfollowset - follow the symbol transitions one step
 *
 * synopsis
 *    int ds[current_max_dfa_size], dsize, transsym;
 *    int nset[current_max_dfa_size], numstates;
 *    numstates = symfollowset( ds, dsize, transsym, nset );
 */

int symfollowset( ds, dsize, transsym, nset )
int ds[], dsize, transsym, nset[];

    {
    int ns, tsp, sym, i, j, lenccl, ch, numstates;
    int 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 )
			break;	/* transsym isn't in negated ccl */

		    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
 *    integer ds[current_max_dfa_size], numstates, duplist[numecs];
 *    symlist[numecs];
 *    sympartition( ds, numstates, symlist, duplist );
 */

void sympartition( ds, numstates, symlist, duplist )
int ds[], numstates, duplist[];
int symlist[];

    {
    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 )
		{
		if ( tch > csize && tch <= CSIZE )
		    flexerror( "scanner requires -8 flag" );

		else
		    flexfatal(
			"bad transition character detected in sympartition()" );
		}

	    if ( tch >= 0 )
		{ /* character transition */
		/* abs() needed for fake %t ec's */
		int ec = abs( 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;
			}
		}
	    }
	}
    }