home *** CD-ROM | disk | FTP | other *** search
/ Super Net 1 / SUPERNET_1.iso / PC / OTROS / UNIX / ARCHIE / CLIENTS / XARCHIE2.TAR / regex.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-21  |  15.7 KB  |  690 lines
  1. #ifdef NOREGEX
  2. /*
  3.  * These routines are BSD regex(3)/ed(1) compatible regular-expression
  4.  * routines written by Ozan S. Yigit, Computer Science, York University.
  5.  * Parts of the code that are not needed by Prospero have been removed,
  6.  * but most of the accompanying information has been left intact. 
  7.  * This file is to be included on those operating systems that do not
  8.  * support re_comp and re_exec.
  9.  */
  10.  
  11. /*
  12.  * regex - Regular expression pattern matching
  13.  *         and replacement
  14.  *
  15.  * by:  Ozan S. Yigit (oz@nexus.yorku.ca)
  16.  *    Dept. of Computing Services
  17.  *      York University
  18.  *
  19.  * These routines are the PUBLIC DOMAIN equivalents 
  20.  * of regex routines as found in 4.nBSD UN*X, with minor
  21.  * extensions.
  22.  *
  23.  * Modification history:
  24.  *
  25.  * $Log:    regex.c,v $
  26.  * Revision 1.3  89/04/01  14:18:09  oz
  27.  * Change all references to a dfa: this is actually an nfa.
  28.  * 
  29.  * Revision 1.2  88/08/28  15:36:04  oz
  30.  * Use a complement bitmap to represent NCL.
  31.  * This removes the need to have seperate 
  32.  * code in the pmatch case block - it is 
  33.  * just CCL code now.
  34.  * 
  35.  * Use the actual CCL code in the CLO
  36.  * section of pmatch. No need for a recursive
  37.  * pmatch call.
  38.  * 
  39.  * Use a bitmap table to set char bits in an
  40.  * 8-bit chunk.
  41.  * 
  42.  * Routines:
  43.  *      re_comp:        compile a regular expression into
  44.  *                      a NFA.
  45.  *
  46.  *            char *re_comp(s)
  47.  *            char *s;
  48.  *
  49.  *      re_exec:        execute the NFA to match a pattern.
  50.  *
  51.  *            int re_exec(s)
  52.  *            char *s;
  53.  *
  54.  * Regular Expressions:
  55.  *
  56.  *      [1]     char    matches itself, unless it is a special
  57.  *                      character (metachar): . \ [ ] * + ^ $
  58.  *
  59.  *      [2]     .       matches any character.
  60.  *
  61.  *      [3]     \       matches the character following it, except
  62.  *            when followed by a left or right round bracket,
  63.  *            a digit 1 to 9 or a left or right angle bracket. 
  64.  *            (see [7], [8] and [9])
  65.  *            It is used as an escape character for all 
  66.  *            other meta-characters, and itself. When used
  67.  *            in a set ([4]), it is treated as an ordinary
  68.  *            character.
  69.  *
  70.  *      [4]     [set]   matches one of the characters in the set.
  71.  *                      If the first character in the set is "^",
  72.  *                      it matches a character NOT in the set, i.e. 
  73.  *            complements the set. A shorthand S-E is 
  74.  *            used to specify a set of characters S upto 
  75.  *            E, inclusive. The special characters "]" and 
  76.  *            "-" have no special meaning if they appear 
  77.  *            as the first chars in the set.
  78.  *                      examples:        match:
  79.  *
  80.  *                              [a-z]    any lowercase alpha
  81.  *
  82.  *                              [^]-]    any char except ] and -
  83.  *
  84.  *                              [^A-Z]   any char except uppercase
  85.  *                                       alpha
  86.  *
  87.  *                              [a-zA-Z] any alpha
  88.  *
  89.  *      [5]     *       any regular expression form [1] to [4], followed by
  90.  *                      closure char (*) matches zero or more matches of
  91.  *                      that form.
  92.  *
  93.  *      [6]     +       same as [5], except it matches one or more.
  94.  *
  95.  *      [7]             a regular expression in the form [1] to [10], enclosed
  96.  *                      as \(form\) matches what form matches. The enclosure
  97.  *                      creates a set of tags, used for [8] and for
  98.  *                      pattern substution. The tagged forms are numbered
  99.  *            starting from 1.
  100.  *
  101.  *      [8]             a \ followed by a digit 1 to 9 matches whatever a
  102.  *                      previously tagged regular expression ([7]) matched.
  103.  *
  104.  *    [9]    \<    a regular expression starting with a \< construct
  105.  *        \>    and/or ending with a \> construct, restricts the
  106.  *            pattern matching to the beginning of a word, and/or
  107.  *            the end of a word. A word is defined to be a character
  108.  *            string beginning and/or ending with the characters
  109.  *            A-Z a-z 0-9 and _. It must also be preceded and/or
  110.  *            followed by any character outside those mentioned.
  111.  *
  112.  *      [10]            a composite regular expression xy where x and y
  113.  *                      are in the form [1] to [10] matches the longest
  114.  *                      match of x followed by a match for y.
  115.  *
  116.  *      [11]    ^    a regular expression starting with a ^ character
  117.  *        $    and/or ending with a $ character, restricts the
  118.  *                      pattern matching to the beginning of the line,
  119.  *                      or the end of line. [anchors] Elsewhere in the
  120.  *            pattern, ^ and $ are treated as ordinary characters.
  121.  *
  122.  *
  123.  * Acknowledgements:
  124.  *
  125.  *    HCR's Hugh Redelmeier has been most helpful in various
  126.  *    stages of development. He convinced me to include BOW
  127.  *    and EOW constructs, originally invented by Rob Pike at
  128.  *    the University of Toronto.
  129.  *
  130.  * References:
  131.  *              Software tools            Kernighan & Plauger
  132.  *              Software tools in Pascal        Kernighan & Plauger
  133.  *              Grep [rsx-11 C dist]            David Conroy
  134.  *        ed - text editor        Un*x Programmer's Manual
  135.  *        Advanced editing on Un*x    B. W. Kernighan
  136.  *        regexp routines            Henry Spencer
  137.  *
  138.  * Notes:
  139.  *
  140.  *    This implementation uses a bit-set representation for character
  141.  *    classes for speed and compactness. Each character is represented 
  142.  *    by one bit in a 128-bit block. Thus, CCL always takes a 
  143.  *    constant 16 bytes in the internal nfa, and re_exec does a single
  144.  *    bit comparison to locate the character in the set.
  145.  *
  146.  * Examples:
  147.  *
  148.  *    pattern:    foo*.*
  149.  *    compile:    CHR f CHR o CLO CHR o END CLO ANY END END
  150.  *    matches:    fo foo fooo foobar fobar foxx ...
  151.  *
  152.  *    pattern:    fo[ob]a[rz]    
  153.  *    compile:    CHR f CHR o CCL bitset CHR a CCL bitset END
  154.  *    matches:    fobar fooar fobaz fooaz
  155.  *
  156.  *    pattern:    foo\\+
  157.  *    compile:    CHR f CHR o CHR o CHR \ CLO CHR \ END END
  158.  *    matches:    foo\ foo\\ foo\\\  ...
  159.  *
  160.  *    pattern:    \(foo\)[1-3]\1    (same as foo[1-3]foo)
  161.  *    compile:    BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
  162.  *    matches:    foo1foo foo2foo foo3foo
  163.  *
  164.  *    pattern:    \(fo.*\)-\1
  165.  *    compile:    BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
  166.  *    matches:    foo-foo fo-fo fob-fob foobar-foobar ...
  167.  * 
  168.  */
  169.  
  170. #define MAXNFA  1024
  171. #define MAXTAG  10
  172.  
  173. #define OKP     1
  174. #define NOP     0
  175.  
  176. #define CHR     1
  177. #define ANY     2
  178. #define CCL     3
  179. #define BOL     4
  180. #define EOL     5
  181. #define BOT     6
  182. #define EOT     7
  183. #define BOW    8
  184. #define EOW    9
  185. #define REF     10
  186. #define CLO     11
  187.  
  188. #define END     0
  189.  
  190. /*
  191.  * The following defines are not meant
  192.  * to be changeable. They are for readability
  193.  * only.
  194.  *
  195.  */
  196. #define MAXCHR    128
  197. #define CHRBIT    8
  198. #define BITBLK    MAXCHR/CHRBIT
  199. #define BLKIND    0170
  200. #define BITIND    07
  201.  
  202. #define ASCIIB    0177
  203.  
  204. typedef /*unsigned*/ char CHAR;
  205.  
  206. static int  tagstk[MAXTAG];             /* subpat tag stack..*/
  207. static CHAR nfa[MAXNFA];        /* automaton..       */
  208. static int  sta = NOP;                   /* status of lastpat */
  209.  
  210. static CHAR bittab[BITBLK];        /* bit table for CCL */
  211.                     /* pre-set bits...   */
  212. static CHAR bitarr[] = {1,2,4,8,16,32,64,128};
  213.  
  214. static int internal_error;
  215.  
  216. static void
  217. chset(c)
  218. register CHAR c;
  219. {
  220.     bittab[((c) & BLKIND) >> 3] |= bitarr[(c) & BITIND];
  221. }
  222.  
  223. #define badpat(x)    return (*nfa = END, x)
  224. #define store(x)    *mp++ = x
  225.  
  226. char *     
  227. re_comp(pat)
  228. char *pat;
  229. {
  230.     register char *p;               /* pattern pointer   */
  231.     register CHAR *mp = nfa;        /* nfa pointer       */
  232.     register CHAR *lp;              /* saved pointer..   */
  233.     register CHAR *sp = nfa;        /* another one..     */
  234.  
  235.     register int tagi = 0;          /* tag stack index   */
  236.     register int tagc = 1;          /* actual tag count  */
  237.  
  238.     register int n;
  239.     register CHAR mask;        /* xor mask -CCL/NCL */
  240.     int c1, c2;
  241.         
  242.     if (!pat || !*pat)
  243.         if (sta)
  244.             return 0;
  245.         else
  246.             badpat("No previous regular expression");
  247.     sta = NOP;
  248.  
  249.     for (p = pat; *p; p++) {
  250.         lp = mp;
  251.         switch(*p) {
  252.  
  253.         case '.':               /* match any char..  */
  254.             store(ANY);
  255.             break;
  256.  
  257.         case '^':               /* match beginning.. */
  258.             if (p == pat)
  259.                 store(BOL);
  260.             else {
  261.                 store(CHR);
  262.                 store(*p);
  263.             }
  264.             break;
  265.  
  266.         case '$':               /* match endofline.. */
  267.             if (!*(p+1))
  268.                 store(EOL);
  269.             else {
  270.                 store(CHR);
  271.                 store(*p);
  272.             }
  273.             break;
  274.  
  275.         case '[':               /* match char class..*/
  276.             store(CCL);
  277.  
  278.             if (*++p == '^') {
  279.                 mask = 0377;    
  280.                 p++;
  281.             }
  282.             else
  283.                 mask = 0;
  284.  
  285.             if (*p == '-')        /* real dash */
  286.                 chset(*p++);
  287.             if (*p == ']')        /* real brac */
  288.                 chset(*p++);
  289.             while (*p && *p != ']') {
  290.                 if (*p == '-' && *(p+1) && *(p+1) != ']') {
  291.                     p++;
  292.                     c1 = *(p-2) + 1;
  293.                     c2 = *p++;
  294.                     while (c1 <= c2)
  295.                         chset(c1++);
  296.                 }
  297. #ifdef EXTEND
  298.                 else if (*p == '\\' && *(p+1)) {
  299.                     p++;
  300.                     chset(*p++);
  301.                 }
  302. #endif
  303.                 else
  304.                     chset(*p++);
  305.             }
  306.             if (!*p)
  307.                 badpat("Missing ]");
  308.  
  309.             for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
  310.                 store(mask ^ bittab[n]);
  311.     
  312.             break;
  313.  
  314.         case '*':               /* match 0 or more.. */
  315.         case '+':               /* match 1 or more.. */
  316.             if (p == pat)
  317.                 badpat("Empty closure");
  318.             lp = sp;        /* previous opcode */
  319.             if (*lp == CLO)        /* equivalence..   */
  320.                 break;
  321.             switch(*lp) {
  322.  
  323.             case BOL:
  324.             case BOT:
  325.             case EOT:
  326.             case BOW:
  327.             case EOW:
  328.             case REF:
  329.                 badpat("Illegal closure");
  330.             default:
  331.                 break;
  332.             }
  333.  
  334.             if (*p == '+')
  335.                 for (sp = mp; lp < sp; lp++)
  336.                     store(*lp);
  337.  
  338.             store(END);
  339.             store(END);
  340.             sp = mp;
  341.             while (--mp > lp)
  342.                 *mp = mp[-1];
  343.             store(CLO);
  344.             mp = sp;
  345.             break;
  346.  
  347.         case '\\':              /* tags, backrefs .. */
  348.             switch(*++p) {
  349.  
  350.             case '(':
  351.                 if (tagc < MAXTAG) {
  352.                     tagstk[++tagi] = tagc;
  353.                     store(BOT);
  354.                     store(tagc++);
  355.                 }
  356.                 else
  357.                     badpat("Too many \\(\\) pairs");
  358.                 break;
  359.             case ')':
  360.                 if (*sp == BOT)
  361.                     badpat("Null pattern inside \\(\\)");
  362.                 if (tagi > 0) {
  363.                     store(EOT);
  364.                     store(tagstk[tagi--]);
  365.                 }
  366.                 else
  367.                     badpat("Unmatched \\)");
  368.                 break;
  369.             case '<':
  370.                 store(BOW);
  371.                 break;
  372.             case '>':
  373.                 if (*sp == BOW)
  374.                     badpat("Null pattern inside \\<\\>");
  375.                 store(EOW);
  376.                 break;
  377.             case '1':
  378.             case '2':
  379.             case '3':
  380.             case '4':
  381.             case '5':
  382.             case '6':
  383.             case '7':
  384.             case '8':
  385.             case '9':
  386.                 n = *p-'0';
  387.                 if (tagi > 0 && tagstk[tagi] == n)
  388.                     badpat("Cyclical reference");
  389.                 if (tagc > n) {
  390.                     store(REF);
  391.                     store(n);
  392.                 }
  393.                 else
  394.                     badpat("Undetermined reference");
  395.                 break;
  396. #ifdef EXTEND
  397.             case 'b':
  398.                 store(CHR);
  399.                 store('\b');
  400.                 break;
  401.             case 'n':
  402.                 store(CHR);
  403.                 store('\n');
  404.                 break;
  405.             case 'f':
  406.                 store(CHR);
  407.                 store('\f');
  408.                 break;
  409.             case 'r':
  410.                 store(CHR);
  411.                 store('\r');
  412.                 break;
  413.             case 't':
  414.                 store(CHR);
  415.                 store('\t');
  416.                 break;
  417. #endif
  418.             default:
  419.                 store(CHR);
  420.                 store(*p);
  421.             }
  422.             break;
  423.  
  424.         default :               /* an ordinary char  */
  425.             store(CHR);
  426.             store(*p);
  427.             break;
  428.         }
  429.         sp = lp;
  430.     }
  431.     if (tagi > 0)
  432.         badpat("Unmatched \\(");
  433.     store(END);
  434.     sta = OKP;
  435.     return 0;
  436. }
  437.  
  438.  
  439. static char *bol;
  440. static char *bopat[MAXTAG];
  441. static char *eopat[MAXTAG];
  442. char *pmatch();
  443.  
  444. /*
  445.  * re_exec:
  446.  *     execute nfa to find a match.
  447.  *
  448.  *    special cases: (nfa[0])    
  449.  *        BOL
  450.  *            Match only once, starting from the
  451.  *            beginning.
  452.  *        CHR
  453.  *            First locate the character without
  454.  *            calling pmatch, and if found, call
  455.  *            pmatch for the remaining string.
  456.  *        END
  457.  *            re_comp failed, poor luser did not
  458.  *            check for it. Fail fast.
  459.  *
  460.  *    If a match is found, bopat[0] and eopat[0] are set
  461.  *    to the beginning and the end of the matched fragment,
  462.  *    respectively.
  463.  *
  464.  */
  465.  
  466. int
  467. re_exec(lp)
  468. register char *lp;
  469. {
  470.     register char c;
  471.     register char *ep = 0;
  472.     register CHAR *ap = nfa;
  473.  
  474.     bol = lp;
  475.  
  476.     bopat[0] = 0;
  477.     bopat[1] = 0;
  478.     bopat[2] = 0;
  479.     bopat[3] = 0;
  480.     bopat[4] = 0;
  481.     bopat[5] = 0;
  482.     bopat[6] = 0;
  483.     bopat[7] = 0;
  484.     bopat[8] = 0;
  485.     bopat[9] = 0;
  486.  
  487.     switch(*ap) {
  488.  
  489.     case BOL:            /* anchored: match from BOL only */
  490.         ep = pmatch(lp,ap);
  491.         break;
  492.     case CHR:            /* ordinary char: locate it fast */
  493.         c = *(ap+1);
  494.         while (*lp && *lp != c)
  495.             lp++;
  496.         if (!*lp)        /* if EOS, fail, else fall thru. */
  497.             return 0;
  498.     default:            /* regular matching all the way. */
  499.         while (*lp) {
  500.             if ((ep = pmatch(lp,ap)))
  501.                 break;
  502.             lp++;
  503.         }
  504.         break;
  505.     case END:            /* munged automaton. fail always */
  506.         return 0;
  507.     }
  508.     if (!ep)
  509.         return 0;
  510.  
  511.     if (internal_error)
  512.         return -1;
  513.  
  514.     bopat[0] = lp;
  515.     eopat[0] = ep;
  516.     return 1;
  517. }
  518.  
  519. /* 
  520.  * pmatch: 
  521.  *    internal routine for the hard part
  522.  *
  523.  *     This code is mostly snarfed from an early
  524.  *     grep written by David Conroy. The backref and
  525.  *     tag stuff, and various other mods are by oZ.
  526.  *
  527.  *    special cases: (nfa[n], nfa[n+1])
  528.  *        CLO ANY
  529.  *            We KNOW ".*" will match ANYTHING
  530.  *            upto the end of line. Thus, go to
  531.  *            the end of line straight, without
  532.  *            calling pmatch recursively. As in
  533.  *            the other closure cases, the remaining
  534.  *            pattern must be matched by moving
  535.  *            backwards on the string recursively,
  536.  *            to find a match for xy (x is ".*" and 
  537.  *            y is the remaining pattern) where
  538.  *            the match satisfies the LONGEST match
  539.  *            for x followed by a match for y.
  540.  *        CLO CHR
  541.  *            We can again scan the string forward
  542.  *            for the single char without recursion, 
  543.  *            and at the point of failure, we execute 
  544.  *            the remaining nfa recursively, as
  545.  *            described above.
  546.  *
  547.  *    At the end of a successful match, bopat[n] and eopat[n]
  548.  *    are set to the beginning and end of subpatterns matched
  549.  *    by tagged expressions (n = 1 to 9).    
  550.  *
  551.  */
  552.  
  553. /*
  554.  * character classification table for word boundary
  555.  * operators BOW and EOW. the reason for not using 
  556.  * ctype macros is that we can let the user add into 
  557.  * our own table. see re_modw. This table is not in
  558.  * the bitset form, since we may wish to extend it
  559.  * in the future for other character classifications. 
  560.  *
  561.  *    TRUE for 0-9 A-Z a-z _
  562.  */
  563. static char chrtyp[MAXCHR] = {
  564.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  565.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  566.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  567.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  568.     0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 
  569.     1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 
  570.     0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 
  571.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  572.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  573.     1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 
  574.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  575.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  576.     1, 1, 1, 0, 0, 0, 0, 0
  577.     };
  578.  
  579. #define inascii(x)    (0177&(x))
  580. #define iswordc(x)     chrtyp[inascii(x)]
  581. #define isinset(x,y)     ((x)[((y)&BLKIND)>>3] & bitarr[(y)&BITIND])
  582.  
  583. /*
  584.  * skip values for CLO XXX to skip past the closure
  585.  *
  586.  */
  587.  
  588. #define ANYSKIP    2     /* [CLO] ANY END ...         */
  589. #define CHRSKIP    3    /* [CLO] CHR chr END ...     */
  590. #define CCLSKIP 18    /* [CLO] CCL 16bytes END ... */
  591.  
  592. static char *
  593. pmatch(lp, ap)
  594. register char *lp;
  595. register CHAR *ap;
  596. {
  597.     register int op, c, n;
  598.     register char *e;        /* extra pointer for CLO */
  599.     register char *bp;        /* beginning of subpat.. */
  600.     register char *ep;        /* ending of subpat..     */
  601.     char *are;            /* to save the line ptr. */
  602.  
  603.     while ((op = *ap++) != END)
  604.         switch(op) {
  605.  
  606.         case CHR:
  607.             if (*lp++ != *ap++)
  608.                 return 0;
  609.             break;
  610.         case ANY:
  611.             if (!*lp++)
  612.                 return 0;
  613.             break;
  614.         case CCL:
  615.             c = *lp++;
  616.             if (!isinset(ap,c))
  617.                 return 0;
  618.             ap += BITBLK;
  619.             break;
  620.         case BOL:
  621.             if (lp != bol)
  622.                 return 0;
  623.             break;
  624.         case EOL:
  625.             if (*lp)
  626.                 return 0;
  627.             break;
  628.         case BOT:
  629.             bopat[*ap++] = lp;
  630.             break;
  631.         case EOT:
  632.             eopat[*ap++] = lp;
  633.             break;
  634.          case BOW:
  635.             if (lp!=bol && iswordc(lp[-1]) || !iswordc(*lp))
  636.                 return 0;
  637.             break;
  638.         case EOW:
  639.             if (lp==bol || !iswordc(lp[-1]) || iswordc(*lp))
  640.                 return 0;
  641.             break;
  642.         case REF:
  643.             n = *ap++;
  644.             bp = bopat[n];
  645.             ep = eopat[n];
  646.             while (bp < ep)
  647.                 if (*bp++ != *lp++)
  648.                     return 0;
  649.             break;
  650.         case CLO:
  651.             are = lp;
  652.             switch(*ap) {
  653.  
  654.             case ANY:
  655.                 while (*lp)
  656.                     lp++;
  657.                 n = ANYSKIP;
  658.                 break;
  659.             case CHR:
  660.                 c = *(ap+1);
  661.                 while (*lp && c == *lp)
  662.                     lp++;
  663.                 n = CHRSKIP;
  664.                 break;
  665.             case CCL:
  666.                 while ((c = *lp) && isinset(ap+1,c))
  667.                     lp++;
  668.                 n = CCLSKIP;
  669.                 break;
  670.             default:
  671.                 internal_error++;
  672.                 return 0;
  673.             }
  674.  
  675.             ap += n;
  676.  
  677.             while (lp >= are) {
  678.                 if (e = pmatch(lp, ap))
  679.                     return e;
  680.                 --lp;
  681.             }
  682.             return 0;
  683.         default:
  684.             internal_error++;
  685.             return 0;
  686.         }
  687.     return lp;
  688. }
  689. #endif /* Need regex libraries? Compile to nothing if not.  */
  690.