nfa.c

另一版的词法分析器

 *
 *   branch = mkbranch( first, second );
 *
 *     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
		{
		check_char( sym );

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

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 );
		rule_useful = reallocate_integer_array( rule_useful,
							current_max_rules );
		}

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

	rule_linenum[num_rules] = linenum;
	rule_useful[num_rules] = false;
	}