/* 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: (1) source distributions retain * this entire copyright notice and comment, and (2) distributions including * binaries display the following acknowledgement:  ``This product includes * software developed by the University of California, Berkeley and its * contributors'' in the documentation or other materials provided with the * distribution and in all advertising materials mentioning features or use * of this software.  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: /home/daffy/u0/vern/flex/RCS/nfa.c,v 2.17 95/03/04 16:11:42 vern 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];	sprintf( 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 )				{				sprintf( action_text, "%s = %s + %d;\n",				scanner_cp, scanner_bp, headcnt );				add_action( action_text );				}			else				{				sprintf( 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 )register 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