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