home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / dgrep.arc / REGMUST.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-01-14  |  3.2 KB  |  133 lines
  1. /**********************************************************************\
  2.  *
  3.  *    REGMUST.C
  4.  *
  5.  * Finds regmust string from syntax tree and stores it to rbuf.regmust.
  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.  
  16. /**********************************************************************
  17.  *
  18.  *    save_must
  19.  *
  20.  * Saves regmust.
  21.  */
  22. static bool save_must(REG1 node_t* tree, REG2 int pos, int len)
  23. {
  24.     REG3 char*    ptr;
  25.     REG4 int    left, right;
  26.  
  27.     if (len <= 0) {
  28.         rbuf.regmust = NULL;
  29.         return TRUE;
  30.     }
  31.     if ((ptr = malloc(len+1)) == NULL)
  32.         return FALSE;
  33.     rbuf.regmust = ptr;
  34.     ptr += len;
  35.     *ptr-- = '\0';
  36.     while (tree[pos].type == CAT && len--) {
  37.         left = tree[pos].val.next.left;
  38.         right = tree[pos].val.next.right;
  39.         if (tree[right].type != ID)
  40.             break;
  41.         *ptr-- = tree[right].val.item;
  42.         pos = left;
  43.     }
  44.     if (len && tree[pos].type == ID)
  45.         *ptr-- = tree[pos].val.item;
  46.     if (strlen(rbuf.regmust) == 0)
  47.         d_free(&rbuf.regmust);
  48.     return TRUE;
  49. }
  50.  
  51. /**********************************************************************
  52.  *
  53.  *    IS_MUST_CH
  54.  */
  55. #define IS_MUST_CH(c)    ((int)(c) < NCHARS)
  56.  
  57. /**********************************************************************
  58.  *
  59.  *    must_len
  60.  *
  61.  * Calculates regmust lenght starting from 'pos'. Length is zero if
  62.  * current position doesn't start any regmust.
  63.  */
  64. static int must_len(REG1 node_t* tree, REG2 int* pos)
  65. {
  66.     REG3 int    len = 0;
  67.     REG4 int    left, right;
  68.     
  69.     while (tree[*pos].type == CAT) {
  70.         left = tree[*pos].val.next.left;
  71.         right = tree[*pos].val.next.right;
  72.         if (tree[right].type != ID)
  73.             return len;
  74.         if (!IS_MUST_CH(tree[right].val.item))
  75.             return len;
  76.         ++len;
  77.         if (tree[left].type == ID) {
  78.             if (IS_MUST_CH(tree[left].val.item))
  79.                 return len+1;
  80.             else
  81.                 return len;
  82.         }
  83.         *pos = left;
  84.     }
  85.     return len;
  86. }
  87.  
  88. /**********************************************************************
  89.  *
  90.  *    find_regmust
  91.  *
  92.  * Finds longest regmust, i.e. string that must match exactly in regular
  93.  * expression. A very simple linear algorithm is used: starting from root go
  94.  * always to the left and from every CAT node try to calculate regmust
  95.  * that begins from that position. Routine stops to first node that isn't
  96.  * CAT node. A better algorithm should also check possible common
  97.  * substrings from OR's, now we just give up if we find OR.
  98.  */
  99. bool find_regmust(REG1 node_t* tree, int root)
  100. {
  101.     REG2 int    len, new_len;
  102.     REG4 int    pos, save;
  103.  
  104.     rbuf.regmust = NULL;
  105.     root -= rbuf.search ? 3 : 2;
  106.     if (root == 0) {
  107.         if (rbuf.tree[0].type == ID 
  108.             && IS_MUST_CH(rbuf.tree[0].val.item))
  109.             len = 1;
  110.         else
  111.             len = 0;
  112.         return save_must(tree, 0, len);
  113.     }
  114.     len = 0;
  115.     while (tree[root].type == CAT) {
  116.         save = root;
  117.         new_len = must_len(tree, &root);
  118.         if (new_len > len) {
  119.             len = new_len;
  120.             pos = save;
  121.         }
  122.         if (root == save)
  123.             root = tree[root].val.next.left;
  124.     }
  125.     if (tree[root].type == ID && len < 1 
  126.         && IS_MUST_CH(rbuf.tree[root].val.item))
  127.     {
  128.         len = 1;
  129.         pos = root;
  130.     }
  131.     return save_must(tree, pos, len > MAXREGMUST ? MAXREGMUST : len);
  132. }
  133.