home *** CD-ROM | disk | FTP | other *** search
/ The Fred Fish Collection 1.5 / ffcollection-1-5-1992-11.iso / ff_progs / commands / dr.lzh / DR / SOURCE / PATMATCH.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-08-15  |  6.2 KB  |  283 lines
  1. /*******
  2.  Made reentrant by Paul Kienitz 12/31/90.  Used function prototypes just to
  3.  avoid booboos.  Also replaced _toupper with real toupper.  I hope someday to
  4.  eliminate the error return of CmplPat; make missing parens be assumed to be
  5.  at the beginning or end as appropriate, and an empty half of | be treated
  6.  like a %.  I guess ' at the end is ignored?  Actually it already ignores
  7.  extra right parens at the end.  But with an extra right paren in the middle
  8.  it ignores everything after it.
  9. *******/
  10.  
  11. /* PatMatch.c - Implements AmigaDos Regular Expression Pattern Matching.
  12. **
  13. **  This program will test whether a string is an AmigaDos  regular expression
  14. **  It may be used to implement wild expressions such as:
  15. **
  16. **    "copy #?.c to <dir>" to copy any file ending in .c
  17. **
  18. **  The program has two entry points: CmplPat, and Match.
  19. **
  20. **    CmplPat - takes a pattern and returns an auxilliary array of short
  21. **              ints which is used by Match.  The pattern is not modified
  22. **              in any way.  CmplPat returns 1 if no errors were detected
  23. **              while compiling the pattern; otherwise it returns 0;
  24. **
  25. **    Match   - takes the pattern, the auxilliary vector, and the string
  26. **              to be matched.  It returns 1 if the string matches the
  27. **              pattern; otherwise it returns 0;
  28. **
  29. **  Translated from BCPL by:
  30. **              Jeff Lydiatt
  31. **              Richmond B.C. Canada
  32. **              16 May 1986.
  33. **
  34. **  Source: "A Compact Function for Regular Expression Pattern Matching",
  35. **           Software - Practice and Experience, September 1979.
  36. **
  37. **  Useage:
  38. **     To test if "file.c" matches the regular expression "#?.c"
  39. **     char *Pat = "#?.c";
  40. **     char *Str = "file.c";
  41. **     WORD Aux[128];
  42. **
  43. **     if ( CmplPat( Pat, Aux ) == 0 )
  44. **        {
  45. **           printf("Bad Wildcard Expression\n");
  46. **           exit(1);
  47. **        }
  48. **     if ( Match( Pat, Aux, Str ) == 1 )
  49. **        printf("String matches the pattern\n");
  50. **     else
  51. **        printf("String does NOT match the pattern\n");
  52. **/
  53.  
  54. /*--- Included files ----*/
  55.  
  56. #include <stdio.h>
  57. #include <exec/types.h>
  58. #include <ctype.h>
  59.  
  60. #define  EOS '\0'
  61.  
  62. /*----------------------------------------------------------------*/
  63. /*                   The Interpreter                              */
  64. /*----------------------------------------------------------------*/
  65.  
  66.  
  67. struct GM {
  68.     BOOL  Succflag;
  69.     short Wp;
  70.     short *Work;
  71. };
  72.  
  73.  
  74. static void Put(short N, register struct GM *m)
  75. {
  76.    register short *ip;
  77.    register short *to;
  78.  
  79.    if ( N == 0 )
  80.       m->Succflag = TRUE;
  81.    else
  82.       {
  83.     for ( ip = m->Work + 1, to = m->Work + m->Wp; ip <= to; ip++)
  84.        if ( *ip == N )
  85.           return;
  86.     m->Work[ ++m->Wp ] = N;
  87.       }
  88. }
  89.  
  90. long Match( char Pat[], short Aux[], char Str[] )
  91. {
  92.    struct GM m;
  93.    short     W[ 128 ];
  94.    short     S = 0;
  95.    short     I, N, Q, P, Strlength;
  96.    char      K, Ch;
  97.    size_t    strlen(char *s);
  98.  
  99.    m.Work = W;
  100.    m.Wp = 0;
  101.    m.Succflag = FALSE;
  102.    Strlength = strlen( Str );
  103.    Put( 1, &m );
  104.  
  105.    if ( Aux[ 0 ] != 0 )
  106.       Put( Aux[ 0 ], &m );
  107.  
  108.    for(;;)
  109.       {
  110.         /* First complete the closure */
  111.         for( N=1; N <= m.Wp; N++ )
  112.           {
  113.          P = m.Work[ N ];
  114.          K = Pat[ P-1 ];
  115.          Q = Aux[ P ];
  116.          switch( K )
  117.            {
  118.           case '#': Put( P + 1, &m );
  119.           case '%': Put( Q, &m );
  120.           default : break;
  121.           case '(':
  122.           case '|': Put( P + 1, &m);
  123.                 if ( Q != 0 )
  124.                    Put( Q, &m );
  125.         }
  126.        }
  127.  
  128.     if ( S >= Strlength )
  129.        return m.Succflag;
  130.     if ( m.Wp == 0 )
  131.        return FALSE;
  132.     Ch = Str[ S++ ];
  133.  
  134.     /* Now deal with the match items */
  135.  
  136.     N = m.Wp;
  137.     m.Wp = 0;
  138.     m.Succflag = FALSE;
  139.  
  140.     for ( I = 1; I <= N; I++)
  141.       {
  142.          P = m.Work[ I ];
  143.          K = Pat[ P - 1 ];
  144.          switch( K )
  145.            {
  146.          case '#':
  147.          case '|':
  148.          case '%':
  149.          case '(': break;
  150.          case '\'': K = Pat[ P ];
  151.          default : if ( toupper( Ch ) != toupper( K ) )
  152.                   break;
  153.          case '?': /* Successful match */
  154.                 Put( Aux[ P ], &m );
  155.         } /* End Switch */
  156.       } /* End For I */
  157.      } /* End for(;;) */
  158. }
  159.  
  160.  
  161. /*----------------------------------------------------------------*/
  162. /*                     The Compiler                               */
  163. /*----------------------------------------------------------------*/
  164.  
  165. struct CM {
  166.     short *Aux;
  167.     char  *Pat;
  168.     short PatP, Patlen;
  169.     BOOL  Errflag;
  170.     char  Ch;
  171. };
  172.  
  173. #define CC register struct CM *c
  174.  
  175.  
  176.  
  177. static void Rch( CC ) /* Read next character from Pat */
  178. {
  179.    if ( c->PatP >= c->Patlen )
  180.       c->Ch = EOS;
  181.    else
  182.       c->Ch = c->Pat[ c->PatP++ ];
  183. }
  184.  
  185.  
  186.  
  187. static void Nextitem( CC ) /* Get next char from Pat; recognize ' escape char */
  188. {
  189.    if ( c->Ch == '\'' )
  190.       Rch( c );
  191.    Rch( c );
  192. }
  193.  
  194.  
  195. static void Setexits( short List, short Val, short *Aux )
  196. {
  197.    short A;
  198.  
  199.    do
  200.      {
  201.     A = Aux[ List ];
  202.     Aux[ List ] = Val;
  203.     List = A;
  204.      }
  205.     while ( List != 0 );
  206. }
  207.  
  208. static short Join( short A, short B, short *Aux )
  209. {
  210.     short T = A;
  211.  
  212.     if ( A == 0 )
  213.     return B;
  214.     while ( Aux[ A ] != 0 )
  215.     A = Aux[ A ];
  216.     Aux[ A ] = B;
  217.     return T;
  218. }
  219.  
  220. static short Prim( CC )      /* Parse a Prim symbol */
  221. {
  222.    short   A = c->PatP;
  223.    char Op = c->Ch;
  224.    short  Exp( short A, CC );
  225.  
  226.    Nextitem( c );
  227.    switch( Op )
  228.      {
  229.         case EOS:                /* empty string after | ? */
  230.         case ')':                /* missing ( ? */
  231.         case '|': c->Errflag = TRUE;        /* empty string before | ? */
  232.         default : return A;
  233.         case '#': Setexits( Prim( c ), A, c->Aux );
  234.           return A;
  235.         case '(': A = Exp( A, c );
  236.           if ( c->Ch != ')' )
  237.             c->Errflag = TRUE;    /* missing ) ? */
  238.           Nextitem( c );
  239.           return A;
  240.      }
  241. }
  242.  
  243. static short Exp( short AltP, CC )    /* Parse an expression */
  244. {
  245.    short Exits = 0;
  246.    short A;
  247.  
  248.    for (;;)
  249.     {
  250.        A = Prim( c );
  251.        if ( c->Ch == '|' || c->Ch == ')' || c->Ch == EOS )
  252.           {
  253.         Exits = Join( Exits, A, c->Aux );
  254.         if ( c->Ch != '|' )
  255.            return Exits;
  256.         c->Aux[ AltP ] = c->PatP;
  257.         AltP = c->PatP;
  258.         Nextitem( c );
  259.           }
  260.        else
  261.           Setexits( A, c->PatP, c->Aux );
  262.     }
  263. }
  264.  
  265. long CmplPat( char Pattern[], short CmplPattern[] )
  266. {
  267.    short     i;
  268.    struct CM c;
  269.    size_t    strlen();
  270.  
  271.    c.Pat = Pattern;
  272.    c.Aux = CmplPattern;
  273.    c.PatP = 0;
  274.    c.Patlen = strlen( c.Pat );
  275.    c.Errflag = FALSE;
  276.  
  277.    for ( i = 0; i <= c.Patlen; i++ )
  278.       c.Aux[ i ] = 0;
  279.    Rch( &c );
  280.    Setexits( Exp( 0, &c ), 0, &c.Aux[0] );
  281.    return (!c.Errflag);
  282. }
  283.