home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / me34src.zip / me3 / util / regex.c < prev    next >
C/C++ Source or Header  |  1995-01-14  |  22KB  |  695 lines
  1. /*
  2.  * regex - Regular expression pattern matching
  3.  *         and replacement
  4.  *
  5.  * By:  Ozan S. Yigit (oz), Dept. of Computer Science, York University
  6.  * Mods: C Durland
  7.  *
  8.  * These routines are the PUBLIC DOMAIN equivalents of regex routines as
  9.  * found in 4.nBSD UN*X, with minor extensions.
  10.  *
  11.  * These routines are derived from various implementations found in software
  12.  * tools books, and Conroy's grep.  They are NOT derived from
  13.  * licensed/restricted software.  For more interesting/academic/complicated
  14.  * implementations, see Henry Spencer's regexp routines, or GNU Emacs
  15.  * pattern matching module.
  16.  *
  17.  * dfa = deterministic finite automata
  18.  * Routines:
  19.  *  re_comp: compile a regular expression into a DFA.
  20.  *    char *re_comp(s)
  21.  *    char *s;
  22.  *    returns: NULL if OK, else error string
  23.  *    If s is NULL or 0 length, last compiled pattern is used.
  24.  *  re_exec: execute the DFA to match a pattern.
  25.  *    int re_exec(s)
  26.  *    char *s;
  27.  *  re_subs: substitute the matched portions in a new string.
  28.  *    int re_subs(src, dst)
  29.  *    char *src;
  30.  *    char *dst;
  31.  *  re_fail:    failure routine for re_exec.
  32.  *    void re_fail(msg, op)
  33.  *    char *msg;
  34.  *    char op;
  35.  *  
  36.  * Regular Expressions:
  37.  *
  38.  *      [1]     char    matches itself, unless it is a special
  39.  *                      character (metachar): . \ [ ] * + ^ $
  40.  *
  41.  *      [2]     .       matches any character.
  42.  *
  43.  *      [3]     \       matches the character following it, except
  44.  *            when followed by one of: ()123456789<> adnwW
  45.  *            (see [7], [8] and [9])
  46.  *            It is used as an escape character for all other
  47.  *            meta-characters, and itself.  When used in a set
  48.  *            ([4]), it is treated as an ordinary character.
  49.  *
  50.  *      [4]     [set]   matches one of the characters in the set.
  51.  *                      If the first character in the set is "^",
  52.  *                      it matches a character NOT in the set. A
  53.  *                      shorthand S-E is used to specify a set of
  54.  *                      characters S upto E, inclusive. The special
  55.  *                      characters "]" and "-" have no special
  56.  *                      meaning if they appear as the first chars
  57.  *                      in the set.
  58.  *                      Example:   Matches:
  59.  *            --------   -------
  60.  *            [a-z]       Any lowercase alpha.
  61.  *
  62.  *            [^]-]      Any char except ] and -.
  63.  *
  64.  *            [^A-Z]     Any char except uppercase alpha.
  65.  *
  66.  *            [a-zA-Z]   Any alpha.
  67.  *
  68.  *                      [a-b-c] == [a-bb-c] == [a-c]
  69.  *                      [a-a] == [a]
  70.  *            [-abc] == [abc-]  Match -, a, b, c.
  71.  *
  72.  *            []] == ]   Match "]"
  73.  *            [-]]       Match only "-]".  This is a set ([-])
  74.  *                   and a character (]).
  75.  *            
  76.  *            [z-a]      Nothing and is an error.
  77.  *
  78.  *      [5]     *       any regular expression form [1] to [4], followed by
  79.  *                      closure char (*) matches zero or more matches of
  80.  *                      that form.
  81.  *
  82.  *      [6]     +       same as [5], except it matches one or more.
  83.  *
  84.  *      [7]             a regular expression in the form [1] to [10], enclosed
  85.  *                      as \(form\) matches what form matches. The enclosure
  86.  *                      creates a set of tags, used for [8] and for
  87.  *                      pattern substution. The tagged forms are numbered
  88.  *            starting from 1.
  89.  *
  90.  *      [8]             a \ followed by a digit 1 to 9 matches whatever a
  91.  *                      previously tagged regular expression ([7]) matched.
  92.  *
  93.  *    [9]    \<    a regular expression starting with a \< construct
  94.  *        \>    and/or ending with a \> construct, restricts the
  95.  *            pattern matching to the beginning of a word, and/or
  96.  *            the end of a word. A word is defined to be a character
  97.  *            string beginning and/or ending with the characters
  98.  *            A-Z a-z 0-9 and _. It must also be preceded and/or
  99.  *            followed by any character outside those mentioned.
  100.  *
  101.  *      [10]            a composite regular expression xy where x and y
  102.  *                      are in the form [1] to [10] matches the longest
  103.  *                      match of x followed by a match for y.
  104.  *
  105.  *      [11]    ^    a regular expression starting with a ^ character
  106.  *        $    and/or ending with a $ character, restricts the
  107.  *                      pattern matching to the beginning of the line,
  108.  *                      or the end of line. [anchors] Elsewhere in the
  109.  *            pattern, ^ and $ are treated as ordinary characters.
  110.  *
  111.  * Acknowledgements:
  112.  *   HCR's Hugh Redelmeier has been most helpful in various stages of
  113.  *   development.  He convinced me to include BOW and EOW constructs,
  114.  *   originally invented by Rob Pike at the University of Toronto.
  115.  * References:
  116.  *   Software tools        Kernighan & Plauger
  117.  *   Software tools in Pascal    Kernighan & Plauger
  118.  *   Grep [rsx-11 C dist]    David Conroy
  119.  *   ed - text editor        Un*x Programmer's Manual
  120.  *   Advanced editing on Un*x    B. W. Kernighan
  121.  *   RegExp routines        Henry Spencer
  122.  * Notes:
  123.  *  This implementation uses a bit-set representation for character sets for
  124.  *    speed and compactness.  Each character is represented by one bit in a
  125.  *    N-bit block.  Thus, SET or NSET always takes a constant M bytes in the
  126.  *    internal dfa, and re_exec does a single bit comparison to locate the
  127.  *    character in the set.  N is 128 for 7 bits ASCII and 256 for 8 bit
  128.  *    data.  Thus M is 16 or 32 bytes.
  129.  *  Put CLO in front of what gets closed for ease of interpreting.
  130.  *  Put END at end of what gets closed to limit recursion.
  131.  * Examples:
  132.  *    pattern:    foo*.*
  133.  *    compile:    CHR f CHR o CLO CHR o END CLO ANY END END
  134.  *    matches:    fo foo fooo foobar fobar foxx ...
  135.  *
  136.  *    pattern:    fo[ob]a[rz]    
  137.  *    compile:    CHR f CHR o SET bitset CHR a SET bitset END
  138.  *    matches:    fobar fooar fobaz fooaz
  139.  *
  140.  *    pattern:    foo\\+
  141.  *    compile:    CHR f CHR o CHR o CHR \ CLO CHR \ END END
  142.  *    matches:    foo\ foo\\ foo\\\  ...
  143.  *
  144.  *    pattern:    \(foo\)[1-3]\1    (same as foo[1-3]foo)
  145.  *    compile:    BOT 1 CHR f CHR o CHR o EOT 1 SET bitset REF 1 END
  146.  *    matches:    foo1foo foo2foo foo3foo
  147.  *
  148.  *    pattern:    \(fo.*\)-\1
  149.  *    compile:    BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
  150.  *    matches:    foo-foo fo-fo fob-fob foobar-foobar ...
  151.  */
  152.  
  153. #include <char.h>
  154. #include <const.h>
  155.  
  156. typedef unsigned char Char;
  157.  
  158. #define MAXDFA 768    /* amount of space for compiled RE */
  159. #define MAXTAG  10
  160.  
  161. #define CHR     1    /* character        :: CHR<character> */
  162. #define ANY     2    /* .            :: ANY */
  163. #define SET     3    /* set: [...]        :: SET bitset */
  164. #define NSET     4    /* not set: [^...]    :: SET bitset */
  165. #define BOL     5    /* beginning of line: ^ :: BOL */
  166. #define EOL     6    /* end of line: $    :: EOL */
  167. #define BOT     7    /* beginning of tag: \( */
  168. #define EOT     8    /* end of tag: \) */
  169. #define BOW     9    /* beginning of word: \< */
  170. #define EOW    10    /* end of word: \> */
  171. #define REF    11    /* tag reference: \1,...,\9 */
  172. #define CLO    12    /* closure: +, *    :: CLO dfa END */
  173. #define SPACE    13    /* ": ": match isspace() */
  174. #define ALPHA    14    /* :a    match isalpha() */
  175. #define DIGIT    15    /* :d     match isdigit() */
  176. #define ALNUM    16    /* :n    match isalnum() */
  177. #define WORD    17    /* :w    match isword() */
  178. #define NWORD    18    /* :W    match !isword() */
  179.  
  180. #define END     0
  181.  
  182. /* ******************************************************************** */
  183. /* **************************** Bit Tables **************************** */
  184. /* ******************************************************************** */
  185.  
  186. /* 
  187.  * Bit table:  a string of bits stored in an array of char
  188.  *     .-----------------------------------.
  189.  *     |01234567|89012345|67890123|45678901|
  190.  *     `-----------------------------------'
  191.  *    bits[0]      [1]      [2]      [3]
  192.  * To find what bucket the nth bit is in (8 bits per bucket):
  193.  *       bit_bucket(n) = bits[n/8]
  194.  *   It might be a good idea to restrict n so it doesn't index outside its
  195.  *     range (only works if number of bits is a power of 2):
  196.  *       n = n & ((max_n - 1) & ~7)  where max_n is a power of 2
  197.  *     The ~7 is just to get rid of the lower bits that won't do anything
  198.  *     anyway.
  199.  * The nth bit in the bucket is n mod 8 (ie the lower 3 bits of n (0-7) are
  200.  *   the bit position):
  201.  *       bit_flag(n) = 1 << (n & 7)
  202.  * To find the state of the nth bit (0 == off and !0 == on):
  203.  *       bit_bucket(n) & bit_flag(n)
  204.  * To set the nth bit:
  205.  *       bits[bit_bucket(n)] |= bit_flag(n)
  206.  * Notes:
  207.  *   The bits are stored in a character array so that the array can be
  208.  *     easily copied without worrying about alignment (ie can use a loop as
  209.  *     well as memcpy()).
  210.  *   This is based on two's complement math.
  211.  */
  212.  
  213. /* The following defines are for character set size.  128 for straight
  214.  *   ASCII, 256 for Euro ASCII (8 bit characters).
  215.  */
  216. #define MAXCHR    256        /*  128 or  256 */
  217. #define BLKIND    0xf8        /* 0x78 or 0xf8 */
  218.  
  219. /*
  220.  * The following defines are not meant to be changeable.
  221.  * They are for readability only.
  222.  */
  223. #define CHRBIT    8
  224. #define BITBLK    MAXCHR/CHRBIT
  225. #define BITIND    0x7
  226.  
  227. static Char bittab[BITBLK];    /* bit table for SET */
  228.  
  229.     /* Add or check to see if a character is in the bit table (character
  230.      *   set).
  231.      * Note:
  232.      *   When calling these routines, make sure c is an unsigned char (or
  233.      *     int) so if it has the high bit set, casting it to an int won't
  234.      *     make it a large negative number.
  235.      */
  236. #define ISINSET(bittab,c) ((bittab)[((c) & BLKIND)>>3] & (1<<((c) & BITIND)))
  237. #define   CHSET(bittab,c)  (bittab)[((c) & BLKIND)>>3] |= 1<<((c) & BITIND)
  238.  
  239. static void chset(c) register int c; { CHSET(bittab,c); }
  240.  
  241. /* ******************************************************************** */
  242.  
  243. #define SLOP    50        /* dfa overflow protection */
  244.  
  245. static Char dfa[MAXDFA + SLOP];    /* automaton */
  246. static int
  247.   tagstk[MAXTAG],        /* subpat tag stack */
  248.   pattern_compiled = FALSE;    /* status of lastpat */
  249.  
  250. #define BADPAT(msg)    return (*dfa = END, (Char *)msg)
  251. #define STORE(x)    (*mp++ = x)  /* !!! should check for dfa overflow */
  252.  
  253.     /* Compile RE to internal format & store in dfa[]
  254.      * Input:
  255.      *   pat : pointer to regular expression string to compile.
  256.      * Returns:
  257.      *   NULL:  RE compiled OK.
  258.      *   pointer to error message.
  259.      */
  260. Char *re_comp(pat) Char *pat;
  261. {
  262.   register Char
  263.     *p,            /* pattern pointer */
  264.     *mp = dfa,        /* dfa pointer */
  265.     *lp,        /* saved pointer */
  266.     *sp = dfa;        /* another one */
  267.   register int
  268.     tagi = 0,        /* tag stack index */
  269.     tagc = 1,        /* actual tag count */
  270.     n;
  271.  
  272.   if (pat == NULL || *pat == '\0')
  273.     if (pattern_compiled) return NULL;
  274.     else BADPAT("No previous regular expression");
  275.  
  276.   pattern_compiled = FALSE;
  277.  
  278.   *dfa = END;            /* init dfa for lp and sp */
  279.  
  280.   for (p = pat; *p; p++)
  281.   {
  282.     lp = mp;            /* start of next dfa state */
  283.     switch(*p)
  284.     {
  285.       case '.': STORE(ANY); break;        /* match any character */
  286.       case '^':                    /* match beginning of line */
  287.     if (p == pat) STORE(BOL);
  288.     else { STORE(CHR); STORE(*p); }        /* match ^ */
  289.     break;
  290.       case '$':                    /* match end of line */
  291.     if (*(p+1) == '\0') STORE(EOL);
  292.     else { STORE(CHR); STORE(*p); }        /* match $ */
  293.     break;
  294.       case '[':                    /* match a set of characters */
  295.     if (*++p == '^') { STORE(NSET); p++; } else STORE(SET);
  296.     if (*p == ']') chset(*p++);        /* real bracket, match ] */
  297.     if (*p == '-') chset(*p++);        /* real dash, match - */
  298.     while (*p && *p != ']')
  299.     {
  300.       if (*p == '-' && *(p+1) != '\0' && *(p+1) != ']')    /* [a-z] */
  301.       {
  302.         int c1, c2;
  303.  
  304.         p++;
  305.         c1 = *(p-2);    /* 'a' */
  306.         c2 = *p++;        /* 'z' */
  307.         if (c1 > c2) BADPAT("Empty set");    /* something like [z-a] */
  308.         /* remember that 'a' has already been put into bittab */
  309.         while (++c1 <= c2) chset(c1);    /* build bit table */
  310.       }
  311. #ifdef EXTEND
  312.       else if (*p == '\\' && *(p+1)) { p++; chset(*p++); }
  313. #endif
  314.       else chset(*p++);
  315.     }
  316.     if (*p == '\0') BADPAT("Missing ]");
  317.     for (n = 0; n < BITBLK; bittab[n++] = '\0') STORE(bittab[n]);
  318.     break;
  319.       case '*':                /* match 0 or more of preceding RE */
  320.       case '+':            /* match 1 or more.  Note: x+ == xx* */
  321.     if (p == pat) BADPAT("Empty closure");
  322.     lp = sp;        /* previous opcode */
  323.     if (*lp == CLO) break;    /* equivalence: x** == x*  */
  324.     switch(*lp)
  325.     {
  326.       case BOL: case BOT: case EOT: case BOW: case EOW: case REF:
  327.         BADPAT("Illegal closure");
  328.     }
  329.     if (*p == '+') for (sp = mp; lp < sp; lp++) STORE(*lp);
  330.     STORE(END); STORE(END); sp = mp;
  331.     while (--mp > lp) *mp = mp[-1]; STORE(CLO);    /* open hole for CLO */
  332.     mp = sp;
  333.     break;
  334.       case '\\':                      /* tags, backrefs */
  335.     switch(*++p)
  336.     {
  337.       case '\0': BADPAT("Bad quote");
  338.       case '(':
  339.         if (tagc < MAXTAG)
  340.           { tagstk[++tagi] = tagc; STORE(BOT); STORE(tagc++); }
  341.         else BADPAT("Too many \\(\\) pairs");
  342.         break;
  343.       case ')':
  344.         if (*sp == BOT) BADPAT("Null pattern inside \\(\\)");
  345.         if (tagi > 0) { STORE(EOT); STORE(tagstk[tagi--]); }
  346.         else BADPAT("Unmatched \\)");
  347.         break;
  348.       case '<': STORE(BOW); break;
  349.       case '>':
  350.         if (*sp == BOW) BADPAT("Null pattern inside \\<\\>");
  351.         STORE(EOW);
  352.         break;
  353.       case '1': case '2': case '3': case '4': case '5': case '6': 
  354.       case '7': case '8': case '9':
  355.         n = *p - '0';
  356.         if (tagi > 0 && tagstk[tagi] == n) BADPAT("Cyclical reference");
  357.         if (tagc > n) { STORE(REF); STORE(n); }
  358.         else BADPAT("Undetermined reference");
  359.         break;
  360.       case ' ': STORE(SPACE); break;
  361.       case 'a': STORE(ALPHA); break;
  362.       case 'd': STORE(DIGIT); break;
  363.       case 'n': STORE(ALNUM); break;
  364.       case 'w': STORE(WORD);  break;
  365.       case 'W': STORE(NWORD); break;
  366. #ifdef EXTEND
  367.       case 'b': STORE(CHR); STORE('\b'); break;
  368.       case 'n': STORE(CHR); STORE('\n'); break;
  369.       case 'f': STORE(CHR); STORE('\f'); break;
  370.       case 'r': STORE(CHR); STORE('\r'); break;
  371.       case 't': STORE(CHR); STORE('\t'); break;
  372. #endif
  373.       default: STORE(CHR); STORE(*p);
  374.     }
  375.     break;
  376.       default : STORE(CHR); STORE(*p); break;    /* an ordinary character */
  377.     }
  378.     sp = lp;        /* start of previous state */
  379.  
  380.     if (mp > dfa + MAXDFA) BADPAT("Pattern too long (braindead re_comp())");
  381.   }
  382.  
  383.   if (tagi > 0) BADPAT("Unmatched \\(");
  384.  
  385.   STORE(END);
  386.  
  387.   pattern_compiled = TRUE;
  388.  
  389.   return NULL;
  390. }
  391.  
  392. static Char *pmatch();
  393.  
  394. Char *bopat[MAXTAG], *eopat[MAXTAG];
  395. int re_errorcode;    /* sleaze */
  396.  
  397. static Char *bol;
  398.  
  399. /* re_exec:  execute dfa to find a match.
  400.  *
  401.  * special cases: (dfa[0])    
  402.  *  BOL
  403.  *    Match only once, starting from the beginning.
  404.  *  CHR
  405.  *    First locate the character without calling pmatch(), and if found,
  406.  *    call pmatch() for the remaining string.
  407.  *  END
  408.  *    re_comp() failed, poor luser did not check for it. Fail fast.
  409.  *
  410.  * If a match is found, bopat[0] and eopat[0] are set to the beginning and
  411.  *   the end of the matched fragment, respectively.
  412.  *
  413.  * Input:
  414.  *   lp: string to search
  415.  *   SoL==TRUE if lp starts line
  416.  *   move==TRUE if search the entire string for match
  417.  * Returns:
  418.  *   TRUE:  
  419.  *   FALSE:  
  420.  *   ????
  421.  * Munges:
  422.  *   re_errorcode: Set to FALSE, re_fail() might want to set it.
  423.  * Notes:
  424.  *   If SoL is FALSE, lp[-1] MUST be at valid!  A couple of REs will look
  425.  *     there if they can.
  426.  */
  427. int re_exec(lp,SoL,move) register Char *lp; int SoL, move;
  428. {
  429.   register Char *ap = dfa, c;
  430.   Char *ep = NULL;
  431.  
  432.   re_errorcode = FALSE;        /* assume no match */
  433.   bol = (SoL ? lp : NULL);
  434.  
  435.   bopat[0] = bopat[1] = bopat[2] = bopat[3] = bopat[4] = bopat[5] = 
  436.   bopat[6] = bopat[7] = bopat[8] = bopat[9] = NULL;
  437.  
  438.   switch(*ap)
  439.   {
  440.     case END: return FALSE;        /* munged automaton. fail always */
  441.     case BOL:                /* anchored: match from BOL only */
  442.       if (!SoL) return FALSE;        /* BoL can only be at front of dfa */
  443.       ep = pmatch(lp,++ap);
  444.       break;
  445.     case CHR:                /* ordinary char: locate it fast */
  446.       if (move)
  447.       {
  448.     c = *(ap+1);
  449.     while (*lp && !ceq(*lp,c)) lp++;
  450.     if (!*lp) return FALSE;        /* if EoS, fail. else fall thru */
  451.       }
  452.     default:                /* regular matching all the way. */
  453.       if (!move) { ep = pmatch(lp,ap); break; }
  454. #if 0
  455.       while (*lp)
  456.       {
  457.     if ((ep = pmatch(lp,ap))) break;
  458.     lp++;
  459.       }
  460. #else
  461.       while (TRUE)
  462.       {
  463.     if ((ep = pmatch(lp,ap))) break;
  464.     if ('\0' == *lp++) break;
  465.       }
  466. #endif
  467.       break;
  468.   }
  469.   if (!ep) return re_errorcode;        /* only if pmatch() returns NULL */
  470.  
  471.   bopat[0] = lp; eopat[0] = ep; 
  472.  
  473.   return TRUE;
  474. }
  475.  
  476. /* 
  477.  * pmatch: internal routine for the hard part
  478.  *
  479.  * This code is mostly snarfed from an early grep written by David Conroy.
  480.  *   The backref and tag stuff, and various other mods are by oZ.
  481.  *
  482.  * special cases: (dfa[n], dfa[n+1])
  483.  *  CLO ANY
  484.  *    We KNOW ".*" will match ANYTHING upto the end of line.  Thus, go to
  485.  *    the end of line straight, without calling pmatch() recursively.  As in
  486.  *    the other closure cases, the remaining pattern must be matched by
  487.  *    moving backwards on the string recursively, to find a match for xy (x
  488.  *    is ".*" and y is the remaining pattern) where the match satisfies the
  489.  *    LONGEST match for x followed by a match for y.
  490.  *  CLO CHR
  491.  *    Scan forward matching the single char without recursion, and at the
  492.  *    point of failure, we execute the remaining dfa recursively, as
  493.  *    described above.
  494.  *
  495.  * At the end of a successful match, bopat[n] and eopat[n] are set to the
  496.  *   beginning and end of subpatterns matched by tagged expressions (n = 1
  497.  *   to 9).
  498.  * 
  499.  * Input:
  500.  * Returns:
  501.  *   NULL: No match, re_fail() may have been called.
  502.  *   else: pointer to end of match.
  503.  */
  504.  
  505. extern void re_fail();
  506.  
  507.     /* skip values for CLO XXX to skip past the closure */
  508. #define ANYSKIP    2         /* CLO ANY END ...       */
  509. #define CHRSKIP    3        /* CLO CHR chr END ...       */
  510. #define SETSKIP (2 +BITBLK)    /* CLO SET 16bytes END ... */
  511.  
  512. static Char *pmatch(lp,dfa) register Char *lp, *dfa;
  513. {
  514.   register Char
  515.     *e,            /* extra pointer for CLO */
  516.     *bp, *ep;        /* beginning and ending of subpat */
  517.   Char *are;        /* to save the line ptr */
  518.   register int op, c, n;
  519.  
  520.   while ((op = *dfa++) != END)
  521.     switch(op)
  522.     {
  523.       case CHR:    if (!ceq(*lp++,*dfa++)) return NULL; break;
  524.       case ANY: if (*lp++ == '\0')      return NULL; break;
  525.       case SET:
  526.         c = *lp++;
  527.     if (!ISINSET(dfa,c)) return NULL;    /* ISINSET(dfa,0) is FALSE */
  528.     dfa += BITBLK;
  529.     break;
  530.       case NSET:
  531.     if ((c = *lp++) == '\0' || ISINSET(dfa,c)) return NULL;
  532.     dfa += BITBLK;
  533.     break;
  534.       case BOT: bopat[*dfa++] = lp; break;
  535.       case EOT: eopat[*dfa++] = lp; break;
  536.       case EOL:   if (*lp != '\0')            return NULL; break;
  537.       case ALNUM: if (!isalnum(*lp++))            return NULL; break;
  538.       case ALPHA: if (!isalpha(*lp++))             return NULL; break;
  539.       case DIGIT: if (!isdigit(*lp++))            return NULL; break;
  540.       case SPACE: if (!isspace(*lp++))            return NULL; break;
  541.       case WORD:  if (!isword (*lp++))            return NULL; break;
  542.       case NWORD: if (*lp == '\0' || isword(*lp++)) return NULL; break;
  543.       case BOW:
  544.         if (!(lp != bol && isword(lp[-1])) && isword(*lp)) break;
  545.     return NULL;
  546.       case EOW:        /* 'w\0' is OK here */
  547.         if ((lp != bol && isword(lp[-1])) && !isword(*lp)) break;
  548.     return NULL;
  549.       case REF:        /* !!! case_fold? */
  550.         n = *dfa++; bp = bopat[n]; ep = eopat[n];
  551.     while (bp < ep) if (*bp++ != *lp++) return NULL;  /* !!! recurse? */
  552.     break;
  553.       case CLO:
  554.         are = lp; n = ANYSKIP;
  555.     switch(*dfa)
  556.     {
  557.       case ANY:   while (*lp)          lp++; break;
  558.       case ALNUM: while (isalnum(*lp)) lp++; break;
  559.       case ALPHA: while (isalpha(*lp)) lp++; break;
  560.       case DIGIT: while (isdigit(*lp)) lp++; break;
  561.       case SPACE: while (isspace(*lp)) lp++; break;
  562.       case WORD:  while (isword (*lp)) lp++; break;
  563.       case NWORD: while (*lp && !isword(*lp)) lp++; break;
  564.       case CHR:
  565.         c = *(dfa+1);        /* we know c!='\0' */
  566.         while (ceq(*lp,c)) lp++;
  567.         n = CHRSKIP;
  568.         break;
  569.       case SET: case NSET:
  570.         while (*lp && (e = pmatch(lp,dfa))) lp = e;
  571.         n = SETSKIP;
  572.         break;
  573.       default: re_fail("closure: bad dfa.",*dfa); return NULL;
  574.     }
  575.     dfa += n;
  576.     while (lp >= are)    /* backup up till match next pattern */
  577.     {
  578.       if (e = pmatch(lp,dfa)) return e;
  579.       --lp;
  580.     }
  581.     return NULL;
  582.       default: re_fail("re_exec: bad dfa.",op); return NULL;
  583.     }
  584.   return lp;
  585. }
  586.  
  587. /*
  588.  * re_subs: substitute the matched portions of the src in dst.
  589.  *    &    substitute the entire matched pattern.
  590.  *    \digit    substitute a subpattern, with the given
  591.  *        tag number. Tags are numbered from 1 to
  592.  *        9. If the particular tagged subpattern
  593.  *        does not exist, null is substituted.
  594.  *     !!!Note: if the line that was used re_exec() has gone byebye
  595.  *      then \digit will blow cookies since the tags point into the line.
  596.  * Input:
  597.  *   src:
  598.  *   dst:
  599.  * Returns:
  600.  *   TRUE:   everything went as expected
  601.  *   FALSE:  Bad src or no match.
  602.  */
  603. int re_subs(src,dst) register Char *src, *dst;
  604. {
  605.   register Char c, *bp, *ep;
  606.   register int pin;
  607.  
  608.   if (!bopat[0]) return FALSE;
  609.  
  610.   while (c = *src++)
  611.   {
  612.     switch(c)
  613.     {
  614.       case '&': pin = 0; break;
  615.       case '\\': 
  616.         c = *src++;
  617.     if (c >= '0' && c <= '9') { pin = c - '0'; break; }
  618.       default: *dst++ = c; continue;
  619.     }
  620.     if ((bp = bopat[pin]) && (ep = eopat[pin]))
  621.     {
  622.       while (*bp && bp < ep) *dst++ = *bp++;
  623.       if (bp < ep) return FALSE;
  624.     }
  625.   }
  626.   *dst = '\0';
  627.  
  628.   return TRUE;
  629. }
  630.  
  631. /* ******************************************************************** */
  632. /* ************************* DEBUG ************************************ */
  633. /* ******************************************************************** */
  634.  
  635. #ifdef DEBUG
  636. /*
  637.  * symbolic - produce a symbolic dump of the dfa
  638.  */
  639. symbolic(s) 
  640. char *s;
  641. {
  642.     printf("pattern: %s\n", s);
  643.     printf("dfacode:\n");
  644.     dfadump(dfa);
  645. }
  646.  
  647. static    
  648. dfadump(dfa) Char *dfa;
  649. {
  650.   register int n;
  651.  
  652.   while (*dfa != END)
  653.     switch(*dfa++)
  654.     {
  655.       case CLO:
  656.         printf("CLOSURE");
  657.     dfadump(dfa);
  658.     switch(*dfa)
  659.     {
  660.       case CHR: n = CHRSKIP; break;
  661.       case ANY: n = ANYSKIP; break;
  662.       case SET: case NSET: n = SETSKIP; break;
  663.     }
  664.     dfa += n;
  665.     break;
  666.       case CHR: printf("\tCHR %c\n",*dfa++); break;
  667.       case ANY: printf("\tANY .\n"); break;
  668.       case BOL: printf("\tBOL -\n"); break;
  669.       case EOL: printf("\tEOL -\n"); break;
  670.       case BOT: printf("BOT: %d\n",*dfa++); break;
  671.       case EOT: printf("EOT: %d\n",*dfa++); break;
  672.       case BOW: printf("BOW\n"); break;
  673.       case EOW: printf("EOW\n"); break;
  674.       case REF: printf("REF: %d\n",*dfa++); break;
  675.       case SET:
  676.         printf("\tSET [");
  677.     for (n = 0; n < MAXCHR; n++)
  678.       if (ISINSET(dfa,n)) printf("%c",n);
  679.     printf("]\n");
  680.     dfa += BITBLK;
  681.     break;
  682.       case NSET:
  683.         printf("\tNSET [");
  684.     for (n = 0; n < MAXCHR; n++)
  685.       if (ISINSET(dfa,n)) printf("%c",n);
  686.     printf("]\n"); dfa += BITBLK;
  687.     break;
  688.       default:
  689.         printf("bad dfa. opcode %o\n", dfa[-1]);
  690.     exit(1);
  691.     break;
  692.     }
  693. }
  694. #endif
  695.