Logo Search packages:      
Sourcecode: maxdb-buildtools version File versions

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 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
 *
 *   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;
      }

Generated by  Doxygen 1.6.0   Back to index