home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 3 / PDCD_3.iso / tex / lgrind / !lgrind / src / c / regexp < prev    next >
Encoding:
Text File  |  1994-02-15  |  14.6 KB  |  690 lines
  1. #ifndef lint
  2. static char *sccsid="@(#)regexp.c    1.2 (LBL) 4/12/85";
  3. static char Version[] =
  4.    "$Id: regexp.c,v 1.2 91/10/01 00:30:20 gvr Exp $";
  5. #endif
  6.  
  7. /*
  8.  * Regular expression matching routines for lgrind/tgrind/tfontedpr.
  9.  *
  10.  * These routines were written by Dave Presotto (I think) for vgrind.
  11.  * Minor mods & attempts to improve performance by Van Jacobson
  12.  * (van@@lbl-rtsg) and Chris Torek (chris@@maryland).
  13.  *
  14.  * Modifications.
  15.  * --------------
  16.  *    Sep 91    George V Reilly    Fixed up some bogus uses of @NIL@ and @NULL@.
  17.  * 30 Mar 85    Van & Chris    Changed @expmatch()@ to return pointer to
  18.  *                start of what was matched in addition to
  19.  *                pointer to match end.  Several changes to
  20.  *                improve performance (too numerous to mention).
  21.  * 11 Dec 84    Dave Presotto    Written.
  22.  */
  23. #include <stdio.h>
  24. #include <ctype.h>
  25.  
  26. #ifdef __STDC__
  27. #include <stdlib.h>
  28. #else
  29. extern void srand();
  30. extern int rand();
  31. extern void *malloc();
  32. extern void *realloc();
  33. extern void free();
  34. #endif
  35.  
  36.  
  37. typedef int    boolean;
  38. #define TRUE    1
  39. #define FALSE    0
  40.  
  41. #define makelower(c) (isupper((c)) ? tolower((c)) : (c))
  42.  
  43. void    expconv();     /* forward declaration */
  44.  
  45. int    (*re_strncmp)();     /* function used by @expmatch()@ to compare
  46.               * strings.  The caller should make it point to
  47.               * @strncmp()@ if case is significant &
  48.               * @lc_strncmp()@ otherwise.
  49.               */
  50.  
  51.  
  52. /*  @lc_strncmp()@ ---    like @strncmp()@ except that we convert the
  53.  *            first string to lower case before comparing.
  54.  */
  55.    int
  56. lc_strncmp(s1, s2, len)
  57.    register char *s1,*s2;
  58.    register int len;
  59. {
  60.    while (len-- > 0)
  61.       if (*s2 - makelower(*s1))
  62.      return 1;
  63.       else
  64.      s2++, s1++;
  65.    
  66.    return 0;
  67. }
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101. /*  The following routine converts an irregular expression to
  102.  *  internal format.
  103.  *
  104.  *  Either meta symbols (%|\a|%, %|\d|%, or %|\p|%) or character strings
  105.  *  or operations (alternation or parenthesizing) can be specified.
  106.  *  Each starts with a descriptor byte.  The descriptor byte
  107.  *  has @STR@ set for strings, @META@ set for meta symbols,
  108.  *  and @OPER@ set for operations.  The descriptor byte can also have
  109.  *  the @OPT@ bit set if the object defined is optional.  Also @ALT@
  110.  *  can be set to indicate an alternation.
  111.  *
  112.  *  For metasymbols, the byte following the descriptor byte identities
  113.  *  the meta symbol (containing an ASCII @'a'@, @'d'@, @'p'@, @'|'@,
  114.  *  or @'('@).  For strings, the byte after the descriptor is a
  115.  *  character count for the string:
  116.  *@
  117.  *    meta symbols :=    descriptor
  118.  *            symbol
  119.  *
  120.  *    strings :=    descriptor
  121.  *            character count
  122.  *            the string
  123.  *
  124.  *    operations :=    descriptor
  125.  *            symbol
  126.  *            character count@
  127.  */
  128.  
  129.  
  130. /*
  131.  *  handy macros for accessing parts of match blocks
  132.  */
  133. #define MSYM(A)     (*(A+1))    /* symbol in a meta symbol block */
  134. #define MNEXT(A) (A+2)        /* character following a metasymbol block */
  135.  
  136. #define OSYM(A)     (*(A+1))    /* symbol in an operation block */
  137. #define OCNT(A)     (*(A+2))    /* character count */
  138. #define ONEXT(A) (A+3)        /* next character after the operation */
  139. #define OPTR(A)     (A+*(A+2))    /* place pointed to by the operator */
  140.  
  141. #define SCNT(A)     (*(A+1))    /* byte count of a string */
  142. #define SSTR(A)     (A+2)        /* address of the string */
  143. #define SNEXT(A) (A+2+*(A+1))    /* character following the string */
  144.  
  145.  
  146. /*
  147.  *  bit flags in the descriptor 
  148.  */
  149. #define OPT     1
  150. #define STR     2
  151. #define META     4
  152. #define ALT     8
  153. #define OPER    16
  154.  
  155. char *ure;        /* pointer current position in unconverted exp */
  156. char *ccre;        /* pointer to current position in converted exp */
  157.  
  158.  
  159.  
  160. /*
  161.  * Convert an irregular expression to the internal form
  162.  */
  163.    char *
  164. convexp(re)
  165.    char *re;        /* unconverted irregular expression */
  166. {
  167.    register char *cre;    /* pointer to converted regular expression */
  168.    
  169.    /* allocate room for the converted expression */
  170.    if (re == NULL)
  171.       return NULL;
  172.    if (*re == '\0')
  173.       return NULL;
  174.    cre = malloc(4 * strlen(re) + 3);
  175.    ccre = cre;
  176.    ure = re;
  177.    
  178.    /* start the conversion with a %|\a|% */
  179.    *cre = META | OPT;
  180.    MSYM(cre) = 'a';
  181.    ccre = MNEXT(cre);
  182.    
  183.    /* start the conversion (it's recursive) */
  184.    expconv();
  185.    *ccre = 0;
  186.    return cre;
  187. }
  188.  
  189.  
  190. /*
  191.  * Actually do the conversion
  192.  */
  193.    static void
  194. expconv()
  195. {
  196.    register char *cs;    /* pointer to current symbol in converted exp */
  197.    register char c;    /* character being processed */
  198.    register char *acs;    /* pointer to last alternate */
  199.    register int temp;
  200.    
  201.    /* let the conversion begin */
  202.    acs = NULL;
  203.    cs = NULL;
  204.    while (*ure != '\0') {
  205.       switch (c = *ure++) {
  206.      
  207.       case '\\':
  208.      switch (c = *ure++) {
  209.         
  210.         /* escaped characters are just characters */
  211.      default:
  212.         if (cs == NULL || (*cs & STR) == 0) {
  213.            cs = ccre;
  214.            *cs = STR;
  215.            SCNT(cs) = 1;
  216.            ccre += 2;
  217.         } else 
  218.            SCNT(cs)++;
  219.         *ccre++ = c;
  220.         break;
  221.         
  222.         /* normal(?) metacharacters */
  223.      case 'a':
  224.      case 'd':
  225.      case 'e':
  226.      case 'p':
  227.         if (acs != NULL && acs != cs) {
  228.            do {
  229.           temp = OCNT(acs);
  230.           OCNT(acs) = ccre - acs; 
  231.           acs -= temp;
  232.            } while (temp != 0);
  233.            acs = NULL;
  234.         }
  235.         cs = ccre;
  236.         *cs = META;
  237.         MSYM(cs) = c;
  238.         ccre = MNEXT(cs);
  239.         break;
  240.      }
  241.      break;
  242.      
  243.      /* just put the symbol in */
  244.       case '^':
  245.       case '$':
  246.      if (acs != NULL && acs != cs) {
  247.         do {
  248.            temp = OCNT(acs);
  249.            OCNT(acs) = ccre - acs;
  250.            acs -= temp;
  251.         } while (temp != 0);
  252.         acs = NULL;
  253.      }
  254.      cs = ccre;
  255.      *cs = META;
  256.      MSYM(cs) = c;
  257.      ccre = MNEXT(cs);
  258.      break;
  259.      
  260.      /* mark the last match sequence as optional */
  261.       case '?':
  262.      if (cs)
  263.         *cs = *cs | OPT;
  264.      break;
  265.      
  266.      /* recurse and define a subexpression */
  267.       case '(':
  268.      if (acs != NULL && acs != cs) {
  269.         do {
  270.            temp = OCNT(acs);
  271.            OCNT(acs) = ccre - acs;
  272.            acs -= temp;
  273.         } while (temp != 0);
  274.         acs = NULL;
  275.      }
  276.      cs = ccre;
  277.      *cs = OPER;
  278.      OSYM(cs) = '(';
  279.      ccre = ONEXT(cs);
  280.      expconv();
  281.      OCNT(cs) = ccre - cs;        /* offset to next symbol */
  282.      break;
  283.      
  284.      /* return from a recursion */
  285.       case ')':
  286.      if (acs != NULL) {
  287.         do {
  288.            temp = OCNT(acs);
  289.            OCNT(acs) = ccre - acs;
  290.            acs -= temp;
  291.         } while (temp != 0);
  292.         acs = NULL;
  293.      }
  294.      cs = ccre;
  295.      *cs = META;
  296.      MSYM(cs) = c;
  297.      ccre = MNEXT(cs);
  298.      return;
  299.      
  300.      /* Mark the last match sequence as having an alternate. */
  301.      /* The third byte will contain an offset to jump over the */
  302.      /* alternate match in case the first did not fail */
  303.       case '|':
  304.      if (acs != NULL && acs != cs)
  305.         OCNT(ccre) = ccre - acs;    /* make a back pointer */
  306.      else
  307.         OCNT(ccre) = 0;
  308.      *cs |= ALT;
  309.      cs = ccre;
  310.      *cs = OPER;
  311.      OSYM(cs) = '|';
  312.      ccre = ONEXT(cs);
  313.      acs = cs;    /* remember that the pointer is to be filled */
  314.      break;
  315.      
  316.      /* if it's not a metasymbol, just build a character string */
  317.       default:
  318.      if (cs == NULL || (*cs & STR) == 0) {
  319.         cs = ccre;
  320.         *cs = STR;
  321.         SCNT(cs) = 1;
  322.         ccre = SSTR(cs);
  323.      } else
  324.         SCNT(cs)++;
  325.      *ccre++ = c;
  326.      break;
  327.       }
  328.    }
  329.    if (acs != NULL) {
  330.       do {
  331.      temp = OCNT(acs);
  332.      OCNT(acs) = ccre - acs;
  333.      acs -= temp;
  334.       } while (temp != 0);
  335.       acs = NULL;
  336.    }
  337.    return;
  338. } /* end of @expconv()@ */
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345.  
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353.  
  354.  
  355.  
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.  
  370.  
  371.  
  372.  
  373. /*
  374.  *  The following routine recognises an irregular expression
  375.  *  with the following special characters:
  376.  *
  377.  *    %|\?|%        means last match was optional
  378.  *    %|\a|%        matches any number of characters
  379.  *    %|\d|%        matches any number of spaces and tabs
  380.  *    %|\p|%        matches any number of alphanumeric characters.
  381.  *            The characters matched will be copied into
  382.  *            the area pointed to by @mstring@.
  383.  *    %|\||%        alternation
  384.  *    %|\( \)|%    grouping used mostly for alternation and
  385.  *            optionality
  386.  *
  387.  *  The irregular expression must be translated to internal form
  388.  *  prior to calling this routine
  389.  *
  390.  *  The value returned is the pointer to the last character matched.
  391.  *  If @strtptr@ is non-@NULL@, a pointer to the start of the string matched
  392.  *  (excluding %|\a|% matches) will be returned at @*strtptr@.  
  393.  *  If @mstring@ is non-@NULL@, the string matched by a %|\p|% will be copied
  394.  *  into @mstring@.
  395.  */
  396.  
  397. boolean _escaped;        /* true if we are currently @_escaped@ */
  398. char *_start;            /* start of string.  Set in @putScp()@. */
  399.  
  400.  
  401.  
  402.    char *
  403. expmatch(s, re, strtptr, mstring)
  404.    register char *s;        /* string to check for a match in */
  405.    register char *re;        /* a converted irregular expression */
  406.    char **strtptr;        /* where to put ptr to start of match */
  407.    char *mstring;        /* where to put whatever matches a %|\p|% */
  408. {
  409.    register char *cs;        /* the current symbol */
  410.    register char *ptr, *s1;    /* temporary pointer */
  411.    register char c;        /* temporary */
  412.    boolean matched;        /* a temporary @boolean@ */
  413.    
  414.    /* initial conditions */
  415.    if (strtptr)
  416.       *strtptr = '\0';
  417.    if (re == NULL)
  418.       return NULL;
  419.    cs = re;
  420.    matched = FALSE;
  421.    
  422.    /* loop till expression string is exhausted (or at least pretty tired) */
  423.    while (*cs) {
  424.       switch (*cs & (OPER | STR | META)) {
  425.      
  426.      /* try to match a string */
  427.       case STR:
  428.      matched = !((*re_strncmp)(s, SSTR(cs), SCNT(cs)));
  429.      if (matched) {
  430.         
  431.         /* hoorah: it matches */
  432.         s += SCNT(cs);
  433.         cs = SNEXT(cs);
  434.      } else if (*cs & ALT) {
  435.         
  436.         /* alternation: skip to next expression */
  437.         cs = SNEXT(cs);
  438.      } else if (*cs & OPT) {
  439.         
  440.         /* the match is optional */
  441.         cs = SNEXT(cs);
  442.         matched = 1;        /* indicate a successful match */
  443.      } else {
  444.         
  445.         /* no match: error return */
  446.         return NULL;
  447.      }
  448.      break;
  449.      
  450.      /* an operator: do something fancy */
  451.       case OPER:
  452.      switch (OSYM(cs)) {
  453.         
  454.         /* this is an alternation */
  455.      case '|':
  456.         if (matched)
  457.            
  458.            /* last thing in the alternation was a match: skip ahead */
  459.            cs = OPTR(cs);
  460.         else
  461.            
  462.            /* no match: keep trying */
  463.            cs = ONEXT(cs);
  464.         break;
  465.         
  466.         /* this is a grouping: recurse */
  467.      case '(':
  468.         ptr = expmatch(s, ONEXT(cs), strtptr, mstring);
  469.         if (ptr != NULL) {
  470.            
  471.            /* the subexpression matched */
  472.            matched = 1;
  473.            s = ptr;
  474.         } else if (*cs & ALT) {
  475.            
  476.            /* alternation: skip to next expression */
  477.            matched = 0;
  478.         } else if (*cs & OPT) {
  479.            
  480.            /* the match is optional */
  481.            matched = 1;    /* indicate a successful match */
  482.         } else {
  483.            
  484.            /* no match: error return */
  485.            return NULL;
  486.         }
  487.         cs = OPTR(cs);
  488.         break;
  489.      }
  490.      break;
  491.      
  492.      /* try to match a metasymbol */
  493.       case META:
  494.      switch (MSYM(cs)) {
  495.         
  496.         /* try to match anything and remember what was matched */
  497.      case 'p':
  498.         /*
  499.          *  This is really the same as trying the match the
  500.          *  remaining parts of the expression to any subset
  501.          *  of the string.
  502.          */
  503.         s1 = s;
  504.         do {
  505.            ptr = expmatch(s1, MNEXT(cs), strtptr, mstring);
  506.            if (ptr != NULL && s1 != s) {
  507.           
  508.           /* we have a match: remember the match */
  509.           if (mstring) {
  510.              strncpy(mstring, s, s1 - s);
  511.              mstring[s1 - s] = '\0';
  512.           }
  513.           return ptr;
  514.           
  515.            } else if (ptr != NULL && (*cs & OPT)) {
  516.           
  517.           /* %|\p|% was optional, so no match is ok */
  518.           return ptr;
  519.           
  520.            } else if (ptr != NULL) {
  521.           
  522.           /* not optional and we still matched */
  523.           return NULL;
  524.            }
  525.            if (!isalnum(*s1) && *s1 != '_')
  526.           return NULL;
  527.            if (*s1 == '\\')
  528.           _escaped = _escaped ? FALSE : TRUE;
  529.            else
  530.           _escaped = FALSE;
  531.         } while (*s1++);
  532.         return NULL;
  533.         
  534.         /* try to match anything */
  535.      case 'a':
  536.         /*
  537.          *  This is really the same as trying the match the
  538.          *  remaining parts of the expression to any subset
  539.          *  of the string.
  540.          */
  541.         s1 = s;
  542.         do {
  543.            /*
  544.         * Hack for an important special case: if the next thing
  545.         * in the pattern is a string, just gobble characters until
  546.         * we find something that matches that string (this saves
  547.         * the cost of a recursive call on @expmatch()@ while scanning
  548.         * for the start of comments or strings).  Since many
  549.         * patterns end with a string, we also treat that as a
  550.         * special case.
  551.         */
  552.            if(*(ptr = MNEXT(cs)) == STR) {
  553.           c = *SSTR(ptr);
  554.           while(*s1 && *s1 != c)
  555.              s1++;
  556.           
  557.           if (*s1 == 0)
  558.              return NULL;
  559.           
  560.           if (SNEXT(ptr) == 0 && (s1 != s || *cs & OPT)) {
  561.              /* next item is a string, it's the last item and
  562.               * the %|\a|% match is ok --- just loop to try & match
  563.               * the string.
  564.               */
  565.              if (strtptr)
  566.             *strtptr = s1;
  567.              
  568.              cs = ptr;
  569.              s = s1;
  570.              break;
  571.           }
  572.            }
  573.            ptr = expmatch(s1, MNEXT(cs), strtptr, mstring);
  574.            if (ptr != NULL && (s1 != s || *cs & OPT)) {
  575.           
  576.           /* we have a match */
  577.           if (strtptr)
  578.              *strtptr = s1;
  579.           
  580.           return ptr;
  581.           
  582.            } else if (ptr != NULL) {
  583.           
  584.           /* not optional and we still matched */
  585.           return NULL;
  586.            }
  587.            if (*s1 == '\\')
  588.           _escaped = _escaped ? FALSE : TRUE;
  589.            else
  590.           _escaped = FALSE;
  591.         } while (*s1++);
  592.         return NULL;
  593.         
  594.         /* fail if we are currently @_escaped@ */
  595.      case 'e':
  596.         if (_escaped)
  597.            return NULL;
  598.         cs = MNEXT(cs); 
  599.         break;
  600.         
  601.         /* match any number of tabs and spaces */
  602.      case 'd':
  603.         ptr = s;
  604.         while (*s == ' ' || *s == '\t')
  605.            s++;
  606.  
  607.         if (s != ptr || s == _start) {
  608.            
  609.            /* match: be happy */
  610.            matched = 1;
  611.            cs = MNEXT(cs); 
  612.         } else if (*s == '\n' || *s == '\0') {
  613.            
  614.            /* match: be happy */
  615.            matched = 1;
  616.            cs = MNEXT(cs); 
  617.         } else if (*cs & ALT) {
  618.            
  619.            /* try the next part */
  620.            matched = 0;
  621.            cs = MNEXT(cs);
  622.         } else if (*cs & OPT) {
  623.            
  624.            /* doesn't matter */
  625.            matched = 1;
  626.            cs = MNEXT(cs);
  627.         } else
  628.            
  629.            /* no match: error return */
  630.            return NULL;
  631.  
  632.         break;
  633.         
  634.         /* check for end of line */
  635.      case '$':
  636.         if (*s == '\0' || *s == '\n') {
  637.            
  638.            /* match: be happy */
  639.            s++;
  640.            matched = 1;
  641.            cs = MNEXT(cs);
  642.         } else if (*cs & ALT) {
  643.            
  644.            /* try the next part */
  645.            matched = 0;
  646.            cs = MNEXT(cs);
  647.         } else if (*cs & OPT) {
  648.            
  649.            /* doesn't matter */
  650.            matched = 1;
  651.            cs = MNEXT(cs);
  652.         } else
  653.            
  654.            /* no match: error return */
  655.            return NULL;
  656.         break;
  657.         
  658.         /* check for start of line */
  659.      case '^':
  660.         if (s == _start) {
  661.            
  662.            /* match: be happy */
  663.            matched = 1;
  664.            cs = MNEXT(cs);
  665.         } else if (*cs & ALT) {
  666.            
  667.            /* try the next part */
  668.            matched = 0;
  669.            cs = MNEXT(cs);
  670.         } else if (*cs & OPT) {
  671.            
  672.            /* doesn't matter */
  673.            matched = 1;
  674.            cs = MNEXT(cs);
  675.         } else
  676.            
  677.            /* no match: error return */
  678.            return NULL;
  679.         break;
  680.         
  681.         /* end of a subexpression: return success */
  682.      case ')':
  683.         return s;
  684.      }
  685.      break;
  686.       }
  687.    }
  688.    return s;
  689. }
  690.