home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / radsrc22 / src / common / rexpr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-11-01  |  7.1 KB  |  284 lines
  1. /* Copyright (c) 1990 Regents of the University of California */
  2.  
  3. #ifndef lint
  4. static char SCCSid[] = "@(#)rexpr.c 2.2 11/1/92 LBL";
  5. #endif
  6.  
  7. #include <stdio.h>
  8. #include <ctype.h>
  9. /*
  10.  * rexpr.c - regular expression parser (ala grep)
  11.  */
  12.  
  13. #define CCHR    2
  14. #define CDOT    4
  15. #define CCL     6
  16. #define NCCL    8
  17. #define CDOL    10
  18. #define CEOF    11
  19. #define CBRC    14
  20. #define CLET    15
  21. #define STAR    01
  22.  
  23. #define ESIZE   255
  24.  
  25. #define same(a,b) (a==b || (iflag && (a^b)==' ' && isalpha(a)))
  26.  
  27. #ifdef  BSD
  28. #define  memcpy(to,from,len)    bcopy(from,to,len)
  29. #endif
  30.  
  31. static int     advance(), cclass();
  32.  
  33. static char    expbuf[ESIZE];
  34. static int     iflag;
  35. static int     circf;
  36.  
  37. int    explen;                 /* length of the last expression found */
  38.  
  39. int
  40. ecompile(sp, iflg, wflag)               /* compile the expression */
  41. register char  *sp;
  42. int iflg, wflag;
  43. {
  44.         register c;
  45.         register char *ep;
  46.         char *lastep;
  47.         int cclcnt;
  48.         
  49.         iflag = iflg;
  50.         ep = expbuf;
  51.     explen = 0;
  52.         if (*sp == '^') {
  53.                 circf = 1;
  54.                 sp++;
  55.         } else
  56.             circf = 0;
  57.         if (wflag)
  58.                 *ep++ = CBRC;
  59.         for (;;) {
  60.                 if (ep >= &expbuf[ESIZE])
  61.                         return(-1);
  62.                 if ((c = *sp++) != '*')
  63.                         lastep = ep;
  64.                 switch (c) {
  65.  
  66.                 case '\0':
  67.                         if (wflag)
  68.                                 *ep++ = CLET;
  69.                         *ep++ = CEOF;
  70.             explen = ep - expbuf;
  71.                         return(0);
  72.  
  73.                 case '.':
  74.                         *ep++ = CDOT;
  75.                         continue;
  76.  
  77.                 case '*':
  78.                         if (lastep==0)
  79.                                 goto defchar;
  80.                         *lastep |= STAR;
  81.                         continue;
  82.  
  83.                 case '$':
  84.                         if (*sp != '\0')
  85.                                 goto defchar;
  86.                         *ep++ = CDOL;
  87.                         continue;
  88.  
  89.                 case '[':
  90.                         *ep++ = CCL;
  91.                         *ep++ = 0;
  92.                         cclcnt = 1;
  93.                         if ((c = *sp++) == '^') {
  94.                                 c = *sp++;
  95.                                 ep[-2] = NCCL;
  96.                         }
  97.                         do {
  98.                                 *ep++ = c;
  99.                                 cclcnt++;
  100.                                 if (c=='\0' || ep >= &expbuf[ESIZE])
  101.                                         return(-1);
  102.                         } while ((c = *sp++) != ']');
  103.                         lastep[1] = cclcnt;
  104.                         continue;
  105.  
  106.                 case '\\':
  107.                         if ((c = *sp++) == '\0')
  108.                                 return(-1);
  109.                         if (c == '<') {
  110.                 if (ep == expbuf || ep[-1] != CBRC)
  111.                     *ep++ = CBRC;
  112.                                 continue;
  113.                         }
  114.                         if (c == '>') {
  115.                                 *ep++ = CLET;
  116.                                 continue;
  117.                         }
  118.                 defchar:
  119.                 default:
  120.                         *ep++ = CCHR;
  121.                         *ep++ = c;
  122.                 }
  123.         }
  124. }
  125.  
  126. char *
  127. expsave()              /* save compiled string */
  128. {
  129.     extern char  *malloc();
  130.     register char  *ep;
  131.  
  132.     if (explen == 0)
  133.         return(NULL);
  134.     if ((ep = malloc(explen+3)) == NULL)
  135.         return(NULL);
  136.     ep[0] = iflag;
  137.     ep[1] = circf;
  138.     ep[2] = explen;
  139.     (void)memcpy(ep+3, expbuf, explen);
  140.     return(ep);
  141. }
  142.  
  143. expset(ep)            /* install saved string */
  144. register char  *ep;
  145. {
  146.     iflag = ep[0];
  147.     circf = ep[1];
  148.     (void)memcpy(expbuf, ep+3, ep[2]&0xff);
  149. }
  150.  
  151. char *
  152. eindex(sp)                    /* find the expression in string sp */
  153. register char *sp;
  154. {
  155.     /* check for match at beginning of line, watch CBRC */
  156.     if (advance(sp, expbuf[0]==CBRC ? expbuf+1 : expbuf))
  157.         return(sp);
  158.     if (circf)
  159.                 return(NULL);
  160.         /* fast check for first character */
  161.         if (expbuf[0]==CCHR) {
  162.         register c = expbuf[1];
  163.         while (*++sp)
  164.             if (same(*sp, c) && advance(sp, expbuf))
  165.                 return(sp);
  166.                 return(NULL);
  167.         }
  168.         /* regular algorithm */
  169.     while (*++sp)
  170.                 if (advance(sp, expbuf))
  171.                         return(sp);
  172.         return(NULL);
  173. }
  174.  
  175. static int
  176. advance(alp, ep)
  177.         char *alp;
  178. register char *ep;
  179. {
  180.         register char *lp;
  181.     char *curlp;
  182.  
  183.         lp = alp;
  184.         for (;;) switch (*ep++) {
  185.  
  186.         case CCHR:
  187.                 if (!same(*ep, *lp))
  188.                         return (0);
  189.                 ep++, lp++;
  190.                 continue;
  191.  
  192.         case CDOT:
  193.                 if (*lp++)
  194.                         continue;
  195.                 return(0);
  196.  
  197.         case CDOL:
  198.                 if (*lp==0)
  199.                         continue;
  200.                 return(0);
  201.  
  202.         case CEOF:
  203.                 explen = lp - alp;
  204.                 return(1);
  205.  
  206.         case CCL:
  207.                 if (cclass(ep, *lp++, 1)) {
  208.                         ep += *ep;
  209.                         continue;
  210.                 }
  211.                 return(0);
  212.  
  213.         case NCCL:
  214.                 if (cclass(ep, *lp++, 0)) {
  215.                         ep += *ep;
  216.                         continue;
  217.                 }
  218.                 return(0);
  219.  
  220.         case CDOT|STAR:
  221.                 curlp = lp;
  222.                 while (*lp++);
  223.                 goto star;
  224.  
  225.         case CCHR|STAR:
  226.                 curlp = lp;
  227.                 while (same(*lp, *ep))
  228.                         lp++;
  229.                 lp++;
  230.                 ep++;
  231.                 goto star;
  232.  
  233.         case CCL|STAR:
  234.         case NCCL|STAR:
  235.                 curlp = lp;
  236.                 while (cclass(ep, *lp++, ep[-1]==(CCL|STAR)));
  237.                 ep += *ep;
  238.         star:
  239.                 do {
  240.                         lp--;
  241.                         if (advance(lp, ep)) {
  242.                                 explen += lp - alp;
  243.                                 return(1);
  244.                         }
  245.                 } while (lp > curlp);
  246.                 return(0);
  247.  
  248.         case CBRC:
  249.                 if ((isalnum(*lp) || *lp == '_') && !(isalnum(lp[-1]) || lp[-1] == '_'))
  250.                         continue;
  251.                 return (0);
  252.  
  253.         case CLET:
  254.                 if (!isalnum(*lp) && *lp != '_')
  255.                         continue;
  256.                 return (0);
  257.  
  258.         default:
  259.                 fprintf(stderr, "RE botch\n");
  260.         }
  261. }
  262.  
  263. static int
  264. cclass(set, c, af)
  265. register char *set;
  266. register c;
  267. {
  268.         register n;
  269.  
  270.         if (c == 0)
  271.                 return(0);
  272.         n = *set++;
  273.         while (--n)
  274.                 if (n > 2 && set[1] == '-') {
  275.                         if (c >= set[0] && c <= set[2])
  276.                                 return (af);
  277.                         set += 3;
  278.                         n -= 2;
  279.                 } else
  280.                         if (*set++ == c)
  281.                                 return(af);
  282.         return(!af);
  283. }
  284.