home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / alib / d1xx / d102 / match_stuff.lha / Match_Stuff / match.c_BCPL < prev    next >
Text File  |  1987-09-06  |  4KB  |  169 lines
  1. /* Martin Richards' TRIPOS Pattern Matching algorithm in C */
  2. /* This is a direct transliteration of the BCPL code 87:7:7 */
  3. /*
  4.  * Reference:
  5.  *
  6.  *          Martin Richards,
  7.  *                "A Compact Function for Regular Expression
  8.  *                            Pattern Matching"
  9.  *          [Software--Practice and Experience, Vol 9, 527-534 (1979)]
  10.  */
  11.  
  12.  
  13. #include <exec/types.h>
  14.  
  15. /*** Static Variables: ***/
  16.  
  17. #define Endstreamch 0xFF
  18.  
  19. UBYTE   *Work = NULL;    int Wp = 0,     Succflag = FALSE;
  20. char     *Pat = 0;       UBYTE *Aux = 0;
  21. UBYTE    Ch = 0;          int PatP = 0,   Patlen = 0,
  22.         Errflag = FALSE;
  23.  
  24.  
  25. /*** The Interpreter: ***/
  26.  
  27. Match(Pat, Aux, Str) UBYTE *Aux; char *Pat, *Str; {/*$(1*/
  28.     UBYTE W[128];
  29.     int S = 0;
  30. /* declare local BCPL vars */
  31.     int N, I; UBYTE P, Q; char K;
  32. /***********************/
  33.     Work = W;
  34.     Wp = 0;
  35.     Succflag = FALSE;
  36.     Put(1);
  37.     if (!(Aux[0]==0)) Put(Aux[0]);
  38.   do {/*$(2*/
  39.     for (N=1; N <= Wp; N++) { /* first complete the closure: */
  40.         P=Work[N];
  41.         K = Pat[P]; Q = Aux[P];
  42.         switch(K)
  43.         {
  44.          case '#':  Put(P+1);
  45.          case '%':  Put(Q);
  46.          default:   break;
  47.          case '(':
  48.          case '|':  Put(P+1);
  49.                     if (Q != 0) Put(Q);
  50.         }
  51.     }
  52.     if (S >= Str[0]) return Succflag;
  53.     if (Wp == 0) return FALSE;
  54.     Ch = Str[++S];
  55.  
  56.     /* now deal with match items: */
  57.     N = Wp;
  58.     Wp = 0; Succflag = FALSE;
  59.  
  60.     for (I = 1; I <= N; I++) {
  61.         P = Work[I];
  62.         K = Pat[P];
  63.         switch(K) {
  64.          case '#':
  65.          case '|':
  66.          case '%':
  67.          case '(':
  68.                     break; /* BCPL was 'loop' */
  69.          case '\'': K = Pat[P+1];
  70.          default:  if (Ch != K) break; /* 'loop' */
  71.          case '?':  /* successful match */
  72.                     Put(Aux[P]);
  73.                     break; /* 'loop' */
  74.         }
  75.     }
  76.   }/*$)2*/ while (TRUE);
  77. }/*$)1*/ /*** end Match ***/
  78.  
  79.  
  80. Put(N) int N; {
  81.     int I; /* not needed by BCPL */
  82.     if (N == 0)
  83.         Succflag = TRUE;
  84.     else {
  85.         for (I = 1; I <= Wp; I++) if (Work[I] == N) return;
  86.         Work[++Wp] = N;
  87.     }
  88. }
  89.  
  90.  
  91. /*** The Compiler: ***/
  92.  
  93. Rch() {
  94.     if (PatP >= Patlen)
  95.         Ch = Endstreamch;
  96.     else {
  97.         Ch = Pat[++PatP];
  98.     }
  99. }
  100.  
  101. Nextitem() {
  102.     if (Ch == '\'') Rch();
  103.     Rch();
  104. }
  105.  
  106. int Prim()
  107. {   int A = PatP; UBYTE Op = Ch;
  108.     Nextitem();
  109.     switch(Op) {
  110.      case Endstreamch:
  111.      case ')':
  112.      case '|':  Errflag = TRUE;
  113.      default:   return A;
  114.      case '#':  Setexits(Prim(), A);
  115.                 return A;
  116.      case '(':  A = Exp(A);
  117.                 if (Ch != ')') Errflag = TRUE;
  118.                 Nextitem();
  119.                 return A;
  120.     }
  121. }
  122.  
  123. int Exp(AltP) int AltP;
  124. {/*$(1*/
  125.     int Exits = 0, A;
  126.     do/*$(2*/{ A = Prim();
  127.         if (Ch == '|' || Ch == ')' || Ch == Endstreamch)
  128.             {   Exits = Join(Exits, A);
  129.                 if (Ch != '|') return Exits;
  130.                 Aux[AltP] = PatP;
  131.                 AltP = PatP;
  132.                 Nextitem();
  133.             }
  134.         else Setexits(A, PatP);
  135.     }/*$)2*/ while (TRUE);
  136. }/*$)1*/
  137.  
  138.  
  139. Setexits(List, Val) int List, Val; {
  140.     int A;
  141.     while (List != 0) {
  142.         A = Aux[List];
  143.         Aux[List] = Val;
  144.         List = A;
  145.     }
  146. }
  147.  
  148. int Join(A, B) int A, B;
  149. {
  150.     int T = A;
  151.     if (A == 0) return B;
  152.     while (Aux[A] != 0) A = Aux[A];
  153.     Aux[A] = B;
  154.     return T;
  155. }
  156.  
  157. int CmplPat(Pattern, CmplPattern) char *Pattern, *CmplPattern;
  158. {
  159.     int I; /* BCPL local */
  160.     Pat = Pattern; Aux = CmplPattern;
  161.     PatP = 0; Patlen = Pat[0]; /** this is a BSTR!!! **/
  162.     Errflag = FALSE;
  163.     for (I = 0; I <= Patlen; I++) Aux[I] = 0;
  164.     Rch();
  165.     Setexits(Exp(0), 0);
  166.     return !Errflag;
  167. }
  168.  
  169.