home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / dgrep.arc / DFAREGEX.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-01-18  |  5.6 KB  |  200 lines
  1. /**********************************************************************\
  2.  *
  3.  *    DFAREGEX.C
  4.  *
  5.  * Deterministic finite automata regular expression matcher.
  6.  *
  7.  * Author: Jarmo Ruuth 15-Mar-1988
  8.  *
  9.  * Copyright (C) 1988-90 by Jarmo Ruuth
  10.  * May be freely copied for any non-commercial usage.
  11. \**********************************************************************/
  12.  
  13. #include "system.h"
  14. #include "dfa.h"
  15. #include "dfaregex.h"
  16.  
  17. /*
  18.     Regular expression buffer. It is defined statically here, so
  19.     it is not possible to compile and use several regexps at the
  20.     same time. The reason for the static buffer is that it makes
  21.     things slightly faster on the PC. Using dynamic buffer would
  22.     also require adding the regbuf_t* parameter to almost all
  23.     function calls.
  24. */
  25. regbuf_t     rbuf;
  26.  
  27. #ifdef TEST
  28. extern int debug;
  29. #endif
  30.  
  31. /**********************************************************************
  32.  *
  33.  *    free_rbufmem
  34.  *
  35.  * Releases memory held by regular expression.
  36.  */
  37. static void free_rbufmem(void)
  38. {
  39.     REG1 int    i;
  40.     
  41.     for (i = 0; i < NTRAN; i++) {
  42.         d_free(&rbuf.dstates[i]->set);
  43.         d_free(&rbuf.dstates[i]);
  44.     }
  45.     if (rbuf.follow_array != NULL) {
  46.         for (i = 0; i <= rbuf.root; i++)
  47.             d_free(&rbuf.follow_array[i]);
  48.         d_free(&rbuf.follow_array);
  49.     }
  50.     if (rbuf.tree != NULL) {
  51.         for (i = 0; i <= rbuf.root; i++) {
  52.             if (rbuf.tree[i].type == CLASS_ID)
  53.                 d_free(&rbuf.tree[i].val.class);
  54.         }
  55.         d_free(&rbuf.tree);
  56.     }
  57.     d_free(&rbuf.regmust);
  58.     d_free(&rbuf.language);
  59.     d_free(&rbuf.tmpstate);
  60.     rbuf.mem_allocated = FALSE;
  61. }
  62.  
  63. /**********************************************************************
  64.  *
  65.  *    reg_comp_eol
  66.  *
  67.  * Compiles regular expression. It is possible to specify end of line
  68.  * characters. If the end of line characters equal, then only one end
  69.  * of line character is used.
  70.  */
  71. char* reg_comp_eol(REG1 char* regexp, char eol1, char eol2, int type_bits)
  72. {
  73.     if (regexp == NULL)
  74.         return "No regular expression";
  75.     rbuf.reg_error = NULL;
  76.     rbuf.eol = eol1;
  77.     rbuf.eol2 = eol2;
  78.     rbuf.neol = (eol1 == eol2 ? 1 : 2);
  79.     rbuf.ignorecase = type_bits & RE_IGNORECASE;
  80.     rbuf.search = type_bits & RE_SEARCH;
  81.     rbuf.full = type_bits & RE_FULL;
  82.     if (rbuf.mem_allocated)
  83.         free_rbufmem();
  84.     if (create_tree(regexp) == ERROR)
  85.         return rbuf.reg_error;
  86.     if (!find_regmust(rbuf.tree, rbuf.root)) {
  87.         free_rbufmem();
  88.         return rbuf.reg_error = "Out of memory when allocating regmust";
  89.     }
  90. #ifdef TEST
  91.     if (debug)
  92.         printf("Regmust = '%s'\n", rbuf.regmust);
  93. #endif
  94.     if (!calcpos()) {
  95.         free_rbufmem();
  96.         return rbuf.reg_error = "Out of memory in calcpos";
  97.     }
  98.     if (!dfa()) {
  99.         free_rbufmem();
  100.         return rbuf.reg_error = "Out of memory when creating dfa";
  101.     }
  102.     rbuf.mem_allocated = TRUE;
  103. #ifdef TEST
  104.     if (debug > 1) {
  105.         print_accepting_states();
  106.         print_dtran();
  107.     }
  108. #endif
  109.     return rbuf.reg_error;
  110. }
  111.  
  112. /**********************************************************************
  113.  *
  114.  *    reg_comp
  115.  *
  116.  * Compiles regular expression with predefined end of line character
  117.  * suitable for C's null-terminating string representation.
  118.  */
  119. char* reg_comp(char* regexp, int type_bits)
  120. {
  121.     return reg_comp_eol(regexp, '\0', '\0', type_bits);
  122. }
  123.  
  124. /**********************************************************************
  125.  *
  126.  *    reg_exec
  127.  *
  128.  * Executes regular expression to the string 's'. Return value is NULL,
  129.  * if no match was found and pointer to the last matching char, if match 
  130.  * was found. Note that last matching char can be end of line character.
  131.  *
  132.  * Parameters:
  133.  *     Strbeg points to the beginning of the line.
  134.  *    Strend points to the first character after the string. We put
  135.  *        the end of line character to the *strend (like GNU grep), 
  136.  *        so it should point to somewhere valid.
  137.  *    Linecnt points to the counter, that we increment every time we see
  138.  *        an end of line character, if it does not belong to the matched
  139.  *        line. If linecnt is NULL, it is not incremented.
  140.  */
  141. char* reg_exec(char* strbeg, REG5 char* strend, REG6 ulong* linecnt)
  142. {
  143.     REG1 uchar*     s;
  144. #ifdef FAST
  145.     REG2 tran_t    cur_state = FIRST_STATE;
  146.     REG3 tran_t    prev_state;
  147. #else
  148.     /* use unsigned state variables, because some compilers can't
  149.        put char variables to registers (usually tran_t is char) */
  150.     REG2 unsigned    cur_state = FIRST_STATE;
  151.     REG3 unsigned    prev_state;
  152. #endif
  153.     REG4 char    save_char;
  154.     
  155.     s = strbeg;
  156.     if (s == NULL || strend == NULL)
  157.         return NULL;
  158.     save_char = *strend;
  159.     *strend = rbuf.eol;
  160.     if (rbuf.begline) {
  161. check_bol:
  162.         /* we need separate beginning-of-line check, because
  163.            there are no real character for that position */
  164.         prev_state = FIRST_STATE;
  165.         cur_state = rbuf.dstates[0]->tran[BOL];
  166.         if (cur_state == UNKNOWN)
  167.             cur_state = get_transition(FIRST_STATE, BOL);
  168.         if (cur_state == STOPSTATE)
  169.             cur_state = FIRST_STATE;  /* we might match later */
  170.         else if (cur_state == ACCEPTING)
  171.             s++;    /* now we return correct pointer */
  172.     }
  173.     do {
  174.         /* the inner loop */
  175.         for (; cur_state < MAXTRAN; ) {
  176.             prev_state = cur_state;
  177.             cur_state = state_of(cur_state)->tran[*s++];
  178.         }
  179.         if (cur_state == UNKNOWN)
  180.             cur_state = get_transition(prev_state, *(s-1));
  181.         if (cur_state == END_OF_LINE) {
  182.             cur_state = state_of(prev_state)->tran[EOL];
  183.             if (cur_state == ACCEPTING)
  184.                 break;    /* return match */
  185.             if (linecnt)
  186.                 (*linecnt)++;
  187.             /* if there are more than one eol-char, skip them */
  188.             if (rbuf.neol > 1 && *s == rbuf.eol2)
  189.                 s++;
  190.             if (s > strend || cur_state == STOPSTATE)
  191.                 break;    /* return NULL */
  192.             if (rbuf.begline)
  193.                 goto check_bol;
  194.             cur_state = FIRST_STATE;
  195.         }
  196.     } while (cur_state < MAXTRAN);
  197.     *strend = save_char;
  198.     return cur_state == ACCEPTING ? s-1 : NULL;
  199. }
  200.