home *** CD-ROM | disk | FTP | other *** search
/ Amiga Elysian Archive / AmigaElysianArchive.iso / wp_dtp / ispell.lha / regex.c < prev    next >
C/C++ Source or Header  |  1990-12-29  |  19KB  |  894 lines
  1. /*
  2.  * regex - Regular expression pattern matching
  3.  *         and replacement
  4.  *
  5.  *
  6.  * By:  Ozan S. Yigit (oz)
  7.  *      Dept. of Computer Science
  8.  *      York University
  9.  *
  10.  *
  11.  * These routines are the PUBLIC DOMAIN equivalents
  12.  * of regex routines as found in 4.nBSD UN*X, with minor
  13.  * extensions.
  14.  *
  15.  * These routines are derived from various implementations
  16.  * found in software tools books, and Conroy's grep. They
  17.  * are NOT derived from licensed/restricted software.
  18.  * For more interesting/academic/complicated implementations,
  19.  * see Henry Spencer's regexp routines, or GNU Emacs pattern
  20.  * matching module.
  21.  *
  22.  * Routines:
  23.  *      re_comp:        compile a regular expression into
  24.  *                      a DFA.
  25.  *
  26.  *            char *re_comp(s)
  27.  *            char *s;
  28.  *
  29.  *      re_exec:        execute the DFA to match a pattern.
  30.  *
  31.  *            int re_exec(s)
  32.  *            char *s;
  33.  *
  34.  *    re_modw        change re_exec's understanding of what
  35.  *            a "word" looks like (for \< and \>)
  36.  *            by adding into the hidden word-character
  37.  *            table.
  38.  *
  39.  *            void re_modw(s)
  40.  *            char *s;
  41.  *
  42.  *      re_subs:    substitute the matched portions in
  43.  *                  a new string.
  44.  *
  45.  *            int re_subs(src, dst)
  46.  *            char *src;
  47.  *            char *dst;
  48.  *
  49.  *    re_fail:    failure routine for re_exec.
  50.  *
  51.  *            void re_fail(msg, op)
  52.  *            char *msg;
  53.  *            char op;
  54.  *
  55.  * Regular Expressions:
  56.  *
  57.  *      [1]     char    matches itself, unless it is a special
  58.  *                      character (metachar): . \ [ ] * + ^ $
  59.  *
  60.  *      [2]     .       matches any character.
  61.  *
  62.  *      [3]     \       matches the character following it, except
  63.  *            when followed by a left or right round bracket,
  64.  *            a digit 1 to 9 or a left or right angle bracket.
  65.  *            (see [7], [8] and [9])
  66.  *            It is used as an escape character for all
  67.  *            other meta-characters, and itself. When used
  68.  *            in a set ([4]), it is treated as an ordinary
  69.  *            character.
  70.  *
  71.  *      [4]     [set]   matches one of the characters in the set.
  72.  *                      If the first character in the set is "^",
  73.  *                      it matches a character NOT in the set. A
  74.  *                      shorthand S-E is used to specify a set of
  75.  *                      characters S upto E, inclusive. The special
  76.  *                      characters "]" and "-" have no special
  77.  *                      meaning if they appear as the first chars
  78.  *                      in the set.
  79.  *                      examples:        match:
  80.  *
  81.  *                              [a-z]    any lowercase alpha
  82.  *
  83.  *                              [^]-]    any char except ] and -
  84.  *
  85.  *                              [^A-Z]   any char except uppercase
  86.  *                                       alpha
  87.  *
  88.  *                              [a-zA-Z] any alpha
  89.  *
  90.  *      [5]     *       any regular expression form [1] to [4], followed by
  91.  *                      closure char (*) matches zero or more matches of
  92.  *                      that form.
  93.  *
  94.  *      [6]     +       same as [5], except it matches one or more.
  95.  *
  96.  *      [7]             a regular expression in the form [1] to [10], enclosed
  97.  *                      as \(form\) matches what form matches. The enclosure
  98.  *                      creates a set of tags, used for [8] and for
  99.  *                      pattern substution. The tagged forms are numbered
  100.  *            starting from 1.
  101.  *
  102.  *      [8]             a \ followed by a digit 1 to 9 matches whatever a
  103.  *                      previously tagged regular expression ([7]) matched.
  104.  *
  105.  *    [9]    \<    a regular expression starting with a \< construct
  106.  *        \>    and/or ending with a \> construct, restricts the
  107.  *            pattern matching to the beginning of a word, and/or
  108.  *            the end of a word. A word is defined to be a character
  109.  *            string beginning and/or ending with the characters
  110.  *            A-Z a-z 0-9 and _. It must also be preceded and/or
  111.  *            followed by any character outside those mentioned.
  112.  *
  113.  *      [10]            a composite regular expression xy where x and y
  114.  *                      are in the form [1] to [10] matches the longest
  115.  *                      match of x followed by a match for y.
  116.  *
  117.  *      [11]    ^    a regular expression starting with a ^ character
  118.  *        $    and/or ending with a $ character, restricts the
  119.  *                      pattern matching to the beginning of the line,
  120.  *                      or the end of line. [anchors] Elsewhere in the
  121.  *            pattern, ^ and $ are treated as ordinary characters.
  122.  *
  123.  *
  124.  * Acknowledgements:
  125.  *
  126.  *    HCR's Hugh Redelmeier has been most helpful in various
  127.  *    stages of development. He convinced me to include BOW
  128.  *    and EOW constructs, originally invented by Rob Pike at
  129.  *    the University of Toronto.
  130.  *
  131.  * References:
  132.  *              Software tools            Kernighan & Plauger
  133.  *              Software tools in Pascal        Kernighan & Plauger
  134.  *              Grep [rsx-11 C dist]            David Conroy
  135.  *        ed - text editor        Un*x Programmer's Manual
  136.  *        Advanced editing on Un*x    B. W. Kernighan
  137.  *        RegExp routines            Henry Spencer
  138.  *
  139.  * Notes:
  140.  *
  141.  *    This implementation uses a bit-set representation for character
  142.  *    classes for speed and compactness. Each character is represented
  143.  *    by one bit in a 128-bit block. Thus, CCL or NCL always takes a
  144.  *    constant 16 bytes in the internal dfa, and re_exec does a single
  145.  *    bit comparison to locate the character in the set.
  146.  *
  147.  * Examples:
  148.  *
  149.  *    pattern:    foo*.*
  150.  *    compile:    CHR f CHR o CLO CHR o END CLO ANY END END
  151.  *    matches:    fo foo fooo foobar fobar foxx ...
  152.  *
  153.  *    pattern:    fo[ob]a[rz]
  154.  *    compile:    CHR f CHR o CCL 2 o b CHR a CCL bitset END
  155.  *    matches:    fobar fooar fobaz fooaz
  156.  *
  157.  *    pattern:    foo\\+
  158.  *    compile:    CHR f CHR o CHR o CHR \ CLO CHR \ END END
  159.  *    matches:    foo\ foo\\ foo\\\  ...
  160.  *
  161.  *    pattern:    \(foo\)[1-3]\1    (same as foo[1-3]foo)
  162.  *    compile:    BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
  163.  *    matches:    foo1foo foo2foo foo3foo
  164.  *
  165.  *    pattern:    \(fo.*\)-\1
  166.  *    compile:    BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
  167.  *    matches:    foo-foo fo-fo fob-fob foobar-foobar ...
  168.  *
  169.  */
  170.  
  171. #include <stdio.h>
  172. #include <proto/all.h>
  173. #include "ispell.h"
  174.  
  175. /*
  176.  * re_fail:
  177.  *    internal error handler for re_exec.
  178.  *
  179.  *    should probably do something like a
  180.  *    longjump to recover gracefully.
  181.  */
  182. void re_fail (char *s, char c)
  183. {
  184.   fprintf (stderr, "regex: %s [opcode %o]\n", s, c);
  185. }
  186.  
  187. #define MAXDFA  1024
  188. #define MAXTAG  10
  189.  
  190. #define OKP     1
  191. #define NOP     0
  192.  
  193. #define CHR     1
  194. #define ANY     2
  195. #define CCL     3
  196. #define NCL     4
  197. #define BOL     5
  198. #define EOL     6
  199. #define BOT     7
  200. #define EOT     8
  201. #define BOW    9
  202. #define EOW    10
  203. #define REF     11
  204. #define CLO     12
  205.  
  206. #define END     0
  207.  
  208. /*
  209.  * The following defines are not meant
  210.  * to be changeable. They are for readibility
  211.  * only.
  212.  *
  213.  */
  214. #define MAXCHR    128
  215. #define CHRBIT    8
  216. #define BITBLK    MAXCHR/CHRBIT
  217. #define BLKIND    0170
  218. #define BITIND    07
  219.  
  220. #define ASCIIB    0177
  221.  
  222. static int tagstk[MAXTAG];    /* subpat tag stack..*/
  223. static char dfa[MAXDFA];    /* automaton..       */
  224. static int sta = NOP;        /* status of lastpat */
  225.  
  226. static char bittab[BITBLK];    /* bit table for CCL */
  227.  
  228. static void chset (char c)
  229. {
  230.   bittab[((c) & BLKIND) >> 3] |= 1 << ((c) & BITIND);
  231. }
  232.  
  233. #define badpat(x)    return(*dfa = END, x)
  234. #define store(x)    *mp++ = x
  235.  
  236. char *re_comp (char *pat)
  237. {
  238.   register char *p;        /* pattern pointer   */
  239.   register char *mp = dfa;    /* dfa pointer       */
  240.   register char *lp;        /* saved pointer..   */
  241.   register char *sp = dfa;    /* another one..     */
  242.  
  243.   register int tagi = 0;    /* tag stack index   */
  244.   register int tagc = 1;    /* actual tag count  */
  245.  
  246.   register int n;
  247.   int c1, c2;
  248.  
  249.   if (!pat || !*pat)
  250.     if (sta)
  251.       return (0);
  252.     else
  253.       badpat ("No previous regular expression");
  254.   sta = NOP;
  255.  
  256.   for (p = pat; *p; p++)
  257.     {
  258.       lp = mp;
  259.       switch (*p)
  260.     {
  261.  
  262.     case '.':        /* match any char..  */
  263.       store (ANY);
  264.       break;
  265.  
  266.     case '^':        /* match beginning.. */
  267.       if (p == pat)
  268.         store (BOL);
  269.       else
  270.         {
  271.           store (CHR);
  272.           store (*p);
  273.         }
  274.       break;
  275.  
  276.     case '$':        /* match endofline.. */
  277.       if (!*(p + 1))
  278.         store (EOL);
  279.       else
  280.         {
  281.           store (CHR);
  282.           store (*p);
  283.         }
  284.       break;
  285.  
  286.     case '[':        /* match char class..*/
  287.  
  288.       if (*++p == '^')
  289.         {
  290.           store (NCL);
  291.           p++;
  292.         }
  293.       else
  294.         store (CCL);
  295.  
  296.       if (*p == '-')    /* real dash */
  297.         chset (*p++);
  298.       if (*p == ']')    /* real brac */
  299.         chset (*p++);
  300.       while (*p && *p != ']')
  301.         {
  302.           if (*p == '-' && *(p + 1) && *(p + 1) != ']')
  303.         {
  304.           p++;
  305.           c1 = *(p - 2) + 1;
  306.           c2 = *p++;
  307.           while (c1 <= c2)
  308.             chset ((char) c1++);
  309.         }
  310. #ifdef EXTEND
  311.           else if (*p == '\\' && *(p + 1))
  312.         {
  313.           p++;
  314.           chset (*p++);
  315.         }
  316. #endif
  317.           else
  318.         chset (*p++);
  319.         }
  320.       if (!*p)
  321.         badpat ("Missing ]");
  322.  
  323.       for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
  324.         store (bittab[n]);
  325.  
  326.       break;
  327.  
  328.     case '*':        /* match 0 or more.. */
  329.     case '+':        /* match 1 or more.. */
  330.       if (p == pat)
  331.         badpat ("Empty closure");
  332.       lp = sp;        /* previous opcode */
  333.       if (*lp == CLO)    /* equivalence..   */
  334.         break;
  335.       switch (*lp)
  336.         {
  337.  
  338.         case BOL:
  339.         case BOT:
  340.         case EOT:
  341.         case BOW:
  342.         case EOW:
  343.         case REF:
  344.           badpat ("Illegal closure");
  345.         default:
  346.           break;
  347.         }
  348.  
  349.       if (*p == '+')
  350.         for (sp = mp; lp < sp; lp++)
  351.           store (*lp);
  352.  
  353.       store (END);
  354.       store (END);
  355.       sp = mp;
  356.       while (--mp > lp)
  357.         *mp = mp[-1];
  358.       store (CLO);
  359.       mp = sp;
  360.       break;
  361.  
  362.     case '\\':        /* tags, backrefs .. */
  363.       switch (*++p)
  364.         {
  365.  
  366.         case '(':
  367.           if (tagc < MAXTAG)
  368.         {
  369.           tagstk[++tagi] = tagc;
  370.           store (BOT);
  371.           store (tagc++);
  372.         }
  373.           else
  374.         badpat ("Too many \\(\\) pairs");
  375.           break;
  376.         case ')':
  377.           if (*sp == BOT)
  378.         badpat ("Null pattern inside \\(\\)");
  379.           if (tagi > 0)
  380.         {
  381.           store (EOT);
  382.           store (tagstk[tagi--]);
  383.         }
  384.           else
  385.         badpat ("Unmatched \\)");
  386.           break;
  387.         case '<':
  388.           store (BOW);
  389.           break;
  390.         case '>':
  391.           if (*sp == BOW)
  392.         badpat ("Null pattern inside \\<\\>");
  393.           store (EOW);
  394.           break;
  395.         case '1':
  396.         case '2':
  397.         case '3':
  398.         case '4':
  399.         case '5':
  400.         case '6':
  401.         case '7':
  402.         case '8':
  403.         case '9':
  404.           n = *p - '0';
  405.           if (tagi > 0 && tagstk[tagi] == n)
  406.         badpat ("Cyclical reference");
  407.           if (tagc > n)
  408.         {
  409.           store (REF);
  410.           store (n);
  411.         }
  412.           else
  413.         badpat ("Undetermined reference");
  414.           break;
  415. #ifdef EXTEND
  416.         case 'b':
  417.           store (CHR);
  418.           store ('\b');
  419.           break;
  420.         case 'n':
  421.           store (CHR);
  422.           store ('\n');
  423.           break;
  424.         case 'f':
  425.           store (CHR);
  426.           store ('\f');
  427.           break;
  428.         case 'r':
  429.           store (CHR);
  430.           store ('\r');
  431.           break;
  432.         case 't':
  433.           store (CHR);
  434.           store ('\t');
  435.           break;
  436. #endif
  437.         default:
  438.           store (CHR);
  439.           store (*p);
  440.         }
  441.       break;
  442.  
  443.     default:        /* an ordinary char  */
  444.       store (CHR);
  445.       store (*p);
  446.       break;
  447.     }
  448.       sp = lp;
  449.     }
  450.   if (tagi > 0)
  451.     badpat ("Unmatched \\(");
  452.   store (END);
  453.   sta = OKP;
  454.   return (0);
  455. }
  456.  
  457.  
  458. static char *bol;
  459. static char *bopat[MAXTAG];
  460. static char *eopat[MAXTAG];
  461.  
  462. /*
  463.  * re_exec:
  464.  *     execute dfa to find a match.
  465.  *
  466.  *    special cases: (dfa[0])
  467.  *        BOL
  468.  *            Match only once, starting from the
  469.  *            beginning.
  470.  *        CHR
  471.  *            First locate the character without
  472.  *            calling pmatch, and if found, call
  473.  *            pmatch for the remaining string.
  474.  *        END
  475.  *            re_comp failed, poor luser did not
  476.  *            check for it. Fail fast.
  477.  *
  478.  *    If a match is found, bopat[0] and eopat[0] are set
  479.  *    to the beginning and the end of the matched fragment,
  480.  *    respectively.
  481.  *
  482.  */
  483.  
  484. int re_exec (char *lp)
  485. {
  486.   register char c;
  487.   register char *ep = 0;
  488.   register char *ap = dfa;
  489.  
  490.   bol = lp;
  491.  
  492.   bopat[0] = 0;
  493.   bopat[1] = 0;
  494.   bopat[2] = 0;
  495.   bopat[3] = 0;
  496.   bopat[4] = 0;
  497.   bopat[5] = 0;
  498.   bopat[6] = 0;
  499.   bopat[7] = 0;
  500.   bopat[8] = 0;
  501.   bopat[9] = 0;
  502.  
  503.   switch (*ap)
  504.     {
  505.  
  506.     case BOL:            /* anchored: match from BOL only */
  507.       ep = pmatch (lp, ap);
  508.       break;
  509.     case CHR:            /* ordinary char: locate it fast */
  510.       c = *(ap + 1);
  511.       while (*lp && *lp != c)
  512.     lp++;
  513.       if (!*lp)            /* if EOS, fail, else fall thru. */
  514.     return (0);
  515.     default:            /* regular matching all the way. */
  516.       while (*lp)
  517.     {
  518.       if ((ep = pmatch (lp, ap)))
  519.         break;
  520.       lp++;
  521.     }
  522.       break;
  523.     case END:            /* munged automaton. fail always */
  524.       return (0);
  525.     }
  526.   if (!ep)
  527.     return (0);
  528.  
  529.   bopat[0] = lp;
  530.   eopat[0] = ep;
  531.   return (1);
  532. }
  533.  
  534. /*
  535.  * pmatch:
  536.  *    internal routine for the hard part
  537.  *
  538.  *     This code is mostly snarfed from an early
  539.  *     grep written by David Conroy. The backref and
  540.  *     tag stuff, and various other mods are by oZ.
  541.  *
  542.  *    special cases: (dfa[n], dfa[n+1])
  543.  *        CLO ANY
  544.  *            We KNOW ".*" will match ANYTHING
  545.  *            upto the end of line. Thus, go to
  546.  *            the end of line straight, without
  547.  *            calling pmatch recursively. As in
  548.  *            the other closure cases, the remaining
  549.  *            pattern must be matched by moving
  550.  *            backwards on the string recursively,
  551.  *            to find a match for xy (x is ".*" and
  552.  *            y is the remaining pattern) where
  553.  *            the match satisfies the LONGEST match
  554.  *            for x followed by a match for y.
  555.  *        CLO CHR
  556.  *            We can again scan the string forward
  557.  *            for the single char without recursion,
  558.  *            and at the point of failure, we execute
  559.  *            the remaining dfa recursively, as
  560.  *            described above.
  561.  *
  562.  *    At the end of a successful match, bopat[n] and eopat[n]
  563.  *    are set to the beginning and end of subpatterns matched
  564.  *    by tagged expressions (n = 1 to 9).
  565.  *
  566.  */
  567.  
  568. /*
  569.  * character classification table for word boundary
  570.  * operators BOW and EOW. the reason for not using
  571.  * ctype macros is that we can let the user add into
  572.  * our own table. see re_modw. This table is not in
  573.  * the bitset form, since we may wish to extend it
  574.  * in the future for other character classifications.
  575.  *
  576.  *    TRUE for 0-9 A-Z a-z _
  577.  */
  578. static char chrtyp[MAXCHR] =
  579. {
  580.   0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  581.   0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  582.   0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  583.   0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  584.   0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
  585.   1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
  586.   0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
  587.   1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  588.   1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  589.   1, 0, 0, 0, 0, 1, 0, 1, 1, 1,
  590.   1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  591.   1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  592.   1, 1, 1, 0, 0, 0, 0, 0
  593. };
  594.  
  595. #define inascii(x)    (0177&(x))
  596. #define iswordc(x)     chrtyp[inascii(x)]
  597. #define isinset(x,y)     ((x)[((y)&BLKIND)>>3] & (1<<((y)&BITIND)))
  598.  
  599. /*
  600.  * skip values for CLO XXX to skip past the closure
  601.  *
  602.  */
  603.  
  604. #define ANYSKIP    2        /* CLO ANY END ...       */
  605. #define CHRSKIP    3        /* CLO CHR chr END ...       */
  606. #define CCLSKIP 18        /* CLO CCL 16bytes END ... */
  607.  
  608. char *pmatch (char *lp, char *ap)
  609. {
  610.   register char *e;        /* extra pointer for CLO */
  611.   register char *bp;        /* beginning of subpat.. */
  612.   register char *ep;        /* ending of subpat..     */
  613.   register int op, c, n;
  614.   char *are;            /* to save the line ptr. */
  615.  
  616.   while ((op = *ap++) != END)
  617.     switch (op)
  618.       {
  619.  
  620.       case CHR:
  621.     if (*lp++ != *ap++)
  622.       return (0);
  623.     break;
  624.       case ANY:
  625.     if (!*lp++)
  626.       return (0);
  627.     break;
  628.       case CCL:
  629.     c = *lp++;
  630.     if (!isinset (ap, c))
  631.       return (0);
  632.     ap += BITBLK;
  633.     break;
  634.       case NCL:
  635.     c = *lp++;
  636.     if (isinset (ap, c))
  637.       return (0);
  638.     ap += BITBLK;
  639.     break;
  640.       case BOL:
  641.     if (lp != bol)
  642.       return (0);
  643.     break;
  644.       case EOL:
  645.     if (*lp)
  646.       return (0);
  647.     break;
  648.       case BOT:
  649.     bopat[*ap++] = lp;
  650.     break;
  651.       case EOT:
  652.     eopat[*ap++] = lp;
  653.     break;
  654.       case BOW:
  655.     if (!(lp != bol && iswordc (lp[-1])) && iswordc (*lp))
  656.       break;
  657.     return (0);
  658.       case EOW:
  659.     if ((lp != bol && iswordc (lp[-1])) && !iswordc (*lp))
  660.       break;
  661.     return (0);
  662.       case REF:
  663.     n = *ap++;
  664.     bp = bopat[n];
  665.     ep = eopat[n];
  666.     while (bp < ep)
  667.       if (*bp++ != *lp++)
  668.         return (0);
  669.     break;
  670.       case CLO:
  671.     are = lp;
  672.     switch (*ap)
  673.       {
  674.  
  675.       case ANY:
  676.         while (*lp)
  677.           lp++;
  678.         n = ANYSKIP;
  679.         break;
  680.       case CHR:
  681.         c = *(ap + 1);
  682.         while (*lp && c == *lp)
  683.           lp++;
  684.         n = CHRSKIP;
  685.         break;
  686.       case CCL:
  687.       case NCL:
  688.         while (*lp && (e = pmatch (lp, ap)))
  689.           lp = e;
  690.         n = CCLSKIP;
  691.         break;
  692.       default:
  693.         re_fail ("closure: bad dfa.", *ap);
  694.         return (0);
  695.       }
  696.  
  697.     ap += n;
  698.  
  699.     while (lp >= are)
  700.       {
  701.         if (e = pmatch (lp, ap))
  702.           return (e);
  703.         --lp;
  704.       }
  705.     return (0);
  706.       default:
  707.     re_fail ("re_exec: bad dfa.", (char) op);
  708.     return (0);
  709.       }
  710.   return (lp);
  711. }
  712.  
  713. /*
  714.  * re_modw:
  715.  *    add new characters into the word table to
  716.  *    change the re_exec's understanding of what
  717.  *    a word should look like. Note that we only
  718.  *    accept additions into the word definition.
  719.  *
  720.  *    If the string parameter is 0 or null string,
  721.  *    the table is reset back to the default, which
  722.  *    contains A-Z a-z 0-9 _. [We use the compact
  723.  *    bitset representation for the default table]
  724.  *
  725.  */
  726.  
  727. static char deftab[16] =
  728. {
  729.   0, 0, 0, 0, 0, 0, 377, 003, 376, 377, 377, 207,
  730.   376, 377, 377, 007
  731. };
  732.  
  733. void re_modw (char *s)
  734. {
  735.   register int i;
  736.  
  737.   if (!s || !*s)
  738.     {
  739.       for (i = 0; i < MAXCHR; i++)
  740.     if (!isinset (deftab, i))
  741.       iswordc (i) = 0;
  742.     }
  743.   else
  744.     while (*s)
  745.       iswordc (*s++) = 1;
  746. }
  747.  
  748. /*
  749.  * re_subs:
  750.  *    substitute the matched portions of the src in
  751.  *    dst.
  752.  *
  753.  *    &    substitute the entire matched pattern.
  754.  *
  755.  *    \digit    substitute a subpattern, with the given
  756.  *        tag number. Tags are numbered from 1 to
  757.  *        9. If the particular tagged subpattern
  758.  *        does not exist, null is substituted.
  759.  *
  760.  */
  761. int re_subs (char *src, char *dst)
  762. {
  763.   register char c;
  764.   register int pin;
  765.   register char *bp;
  766.   register char *ep;
  767.  
  768.   if (!*src || !bopat[0])
  769.     return (0);
  770.  
  771.   while (c = *src++)
  772.     {
  773.       switch (c)
  774.     {
  775.  
  776.     case '&':
  777.       pin = 0;
  778.       break;
  779.  
  780.     case '\\':
  781.       c = *src++;
  782.       if (c >= '0' && c <= '9')
  783.         {
  784.           pin = c - '0';
  785.           break;
  786.         }
  787.  
  788.     default:
  789.       *dst++ = c;
  790.       continue;
  791.     }
  792.  
  793.       if ((bp = bopat[pin]) && (ep = eopat[pin]))
  794.     {
  795.       while (*bp && bp < ep)
  796.         *dst++ = *bp++;
  797.       if (bp < ep)
  798.         return (0);
  799.     }
  800.     }
  801.   *dst = (char) 0;
  802.   return (1);
  803. }
  804.  
  805. #ifdef DEBUG
  806. /*
  807.  * symbolic - produce a symbolic dump of the
  808.  *            dfa
  809.  */
  810. symbolic (s)
  811.      char *s;
  812. {
  813.   printf ("pattern: %s\n", s);
  814.   printf ("dfacode:\n");
  815.   dfadump (dfa);
  816. }
  817.  
  818. static int dfadump (char *ap)
  819. {
  820.   register int n;
  821.  
  822.   while (*ap != END)
  823.     switch (*ap++)
  824.       {
  825.       case CLO:
  826.     printf ("CLOSURE");
  827.     dfadump (ap);
  828.     switch (*ap)
  829.       {
  830.       case CHR:
  831.         n = CHRSKIP;
  832.         break;
  833.       case ANY:
  834.         n = ANYSKIP;
  835.         break;
  836.       case CCL:
  837.       case NCL:
  838.         n = CCLSKIP;
  839.         break;
  840.       }
  841.     ap += n;
  842.     break;
  843.       case CHR:
  844.     printf ("\tCHR %c\n", *ap++);
  845.     break;
  846.       case ANY:
  847.     printf ("\tANY .\n");
  848.     break;
  849.       case BOL:
  850.     printf ("\tBOL -\n");
  851.     break;
  852.       case EOL:
  853.     printf ("\tEOL -\n");
  854.     break;
  855.       case BOT:
  856.     printf ("BOT: %d\n", *ap++);
  857.     break;
  858.       case EOT:
  859.     printf ("EOT: %d\n", *ap++);
  860.     break;
  861.       case BOW:
  862.     printf ("BOW\n");
  863.     break;
  864.       case EOW:
  865.     printf ("EOW\n");
  866.     break;
  867.       case REF:
  868.     printf ("REF: %d\n", *ap++);
  869.     break;
  870.       case CCL:
  871.     printf ("\tCCL [");
  872.     for (n = 0; n < MAXCHR; n++)
  873.       if (isinset (ap, (char) n))
  874.         printf ("%c", n);
  875.     printf ("]\n");
  876.     ap += BITBLK;
  877.     break;
  878.       case NCL:
  879.     printf ("\tNCL [");
  880.     for (n = 0; n < MAXCHR; n++)
  881.       if (isinset (ap, (char) n))
  882.         printf ("%c", n);
  883.     printf ("]\n");
  884.     ap += BITBLK;
  885.     break;
  886.       default:
  887.     printf ("bad dfa. opcode %o\n", ap[-1]);
  888.     exit (1);
  889.     break;
  890.       }
  891. }
  892.  
  893. #endif
  894.