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