home *** CD-ROM | disk | FTP | other *** search
/ TopWare Tools / TOOLS.iso / tools / top1498 / regx.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-11-13  |  37.0 KB  |  1,301 lines
  1. /*
  2.  * These functions compile a regular expression into an NFA and recognize
  3.  * a pattern.
  4.  *
  5.  * Regular expressions are often used to describe a pattern that might
  6.  * match several different or similar words.  An example of a regular
  7.  * expression subset is the wild card characters '*' and '?' used to list
  8.  * files in a directory.
  9.  *
  10.  * Might as well read the books and papers written by those who first wrote
  11.  * the various [a-z]?greps.  Ken Thompson was the author of grep.  In one
  12.  * weekend, Al Aho wrote egrep and fgrep.  Incidentally, when Dr. Aho was
  13.  * the guest speaker at the Distinguished Lecture Series at Georgia Tech,
  14.  * he personally autographed my copy of his book  _Compilers:  Principles,
  15.  * Techniques, and Tools_, aka the "Dragon Book."
  16.  *
  17.  * See:
  18.  *
  19.  *   Ken Thompson, "Regular Expression Search Algorithm."  _Communications
  20.  *      of the ACM_, 11 (No. 6): 419-422, 1968.
  21.  *
  22.  *   Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, _Compilers: Principles,
  23.  *      Techniques, and Tools_, Addison-Wesley, Reading, Mass., 1986,
  24.  *      Chapter 3, "Lexical Analysis", pp 83-158.  ISBN 0-201-10088-6.
  25.  *
  26.  *   Robert Sedgewick, _Algorithms in C_, Addison-Wesley, Reading, Mass.,
  27.  *      1990, Chapter 20, "Pattern Matching", pp. 293-303, and Chapter 21,
  28.  *      "Parsing", pp. 305-317.  ISBN 0-201-51425-7.
  29.  *
  30.  *   Andrew Hume, "A Tale of Two Greps."  _Software--Practice and Experience_,
  31.  *      18 (No. 11): 1063-1072, 1988.
  32.  *
  33.  *
  34.  *                         Regular Expressions in TDE
  35.  *
  36.  * The core of the regular expression search algorithm in TDE is based on
  37.  * the nondeterministic finite-state machine in Dr. Segdewick's book.
  38.  * Additional parsing, operator precedence, and nfa construction and
  39.  * simulation info is from Dr. Aho's book.  The nfa node naming convention
  40.  * and additional nfa construction guidelines are from Ken Thompson's paper.
  41.  * I'm much too stupid to compile a regular expression into assembly language
  42.  * as suggested in Ken Thompson's paper, but I did get the idea to do the
  43.  * next best thing and added C library functions as NNODE terminal types.
  44.  *
  45.  * The local global NFA is builded with two arrays and a deque.  The
  46.  * first array, next1, in the NFA is used to hold the path for lambda
  47.  * transitions.  The second array, next2, is used to hold alternate paths.
  48.  * Next1 can hold all types of nodes, but it gets priority for lambda
  49.  * transitions.  The deque is a circular array where future states are queued
  50.  * in the head and present states are pushed in the tail.
  51.  *
  52.  * Searching for regular expressions in TDE is not very fast.  The worst
  53.  * case search, .*x, where x is any word or letter, is probably the slowest
  54.  * of any implementation with a regular expression search function.  However,
  55.  * TDE can handle a large regular expression subset.
  56.  *
  57.  * In version 3.1, I added BOW and EOW (beginning of word and end of word.)
  58.  *
  59.  * In version 3.2, the macro letters were moved to letters.h per Byrial Jensen.
  60.  * We also use the bj_isxxx( ) functions to test whether a letter falls into
  61.  * a predefined macro class.
  62.  *
  63.  * New editor name:  TDE, the Thomson-Davis Editor.
  64.  * Author:           Frank Davis
  65.  * Date:             June 5, 1991, version 1.0
  66.  * Date:             July 29, 1991, version 1.1
  67.  * Date:             October 5, 1991, version 1.2
  68.  * Date:             January 20, 1992, version 1.3
  69.  * Date:             February 17, 1992, version 1.4
  70.  * Date:             April 1, 1992, version 1.5
  71.  * Date:             June 5, 1992, version 2.0
  72.  * Date:             October 31, 1992, version 2.1
  73.  * Date:             April 1, 1993, version 2.2
  74.  * Date:             June 5, 1993, version 3.0
  75.  * Date:             August 29, 1993, version 3.1
  76.  * Date:             November 13, 1993, version 3.2
  77.  *
  78.  * This code is released into the public domain, Frank Davis.
  79.  * You may use and distribute it freely.
  80.  */
  81.  
  82. #include "tdestr.h"
  83. #include "common.h"
  84. #include "tdefunc.h"
  85. #include "define.h"
  86.  
  87. #ifndef min
  88.  #define min(a,b)       (((a) < (b)) ? (a) : (b))
  89. #endif
  90.  
  91. /*
  92.  * types of nodes in the NFA.
  93.  *
  94.  * let's use the node naming convention in Ken Thompson's reg ex paper.
  95.  */
  96. #define CNODE           0
  97. #define NNODE           1
  98.  
  99. #define SCAN            -1
  100.  
  101. /*
  102.  * types of terminals in NNODEs.
  103.  *
  104.  * starting with simple ASCII terminals, it's easy to build in other types of
  105.  *  terminals, e.g. wild chars, BOL, EOL, and character classes.  actually,
  106.  *  we can easily build ANSI C ctype library function NNODEs.
  107.  */
  108. #define STRAIGHT_ASCII  0
  109. #define IGNORE_ASCII    1
  110. #define WILD            2
  111. #define BOL             3
  112. #define EOL             4
  113. #define CLASS           5
  114. #define NOTCLASS        6
  115. #define WHITESPACE      7
  116. #define ALPHA           8
  117. #define UPPER           9
  118. #define LOWER           10
  119. #define ALPHANUM        11
  120. #define DECIMAL         12
  121. #define HEX             13
  122. #define BOW             14
  123. #define EOW             15
  124.  
  125.  
  126. /*
  127.  * types of terminals in CNODEs.
  128.  */
  129. #define START           0
  130. #define ACCEPT          1
  131. #define OR_NODE         2
  132. #define JUXTA           3
  133. #define CLOSURE         4
  134. #define ZERO_OR_ONE     5
  135.  
  136.  
  137. int  lookahead;
  138. int  regx_rc;
  139. int  reg_len;
  140. int  parser_state;
  141. char class_bits[32];
  142. int  bit[8] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
  143. int  c1;
  144. int  c2;
  145. int  ttype;
  146. int  regx_error_line;
  147.  
  148. NFA_TYPE  *nfa_pointer;
  149.  
  150. int  nfa_status;
  151. int  search_len;
  152. int  search_col;
  153. text_ptr search_string;
  154.  
  155. int  queued_states[REGX_SIZE+2];
  156. int  deque[REGX_SIZE*2];
  157. int  dq_head;
  158. int  dq_tail;
  159. int  stacked_node_count;
  160. int  reset_count;
  161.  
  162.  
  163. /*
  164.  * Name:    find_regx
  165.  * Purpose: To set up and find a regular expression.
  166.  * Date:    June 5, 1993
  167.  * Passed:  window:  pointer to current window
  168.  * Notes:   Keep the regular expression until changed.
  169.  */
  170. int  find_regx( TDE_WIN *window )
  171. {
  172. int  direction;
  173. int  new_string;
  174. long found_line;
  175. long bin_offset;
  176. line_list_ptr ll;
  177. register TDE_WIN *win;  /* put window pointer in a register */
  178. int  rc;
  179. int  old_rcol;
  180. int  rcol;
  181. char answer[MAX_COLS+2];
  182. char temp[MAX_COLS+2];
  183.  
  184.    switch (g_status.command) {
  185.       case FindRegX :
  186.          new_string = TRUE;
  187.          direction  = FORWARD;
  188.          break;
  189.       case RepeatFindRegX :
  190.          new_string =  regx.search_defined != OK ? TRUE : FALSE;
  191.          direction  = FORWARD;
  192.          break;
  193.       case RepeatFindRegXBackward :
  194.          new_string =  regx.search_defined != OK ? TRUE : FALSE;
  195.          direction  = BACKWARD;
  196.          break;
  197.       default :
  198.          new_string = 0;
  199.          direction  = 0;
  200.          assert( FALSE );
  201.          break;
  202.    }
  203.  
  204.    win = window;
  205.    entab_linebuff( );
  206.    if (un_copy_line( win->ll, win, TRUE ) == ERROR)
  207.       return( ERROR );
  208.  
  209.    regx_error_line = win->bottom_line;
  210.  
  211.    /*
  212.     * get search text, using previous as default
  213.     */
  214.    rc = OK;
  215.    if (new_string == TRUE) {
  216.       *answer = '\0';
  217.       if (regx.search_defined == OK) {
  218.  
  219.          assert( strlen( (char *)regx.pattern ) < (size_t)g_display.ncols );
  220.  
  221.          strcpy( answer, (char *)regx.pattern );
  222.       }
  223.  
  224.       /*
  225.        * string to find:
  226.        */
  227.       if (get_name( reg1, win->bottom_line, answer,
  228.                  g_display.message_color ) != OK  ||  *answer == '\0')
  229.          return( ERROR );
  230.       regx.search_defined = OK;
  231.  
  232.       assert( strlen( answer ) < (size_t)g_display.ncols );
  233.  
  234.       strcpy( (char *)regx.pattern, answer );
  235.       rc = build_nfa( );
  236.       if (rc == ERROR)
  237.          regx.search_defined = ERROR;
  238.    }
  239.  
  240.    if (regx.search_defined == OK) {
  241.       old_rcol = win->rcol;
  242.       if (mode.inflate_tabs)
  243.          win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol);
  244.       update_line( win );
  245.       show_search_message( SEARCHING, g_display.diag_color );
  246.       bin_offset = win->bin_offset;
  247.       if (direction == FORWARD) {
  248.          if ((ll = forward_regx_search( win, &found_line, &rcol )) != NULL) {
  249.             if (g_status.wrapped && g_status.macro_executing)
  250.                rc = ask_wrap_replace( win, &new_string );
  251.             if (rc == OK)
  252.                find_adjust( win, ll, found_line, rcol );
  253.             else
  254.                win->bin_offset = bin_offset;
  255.          }
  256.       } else {
  257.          if ((ll = backward_regx_search( win, &found_line, &rcol )) != NULL) {
  258.             if (g_status.wrapped && g_status.macro_executing)
  259.                rc = ask_wrap_replace( win, &new_string );
  260.             if (rc == OK)
  261.                find_adjust( win, ll, found_line, rcol );
  262.             else
  263.                win->bin_offset = bin_offset;
  264.          }
  265.       }
  266.       if (g_status.wrapped)
  267.          show_search_message( WRAPPED, g_display.diag_color );
  268.       else {
  269.          if (nfa_status == OK)
  270.             show_search_message( CLR_SEARCH, g_display.mode_color );
  271.          else
  272.             g_status.wrapped = TRUE;
  273.       }
  274.       if (ll == NULL) {
  275.          /*
  276.           * string not found
  277.           */
  278.          if (mode.inflate_tabs)
  279.             win->rcol = old_rcol;
  280.          combine_strings( temp, find5a, (char *)regx.pattern, find5b );
  281.          error( WARNING, win->bottom_line, temp );
  282.          rc = ERROR;
  283.       }
  284.       show_curl_line( win );
  285.       make_ruler( win );
  286.       show_ruler( win );
  287.    } else {
  288.       /*
  289.        * find pattern not defined
  290.        */
  291.       error( WARNING, win->bottom_line, find6 );
  292.       rc = ERROR;
  293.    }
  294.    return( rc );
  295. }
  296.  
  297.  
  298. /*
  299.  * Name:    forward_regx_search
  300.  * Purpose: search forward for regular expression
  301.  * Date:    June 5, 1993
  302.  * Passed:  window:  pointer to current window
  303.  *          rline:   pointer to real line counter
  304.  *          rcol:    pointer to real column variable
  305.  * Returns: position in file if found or NULL if not found
  306.  * Notes:   Start searching from cursor position to end of file.  If we hit
  307.  *           end of file without a match, start searching from the beginning
  308.  *           of file to cursor position.  (do wrapped searches)
  309.  */
  310. line_list_ptr forward_regx_search( TDE_WIN *window, long *rline, int *rcol )
  311. {
  312. register int len;
  313. int  i;
  314. int  end;
  315. register TDE_WIN *win;  /* put window pointer in a register */
  316. line_list_ptr ll;
  317.  
  318.    /*
  319.     * if cursor is beyond end of line then start at end of line
  320.     */
  321.    win  = window;
  322.    *rline = win->rline;
  323.    i = win->rcol + 1;
  324.    ll = win->ll;
  325.    len = ll->len;
  326.    if (i > len  &&  len != EOF) {
  327.       ll = ll->next;
  328.       ++*rline;
  329.       i = 0;
  330.    }
  331.    if (i < 0)
  332.       i = 0;
  333.  
  334.    *rcol = i;
  335.    ll = regx_search_forward( ll, rline, rcol );
  336.  
  337.    if (ll == NULL) {
  338.  
  339.       end = 0;
  340.       if (win->ll->next != NULL) {
  341.          end = win->ll->next->len;
  342.          win->ll->next->len = EOF;
  343.       }
  344.  
  345.       /*
  346.        * haven't found pattern yet - now search from beginning of file
  347.        */
  348.       g_status.wrapped = TRUE;
  349.  
  350.       *rcol = 0;
  351.       *rline = 1L;
  352.       ll = regx_search_forward( win->file_info->line_list, rline, rcol );
  353.  
  354.       if (ll == win->ll  &&  *rcol >= win->rcol)
  355.          ll = NULL;
  356.  
  357.       if (win->ll->next != NULL)
  358.          win->ll->next->len = end;
  359.    }
  360.    flush_keyboard( );
  361.  
  362.    if (ll != NULL)
  363.       bin_offset_adjust( win, *rline );
  364.    return( ll );
  365. }
  366.  
  367.  
  368. /*
  369.  * Name:    regx_search_forward
  370.  * Purpose: search forward for pattern using nfa
  371.  * Date:    June 5, 1993
  372.  * Passed:  ll:     pointer to current node in linked list
  373.  *          rline:  pointer to real line counter
  374.  *          col:    column in ll->line to begin search
  375.  * Returns: position in file if found or NULL if not found
  376.  * Notes:   run the nfa machine on each character in each line
  377.  */
  378. line_list_ptr regx_search_forward( line_list_ptr ll, long *rline, int  *col )
  379. {
  380.    if (ll->len == EOF)
  381.       return( NULL );
  382.    else {
  383.       switch (g_status.command) {
  384.          case DefineRegXGrep  :
  385.          case RepeatGrep :
  386.             nfa_pointer = &sas_nfa;
  387.             stacked_node_count = sas_regx.node_count;
  388.             break;
  389.          case FindRegX  :
  390.          case RepeatFindRegX :
  391.             nfa_pointer = &nfa;
  392.             stacked_node_count = regx.node_count;
  393.             break;
  394.          default :
  395.             assert( FALSE );
  396.             break;
  397.       }
  398.       nfa_status = OK;
  399.       search_string = ll->line;
  400.       search_len = ll->len;
  401.       search_col = *col;
  402.       reset_count = stacked_node_count * sizeof(int);
  403.       for (; !g_status.control_break;) {
  404.          for (; search_col <= search_len; search_col++) {
  405.             if (nfa_match( ) != ERROR) {
  406.                *col = search_col;
  407.                return( ll );
  408.             }
  409.          }
  410.          ++*rline;
  411.          ll = ll->next;
  412.          search_string = ll->line;
  413.          if (ll->len == EOF)
  414.             return( NULL );
  415.          search_len = ll->len;
  416.          search_col = 0;
  417.       }
  418.       return( NULL );
  419.    }
  420. }
  421.  
  422.  
  423. /*
  424.  * Name:    backward_regx_search
  425.  * Purpose: search backward for regular expression
  426.  * Date:    June 5, 1993
  427.  * Passed:  window:  pointer to current window
  428.  *          rline:   pointer to real line counter
  429.  *          rcol:    pointer to real column variable
  430.  * Returns: position in file if found or NULL if not found
  431.  * Notes:   Start searching from cursor position to end of file.  If we hit
  432.  *           end of file without a match, start searching from the beginning
  433.  *           of file to cursor position.  (do wrapped searches)
  434.  */
  435. line_list_ptr backward_regx_search( TDE_WIN *window, long *rline, int *rcol )
  436. {
  437. int  i;
  438. int  len;
  439. int  end;
  440. register TDE_WIN *win;  /* put window pointer in a register */
  441. line_list_ptr ll;
  442.  
  443.    win  = window;
  444.    *rline = win->rline;
  445.  
  446.    /*
  447.     * see if cursor is on EOF line.  if so, move search start to previous node.
  448.     */
  449.    if (win->ll->len != EOF) {
  450.       ll = win->ll;
  451.       i  = win->rcol - 1;
  452.       len = ll->len;
  453.       if (i >= len)
  454.          i = len - 1;
  455.    } else {
  456.       ll = win->ll->prev;
  457.       --*rline;
  458.       i = 0;
  459.       if (ll != NULL)
  460.          i = ll->len - 1;
  461.    }
  462.    *rcol = i;
  463.    ll = regx_search_backward( ll, rline, rcol );
  464.  
  465.    if (ll == NULL  &&  win->rline <= win->file_info->length) {
  466.  
  467.       end = 0;
  468.       if (win->ll->prev != NULL) {
  469.          end = win->ll->prev->len;
  470.          win->ll->prev->len = EOF;
  471.       }
  472.  
  473.       /*
  474.        * haven't found pattern yet - now search from end of file
  475.        */
  476.       g_status.wrapped = TRUE;
  477.       ll = win->file_info->line_list_end;
  478.       if (ll->prev != NULL)
  479.          *rcol = ll->prev->len;
  480.       else
  481.         *rcol = 0;
  482.       *rline = win->file_info->length;
  483.       ll = regx_search_backward( ll->prev, rline, rcol );
  484.  
  485.       if (ll == win->ll  &&  *rcol <= win->rcol)
  486.          ll = NULL;
  487.  
  488.       if (win->ll->prev != NULL)
  489.          win->ll->prev->len = end;
  490.    }
  491.    flush_keyboard( );
  492.  
  493.    if (ll != NULL)
  494.       bin_offset_adjust( win, *rline );
  495.    return( ll );
  496. }
  497.  
  498.  
  499. /*
  500.  * Name:    regx_search_backward
  501.  * Purpose: search backward for pattern using regular expression
  502.  * Date:    June 5, 1993
  503.  * Passed:  ll:     pointer to current node in linked list
  504.  *          rline:  pointer to real line counter
  505.  *          col:    column in ll->line to begin search
  506.  * Returns: position in file if found or NULL if not found
  507.  * Notes:   run the nfa machine on each character in each line
  508.  */
  509. line_list_ptr regx_search_backward( line_list_ptr ll, long *rline, int *col )
  510. {
  511.    if (ll == NULL)
  512.       return( NULL );
  513.    if (ll->len == EOF)
  514.       return( NULL );
  515.    else {
  516.       nfa_pointer = &nfa;
  517.       stacked_node_count = regx.node_count;
  518.  
  519.       search_string = ll->line;
  520.       search_len = ll->len;
  521.       search_col = *col;
  522.       reset_count = stacked_node_count * sizeof(int);
  523.       while (!g_status.control_break) {
  524.          for (; search_col >= 0; search_col--) {
  525.             if (nfa_match( ) != ERROR) {
  526.                *col = search_col;
  527.                return( ll );
  528.             }
  529.          }
  530.          --*rline;
  531.          ll = ll->prev;
  532.          if (ll == NULL)
  533.             return( NULL );
  534.          if (ll->len == EOF)
  535.             return( NULL );
  536.          search_string = ll->line;
  537.          search_col = search_len = ll->len;
  538.       }
  539.       return( NULL );
  540.    }
  541. }
  542.  
  543.  
  544. /******************************  NFA Recognizer  *********************/
  545.  
  546.  
  547. /*
  548.  * Name:    nfa_match
  549.  * Purpose: try to recognize a pattern
  550.  * Date:    June 5, 1993
  551.  * Passed:  none, but modifies local global nfa recognizer.
  552.  * Returns: length of recognized pattern if found or ERROR if not found.
  553.  */
  554. int  nfa_match( void )
  555. {
  556. register int c;
  557. int  state;
  558. int  j;
  559. int  n1;
  560. int  rc;
  561.  
  562.    j = search_col;
  563.    c  =  j < search_len  ?  search_string[j]  :  EOF;
  564.    state = nfa_pointer->next1[0];
  565.    dq_head = 0;
  566.    dq_tail = 0;
  567.    memset( queued_states, 0, reset_count );
  568.    put_dq( SCAN );
  569.  
  570.    while (state) {
  571.       if (state == SCAN) {
  572.          memset( queued_states, 0, reset_count );
  573.          j++;
  574.          put_dq( SCAN );
  575.          c  =  j < search_len  ?  search_string[j]  :  EOF;
  576.       } else if (nfa_pointer->node_type[state] == NNODE) {
  577.          n1 = nfa_pointer->next1[state];
  578.          rc = OK;
  579.          switch (nfa_pointer->term_type[state]) {
  580.             case STRAIGHT_ASCII :
  581.                if (nfa_pointer->c[state] == c)
  582.                   rc = put_dq( n1 );
  583.                break;
  584.             case IGNORE_ASCII   :
  585.                if (nfa_pointer->c[state] == tolower( c ))
  586.                   rc = put_dq( n1 );
  587.                break;
  588.             case WILD           :
  589.                if (j < search_len)
  590.                   rc = put_dq( n1 );
  591.                break;
  592.             case BOL            :
  593.                if (j == 0) {
  594.                   rc = put_dq( n1 );
  595.                   if (deque[dq_tail] == SCAN)
  596.                      --j;
  597.                }
  598.                break;
  599.             case EOL            :
  600.                if (j == search_len) {
  601.                   rc = put_dq( n1 );
  602.                   if (deque[dq_tail] == SCAN)
  603.                      --j;
  604.                }
  605.                break;
  606.             case CLASS          :
  607.                if (c != EOF  &&  nfa_pointer->class[state][c/8] & bit[c%8])
  608.                   rc = put_dq( n1 );
  609.                break;
  610.             case NOTCLASS       :
  611.                if (c != EOF  &&  !(nfa_pointer->class[state][c/8] & bit[c%8]))
  612.                   rc = put_dq( n1 );
  613.                break;
  614.             case WHITESPACE     :
  615.                if (c == ' '  ||  c == '\t')
  616.                   rc = put_dq( n1 );
  617.                break;
  618.             case ALPHA          :
  619.                if (c != EOF  &&  bj_isalpha( c ))
  620.                   rc = put_dq( n1 );
  621.                break;
  622.             case UPPER          :
  623.                if (c != EOF  &&  bj_isupper( c ))
  624.                   rc = put_dq( n1 );
  625.                break;
  626.             case LOWER          :
  627.                if (c != EOF  &&  bj_islower( c ))
  628.                   rc = put_dq( n1 );
  629.                break;
  630.             case ALPHANUM       :
  631.                if (c != EOF  &&  bj_isalnum( c ))
  632.                   rc = put_dq( n1 );
  633.                break;
  634.             case DECIMAL        :
  635.                if (c != EOF  &&  bj_isdigit( c ))
  636.                   rc = put_dq( n1 );
  637.                break;
  638.             case HEX            :
  639.                if (c != EOF  &&  bj_isxdigit( c ))
  640.                   rc = put_dq( n1 );
  641.                break;
  642.             case BOW            :
  643.                if (c != EOF) {
  644.                   if (!myiswhitespc( c )) {
  645.                      if (j == 0) {
  646.                         rc = put_dq( n1 );
  647.                         if (deque[dq_tail] == SCAN)
  648.                            --j;
  649.                      } else if (j > 0) {
  650.                         if (myiswhitespc( search_string[j-1] )) {
  651.                            rc = put_dq( n1 );
  652.                            if (deque[dq_tail] == SCAN)
  653.                               --j;
  654.                         }
  655.                      }
  656.                   }
  657.                }
  658.                break;
  659.             case EOW            :
  660.                if (c == EOF) {
  661.                   if (search_len > 0) {
  662.                      if (!myiswhitespc( search_string[search_len-1] )) {
  663.                         rc = put_dq( n1 );
  664.                         if (deque[dq_tail] == SCAN)
  665.                            --j;
  666.                      }
  667.                   }
  668.                } else {
  669.                   if (myiswhitespc( c )  &&  j > 0) {
  670.                      if (!myiswhitespc( search_string[j-1] )) {
  671.                         rc = put_dq( n1 );
  672.                         if (deque[dq_tail] == SCAN)
  673.                            --j;
  674.                      }
  675.                   }
  676.                }
  677.                break;
  678.             default             :
  679.                assert( FALSE );
  680.                break;
  681.          }
  682.          if (rc == ERROR)
  683.             return( 0 );
  684.       } else {
  685.          assert( nfa_pointer->node_type[state] == CNODE );
  686.  
  687.          n1 = nfa_pointer->next1[state];
  688.          if (push_dq( n1 ) == ERROR)
  689.             return( 0 );
  690.  
  691.          if (n1 != nfa_pointer->next2[state])
  692.             if (push_dq( nfa_pointer->next2[state] ) == ERROR)
  693.                return( 0 );
  694.       }
  695.       if (dequeempty( )  ||  j > search_len)
  696.          return( ERROR );
  697.       state = pop_dq( );
  698.    }
  699.    return( j - search_col );
  700. }
  701.  
  702.  
  703. /*
  704.  * Name:    put_dq
  705.  * Purpose: queue future states
  706.  * Date:    June 5, 1993
  707.  * Passed:  v:  state to queue
  708.  * Returns: none, but modifies local global deque variables.  future
  709.  *           states are queued in the head.
  710.  * Notes:   do not add any duplicate states to the head of the deque.
  711.  */
  712. int  put_dq( int v )
  713. {
  714.    if (queued_states[v+1] == 0) {
  715.       ++queued_states[v+1];
  716.       deque[dq_head] = v;
  717.       dq_head--;
  718.       if (dq_head < 0)
  719.          dq_head = REGX_SIZE - 1;
  720.       if (dq_tail == dq_head) {
  721.          nfa_status = ERROR;
  722.          show_search_message( NFA_GAVE_UP, g_display.diag_color );
  723.          return( ERROR );
  724.       }
  725.    }
  726.    return( OK );
  727. }
  728.  
  729.  
  730. /*
  731.  * Name:    push_dq
  732.  * Purpose: push state on deque
  733.  * Date:    June 5, 1993
  734.  * Passed:  v:  state to push
  735.  * Returns: whether stack is OK or if stack overflowed - ERROR.  present
  736.  *           states are stacked.
  737.  */
  738. int  push_dq( int v )
  739. {
  740.    ++dq_tail;
  741.    if (dq_tail == dq_head) {
  742.       nfa_status = ERROR;
  743.       show_search_message( NFA_GAVE_UP, g_display.diag_color );
  744.       return( ERROR );
  745.    } else {
  746.       if (dq_tail > REGX_SIZE - 1)
  747.          dq_tail = 0;
  748.       deque[dq_tail] = v;
  749.       return( OK );
  750.    }
  751. }
  752.  
  753.  
  754. /*
  755.  * Name:    pop_dq
  756.  * Purpose: pop next state on dq
  757.  * Date:    June 5, 1993
  758.  * Passed:  none, but looks at local global nfa recognizer
  759.  * Returns: state on top of deque and decrements stack pointer
  760.  */
  761. int  pop_dq( void )
  762. {
  763. register int v;
  764.  
  765.    v = deque[dq_tail];
  766.    dq_tail--;
  767.    if (dq_tail < 0)
  768.       dq_tail = REGX_SIZE - 1;
  769.    return( v );
  770. }
  771.  
  772.  
  773. /*
  774.  * Name:    dequeempty
  775.  * Purpose: any room on dq?
  776.  * Date:    June 5, 1993
  777.  * Passed:  none, but looks at local global nfa recognizer
  778.  * Returns: boolean, TRUE if empty.
  779.  * Notes:   the deque is a circular array where future states are
  780.  *           queued in the head and present states are pushed in the tail.
  781.  */
  782. int  dequeempty( void )
  783. {
  784.    if (dq_tail > dq_head)
  785.       return( dq_tail - dq_head == 1 );
  786.    else
  787.       return( dq_tail + REGX_SIZE - dq_head == 1 );
  788. }
  789.  
  790.  
  791. /***************************  NFA Compiler  **************************/
  792.  
  793.  
  794. /*
  795.  * Name:    build_nfa
  796.  * Purpose: initialize nfa and call the compiler
  797.  * Date:    June 5, 1993
  798.  * Passed:  none, but looks at local global pattern.
  799.  * Returns: whether or not an ERROR occured
  800.  * Notes:   sets up the initial variables for the compiler.  builds
  801.  *          initial and acceptor states for the nfa after compiler finishes.
  802.  */
  803. int  build_nfa( void )
  804. {
  805.    regx_rc = OK;
  806.  
  807.    init_nfa( );
  808.    lookahead = 0;
  809.    reg_len   = strlen( (char *)regx.pattern );
  810.    parser_state = 1;
  811.  
  812.    nfa.next1[0] = expression( );
  813.    if (regx_rc == OK) {
  814.       emit_cnode( 0, START, nfa.next1[0], nfa.next1[0] );
  815.       emit_cnode( parser_state, ACCEPT, 0, 0 );
  816.       regx.node_count = parser_state + 2;
  817.    }
  818.  
  819.    if (g_status.command == DefineRegXGrep) {
  820.       memcpy( &sas_nfa, &nfa, sizeof(NFA_TYPE) );
  821.       memcpy( &sas_regx, ®x, sizeof(REGX_INFO) );
  822.    }
  823.    return( regx_rc );
  824. }
  825.  
  826.  
  827. /*
  828.  * Name:    expression
  829.  * Purpose: break reg ex into terms and expressions
  830.  * Date:    June 5, 1993
  831.  * Passed:  none, but looks at local global pattern.
  832.  * Returns: none
  833.  * Notes:   because recursion can go fairly deep, almost all variables
  834.  *          were made local global.  no need to save most of this stuff
  835.  *          on the stack.
  836.  */
  837. int  expression( void )
  838. {
  839. int t1;
  840. int t2;
  841. int r;
  842.  
  843.    t1 = term( );
  844.    r = t1;
  845.    if (regx.pattern[lookahead] == '|') {
  846.       lookahead++;
  847.       parser_state++;
  848.       r = t2 = parser_state;
  849.       parser_state++;
  850.       emit_cnode( t2, OR_NODE, expression( ), t1 );
  851.       emit_cnode( t2-1, JUXTA, parser_state, parser_state );
  852.  
  853.       /*
  854.        * the OR_NODE seems to need a path from the previous node
  855.        */
  856.       if (nfa.node_type[t1] == CNODE)
  857.          t1 = min( nfa.next1[t1], nfa.next2[t1] );
  858.       nfa.next1[t1-1] = t2;
  859.       if (nfa.node_type[t1-1] == NNODE)
  860.          nfa.next2[t1-1] = t2;
  861.    }
  862.    return( r );
  863. }
  864.  
  865.  
  866. /*
  867.  * Name:    term
  868.  * Purpose: break reg ex into factors and terms
  869.  * Date:    June 5, 1993
  870.  * Passed:  none, but looks at local global pattern.
  871.  * Returns: none
  872.  */
  873. int  term( void )
  874. {
  875. int r;
  876.  
  877.    r = factor( );
  878.    if (regx.pattern[lookahead] == '('  ||  letter( regx.pattern[lookahead] ))
  879.       term( );
  880.    else if (Kleene_star( regx.pattern[lookahead] ))
  881.       regx_error( reg11 );
  882.    return( r );
  883. }
  884.  
  885.  
  886. /*
  887.  * Name:    factor
  888.  * Purpose: add NNODEs and CNODEs to local global nfa
  889.  * Date:    June 5, 1993
  890.  * Passed:  none
  891.  * Returns: none, but modifies local global nfa.
  892.  * Notes:   this function does most of the compiling.  it recognizes all
  893.  *          NNODEs, predefined macros, escape characters, and operators.
  894.  */
  895. int  factor( void )
  896. {
  897. int t1;
  898. int t2;
  899. int r;
  900. int c;
  901. int paren;
  902.  
  903.    t2 = t1 = parser_state;
  904.    paren = FALSE;
  905.    c = regx.pattern[lookahead];
  906.    if (c == '(') {
  907.       lookahead++;
  908.       t2 = expression( );
  909.       if (regx.pattern[lookahead] == ')') {
  910.          lookahead++;
  911.          paren = TRUE;
  912.       } else
  913.  
  914.          /*
  915.           * unmatched open parens
  916.           */
  917.          regx_error( reg2 );
  918.    } else if (letter( c )) {
  919.       paren = FALSE;
  920.       switch (c) {
  921.          case ']' :
  922.  
  923.             /*
  924.              * unmatched close bracket
  925.              */
  926.             regx_error( reg9 );
  927.             break;
  928.          case '.' :
  929.             ttype = WILD;
  930.             break;
  931.          case ',' :
  932.             ttype = WHITESPACE;
  933.             break;
  934.          case '^' :
  935.             ttype = BOL;
  936.             break;
  937.          case '$' :
  938.             ttype = EOL;
  939.             break;
  940.          case '<' :
  941.             ttype = BOW;
  942.             break;
  943.          case '>' :
  944.             ttype = EOW;
  945.             break;
  946.          case '\\' :
  947.             ++lookahead;
  948.             ttype =  mode.search_case == IGNORE ? IGNORE_ASCII : STRAIGHT_ASCII;
  949.             if (lookahead != '\0') {
  950.                if (regx.pattern[lookahead] != ':')
  951.                   c = escape_char( regx.pattern[lookahead] );
  952.  
  953.                /*
  954.                 * predefined unix-like macros.
  955.                 */
  956.                else {
  957.                   c = regx.pattern[lookahead+1];
  958.                   if (c != '\0') {
  959.                      switch (c) {
  960.                         case REG_ALPHANUM :
  961.                            ++lookahead;
  962.                            ttype = ALPHANUM;
  963.                            break;
  964.                         case REG_WHITESPACE :
  965.                            ++lookahead;
  966.                            ttype = WHITESPACE;
  967.                            break;
  968.                         case REG_ALPHA :
  969.                            ++lookahead;
  970.                            ttype = ALPHA;
  971.                            break;
  972.                         case REG_DECIMAL :
  973.                            ++lookahead;
  974.                            ttype = DECIMAL;
  975.                            break;
  976.                         case REG_HEX :
  977.                            ++lookahead;
  978.                            ttype = HEX;
  979.                            break;
  980.                         case REG_LOWER :
  981.                            ++lookahead;
  982.                            ttype = LOWER;
  983.                            break;
  984.                         case REG_UPPER :
  985.                            ++lookahead;
  986.                            ttype = UPPER;
  987.                            break;
  988.                         default :
  989.                            c = escape_char( regx.pattern[lookahead] );
  990.                            break;
  991.                      }
  992.                   } else
  993.                      c = escape_char( regx.pattern[lookahead] );
  994.                }
  995.             } else
  996.                regx_error( reg4 );
  997.             break;
  998.          case '[' :
  999.             memset( class_bits, 0, sizeof(char) * 32 );
  1000.             ++lookahead;
  1001.             if (lookahead != '\0') {
  1002.                c = regx.pattern[lookahead];
  1003.                if (c == '^') {
  1004.                   ++lookahead;
  1005.                   ttype = NOTCLASS;
  1006.                } else
  1007.                   ttype = CLASS;
  1008.  
  1009.                c1 = regx.pattern[lookahead];
  1010.                do {
  1011.                   class_bits[c1/8]  |=  bit[c1%8];
  1012.                   if (c1 != '\0')
  1013.                      ++lookahead;
  1014.                   if (regx.pattern[lookahead] == '-') {
  1015.                      ++lookahead;
  1016.                      c2 = regx.pattern[lookahead];
  1017.                      if (c2 != '\0') {
  1018.  
  1019.                         /*
  1020.                          * just in case the hi for the range is given first,
  1021.                          *  switch c1 and c2,  e.g. [9-0].
  1022.                          */
  1023.                         if (c2 < c1) {
  1024.                            c  = c2;
  1025.                            c2 = c1;
  1026.                            c1 = c;
  1027.                         }
  1028.  
  1029.                         for (c=c1; c <= c2; c++)
  1030.                            class_bits[c/8] |= bit[c%8];
  1031.  
  1032.                         if (regx.pattern[lookahead] != '\0')
  1033.                            ++lookahead;
  1034.                      } else
  1035.                         regx_error( reg10 );
  1036.                   }
  1037.                   c1 = regx.pattern[lookahead];
  1038.                } while (c1  != '\0'  &&  c1 != ']');
  1039.  
  1040.                if (c1 == '\0')
  1041.                   regx_error( reg5 );
  1042.             } else
  1043.                regx_error( reg6 );
  1044.             break;
  1045.          default :
  1046.             if (mode.search_case == IGNORE) {
  1047.                c = tolower( c );
  1048.                ttype = IGNORE_ASCII;
  1049.             } else
  1050.                ttype = STRAIGHT_ASCII;
  1051.       }
  1052.       emit_nnode( parser_state, ttype, c, parser_state+1, parser_state+1 );
  1053.       if (ttype == CLASS  ||  ttype == NOTCLASS) {
  1054.          nfa.class[parser_state] = calloc( 32, sizeof(char) );
  1055.          if (nfa.class[parser_state] != NULL)
  1056.             memcpy( nfa.class[parser_state], class_bits, sizeof( char )*32 );
  1057.          else
  1058.             regx_error( reg7 );
  1059.       }
  1060.       t2 = parser_state;
  1061.       lookahead++;
  1062.       parser_state++;
  1063.    } else if (c == '\0')
  1064.       return( 0 );
  1065.    else {
  1066.       if (c == '*'  ||  c == '+'  ||  c == '?')
  1067.          regx_error( reg8 );
  1068.       else if (c  ==  ')')
  1069.          regx_error( reg3 );
  1070.       else
  1071.          regx_error( reg2 );
  1072.    }
  1073.  
  1074.    c = regx.pattern[lookahead];
  1075.    switch (c) {
  1076.       case '*' :
  1077.          emit_cnode( parser_state, CLOSURE, parser_state+1, t2 );
  1078.          r = parser_state;
  1079.          if (nfa.node_type[t1] == CNODE)
  1080.             t1 = min( nfa.next1[t1], nfa.next2[t1] );
  1081.          nfa.next1[t1-1] = parser_state;
  1082.          if (nfa.node_type[t1-1] == NNODE)
  1083.             nfa.next2[t1-1] = parser_state;
  1084.          lookahead++;
  1085.          parser_state++;
  1086.          paren = FALSE;
  1087.          break;
  1088.       case '+' :
  1089.          if (paren == TRUE) {
  1090.             emit_cnode( parser_state, JUXTA, parser_state+2, parser_state+2 );
  1091.             parser_state++;
  1092.          }
  1093.  
  1094.          emit_cnode( parser_state, JUXTA, t2, t2 );
  1095.          r = parser_state;
  1096.          parser_state++;
  1097.  
  1098.          if (paren == FALSE) {
  1099.             nfa.next1[t2] = parser_state;
  1100.             if (nfa.node_type[t2] == NNODE)
  1101.                nfa.next2[t2] = parser_state;
  1102.          }
  1103.  
  1104.          emit_cnode( parser_state, CLOSURE, parser_state+1, t2 );
  1105.          if (nfa.node_type[t1] == CNODE)
  1106.             t1 = min( nfa.next1[t1], nfa.next2[t1] );
  1107.          nfa.next1[t1-1] = r;
  1108.          if (nfa.node_type[t1-1] == NNODE)
  1109.             nfa.next2[t1-1] = r;
  1110.          parser_state++;
  1111.          lookahead++;
  1112.          paren = FALSE;
  1113.          break;
  1114.       case '?' :
  1115.          emit_cnode( parser_state, JUXTA, parser_state+2, parser_state+2 );
  1116.          parser_state++;
  1117.          r = parser_state;
  1118.          emit_cnode( parser_state, ZERO_OR_ONE, parser_state+1, t2 );
  1119.          if (nfa.node_type[t1] == CNODE)
  1120.             t1 = min( nfa.next1[t1], nfa.next2[t1] );
  1121.          nfa.next1[t1-1] = parser_state;
  1122.          if (nfa.node_type[t1-1] == NNODE)
  1123.             nfa.next2[t1-1] = parser_state;
  1124.          parser_state++;
  1125.          lookahead++;
  1126.          paren = FALSE;
  1127.          break;
  1128.       default  :
  1129.          r = t2;
  1130.          break;
  1131.    }
  1132.  
  1133.    /*
  1134.     * close parens seem to need a JUXTA node to gather all reg ex's
  1135.     *  to a common point.
  1136.     */
  1137.    if (paren) {
  1138.       emit_cnode( parser_state, JUXTA, parser_state+1, parser_state+1 );
  1139.       parser_state++;
  1140.    }
  1141.    return( r );
  1142. }
  1143.  
  1144.  
  1145. /*
  1146.  * Name:    escape_char
  1147.  * Purpose: recognize escape and C escape sequences
  1148.  * Date:    June 5, 1993
  1149.  * Passed:  let:  letter to escape
  1150.  * Returns: escaped letter
  1151.  */
  1152. int  escape_char( int let )
  1153. {
  1154.    switch (let) {
  1155.       case '0' :
  1156.          let = 0x00;
  1157.          break;
  1158.       case 'a' :
  1159.          let = 0x07;
  1160.          break;
  1161.       case 'b' :
  1162.          let = 0x08;
  1163.          break;
  1164.       case 'n' :
  1165.          let = 0x0a;
  1166.          break;
  1167.       case 'r' :
  1168.          let = 0x0d;
  1169.          break;
  1170.       case 't' :
  1171.          let = 0x09;
  1172.          break;
  1173.       default  :
  1174.          break;
  1175.    }
  1176.    return( let );
  1177. }
  1178.  
  1179.  
  1180. /*
  1181.  * Name:    emit_cnode
  1182.  * Purpose: add a null node to our pattern matching machine
  1183.  * Date:    June 5, 1993
  1184.  * Passed:  index:  current node in nfa
  1185.  *          ttype:  terminal type - CLOSURE, OR, JUXTA, etc...
  1186.  *          n1:     pointer to next state, path for lambda transitions
  1187.  *          n2:     pointer to other next state, usually a NNODE
  1188.  * Returns: none, but modifies local global nfa.
  1189.  */
  1190. void emit_cnode( int index, int ttype, int n1, int n2 )
  1191. {
  1192.    assert( index >= 0);
  1193.    assert( index < REGX_SIZE );
  1194.  
  1195.    nfa.node_type[index] = CNODE;
  1196.    nfa.term_type[index] = ttype;
  1197.    nfa.c[index] = 0;
  1198.    nfa.next1[index] = n1;
  1199.    nfa.next2[index] = n2;
  1200. }
  1201.  
  1202.  
  1203. /*
  1204.  * Name:    emit_nnode
  1205.  * Purpose: add a to our pattern matching machine
  1206.  * Date:    June 5, 1993
  1207.  * Passed:  index:  current node in nfa
  1208.  *          ttype:  terminal type - EOL, ASCII, etc...
  1209.  *          c:      letter this node recognizes
  1210.  *          n1:     pointer to next state
  1211.  *          n2:     pointer to other next state, which can be same as n1
  1212.  * Returns: none, but modifies local global nfa.
  1213.  */
  1214. void emit_nnode( int index, int ttype, int c, int n1, int n2 )
  1215. {
  1216.    assert( index >= 0);
  1217.    assert( index < REGX_SIZE );
  1218.  
  1219.    nfa.node_type[index] = NNODE;
  1220.    nfa.term_type[index] = ttype;
  1221.    nfa.c[index] = c;
  1222.    nfa.next1[index] = n1;
  1223.    nfa.next2[index] = n2;
  1224. }
  1225.  
  1226.  
  1227. /*
  1228.  * Name:    init_nfa
  1229.  * Purpose: set local global nfa to NULL state
  1230.  * Date:    June 5, 1993
  1231.  * Passed:  none
  1232.  */
  1233. void init_nfa( void )
  1234. {
  1235. int i;
  1236.  
  1237.    for (i=0; i < REGX_SIZE; i++) {
  1238.       nfa.node_type[i] = NNODE;
  1239.       nfa.term_type[i] = 0;
  1240.       nfa.c[i] = 0;
  1241.       nfa.next1[i] = 0;
  1242.       nfa.next2[i] = 0;
  1243.       if (nfa.class[i] != NULL)
  1244.          free( nfa.class[i] );
  1245.       nfa.class[i] = NULL;
  1246.    }
  1247. }
  1248.  
  1249.  
  1250. /*
  1251.  * Name:    regx_error
  1252.  * Purpose: display reg ex error message and set reg ex error code
  1253.  * Date:    June 5, 1993
  1254.  * Passed:  line:  line to display error
  1255.  * Returns: none, but sets reg ex return code to error.
  1256.  */
  1257. void regx_error( char *line )
  1258. {
  1259.    error( WARNING, regx_error_line, line );
  1260.    regx_rc = ERROR;
  1261. }
  1262.  
  1263.  
  1264. /*
  1265.  * Name:    separator
  1266.  * Purpose: determine if character is a reg ex separator
  1267.  * Date:    June 5, 1993
  1268.  * Passed:  let:  letter to look at
  1269.  * Returns: whether or not 'let' is a separator
  1270.  */
  1271. int  separator( int let )
  1272. {
  1273.    return( let == 0  ||  let == ')'  ||  let == '|' );
  1274. }
  1275.  
  1276.  
  1277. /*
  1278.  * Name:    Kleene_star
  1279.  * Purpose: determine if character is a reg ex operator
  1280.  * Date:    June 5, 1993
  1281.  * Passed:  let:  letter to look at
  1282.  * Returns: whether or not 'let' is a letter
  1283.  */
  1284. int  Kleene_star( int let )
  1285. {
  1286.    return( let == '*'  ||  let == '+'  ||  let == '?' );
  1287. }
  1288.  
  1289.  
  1290. /*
  1291.  * Name:    letter
  1292.  * Purpose: determine if character is a recognized reg ex character
  1293.  * Date:    June 5, 1993
  1294.  * Passed:  let:  letter to look at
  1295.  * Returns: whether or not 'let' is a letter.
  1296.  */
  1297. int  letter( int let )
  1298. {
  1299.    return( !separator( let )  &&  !Kleene_star( let ) );
  1300. }
  1301.