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