nfa.c

操作系统源代码

 *
 *     branch - a machine which matches either first's pattern or second's
 *     first, second - machines whose patterns are to be or'ed (the | operator)
 *
 * note that first and second are NEITHER destroyed by the operation.  Also,
 * the resulting machine CANNOT be used with any other "mk" operation except
 * more mkbranch's.  Compare with mkor()
 */

int mkbranch( first, second )
int first, second;

    {
    int eps;

    if ( first == NO_TRANSITION )
	return ( second );

    else if ( second == NO_TRANSITION )
	return ( first );

    eps = mkstate( SYM_EPSILON );

    mkxtion( eps, first );
    mkxtion( eps, second );

    return ( eps );
    }


/* mkclos - convert a machine into a closure
 *
 * synopsis
 *   new = mkclos( state );
 *
 *     new - a new state which matches the closure of "state"
 */

int mkclos( state )
int state;

    {
    return ( mkopt( mkposcl( state ) ) );
    }


/* mkopt - make a machine optional
 *
 * synopsis
 *
 *   new = mkopt( mach );
 *
 *     new  - a machine which optionally matches whatever mach matched
 *     mach - the machine to make optional
 *
 * notes:
 *     1. mach must be the last machine created
 *     2. mach is destroyed by the call
 */

int mkopt( mach )
int mach;

    {
    int eps;

    if ( ! SUPER_FREE_EPSILON(finalst[mach]) )
	{
	eps = mkstate( SYM_EPSILON );
	mach = link_machines( mach, eps );
	}

    /* can't skimp on the following if FREE_EPSILON(mach) is true because
     * some state interior to "mach" might point back to the beginning
     * for a closure
     */
    eps = mkstate( SYM_EPSILON );
    mach = link_machines( eps, mach );

    mkxtion( mach, finalst[mach] );

    return ( mach );
    }


/* mkor - make a machine that matches either one of two machines
 *
 * synopsis
 *
 *   new = mkor( first, second );
 *
 *     new - a machine which matches either first's pattern or second's
 *     first, second - machines whose patterns are to be or'ed (the | operator)
 *
 * note that first and second are both destroyed by the operation
 * the code is rather convoluted because an attempt is made to minimize
 * the number of epsilon states needed
 */

int mkor( first, second )
int first, second;

    {
    int eps, orend;

    if ( first == NIL )
	return ( second );

    else if ( second == NIL )
	return ( first );

    else
	{
	/* see comment in mkopt() about why we can't use the first state
	 * of "first" or "second" if they satisfy "FREE_EPSILON"
	 */
	eps = mkstate( SYM_EPSILON );

	first = link_machines( eps, first );

	mkxtion( first, second );

	if ( SUPER_FREE_EPSILON(finalst[first]) &&
	     accptnum[finalst[first]] == NIL )
	    {
	    orend = finalst[first];
	    mkxtion( finalst[second], orend );
	    }

	else if ( SUPER_FREE_EPSILON(finalst[second]) &&
		  accptnum[finalst[second]] == NIL )
	    {
	    orend = finalst[second];
	    mkxtion( finalst[first], orend );
	    }

	else
	    {
	    eps = mkstate( SYM_EPSILON );

	    first = link_machines( first, eps );
	    orend = finalst[first];

	    mkxtion( finalst[second], orend );
	    }
	}

    finalst[first] = orend;
    return ( first );
    }


/* mkposcl - convert a machine into a positive closure
 *
 * synopsis
 *   new = mkposcl( state );
 *
 *    new - a machine matching the positive closure of "state"
 */

int mkposcl( state )
int state;

    {
    int eps;

    if ( SUPER_FREE_EPSILON(finalst[state]) )
	{
	mkxtion( finalst[state], state );
	return ( state );
	}

    else
	{
	eps = mkstate( SYM_EPSILON );
	mkxtion( eps, state );
	return ( link_machines( state, eps ) );
	}
    }


/* mkrep - make a replicated machine
 *
 * synopsis
 *   new = mkrep( mach, lb, ub );
 *
 *    new - a machine that matches whatever "mach" matched from "lb"
 *          number of times to "ub" number of times
 *
 * note
 *   if "ub" is INFINITY then "new" matches "lb" or more occurrences of "mach"
 */

