fatbase

nfa.c (17417B)

---

 /*	$OpenBSD: nfa.c,v 1.9 2003/06/04 17:34:44 millert Exp $	*/
 
 /* nfa - NFA construction routines */
 
 /*-
  * Copyright (c) 1990 The Regents of the University of California.
  * All rights reserved.
  *
  * This code is derived from software contributed to Berkeley by
  * Vern Paxson.
  * 
  * The United States Government has rights in this work pursuant
  * to contract no. DE-AC03-76SF00098 between the United States
  * Department of Energy and the University of California.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * Neither the name of the University nor the names of its contributors
  * may be used to endorse or promote products derived from this software
  * without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE.
  */
 
 /* $Header: /cvs/src/usr.bin/lex/nfa.c,v 1.9 2003/06/04 17:34:44 millert Exp $ */
 
 #include "flexdef.h"
 
 
 /* declare functions that have forward references */
 
 int dupmachine PROTO((int));
 void mkxtion PROTO((int, int));
 
 
 /* add_accept - add an accepting state to a machine
  *
  * accepting_number becomes mach's accepting number.
  */
 
 void add_accept( mach, accepting_number )
 int mach, accepting_number;
 	{
 	/* Hang the accepting number off an epsilon state.  if it is associated
 	 * with a state that has a non-epsilon out-transition, then the state
 	 * will accept BEFORE it makes that transition, i.e., one character
 	 * too soon.
 	 */
 
 	if ( transchar[finalst[mach]] == SYM_EPSILON )
 		accptnum[finalst[mach]] = accepting_number;
 
 	else
 		{
 		int astate = mkstate( SYM_EPSILON );
 		accptnum[astate] = accepting_number;
 		(void) link_machines( mach, astate );
 		}
 	}
 
 
 /* copysingl - make a given number of copies of a singleton machine
  *
  * synopsis
  *
  *   newsng = copysingl( singl, num );
  *
  *     newsng - a new singleton composed of num copies of singl
  *     singl  - a singleton machine
  *     num    - the number of copies of singl to be present in newsng
  */
 
 int copysingl( singl, num )
 int singl, num;
 	{
 	int copy, i;
 
 	copy = mkstate( SYM_EPSILON );
 
 	for ( i = 1; i <= num; ++i )
 		copy = link_machines( copy, dupmachine( singl ) );
 
 	return copy;
 	}
 
 
 /* dumpnfa - debugging routine to write out an nfa */
 
 void dumpnfa( state1 )
 int state1;
 
 	{
 	int sym, tsp1, tsp2, anum, ns;
 
 	fprintf( stderr,
 	_( "\n\n********** beginning dump of nfa with start state %d\n" ),
 		state1 );
 
 	/* We probably should loop starting at firstst[state1] and going to
 	 * lastst[state1], but they're not maintained properly when we "or"
 	 * all of the rules together.  So we use our knowledge that the machine
 	 * starts at state 1 and ends at lastnfa.
 	 */
 
 	/* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
 	for ( ns = 1; ns <= lastnfa; ++ns )
 		{
 		fprintf( stderr, _( "state # %4d\t" ), ns );
 
 		sym = transchar[ns];
 		tsp1 = trans1[ns];
 		tsp2 = trans2[ns];
 		anum = accptnum[ns];
 
 		fprintf( stderr, "%3d:  %4d, %4d", sym, tsp1, tsp2 );
 
 		if ( anum != NIL )
 			fprintf( stderr, "  [%d]", anum );
 
 		fprintf( stderr, "\n" );
 		}
 
 	fprintf( stderr, _( "********** end of dump\n" ) );
 	}
 
 
 /* dupmachine - make a duplicate of a given machine
  *
  * synopsis
  *
  *   copy = dupmachine( mach );
  *
  *     copy - holds duplicate of mach
  *     mach - machine to be duplicated
  *
  * note that the copy of mach is NOT an exact duplicate; rather, all the
  * transition states values are adjusted so that the copy is self-contained,
  * as the original should have been.
  *
  * also note that the original MUST be contiguous, with its low and high
  * states accessible by the arrays firstst and lastst
  */
 
 int dupmachine( mach )
 int mach;
 	{
 	int i, init, state_offset;
 	int state = 0;
 	int last = lastst[mach];
 
 	for ( i = firstst[mach]; i <= last; ++i )
 		{
 		state = mkstate( transchar[i] );
 
 		if ( trans1[i] != NO_TRANSITION )
 			{
 			mkxtion( finalst[state], trans1[i] + state - i );
 
 			if ( transchar[i] == SYM_EPSILON &&
 			     trans2[i] != NO_TRANSITION )
 				mkxtion( finalst[state],
 					trans2[i] + state - i );
 			}
 
 		accptnum[state] = accptnum[i];
 		}
 
 	if ( state == 0 )
 		flexfatal( _( "empty machine in dupmachine()" ) );
 
 	state_offset = state - i + 1;
 
 	init = mach + state_offset;
 	firstst[init] = firstst[mach] + state_offset;
 	finalst[init] = finalst[mach] + state_offset;
 	lastst[init] = lastst[mach] + state_offset;
 
 	return init;
 	}
 
 
 /* finish_rule - finish up the processing for a rule
  *
  * An accepting number is added to the given machine.  If variable_trail_rule
  * is true then the rule has trailing context and both the head and trail
  * are variable size.  Otherwise if headcnt or trailcnt is non-zero then
  * the machine recognizes a pattern with trailing context and headcnt is
  * the number of characters in the matched part of the pattern, or zero
  * if the matched part has variable length.  trailcnt is the number of
  * trailing context characters in the pattern, or zero if the trailing
  * context has variable length.
  */
 
 void finish_rule( mach, variable_trail_rule, headcnt, trailcnt )
 int mach, variable_trail_rule, headcnt, trailcnt;
 	{
 	char action_text[MAXLINE];
 
 	add_accept( mach, num_rules );
 
 	/* We did this in new_rule(), but it often gets the wrong
 	 * number because we do it before we start parsing the current rule.
 	 */
 	rule_linenum[num_rules] = linenum;
 
 	/* If this is a continued action, then the line-number has already
 	 * been updated, giving us the wrong number.
 	 */
 	if ( continued_action )
 		--rule_linenum[num_rules];
 
 	snprintf( action_text, sizeof action_text, "case %d:\n", num_rules );
 	add_action( action_text );
 
 	if ( variable_trail_rule )
 		{
 		rule_type[num_rules] = RULE_VARIABLE;
 
 		if ( performance_report > 0 )
 			fprintf( stderr,
 			_( "Variable trailing context rule at line %d\n" ),
 				rule_linenum[num_rules] );
 
 		variable_trailing_context_rules = true;
 		}
 
 	else
 		{
 		rule_type[num_rules] = RULE_NORMAL;
 
 		if ( headcnt > 0 || trailcnt > 0 )
 			{
 			/* Do trailing context magic to not match the trailing
 			 * characters.
 			 */
 			char *scanner_cp = "yy_c_buf_p = yy_cp";
 			char *scanner_bp = "yy_bp";
 
 			add_action(
 	"*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" );
 
 			if ( headcnt > 0 )
 				{
 				snprintf( action_text, sizeof action_text,
 					"%s = %s + %d;\n",
 					scanner_cp, scanner_bp, headcnt );
 				add_action( action_text );
 				}
 
 			else
 				{
 				snprintf( action_text, sizeof action_text,
 					"%s -= %d;\n",
 					scanner_cp, trailcnt );
 				add_action( action_text );
 				}
 
 			add_action(
 			"YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
 			}
 		}
 
 	/* Okay, in the action code at this point yytext and yyleng have
 	 * their proper final values for this rule, so here's the point
 	 * to do any user action.  But don't do it for continued actions,
 	 * as that'll result in multiple YY_RULE_SETUP's.
 	 */
 	if ( ! continued_action )
 		add_action( "YY_RULE_SETUP\n" );
 
 	line_directive_out( (FILE *) 0, 1 );
 	}
 
 
 /* link_machines - connect two machines together
  *
  * synopsis
  *
  *   new = link_machines( first, last );
  *
  *     new    - a machine constructed by connecting first to last
  *     first  - the machine whose successor is to be last
  *     last   - the machine whose predecessor is to be first
  *
  * note: this routine concatenates the machine first with the machine
  *  last to produce a machine new which will pattern-match first first
  *  and then last, and will fail if either of the sub-patterns fails.
  *  FIRST is set to new by the operation.  last is unmolested.
  */
 
 int link_machines( first, last )
 int first, last;
 	{
 	if ( first == NIL )
 		return last;
 
 	else if ( last == NIL )
 		return first;
 
 	else
 		{
 		mkxtion( finalst[first], last );
 		finalst[first] = finalst[last];
 		lastst[first] = MAX( lastst[first], lastst[last] );
 		firstst[first] = MIN( firstst[first], firstst[last] );
 
 		return first;
 		}
 	}
 
 
 /* mark_beginning_as_normal - mark each "beginning" state in a machine
  *                            as being a "normal" (i.e., not trailing context-
  *                            associated) states
  *
  * The "beginning" states are the epsilon closure of the first state
  */
 
 void mark_beginning_as_normal( mach )
 int mach;
 	{
 	switch ( state_type[mach] )
 		{
 		case STATE_NORMAL:
 			/* Oh, we've already visited here. */
 			return;
 
 		case STATE_TRAILING_CONTEXT:
 			state_type[mach] = STATE_NORMAL;
 
 			if ( transchar[mach] == SYM_EPSILON )
 				{
 				if ( trans1[mach] != NO_TRANSITION )
 					mark_beginning_as_normal(
 						trans1[mach] );
 
 				if ( trans2[mach] != NO_TRANSITION )
 					mark_beginning_as_normal(
 						trans2[mach] );
 				}
 			break;
 
 		default:
 			flexerror(
 			_( "bad state type in mark_beginning_as_normal()" ) );
 			break;
 		}
 	}
 
 
 /* mkbranch - make a machine that branches to two machines
  *
  * synopsis
  *
  *   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;
 	}