home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / msdos / txtutl / ddjgrep.arc / TOOLS.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-11-05  |  8.4 KB  |  504 lines
  1. /*---------------------------------------------------------------------------
  2.  *         TOOLS.C  the expression parser used by grep 
  3.  *
  4.  *
  5.  *          Copyright (c)    1984 Allen Holub
  6.  *    Copyright (c) 1984 Software Engineering    Consultants
  7.  *            P.O. Box 5679
  8.  *             Berkeley, CA.  94705
  9.  *
  10.  *               All rights reserved.
  11.  *
  12.  *    This program may be copied for personal, non-commmercial use
  13.  *    only, provided that this copyright notice is included in all
  14.  *    copies and that    this program is    not modified in    any way.
  15.  *    Copying    for any    other use without previously obtaining the 
  16.  *    written    permission of the author is prohibited.
  17.  *
  18.  *---------------------------------------------------------------------------
  19.  */
  20.  
  21.  
  22. #include <stdio.h>
  23. #include "tools.h"
  24. #include <ctype.h>
  25. #include <malloc.h>
  26. #include <string.h>
  27.  
  28. /*    This module contains the various routines needed by grep 
  29.  *    to match regular expressions. Routines are ordered alphabeticaly.
  30.  */
  31.  
  32. int    amatch(lin, pat,boln)
  33. char    *lin, *boln;
  34. TOKEN    *pat;
  35. {
  36.     register  char    *bocl, *rval, *strstart;
  37.     
  38.     if (pat    == 0)    return (0);
  39.     
  40.     strstart = lin;
  41.     
  42.     while (pat)
  43.     {
  44.         if (pat->tok ==    CLOSURE      &&   pat->next)
  45.         {
  46.             pat = pat->next;
  47.             bocl = lin;
  48.             while (*lin  &&     omatch(&lin, pat))
  49.                 ;
  50.             if (pat    = pat->next)
  51.             { 
  52.                 while (bocl <= lin)
  53.                 {
  54.                     if (rval = amatch(lin, pat, boln))
  55.                         return(rval);
  56.                     else   
  57.                         --lin;
  58.                 }
  59.                 return (0);
  60.             }
  61.         }
  62.         else if    ( omatch(&lin, pat, boln) )
  63.             pat = pat->next;
  64.         else  
  65.             return(0);
  66.     }
  67.     return ( max(strstart    , --lin) );
  68. }
  69.  
  70. /* ----------------------------------------------------------------------- */
  71.  
  72. delete (ch, str)
  73. int    ch;
  74. register char    *str;
  75. {
  76.     ch &= 0xff;
  77.     while (*str && *str != ch)
  78.         str++;
  79.     while (*str)
  80.     {
  81.         *str = *(str+1);
  82.         str++;
  83.     }
  84. }
  85.       
  86. /* ----------------------------------------------------------------------- */
  87.  
  88. int    dodash(delim, src, map)
  89. int    delim;
  90. char    *src, *map;
  91. {
  92.     register int    first,last;
  93.     char        *start;
  94.  
  95.     start =    src;
  96.  
  97.     while (*src  &&     *src != delim)
  98.     {
  99.         if (*src != '-')
  100.             setbit (esc(&src),map,1);
  101.         else if    (src ==    start || *(src+1) == delim)
  102.             setbit ('-',map,1);
  103.         else
  104.         {    
  105.             src++;
  106.             if (*src < *(src-2))
  107.             {    
  108.                 first =    *src;
  109.                 last = *(src-2);
  110.             }
  111.             else
  112.             {      
  113.                 first =    *(src-2);
  114.                 last = *src;
  115.             }
  116.             while (++first <= last)
  117.                 setbit(first,map,1);
  118.         }
  119.     src++;
  120.     }
  121.     return (src);
  122. }
  123.  
  124. /* ------------------------------------------------------------------------ */
  125.  
  126. int    esc(s)
  127. char    **s;
  128. {
  129.     register int    rval;
  130.  
  131.     if (**s    != ESCAPE)
  132.         rval = **s;
  133.     else
  134.     {
  135.         (*s)++;
  136.  
  137.         switch (toupper(**s))
  138.         {
  139.         case '\000':    rval = ESCAPE;    break;
  140.         case 'S':    rval = ' '   ;    break;
  141.         case 'N':    rval = '\n'  ;    break;
  142.         case 'T':    rval = '\t'  ;    break;
  143.         case 'B':    rval = '\b'  ;    break;
  144.         case 'R':    rval = '\r'  ;    break;
  145.         default:    rval = **s   ;
  146.         }
  147.     }
  148.     return (rval);
  149. }
  150.  
  151. /* ----------------------------------------------------------------------- */
  152.  
  153. TOKEN    *getpat(arg)
  154. char    *arg;
  155. {
  156.     return (makepat(arg, '\000'));
  157. }
  158.  
  159. /* ----------------------------------------------------------------------- */
  160.  
  161. insert(ch, str)
  162. int    ch;
  163. register char    *str;
  164. {
  165.     register char    *bp;
  166.     bp = str;
  167.     while (*str)
  168.         str++;
  169.     do
  170.     {
  171.         *(str+1) = *str;
  172.         str--;
  173.     } while    (str >=    bp);
  174.     *bp = ch;
  175. }
  176.  
  177. /* ----------------------------------------------------------------------- */
  178.  
  179. char    *in_string(delim,str)
  180. register int    delim;
  181. register char    *str;
  182. {
  183.     delim &= 0x7f;
  184.     while (*str  &&     *str != delim)    
  185.         str++;
  186.     return (*str ? str : 0);
  187. }
  188.  
  189. /* ----------------------------------------------------------------------- */
  190.  
  191. int isalphanum(c)
  192. int    c;
  193. {
  194.     return (('a' <=    c && c <= 'z') ||
  195.         ('A' <=    c && c <= 'Z') ||
  196.         ('0' <=    c && c <= '9') 
  197.            );
  198. }
  199.  
  200. /* ----------------------------------------------------------------------- */ 
  201.  
  202. TOKEN    *makepat(arg, delim)
  203. char    *arg;
  204. int    delim;
  205. {
  206.     TOKEN    *head, *tail;
  207.     TOKEN    *ntok;
  208.     char    buf[CLS_SIZE];
  209.     int    error;
  210.  
  211.     if (*arg=='\0' || *arg==delim || *arg=='\n' || *arg==CLOSURE)
  212.         return (0);
  213.     error =    0;
  214.     head = 0;
  215.     tail = 0;
  216.  
  217.     while (*arg && *arg != delim &&    *arg !=    '\n' &&    !error)
  218.     {
  219.         ntok = malloc(TOKSIZE);
  220.         ntok->bitmap = &(ntok->lchar);
  221.         ntok->lchar = '\000';
  222.         ntok->next = 0;
  223.  
  224.         switch (*arg)
  225.         {
  226.         case ANY:
  227.             ntok->tok = ANY;
  228.             break;
  229.         case BOL:
  230.             if (head==0)  
  231.                 ntok->tok = BOL;
  232.             else  
  233.                 error =    1;
  234.             break;
  235.         case EOL:
  236.             if (*(arg+1) ==    delim || *(arg+1) == '\000'
  237.                           || *(arg+1) == '\n')
  238.                 ntok->tok = EOL;
  239.             else    
  240.                 error =    1;
  241.             break;
  242.         case CCL:
  243.             if (*(arg+1) ==    NEGATE)
  244.             {
  245.                 ntok->tok = NCCL;
  246.                 arg += 2;
  247.             }
  248.             else
  249.             {
  250.                 ntok->tok = CCL;
  251.                 arg++;
  252.             }
  253.             if (ntok->bitmap = makebitmap(128))
  254.                 arg = dodash(CCLEND,arg,ntok->bitmap);
  255.             else
  256.             {
  257.                 fprintf    (stderr,"Not enough memory for pat\n");
  258.                 error =    1;
  259.             }
  260.             break;
  261.         case CLOSURE:
  262.             if (head != 0)
  263.             {
  264.                 switch (tail->tok)
  265.                 {
  266.                 case BOL:
  267.                 case EOL:
  268.                 case CLOSURE:
  269.                     return(0);
  270.                 default:
  271.                     ntok->tok = CLOSURE;
  272.                 }
  273.             }
  274.             break;
  275.         default:
  276.             ntok->tok = LITCHAR;
  277.             ntok->lchar = esc(&arg);
  278.         }
  279.  
  280.         if (error || ntok == 0)
  281.         {
  282.             unmakepat(head);
  283.             return (0);
  284.         }
  285.         else if    (head == 0)
  286.         {
  287.             ntok->next = 0;
  288.             head = tail = ntok;
  289.         }
  290.         else if    (ntok->tok != CLOSURE)
  291.         {
  292.             tail->next = ntok;
  293.             ntok->next = tail;
  294.             tail = ntok;
  295.         }
  296.         else if    (head != tail)
  297.         {
  298.             (tail->next)->next = ntok;
  299.             ntok->next = tail;
  300.         }
  301.         else
  302.         {
  303.             ntok->next = head;
  304.             tail->next = ntok;
  305.             head = ntok;
  306.         }
  307.         arg++;
  308.     }
  309.     tail->next = 0;
  310.     return (head);
  311. }
  312.  
  313. /* ----------------------------------------------------------------------- */ 
  314.  
  315. char    *matchs(line,pat,ret_endp)
  316. char    *line;
  317. TOKEN    *pat;
  318. int    ret_endp;
  319. {
  320.     char    *rval, *bptr;
  321.     bptr = line;
  322.     while (*line)
  323.     {
  324.         if ((rval = amatch(line, pat,bptr)) == 0)
  325.             line++;
  326.         else
  327.         {
  328.             rval = ret_endp    ? rval : line ;
  329.             break;
  330.         }
  331.     }
  332.     return (rval);
  333. }
  334.  
  335. /* ----------------------------------------------------------------------- */ 
  336.  
  337. stoupper(str)
  338. char    *str;
  339. {
  340.     char    *rval;
  341.     rval = str;
  342.     while (*str)
  343.     {
  344.         if ('a' <= *str && *str <= 'z')
  345.             *str -=    ('a' - 'A');
  346.         str++;
  347.     }
  348.     return (rval);
  349. }
  350.  
  351. /* ----------------------------------------------------------------------- */ 
  352.  
  353. int    max(x,y)
  354. int    x,y;
  355. {
  356.     return ((x>y) ? x : y);
  357. }
  358.  
  359. /* ----------------------------------------------------------------------- */ 
  360.  
  361. int    omatch (linp, pat, boln)
  362. char    **linp,    *boln;
  363. TOKEN    *pat;
  364. {
  365.     register int    advance;
  366.     advance    = -1;
  367.     if ( **linp )
  368.     {
  369.         switch (pat->tok)
  370.         {
  371.         case LITCHAR:
  372.             if (**linp == pat->lchar) 
  373.                 advance    = 1;
  374.             break;
  375.         case BOL:
  376.             if (*linp == boln) 
  377.                 advance    = 0;
  378.             break;
  379.         case ANY:
  380.             if (**linp != '\n')   
  381.                 advance    = 1;
  382.             break;
  383.         case EOL:
  384.             if (**linp == '\n')  
  385.                 advance    = 0;
  386.         case CCL:
  387.             if (testbit (**linp, pat->bitmap))  
  388.                 advance    = 1;
  389.             break;
  390.         case NCCL:
  391.             if (!testbit(**linp, pat->bitmap)) 
  392.                 advance    = 1;
  393.             break;
  394.         default:
  395.             printf("omatch:    can't happen\n");
  396.         }
  397.     }
  398.     if (advance >= 0)    
  399.         *linp += advance;
  400.     return (++advance);
  401. }
  402.  
  403. /* ----------------------------------------------------------------------- */ 
  404.  
  405. pr_line(ln)
  406. register char    *ln;
  407. {
  408.     for (;*ln;ln++)
  409.     {
  410.         if ((' ' <= *ln)  &&  (*ln <= '~'))
  411.             putchar    (*ln);
  412.         else
  413.         {
  414.             printf ("\\0x%02x", *ln);
  415.             if (*ln    == '\n') 
  416.                 putchar    ('\n');
  417.         }
  418.     }
  419. }
  420.  
  421. /* ----------------------------------------------------------------------- */ 
  422.  
  423. pr_tok(head)
  424. TOKEN    *head;
  425. {
  426.     int    i;
  427.     register char    *str;
  428.  
  429.     for (;head;head=head->next)
  430.     {
  431.          if    (head->tok == BOL)   
  432.              str = "BOL";
  433.          else
  434.         switch (head->tok)
  435.         {
  436.         case EOL:
  437.             str = "EOL";
  438.             break;
  439.         case ANY:
  440.             str = "ANY";
  441.             break;
  442.         case LITCHAR:
  443.             str = "LITCHAR";
  444.             break;
  445.         case ESCAPE:
  446.             str = "ESCAPE";
  447.             break;
  448.         case CCL:
  449.             str = "CCL";
  450.             break;
  451.         case CCLEND:
  452.             str = "CCLEND";
  453.             break;
  454.         case NEGATE:
  455.             str = "NEGATE";
  456.             break;
  457.         case NCCL:
  458.             str = "NCCL";
  459.             break;
  460.         case CLOSURE:
  461.             str = "CLOSURE";
  462.             break;
  463.         default:
  464.             str = "**** unknown ****";
  465.         }
  466.         printf("%-8s at: 0x%x, ", str, head);
  467.         if (head->tok == CCL ||    head->tok == NCCL)
  468.         {    printf ("string    (at 0x%x) =<",head->bitmap);
  469.             for  (i    = 0;i <    0x7f;i++)
  470.                 if (testbit(i,head->bitmap))
  471.                     putchar(i);
  472.             printf (">, ");
  473.         }
  474.         else if    (head->tok == LITCHAR)
  475.             printf ("lchar = %c, ",    head->lchar);
  476.         printf ("next =    0x%x\n", head->next);
  477.     }
  478.     putchar    ('\n');
  479. }
  480.  
  481. /* ----------------------------------------------------------------------- */ 
  482.  
  483. unmakepat(head)
  484. TOKEN    *head;
  485. {
  486.     register TOKEN    *old_head;
  487.  
  488.     while (head)
  489.     {
  490.         switch (head->tok)
  491.         {
  492.         case CCL:
  493.         case NCCL: 
  494.             free (head->bitmap);
  495.         default:
  496.             old_head = head;
  497.             head = head->next;
  498.             free(old_head);
  499.             break;
  500.         }
  501.     }
  502. }
  503.  
  504.