regx.c

C++游戏开发书籍的实例非常适合初学但又又想往游戏开发方面发展的人学习哦

   }
   flush_keyboard( );

   if (ll != NULL)
      bin_offset_adjust( win, *rline );
   return( ll );
}


/*
 * Name:    regx_search_backward
 * Purpose: search backward for pattern using regular expression
 * Date:    June 5, 1993
 * Passed:  ll:     pointer to current node in linked list
 *          rline:  pointer to real line counter
 *          col:    column in ll->line to begin search
 * Returns: position in file if found or NULL if not found
 * Notes:   run the nfa machine on each character in each line
 */
line_list_ptr regx_search_backward( line_list_ptr ll, long *rline, int *col )
{
   if (ll == NULL)
      return( NULL );
   if (ll->len == EOF)
      return( NULL );
   else {
      nfa_pointer = &nfa;
      stacked_node_count = regx.node_count;

      search_string = ll->line;
      search_len = ll->len;
      search_col = *col;
      reset_count = stacked_node_count * sizeof(int);
      while (!g_status.control_break) {
         for (; search_col >= 0; search_col--) {
            if (nfa_match( ) != ERROR) {
               *col = search_col;
               return( ll );
            }
         }
         --*rline;
         ll = ll->prev;
         if (ll == NULL)
            return( NULL );
         if (ll->len == EOF)
            return( NULL );
         search_string = ll->line;
         search_col = search_len = ll->len;
      }
      return( NULL );
   }
}


/******************************  NFA Recognizer  *********************/


/*
 * Name:    nfa_match
 * Purpose: try to recognize a pattern
 * Date:    June 5, 1993
 * Passed:  none, but modifies local global nfa recognizer.
 * Returns: length of recognized pattern if found or ERROR if not found.
 */
int  nfa_match( void )
{
register int c;
int  state;
int  j;
int  n1;
int  rc;

   j = search_col;
   c  =  j < search_len  ?  search_string[j]  :  EOF;
   state = nfa_pointer->next1[0];
   dq_head = 0;
   dq_tail = 0;
   memset( queued_states, 0, reset_count );
   put_dq( SCAN );

   while (state) {
      if (state == SCAN) {
         memset( queued_states, 0, reset_count );
         j++;
         put_dq( SCAN );
         c  =  j < search_len  ?  search_string[j]  :  EOF;
      } else if (nfa_pointer->node_type[state] == NNODE) {
         n1 = nfa_pointer->next1[state];
         rc = OK;
         switch (nfa_pointer->term_type[state]) {
            case STRAIGHT_ASCII :
               if (nfa_pointer->c[state] == c)
                  rc = put_dq( n1 );
               break;
            case IGNORE_ASCII   :
               if (nfa_pointer->c[state] == tolower( c ))
                  rc = put_dq( n1 );
               break;
            case WILD           :
               if (j < search_len)
                  rc = put_dq( n1 );
               break;
            case BOL            :
               if (j == 0) {
                  rc = put_dq( n1 );
                  if (deque[dq_tail] == SCAN)
                     --j;
               }
               break;
            case EOL            :
               if (j == search_len) {
                  rc = put_dq( n1 );
                  if (deque[dq_tail] == SCAN)
                     --j;
               }
               break;
            case CLASS          :
               if (c != EOF  &&  nfa_pointer->class[state][c/8] & bit[c%8])
                  rc = put_dq( n1 );
               break;
            case NOTCLASS       :
               if (c != EOF  &&  !(nfa_pointer->class[state][c/8] & bit[c%8]))
                  rc = put_dq( n1 );
               break;
            case WHITESPACE     :
               if (c == ' '  ||  c == '\t')
                  rc = put_dq( n1 );
               break;
            case ALPHA          :
               if (c != EOF  &&  isalpha( c ))
                  rc = put_dq( n1 );
               break;
            case UPPER          :
               if (c != EOF  &&  isupper( c ))
                  rc = put_dq( n1 );
               break;
            case LOWER          :
               if (c != EOF  &&  islower( c ))
                  rc = put_dq( n1 );
               break;
            case ALPHANUM       :
               if (c != EOF  &&  isalnum( c ))
                  rc = put_dq( n1 );
               break;
            case DECIMAL        :
               if (c != EOF  &&  isdigit( c ))
                  rc = put_dq( n1 );
               break;
            case HEX            :
               if (c != EOF  &&  isxdigit( c ))
                  rc = put_dq( n1 );
               break;
            case BOW            :
               if (c != EOF) {
                  if (!myiswhitespc( c )) {
                     if (j == 0) {
                        rc = put_dq( n1 );
                        if (deque[dq_tail] == SCAN)
                           --j;
                     } else if (j > 0) {
                        if (myiswhitespc( search_string[j-1] )) {
                           rc = put_dq( n1 );
                           if (deque[dq_tail] == SCAN)
                              --j;
                        }
                     }
                  }
               }
               break;
            case EOW            :
               if (c == EOF) {
                  if (search_len > 0) {
                     if (!myiswhitespc( search_string[search_len-1] )) {
                        rc = put_dq( n1 );
                        if (deque[dq_tail] == SCAN)
                           --j;
                     }
                  }
               } else {
                  if (myiswhitespc( c )  &&  j > 0) {
                     if (!myiswhitespc( search_string[j-1] )) {
                        rc = put_dq( n1 );
                        if (deque[dq_tail] == SCAN)
                           --j;
                     }
                  }
               }
               break;
            default             :
               assert( FALSE );
               break;
         }
         if (rc == ERROR)
            return( 0 );
      } else {
         assert( nfa_pointer->node_type[state] == CNODE );

         n1 = nfa_pointer->next1[state];
         if (push_dq( n1 ) == ERROR)
            return( 0 );

         if (n1 != nfa_pointer->next2[state])
            if (push_dq( nfa_pointer->next2[state] ) == ERROR)
               return( 0 );
      }
      if (dequeempty( )  ||  j > search_len)
         return( ERROR );
      state = pop_dq( );
   }
   return( j - search_col );
}


