home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume7 / regex / regex.c < prev   
Encoding:
C/C++ Source or Header  |  1988-10-17  |  18.3 KB  |  867 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. #define MAXDFA  1024
  172. #define MAXTAG  10
  173.  
  174. #define OKP     1
  175. #define NOP     0
  176.  
  177. #define CHR     1
  178. #define ANY     2
  179. #define CCL     3
  180. #define NCL     4
  181. #define BOL     5
  182. #define EOL     6
  183. #define BOT     7
  184. #define EOT     8
  185. #define BOW    9
  186. #define EOW    10
  187. #define REF     11
  188. #define CLO     12
  189.  
  190. #define END     0
  191.  
  192. /*
  193.  * The following defines are not meant
  194.  * to be changeable. They are for readibility
  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 dfa[MAXDFA];        /* automaton..       */
  210. static int  sta = NOP;                   /* status of lastpat */
  211.  
  212. static CHAR bittab[BITBLK];        /* bit table for CCL */
  213.  
  214. static void
  215. chset(c) register CHAR c; { bittab[((c)&BLKIND)>>3] |= 1<<((c)&BITIND); }
  216.  
  217. #define badpat(x)    return(*dfa = END, x)
  218. #define store(x)    *mp++ = x
  219.  
  220. char *     
  221. re_comp(pat)
  222. char *pat;
  223. {
  224.     register char *p;               /* pattern pointer   */
  225.     register CHAR *mp=dfa;          /* dfa pointer       */
  226.     register CHAR *lp;              /* saved pointer..   */
  227.     register CHAR *sp=dfa;          /* another one..     */
  228.  
  229.     register int tagi = 0;          /* tag stack index   */
  230.     register int tagc = 1;          /* actual tag count  */
  231.  
  232.     register int n;
  233.     int c1, c2;
  234.         
  235.     if (!pat || !*pat)
  236.         if (sta)
  237.             return(0);
  238.         else
  239.             badpat("No previous regular expression");
  240.     sta = NOP;
  241.  
  242.     for (p = pat; *p; p++) {
  243.         lp = mp;
  244.         switch(*p) {
  245.  
  246.         case '.':               /* match any char..  */
  247.             store(ANY);
  248.             break;
  249.  
  250.         case '^':               /* match beginning.. */
  251.             if (p == pat)
  252.                 store(BOL);
  253.             else {
  254.                 store(CHR);
  255.                 store(*p);
  256.             }
  257.             break;
  258.  
  259.         case '$':               /* match endofline.. */
  260.             if (!*(p+1))
  261.                 store(EOL);
  262.             else {
  263.                 store(CHR);
  264.                 store(*p);
  265.             }
  266.             break;
  267.  
  268.         case '[':               /* match char class..*/
  269.  
  270.             if (*++p == '^') {
  271.                 store(NCL);
  272.                 p++;
  273.             }
  274.             else
  275.                 store(CCL);
  276.  
  277.             if (*p == '-')        /* real dash */
  278.                 chset(*p++);
  279.             if (*p == ']')        /* real brac */
  280.                 chset(*p++);
  281.             while (*p && *p != ']') {
  282.                 if (*p == '-' && *(p+1) && *(p+1) != ']') {
  283.                     p++;
  284.                     c1 = *(p-2) + 1;
  285.                     c2 = *p++;
  286.                     while (c1 <= c2)
  287.                         chset(c1++);
  288.                 }
  289. #ifdef EXTEND
  290.                 else if (*p == '\\' && *(p+1)) {
  291.                     p++;
  292.                     chset(*p++);
  293.                 }
  294. #endif
  295.                 else
  296.                     chset(*p++);
  297.             }
  298.             if (!*p)
  299.                 badpat("Missing ]");
  300.  
  301.             for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
  302.                 store(bittab[n]);
  303.     
  304.             break;
  305.  
  306.         case '*':               /* match 0 or more.. */
  307.         case '+':               /* match 1 or more.. */
  308.             if (p == pat)
  309.                 badpat("Empty closure");
  310.             lp = sp;                /* previous opcode */
  311.             if (*lp == CLO)         /* equivalence..   */
  312.                 break;
  313.             switch(*lp) {
  314.  
  315.             case BOL:
  316.             case BOT:
  317.             case EOT:
  318.             case BOW:
  319.             case EOW:
  320.             case REF:
  321.                 badpat("Illegal closure");
  322.             default:
  323.                 break;
  324.             }
  325.  
  326.             if (*p == '+')
  327.                 for (sp = mp; lp < sp; lp++)
  328.                     store(*lp);
  329.  
  330.             store(END);
  331.             store(END);
  332.             sp = mp;
  333.             while (--mp > lp)
  334.                 *mp = mp[-1];
  335.             store(CLO);
  336.             mp = sp;
  337.             break;
  338.  
  339.         case '\\':              /* tags, backrefs .. */
  340.             switch(*++p) {
  341.  
  342.             case '(':
  343.                 if (tagc < MAXTAG) {
  344.                     tagstk[++tagi] = tagc;
  345.                     store(BOT);
  346.                     store(tagc++);
  347.                 }
  348.                 else
  349.                     badpat("Too many \\(\\) pairs");
  350.                 break;
  351.             case ')':
  352.                 if (*sp == BOT)
  353.                     badpat("Null pattern inside \\(\\)");
  354.                 if (tagi > 0) {
  355.                     store(EOT);
  356.                     store(tagstk[tagi--]);
  357.                 }
  358.                 else
  359.                     badpat("Unmatched \\)");
  360.                 break;
  361.             case '<':
  362.                 store(BOW);
  363.                 break;
  364.             case '>':
  365.                 if (*sp == BOW)
  366.                     badpat("Null pattern inside \\<\\>");
  367.                 store(EOW);
  368.                 break;
  369.             case '1':
  370.             case '2':
  371.             case '3':
  372.             case '4':
  373.             case '5':
  374.             case '6':
  375.             case '7':
  376.             case '8':
  377.             case '9':
  378.                 n = *p-'0';
  379.                 if (tagi > 0 && tagstk[tagi] == n)
  380.                     badpat("Cyclical reference");
  381.                 if (tagc > n) {
  382.                     store(REF);
  383.                     store(n);
  384.                 }
  385.                 else
  386.                     badpat("Undetermined reference");
  387.                 break;
  388. #ifdef EXTEND
  389.             case 'b':
  390.                 store(CHR);
  391.                 store('\b');
  392.                 break;
  393.             case 'n':
  394.                 store(CHR);
  395.                 store('\n');
  396.                 break;
  397.             case 'f':
  398.                 store(CHR);
  399.                 store('\f');
  400.                 break;
  401.             case 'r':
  402.                 store(CHR);
  403.                 store('\r');
  404.                 break;
  405.             case 't':
  406.                 store(CHR);
  407.                 store('\t');
  408.                 break;
  409. #endif
  410.             default:
  411.                 store(CHR);
  412.                 store(*p);
  413.             }
  414.             break;
  415.  
  416.         default :               /* an ordinary char  */
  417.             store(CHR);
  418.             store(*p);
  419.             break;
  420.         }
  421.         sp = lp;
  422.     }
  423.     if (tagi > 0)
  424.         badpat("Unmatched \\(");
  425.     store(END);
  426.     sta = OKP;
  427.     return(0);
  428. }
  429.  
  430.  
  431. static char *bol;
  432. static char *bopat[MAXTAG];
  433. static char *eopat[MAXTAG];
  434. char *pmatch();
  435.  
  436. /*
  437.  * re_exec:
  438.  *     execute dfa to find a match.
  439.  *
  440.  *    special cases: (dfa[0])    
  441.  *        BOL
  442.  *            Match only once, starting from the
  443.  *            beginning.
  444.  *        CHR
  445.  *            First locate the character without
  446.  *            calling pmatch, and if found, call
  447.  *            pmatch for the remaining string.
  448.  *        END
  449.  *            re_comp failed, poor luser did not
  450.  *            check for it. Fail fast.
  451.  *
  452.  *    If a match is found, bopat[0] and eopat[0] are set
  453.  *    to the beginning and the end of the matched fragment,
  454.  *    respectively.
  455.  *
  456.  */
  457.  
  458. int
  459. re_exec(lp)
  460. register char *lp;
  461. {
  462.     register char c;
  463.     register char *ep = 0;
  464.     register CHAR *ap = dfa;
  465.  
  466.     bol = lp;
  467.  
  468.     bopat[0] = 0;
  469.     bopat[1] = 0;
  470.     bopat[2] = 0;
  471.     bopat[3] = 0;
  472.     bopat[4] = 0;
  473.     bopat[5] = 0;
  474.     bopat[6] = 0;
  475.     bopat[7] = 0;
  476.     bopat[8] = 0;
  477.     bopat[9] = 0;
  478.  
  479.     switch(*ap) {
  480.  
  481.     case BOL:            /* anchored: match from BOL only */
  482.         ep = pmatch(lp,ap);
  483.         break;
  484.     case CHR:            /* ordinary char: locate it fast */
  485.         c = *(ap+1);
  486.         while (*lp && *lp != c)
  487.             lp++;
  488.         if (!*lp)        /* if EOS, fail, else fall thru. */
  489.             return(0);
  490.     default:            /* regular matching all the way. */
  491.         while (*lp) {
  492.             if ((ep = pmatch(lp,ap)))
  493.                 break;
  494.             lp++;
  495.         }
  496.         break;
  497.     case END:            /* munged automaton. fail always */
  498.         return(0);
  499.     }
  500.     if (!ep)
  501.         return(0);
  502.  
  503.     bopat[0] = lp;
  504.     eopat[0] = ep;
  505.     return(1);
  506. }
  507.  
  508. /* 
  509.  * pmatch: 
  510.  *    internal routine for the hard part
  511.  *
  512.  *     This code is mostly snarfed from an early
  513.  *     grep written by David Conroy. The backref and
  514.  *     tag stuff, and various other mods are by oZ.
  515.  *
  516.  *    special cases: (dfa[n], dfa[n+1])
  517.  *        CLO ANY
  518.  *            We KNOW ".*" will match ANYTHING
  519.  *            upto the end of line. Thus, go to
  520.  *            the end of line straight, without
  521.  *            calling pmatch recursively. As in
  522.  *            the other closure cases, the remaining
  523.  *            pattern must be matched by moving
  524.  *            backwards on the string recursively,
  525.  *            to find a match for xy (x is ".*" and 
  526.  *            y is the remaining pattern) where
  527.  *            the match satisfies the LONGEST match
  528.  *            for x followed by a match for y.
  529.  *        CLO CHR
  530.  *            We can again scan the string forward
  531.  *            for the single char without recursion, 
  532.  *            and at the point of failure, we execute 
  533.  *            the remaining dfa recursively, as
  534.  *            described above.
  535.  *
  536.  *    At the end of a successful match, bopat[n] and eopat[n]
  537.  *    are set to the beginning and end of subpatterns matched
  538.  *    by tagged expressions (n = 1 to 9).    
  539.  *
  540.  */
  541.  
  542. extern void re_fail();
  543.  
  544. /*
  545.  * character classification table for word boundary
  546.  * operators BOW and EOW. the reason for not using 
  547.  * ctype macros is that we can let the user add into 
  548.  * our own table. see re_modw. This table is not in
  549.  * the bitset form, since we may wish to extend it
  550.  * in the future for other character classifications. 
  551.  *
  552.  *    TRUE for 0-9 A-Z a-z _
  553.  */
  554. static char chrtyp[MAXCHR] = {
  555.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  556.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  557.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  558.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  559.     0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 
  560.     1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 
  561.     0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 
  562.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  563.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  564.     1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 
  565.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  566.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  567.     1, 1, 1, 0, 0, 0, 0, 0
  568.     };
  569.  
  570. #define inascii(x)    (0177&(x))
  571. #define iswordc(x)     chrtyp[inascii(x)]
  572. #define isinset(x,y)     ((x)[((y)&BLKIND)>>3] & (1<<((y)&BITIND)))
  573.  
  574. /*
  575.  * skip values for CLO XXX to skip past the closure
  576.  *
  577.  */
  578.  
  579. #define ANYSKIP    2     /* CLO ANY END ...       */
  580. #define CHRSKIP    3    /* CLO CHR chr END ...       */
  581. #define CCLSKIP 18    /* CLO CCL 16bytes END ... */
  582.  
  583. static char *
  584. pmatch(lp, ap)
  585. register char *lp;
  586. register CHAR *ap;
  587. {
  588.     register char *e;        /* extra pointer for CLO */
  589.     register char *bp;        /* beginning of subpat.. */
  590.     register char *ep;        /* ending of subpat..     */
  591.     register int op, c, n;
  592.     char *are;            /* to save the line ptr. */
  593.  
  594.     while ((op = *ap++) != END)
  595.         switch(op) {
  596.  
  597.         case CHR:
  598.             if (*lp++ != *ap++)
  599.                 return(0);
  600.             break;
  601.         case ANY:
  602.             if (!*lp++)
  603.                 return(0);
  604.             break;
  605.         case CCL:
  606.             c = *lp++;
  607.             if (!isinset(ap,c))
  608.                 return(0);
  609.             ap += BITBLK;
  610.             break;
  611.         case NCL:
  612.             c = *lp++;
  613.             if (isinset(ap,c))
  614.                 return(0);
  615.             ap += BITBLK;
  616.             break;
  617.         case BOL:
  618.             if (lp != bol)
  619.                 return(0);
  620.             break;
  621.         case EOL:
  622.             if (*lp)
  623.                 return(0);
  624.             break;
  625.         case BOT:
  626.             bopat[*ap++] = lp;
  627.             break;
  628.         case EOT:
  629.             eopat[*ap++] = lp;
  630.             break;
  631.          case BOW:
  632.             if (!(lp!=bol && iswordc(lp[-1])) && iswordc(*lp))
  633.                 break;
  634.             return(0);
  635.         case EOW:
  636.             if ((lp!=bol && iswordc(lp[-1])) && !iswordc(*lp))
  637.                 break;
  638.             return(0);
  639.         case REF:
  640.             n = *ap++;
  641.             bp = bopat[n];
  642.             ep = eopat[n];
  643.             while (bp < ep)
  644.                 if (*bp++ != *lp++)
  645.                     return(0);
  646.             break;
  647.         case CLO:
  648.             are = lp;
  649.             switch(*ap) {
  650.  
  651.             case ANY:
  652.                 while (*lp)
  653.                     lp++;
  654.                 n = ANYSKIP;
  655.                 break;
  656.             case CHR:
  657.                 c = *(ap+1);
  658.                 while (*lp && c == *lp)
  659.                     lp++;
  660.                 n = CHRSKIP;
  661.                 break;
  662.             case CCL:
  663.             case NCL:
  664.                 while (*lp && (e = pmatch(lp, ap)))
  665.                     lp = e;
  666.                 n = CCLSKIP;
  667.                 break;
  668.             default:
  669.                 re_fail("closure: bad dfa.", *ap);
  670.                 return(0);
  671.             }
  672.  
  673.             ap += n;
  674.  
  675.             while (lp >= are) {
  676.                 if (e = pmatch(lp, ap))
  677.                     return(e);
  678.                 --lp;
  679.             }
  680.             return(0);
  681.         default:
  682.             re_fail("re_exec: bad dfa.", op);
  683.             return(0);
  684.         }
  685.     return(lp);
  686. }
  687.  
  688. /*
  689.  * re_modw:
  690.  *    add new characters into the word table to
  691.  *    change the re_exec's understanding of what
  692.  *    a word should look like. Note that we only
  693.  *    accept additions into the word definition.
  694.  *
  695.  *    If the string parameter is 0 or null string,
  696.  *    the table is reset back to the default, which
  697.  *    contains A-Z a-z 0-9 _. [We use the compact
  698.  *    bitset representation for the default table]
  699.  *
  700.  */
  701.  
  702. static char deftab[16] = {    
  703.     0, 0, 0, 0, 0, 0, 377, 003, 376, 377, 377, 207,  
  704.     376, 377, 377, 007 
  705. }; 
  706.  
  707. void
  708. re_modw(s)
  709. register char *s;
  710. {
  711.     register int i;
  712.  
  713.     if (!s || !*s) {
  714.         for (i = 0; i < MAXCHR; i++)
  715.             if (!isinset(deftab,i))
  716.                 iswordc(i) = 0;
  717.     }
  718.     else
  719.         while(*s)
  720.             iswordc(*s++) = 1;
  721. }
  722.  
  723. /*
  724.  * re_subs:
  725.  *    substitute the matched portions of the src in
  726.  *    dst.
  727.  *
  728.  *    &    substitute the entire matched pattern.
  729.  *
  730.  *    \digit    substitute a subpattern, with the given
  731.  *        tag number. Tags are numbered from 1 to
  732.  *        9. If the particular tagged subpattern
  733.  *        does not exist, null is substituted.
  734.  *
  735.  */
  736. int
  737. re_subs(src, dst)
  738. register char *src;
  739. register char *dst;
  740. {
  741.     register char c;
  742.     register int  pin;
  743.     register char *bp;
  744.     register char *ep;
  745.  
  746.     if (!*src || !bopat[0])
  747.         return(0);
  748.  
  749.     while (c = *src++) {
  750.         switch(c) {
  751.  
  752.         case '&':
  753.             pin = 0;
  754.             break;
  755.  
  756.         case '\\':
  757.             c = *src++;
  758.             if (c >= '0' && c <= '9') {
  759.                 pin = c - '0';
  760.                 break;
  761.             }
  762.             
  763.         default:
  764.             *dst++ = c;
  765.             continue;
  766.         }
  767.  
  768.         if ((bp = bopat[pin]) && (ep = eopat[pin])) {
  769.             while (*bp && bp < ep)
  770.                 *dst++ = *bp++;
  771.             if (bp < ep)
  772.                 return(0);
  773.         }
  774.     }
  775.     *dst = (char) 0;
  776.     return(1);
  777. }
  778.             
  779. #ifdef DEBUG
  780. /*
  781.  * symbolic - produce a symbolic dump of the
  782.  *            dfa
  783.  */
  784. symbolic(s) 
  785. char *s;
  786. {
  787.     printf("pattern: %s\n", s);
  788.     printf("dfacode:\n");
  789.     dfadump(dfa);
  790. }
  791.  
  792. static    
  793. dfadump(ap)
  794. CHAR *ap;
  795. {
  796.     register int n;
  797.  
  798.     while (*ap != END)
  799.         switch(*ap++) {
  800.         case CLO:
  801.             printf("CLOSURE");
  802.             dfadump(ap);
  803.             switch(*ap) {
  804.             case CHR:
  805.                 n = CHRSKIP;
  806.                 break;
  807.             case ANY:
  808.                 n = ANYSKIP;
  809.                 break;
  810.             case CCL:
  811.             case NCL:
  812.                 n = CCLSKIP;
  813.                 break;
  814.             }
  815.             ap += n;
  816.             break;
  817.         case CHR:
  818.             printf("\tCHR %c\n",*ap++);
  819.             break;
  820.         case ANY:
  821.             printf("\tANY .\n");
  822.             break;
  823.         case BOL:
  824.             printf("\tBOL -\n");
  825.             break;
  826.         case EOL:
  827.             printf("\tEOL -\n");
  828.             break;
  829.         case BOT:
  830.             printf("BOT: %d\n",*ap++);
  831.             break;
  832.         case EOT:
  833.             printf("EOT: %d\n",*ap++);
  834.             break;
  835.         case BOW:
  836.             printf("BOW\n");
  837.             break;
  838.         case EOW:
  839.             printf("EOW\n");
  840.             break;
  841.         case REF:
  842.             printf("REF: %d\n",*ap++);
  843.             break;
  844.         case CCL:
  845.             printf("\tCCL [");
  846.             for (n = 0; n < MAXCHR; n++)
  847.                 if (isinset(ap,(CHAR)n))
  848.                     printf("%c",n);
  849.             printf("]\n");
  850.             ap += BITBLK;
  851.             break;
  852.         case NCL:
  853.             printf("\tNCL [");
  854.             for (n = 0; n < MAXCHR; n++)
  855.                 if (isinset(ap,(CHAR)n))
  856.                     printf("%c",n);
  857.             printf("]\n");
  858.             ap += BITBLK;
  859.             break;
  860.         default:
  861.             printf("bad dfa. opcode %o\n", ap[-1]);
  862.             exit(1);
  863.             break;
  864.         }
  865. }
  866. #endif
  867.