nfa.c

操作系统源代码

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

#ifndef lint
static char rcsid[] =
    "@(#) $Header: /usr/fsys/odin/a/vern/flex/RCS/nfa.c,v 2.6 90/06/27 23:48:29 vern Exp $ (LBL)";
#endif

#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
 *
 * synopsis
 *
 *   add_accept( mach, accepting_number );
 *
 * 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;
	mach = 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
 *
 * synopsis
 *    int state1;
 *    dumpnfa( state1 );
 */

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
 *
 * synopsis
 *
 *   finish_rule( mach, variable_trail_rule, headcnt, trailcnt );
 *
 * 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;

    {
    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];

    fprintf( temp_action_file, "case %d:\n", num_rules );

    if ( variable_trail_rule )
	{
	rule_type[num_rules] = RULE_VARIABLE;

	if ( performance_report )
	    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";

	    fprintf( temp_action_file,
	"*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" );

	    if ( headcnt > 0 )
		fprintf( temp_action_file, "%s = %s + %d;\n",
			 scanner_cp, scanner_bp, headcnt );

	    else
		fprintf( temp_action_file,
			 "%s -= %d;\n", scanner_cp, trailcnt );
	
	    fprintf( temp_action_file,
		     "YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
	    }
	}

    line_directive_out( temp_action_file );
    }


/* 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
 *
 * synopsis
 *
 *   mark_beginning_as_normal( mach )
 *
 *     mach - machine to mark
 *
 * 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
 *
 *   branch = mkbranch( first, second );