/*
 * Name:    put_dq
 * Purpose: queue future states
 * Date:    June 5, 1993
 * Passed:  v:  state to queue
 * Returns: none, but modifies local global deque variables.  future
 *           states are queued in the head.
 * Notes:   do not add any duplicate states to the head of the deque.
 */
int  put_dq( int v )
{
   if (queued_states[v+1] == 0) {
      ++queued_states[v+1];
      deque[dq_head] = v;
      dq_head--;
      if (dq_head < 0)
         dq_head = REGX_SIZE - 1;
      if (dq_tail == dq_head) {
         nfa_status = ERROR;
         show_search_message( NFA_GAVE_UP, g_display.diag_color );
         return( ERROR );
      }
   }
   return( OK );
}


/*
 * Name:    push_dq
 * Purpose: push state on deque
 * Date:    June 5, 1993
 * Passed:  v:  state to push
 * Returns: whether stack is OK or if stack overflowed - ERROR.  present
 *           states are stacked.
 */
int  push_dq( int v )
{
   ++dq_tail;
   if (dq_tail == dq_head) {
      nfa_status = ERROR;
      show_search_message( NFA_GAVE_UP, g_display.diag_color );
      return( ERROR );
   } else {
      if (dq_tail > REGX_SIZE - 1)
         dq_tail = 0;
      deque[dq_tail] = v;
      return( OK );
   }
}


/*
 * Name:    pop_dq
 * Purpose: pop next state on dq
 * Date:    June 5, 1993
 * Passed:  none, but looks at local global nfa recognizer
 * Returns: state on top of deque and decrements stack pointer
 */
int  pop_dq( void )
{
register int v;

   v = deque[dq_tail];
   dq_tail--;
   if (dq_tail < 0)
      dq_tail = REGX_SIZE - 1;
   return( v );
}


/*
 * Name:    dequeempty
 * Purpose: any room on dq?
 * Date:    June 5, 1993
 * Passed:  none, but looks at local global nfa recognizer
 * Returns: boolean, TRUE if empty.
 * Notes:   the deque is a circular array where future states are
 *           queued in the head and present states are pushed in the tail.
 */
int  dequeempty( void )
{
   if (dq_tail > dq_head)
      return( dq_tail - dq_head == 1 );
   else
      return( dq_tail + REGX_SIZE - dq_head == 1 );
}


/***************************  NFA Compiler  **************************/


/*
 * Name:    build_nfa
 * Purpose: initialize nfa and call the compiler
 * Date:    June 5, 1993
 * Passed:  none, but looks at local global pattern.
 * Returns: whether or not an ERROR occured
 * Notes:   sets up the initial variables for the compiler.  builds
 *          initial and acceptor states for the nfa after compiler finishes.
 */
int  build_nfa( void )
{
   regx_rc = OK;

   init_nfa( );
   lookahead = 0;
   reg_len   = strlen( (char *)regx.pattern );
   parser_state = 1;

   nfa.next1[0] = expression( );
   if (regx_rc == OK) {
      emit_cnode( 0, START, nfa.next1[0], nfa.next1[0] );
      emit_cnode( parser_state, ACCEPT, 0, 0 );
      regx.node_count = parser_state + 2;
   }

   if (g_status.command == DefineRegXGrep) {
      memcpy( &sas_nfa, &nfa, sizeof(NFA_TYPE) );
      memcpy( &sas_regx, &regx, sizeof(REGX_INFO) );
   }
   return( regx_rc );
}


/*
 * Name:    expression
 * Purpose: break reg ex into terms and expressions
 * Date:    June 5, 1993
 * Passed:  none, but looks at local global pattern.
 * Returns: none
 * Notes:   because recursion can go fairly deep, almost all variables
 *          were made local global.  no need to save most of this stuff
 *          on the stack.
 */
int  expression( void )
{
int t1;
int t2;
int r;

   t1 = term( );
   r = t1;
   if (regx.pattern[lookahead] == '|') {
      lookahead++;
      parser_state++;
      r = t2 = parser_state;
      parser_state++;
      emit_cnode( t2, OR_NODE, expression( ), t1 );
      emit_cnode( t2-1, JUXTA, parser_state, parser_state );

      /*
       * the OR_NODE seems to need a path from the previous node
       */
      if (nfa.node_type[t1] == CNODE)
         t1 = min( nfa.next1[t1], nfa.next2[t1] );
      nfa.next1[t1-1] = t2;
      if (nfa.node_type[t1-1] == NNODE)
         nfa.next2[t1-1] = t2;
   }
   return( r );
}


/*
 * Name:    term
 * Purpose: break reg ex into factors and terms
 * Date:    June 5, 1993
 * Passed:  none, but looks at local global pattern.
 * Returns: none
 */
int  term( void )
{
int r;

   r = factor( );
   if (regx.pattern[lookahead] == '('  ||  letter( regx.pattern[lookahead] ))
      term( );
   else if (Kleene_star( regx.pattern[lookahead] ))
      regx_error( reg11 );
   return( r );
}


/*
 * Name:    factor
 * Purpose: add NNODEs and CNODEs to local global nfa
 * Date:    June 5, 1993
 * Passed:  none
 * Returns: none, but modifies local global nfa.
 * Notes:   this function does most of the compiling.  it recognizes all
 *          NNODEs, predefined macros, escape characters, and operators.
 */
int  factor( void )