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 < prev    next >
C/C++ Source or Header  |  1987-09-06  |  13KB  |  442 lines
  1. /* TRIPOS Pattern Matching algorithm with extensions */
  2. /*
  3.  * Original BCPL version by Martin Richards
  4.  * This is a transliteration of the BCPL code with additions
  5.  * by Pete Goodeve 87:8:10
  6.  *
  7.  * This version has:
  8.  *                      simple repetition ("*") (alternative to "#?")
  9.  *                      negation ("~" and "||")
  10.  *                      slicing ("^")
  11.  */
  12.  
  13. /*
  14.  * Reference:
  15.  *
  16.  *          Martin Richards,
  17.  *                "A Compact Function for Regular Expression
  18.  *                            Pattern Matching"
  19.  *          [Software--Practice and Experience, Vol 9, 527-534 (1979)]
  20.  */
  21.  
  22. /* don't #define DEBUG 1 */
  23. /* ...there are large hunks of optional trace code in this version */
  24.  
  25. #include <exec/types.h>
  26.  
  27. /* Code bits returned by Pattern Compiler: */
  28.  
  29. /*  this bit always set unless pattern is bad: */
  30. #define CODE_OK 1
  31. /*   the following bits will not be set if pattern is bad: */
  32. /*  set if any single-wild-match characters present ("?"): */
  33. #define CODE_ANY 2
  34. /*  set if any multiple=-wild-match characters present ("*"): */
  35. #define CODE_ALL 4
  36. /*  set if any grouping characters present ("()"): */
  37. #define CODE_GROUP 8
  38. /*  set if pattern has alternations ("|"): */
  39. #define CODE_ALT 16
  40. /*  set if pattern has repeating segments ("#" or "*"): */
  41. #define CODE_REP 32
  42. /*  set if pattern has negation ("~" or "||"): */
  43. #define CODE_NEG 64
  44. /*  set if pattern is sliced ("^"): */
  45. #define CODE_SLICE 128
  46. /*  set if more than MAXMARK slices or if used within parentheses */
  47. #define CODE_OVERSLICE CODE_SLICE | 256
  48.  
  49. /* Pattern Control Characters are defined here so you can change them
  50.  * easily.
  51.  * You may undefine PAT_ALL or PAT_SLICE to remove the sections of code
  52.  * that provide these functions; the other definitions may be changed but
  53.  * not removed.
  54.  */
  55.  
  56. #define PAT_QUOTE '\''
  57. #define PAT_LGROUP '('
  58. #define PAT_RGROUP ')'
  59. #define PAT_ALT '|'
  60. #define PAT_REP '#'
  61. #define PAT_ANY '?'
  62. #define PAT_ALL '*'
  63. #define PAT_NEG '~'
  64.     /* -- note double PAT_ALT is also always a negation code */
  65. #define PAT_NULL '%'
  66. #define PAT_SLICE '^'
  67.  
  68. #define Endstreamch 0xFF
  69. #define WORKSIZE 128
  70.  
  71.  
  72. /*** Static Variables: ***/
  73.  
  74. UBYTE    *Work = NULL;
  75. int      Wp = 0, Succflag = FALSE;
  76. char     *Pat = 0;
  77. UBYTE    *Aux = 0;
  78. UBYTE    Ch = 0;
  79. int      PatP = 0,  Patlen = 0,
  80.          Errflag = FALSE,
  81.          NegP = 0;
  82. UBYTE    *NWork = NULL;
  83. #ifdef PAT_SLICE -------------------------v
  84. #define MAXMARK 4
  85. #define MAXCUT 16
  86. struct  MarkSet {UBYTE mk[MAXMARK];};
  87. UBYTE   *Svect = NULL;
  88. int     cutlimit;
  89. struct MarkSet   MarkP, *MWork;
  90. #endif -----------------------------------^
  91.  
  92. int S, StrLength;
  93.  
  94. #ifdef DEBUG ==============================V
  95. int DEBmode = TRUE; /* set this false for no printout when DEBUG defined */
  96. int ii; /* local variable -- defined here for convenience */
  97. #endif ====================================^
  98.  
  99. /*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/
  100.  
  101.  
  102. /*** The Interpreter: ***/
  103.  
  104. #ifdef PAT_SLICE --------------------------v
  105. SMatch(Pat, Aux, Str, Slice) UBYTE *Aux; char *Pat, *Str, *Slice;
  106. #else ------------------------------------
  107. Match(Pat, Aux, Str) UBYTE *Aux; char *Pat, *Str;
  108. #endif ------------------------------------^
  109. {
  110.     UBYTE W[WORKSIZE];
  111.     UBYTE NegW[WORKSIZE]; /* for negation */
  112. #ifdef PAT_SLICE --------------------------v
  113.     struct MarkSet MarkW[WORKSIZE]; /* for slice marking */
  114. #endif ------------------------------------^
  115.     register int N, I;
  116.     register UBYTE P, Q;
  117.     char K;
  118.  
  119.     StrLength = strlen(Str);
  120.     S = 0;
  121.     Pat -= 1; /* align into "BCPL" form (byte 0 never accessed) */
  122.     Work = W;
  123.     *Work = 0; /* remote possibility of first Put failing otherwise */
  124.     NWork = NegW;
  125. #ifdef PAT_SLICE ---------------------------v
  126.     MWork = MarkW;
  127.     for (I=0; I < MAXMARK; I++) {
  128.         MWork->mk[I] = MarkP.mk[I] = 0;
  129.     }
  130.     if (Svect = Slice) /* allowed to be NULL */
  131.         *Svect = 0;
  132.     cutlimit = MAXCUT;
  133. #endif -------------------------------------^
  134.     Wp = 0;
  135.     Succflag = FALSE;
  136.     NegP = 0;
  137.     Put(1);
  138.     if (!(Aux[0]==0)) Put(Aux[0]);
  139.   do {
  140.     for (N=1; N <= Wp; N++) { /* first complete the closure: */
  141.         P = Work[N];
  142.         NegP = NWork[N] & 1; /* propagate low bit only */
  143. #ifdef PAT_SLICE ---------------------------v
  144.         MarkP = MWork[N];
  145. #endif -------------------------------------^
  146.         K = Pat[P]; Q = Aux[P];
  147.         switch(K)
  148.         {
  149.          case PAT_REP:  Put(P+1);
  150. #ifdef PAT_ALL -----------------------------v
  151.          case PAT_ALL:
  152. #endif -------------------------------------^
  153.          case PAT_NULL: Put(Q);
  154.          default:       break;
  155.          case PAT_LGROUP:
  156.          case PAT_ALT:
  157.                         if (Q != 0) Put(Q);
  158.                         if (Pat[P+1] == '|') { /* Negative alternate */
  159.                             NegP = 1;
  160.                             P++;
  161.                         }
  162.                         Put(P+1);
  163.                         break;
  164.          case PAT_NEG:
  165.                         Put(Q);
  166.                         NegP = 1;
  167.                         if (!(NWork[N] & 2)) Put(P+1);
  168.                         break;
  169. #ifdef PAT_SLICE ----------------------------v
  170.          case PAT_SLICE:
  171.                         Putslice(P, S);
  172.                         Put(Q);
  173. #endif --------------------------------------^
  174.         }
  175.     }
  176. #ifdef DEBUG ====================================V
  177.     if (DEBmode) {
  178.        printf("\nSucc=%d  Closure Vector (len=%d):\n", Succflag, Wp);
  179.        for (ii=1; ii<=Wp; ii++) printf("%3d", Work[ii]);
  180.        putchar('\n');
  181.        for (ii=1; ii<=Wp; ii++) printf("%3d", NWork[ii]);
  182.        puts("\n=====");
  183.     }
  184. #endif ==========================================^
  185.  
  186.     if (S >= StrLength)
  187.         return (Succflag > 0);
  188.     if (Wp == 0) return FALSE;
  189.  
  190.     Ch = Str[S++];
  191. #ifdef DEBUG ====================================V
  192.     if (DEBmode)
  193.        printf("Matching character %c:\n",Ch);
  194. #endif ==========================================^
  195.  
  196.     /* now deal with match items: */
  197.     N = Wp;
  198.     Wp = 0;
  199.     Succflag = FALSE;
  200.  
  201.     for (I = 1; I <= N; I++) {
  202.         P = Work[I];
  203.         NegP = NWork[I];
  204. #ifdef PAT_SLICE ------------------------------v
  205.         MarkP = MWork[I];
  206. #endif ----------------------------------------^
  207.         K = Pat[P];
  208.         switch(K) {
  209.          case PAT_NEG:  NegP |= 2; Put(P);
  210. #ifdef PAT_SLICE ------------------------------v
  211.          case PAT_SLICE:
  212. #endif ----------------------------------------^
  213.          case PAT_REP:
  214.          case PAT_ALT:
  215.          case PAT_NULL:
  216.          case PAT_LGROUP:
  217.                     break; /* BCPL was 'loop' */
  218.          case PAT_QUOTE: K = Pat[P+1];
  219.          default:   if (Ch != K) break; /* 'loop' */
  220.          case PAT_ANY:  /* successful match */
  221.                     Put(Aux[P]);
  222.                     break; /* 'loop' */
  223. #ifdef PAT_ALL --------------------------------v
  224.          case PAT_ALL:  Put(P); /* point back to self...*/
  225.                     break; /* 'loop' */
  226. #endif ----------------------------------------^
  227.         }
  228.     }
  229. #ifdef DEBUG ======================================V
  230.     if (DEBmode) {
  231.        printf("\nSucc=%d Match Vector (len=%d):\n", Succflag, Wp);
  232.        for (ii=1; ii<=Wp; ii++) printf("%3d", Work[ii]);
  233.        putchar('\n');
  234.        for (ii=1; ii<=Wp; ii++) printf("%3d", NWork[ii]);
  235.        puts("\n=====");
  236.     }
  237. #endif ============================================^
  238.   } while (TRUE);
  239. } /*** end Match ***/
  240.  
  241.  
  242. Put(N) int N;
  243. {
  244.     UBYTE *W, *Wlim, *NW;
  245. #ifdef DEBUG ======================================V
  246.     if (DEBmode)
  247. #ifdef PAT_SLICE ------------------------------v
  248.        printf("Put %d[%d, %d/%d]  ", N, NegP, MarkP.mk[0], MarkP.mk[1]);
  249. #else ----------------------------------------
  250.        printf("Put %d[%d]  ", N, NegP);
  251. #endif ----------------------------------------^
  252. #endif ============================================^
  253.     if (N == 0) {
  254.         Succflag |= NegP ? -1 : 1;
  255. #ifdef PAT_SLICE ------------------------------v
  256.         if (S == StrLength) RetSlice(); /* matched -- pass back slice info */
  257. #endif ----------------------------------------^
  258.     }
  259.     else {
  260.         W = Work;
  261.         Wlim = W + Wp;
  262.         NW = NWork;
  263.         for(;W <= Wlim; W++, NW++)
  264.              if ((*W == N)&&(*NW == NegP))
  265.                  return;
  266.         *W = N;
  267.         *NW = NegP;
  268.         Wp = W - Work;
  269. #ifdef PAT_SLICE ------------------------------v
  270.         MWork[Wp] = MarkP;
  271. #endif ----------------------------------------^
  272.     if (Wp >= WORKSIZE) exit(33);
  273.     }
  274. }
  275.  
  276. #ifdef PAT_SLICE -----------------------------------------------v
  277. Putslice(P, S) int P, S;
  278. {
  279.     int i;
  280.     UBYTE *MW;
  281. #ifdef DEBUG ======================================V
  282.     if (DEBmode)
  283.        printf("Slice ^%d=%d  ", P, S);
  284. #endif ============================================^
  285.     for (i = 0, MW = (UBYTE *)MWork;
  286.          i<MAXMARK && *MW && (P != *MW); i++, MW++)
  287.         ; /* loop */
  288.     if (i==MAXMARK) return;
  289.     *MW = P;
  290.     MarkP.mk[i] = S;
  291. }
  292.  
  293.  
  294.  
  295. RetSlice() {
  296.     int i;
  297.     UBYTE *mwp = MWork->mk,
  298.           *mpp = MarkP.mk,
  299.           lastcut = 0;
  300.     if (!Svect) return; /* ignore if NULL */
  301. #ifdef DEBUG ======================================V
  302.     if (DEBmode)
  303.         printf("RetSlice.. Svect = %d\n",Svect);
  304. #endif ============================================^
  305.     for (i=MAXMARK; i && *mwp && cutlimit; i--, cutlimit--)
  306.         if(*mpp >= lastcut) { /* avoid supefluous cuts */
  307.             *Svect++ = *mwp++;
  308.             lastcut = *Svect++ = *mpp++;
  309.         }
  310.     *Svect = 0;
  311. }
  312. #endif ---------------------------------------------------------^
  313.  
  314.  
  315. /*********************************************************************/
  316.  
  317.  
  318. /*** The Compiler: ***/
  319.  
  320. int retcode, grouplevel, slicecount;
  321.  
  322. Rch() {
  323.     if (PatP >= Patlen)
  324.         Ch = Endstreamch;
  325.     else {
  326.         Ch = Pat[++PatP];
  327.     }
  328. }
  329.  
  330. Nextitem() {
  331.     if (Ch == PAT_QUOTE) Rch();
  332.     Rch();
  333. }
  334.  
  335. int Prim(NegMark) int NegMark;
  336. {
  337.     int A = PatP;
  338.     UBYTE Op = Ch;
  339.     if (NegMark) retcode |= CODE_NEG;
  340.     Nextitem();
  341.     switch(Op) {
  342.      case PAT_ANY:
  343.                 retcode |= CODE_ANY;
  344.                 return A;
  345.      case PAT_ALL:
  346.                 retcode |= CODE_ALL;
  347.                 return A;
  348.      case Endstreamch:
  349.      case PAT_RGROUP:
  350.      case PAT_ALT:
  351.                 Errflag = TRUE;
  352.      default:   return A;
  353.      case PAT_REP:
  354.                 Setexits(Prim(NegMark), A);
  355.                 retcode |= CODE_REP;
  356.                 return A;
  357.      case PAT_LGROUP:
  358.                 grouplevel++;
  359.                 A = Exp(A, (NegMark ? 1 : FALSE));
  360.                 grouplevel--;
  361.                 if (Ch != PAT_RGROUP) Errflag = TRUE;
  362.                 retcode |= CODE_GROUP;
  363.                 Nextitem();
  364.                 return A;
  365.      case PAT_NEG:
  366.                 if (NegMark) Errflag = TRUE;
  367.                 NegMark = 1;
  368.                 retcode |= CODE_NEG;
  369.                 Join(A, Prim(NegMark));
  370.                 NegMark = FALSE;
  371.                 return A;
  372. #ifdef PAT_SLICE ------------------------------v
  373.      case PAT_SLICE:
  374.                 retcode |= (++slicecount > MAXMARK || grouplevel ) ?
  375.                     CODE_OVERSLICE : CODE_SLICE;
  376.                 return A;
  377. #endif ----------------------------------------^
  378.     }
  379. }
  380.  
  381. int Exp(AltP, NegMark) int AltP, NegMark;
  382. {
  383.     int Exits = 0, A;
  384.     do {
  385.         A = Prim(NegMark);
  386.         if (Ch == PAT_ALT || Ch == PAT_RGROUP || Ch == Endstreamch)
  387.             {   Exits = Join(Exits, A);
  388.                 if (Ch != PAT_ALT)
  389.                     return Exits;
  390.                 retcode |= CODE_ALT;
  391.                 Aux[AltP] = PatP;
  392.                 AltP = PatP;
  393.                 Nextitem();
  394.                 if (Ch == PAT_ALT) { /* negation convention */
  395.                     if (NegMark == 1) Errflag = TRUE;
  396.                     NegMark = -1; /* not an error to meet oneself */
  397.                     retcode |= CODE_NEG;
  398.                     Nextitem();
  399.                 }
  400.                 else NegMark = FALSE;
  401.             }
  402.         else Setexits(A, PatP);
  403.     } while (TRUE);
  404. }
  405.  
  406.  
  407. Setexits(List, Val) int List, Val;
  408. {
  409.     int A;
  410.     while (List != 0) {
  411.         A = Aux[List];
  412.         Aux[List] = Val;
  413.         List = A;
  414.     }
  415. }
  416.  
  417. int Join(A, B) int A, B;
  418. {
  419.     int T = A;
  420.     if (A == 0) return B;
  421.     while (Aux[A] != 0) A = Aux[A];
  422.     Aux[A] = B;
  423.     return T;
  424. }
  425.  
  426. int CmplPat(Pattern, CmplPattern) char *Pattern, *CmplPattern;
  427. {
  428.     int I;
  429.     Pat = Pattern - 1;
  430.     Aux = CmplPattern;
  431.     Patlen = strlen(Pattern); /** this is no longer a BSTR!!! **/
  432.     PatP = 0;
  433.     Errflag = FALSE;
  434.     retcode = CODE_OK;
  435.     grouplevel = slicecount = 0;
  436.     for (I = 0; I <= Patlen; I++) Aux[I] = 0;
  437.     Rch();
  438.     Setexits(Exp(0,FALSE), 0);
  439.     return Errflag ? 0 : retcode;
  440. }
  441.  
  442.