int mkrep( mach, lb, ub )
int mach, lb, ub;

    {
    int base_mach, tail, copy, i;

    base_mach = copysingl( mach, lb - 1 );

    if ( ub == INFINITY )
	{
	copy = dupmachine( mach );
	mach = link_machines( mach,
			      link_machines( base_mach, mkclos( copy ) ) );
	}

    else
	{
	tail = mkstate( SYM_EPSILON );

	for ( i = lb; i < ub; ++i )
	    {
	    copy = dupmachine( mach );
	    tail = mkopt( link_machines( copy, tail ) );
	    }

	mach = link_machines( mach, link_machines( base_mach, tail ) );
	}

    return ( mach );
    }


/* mkstate - create a state with a transition on a given symbol
 *
 * synopsis
 *
 *   state = mkstate( sym );
 *
 *     state - a new state matching sym
 *     sym   - the symbol the new state is to have an out-transition on
 *
 * note that this routine makes new states in ascending order through the
 * state array (and increments LASTNFA accordingly).  The routine DUPMACHINE
 * relies on machines being made in ascending order and that they are
 * CONTIGUOUS.  Change it and you will have to rewrite DUPMACHINE (kludge
 * that it admittedly is)
 */

int mkstate( sym )
int sym;

    {
    if ( ++lastnfa >= current_mns )
	{
	if ( (current_mns += MNS_INCREMENT) >= MAXIMUM_MNS )
	    lerrif( "input rules are too complicated (>= %d NFA states)",
		    current_mns );
	
	++num_reallocs;

	firstst = reallocate_integer_array( firstst, current_mns );
	lastst = reallocate_integer_array( lastst, current_mns );
	finalst = reallocate_integer_array( finalst, current_mns );
	transchar = reallocate_integer_array( transchar, current_mns );
	trans1 = reallocate_integer_array( trans1, current_mns );
	trans2 = reallocate_integer_array( trans2, current_mns );
	accptnum = reallocate_integer_array( accptnum, current_mns );
	assoc_rule = reallocate_integer_array( assoc_rule, current_mns );
	state_type = reallocate_integer_array( state_type, current_mns );
	}

    firstst[lastnfa] = lastnfa;
    finalst[lastnfa] = lastnfa;
    lastst[lastnfa] = lastnfa;
    transchar[lastnfa] = sym;
    trans1[lastnfa] = NO_TRANSITION;
    trans2[lastnfa] = NO_TRANSITION;
    accptnum[lastnfa] = NIL;
    assoc_rule[lastnfa] = num_rules;
    state_type[lastnfa] = current_state_type;

    /* fix up equivalence classes base on this transition.  Note that any
     * character which has its own transition gets its own equivalence class.
     * Thus only characters which are only in character classes have a chance
     * at being in the same equivalence class.  E.g. "a|b" puts 'a' and 'b'
     * into two different equivalence classes.  "[ab]" puts them in the same
     * equivalence class (barring other differences elsewhere in the input).
     */

    if ( sym < 0 )
	{
	/* we don't have to update the equivalence classes since that was
	 * already done when the ccl was created for the first time
	 */
	}

    else if ( sym == SYM_EPSILON )
	++numeps;

    else
	{
	if ( useecs )
	    /* map NUL's to csize */
	    mkechar( sym ? sym : csize, nextecm, ecgroup );
	}

    return ( lastnfa );
    }


/* mkxtion - make a transition from one state to another
 *
 * synopsis
 *
 *   mkxtion( statefrom, stateto );
 *
 *     statefrom - the state from which the transition is to be made
 *     stateto   - the state to which the transition is to be made
 */

void mkxtion( statefrom, stateto )
int statefrom, stateto;

    {
    if ( trans1[statefrom] == NO_TRANSITION )
	trans1[statefrom] = stateto;

    else if ( (transchar[statefrom] != SYM_EPSILON) ||
	      (trans2[statefrom] != NO_TRANSITION) )
	flexfatal( "found too many transitions in mkxtion()" );

    else
	{ /* second out-transition for an epsilon state */
	++eps2;
	trans2[statefrom] = stateto;
	}
    }

/* new_rule - initialize for a new rule
 *
 * synopsis
 *
 *   new_rule();
 *
 * the global num_rules is incremented and the any corresponding dynamic
 * arrays (such as rule_type[]) are grown as needed.
 */

void new_rule()

    {
    if ( ++num_rules >= current_max_rules )
	{
	++num_reallocs;
	current_max_rules += MAX_RULES_INCREMENT;
	rule_type = reallocate_integer_array( rule_type, current_max_rules );
	rule_linenum =
	    reallocate_integer_array( rule_linenum, current_max_rules );
	}

    if ( num_rules > MAX_RULE )
	lerrif( "too many rules (> %d)!", MAX_RULE );

    rule_linenum[num_rules] = linenum;
    }