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