home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The CDPD Public Domain Collection for CDTV 1
/
CDPD_Vol1.bin
/
pd
/
101-125
/
102
/
match_stuff
/
match.c_bcpl
< prev
next >
Wrap
Text File
|
1992-06-23
|
4KB
|
169 lines
/* Martin Richards' TRIPOS Pattern Matching algorithm in C */
/* This is a direct transliteration of the BCPL code 87:7:7 */
/*
* Reference:
*
* Martin Richards,
* "A Compact Function for Regular Expression
* Pattern Matching"
* [Software--Practice and Experience, Vol 9, 527-534 (1979)]
*/
#include <exec/types.h>
/*** Static Variables: ***/
#define Endstreamch 0xFF
UBYTE *Work = NULL; int Wp = 0, Succflag = FALSE;
char *Pat = 0; UBYTE *Aux = 0;
UBYTE Ch = 0; int PatP = 0, Patlen = 0,
Errflag = FALSE;
/*** The Interpreter: ***/
Match(Pat, Aux, Str) UBYTE *Aux; char *Pat, *Str; {/*$(1*/
UBYTE W[128];
int S = 0;
/* declare local BCPL vars */
int N, I; UBYTE P, Q; char K;
/***********************/
Work = W;
Wp = 0;
Succflag = FALSE;
Put(1);
if (!(Aux[0]==0)) Put(Aux[0]);
do {/*$(2*/
for (N=1; N <= Wp; N++) { /* first complete the closure: */
P=Work[N];
K = Pat[P]; Q = Aux[P];
switch(K)
{
case '#': Put(P+1);
case '%': Put(Q);
default: break;
case '(':
case '|': Put(P+1);
if (Q != 0) Put(Q);
}
}
if (S >= Str[0]) return Succflag;
if (Wp == 0) return FALSE;
Ch = Str[++S];
/* now deal with match items: */
N = Wp;
Wp = 0; Succflag = FALSE;
for (I = 1; I <= N; I++) {
P = Work[I];
K = Pat[P];
switch(K) {
case '#':
case '|':
case '%':
case '(':
break; /* BCPL was 'loop' */
case '\'': K = Pat[P+1];
default: if (Ch != K) break; /* 'loop' */
case '?': /* successful match */
Put(Aux[P]);
break; /* 'loop' */
}
}
}/*$)2*/ while (TRUE);
}/*$)1*/ /*** end Match ***/
Put(N) int N; {
int I; /* not needed by BCPL */
if (N == 0)
Succflag = TRUE;
else {
for (I = 1; I <= Wp; I++) if (Work[I] == N) return;
Work[++Wp] = N;
}
}
/*** The Compiler: ***/
Rch() {
if (PatP >= Patlen)
Ch = Endstreamch;
else {
Ch = Pat[++PatP];
}
}
Nextitem() {
if (Ch == '\'') Rch();
Rch();
}
int Prim()
{ int A = PatP; UBYTE Op = Ch;
Nextitem();
switch(Op) {
case Endstreamch:
case ')':
case '|': Errflag = TRUE;
default: return A;
case '#': Setexits(Prim(), A);
return A;
case '(': A = Exp(A);
if (Ch != ')') Errflag = TRUE;
Nextitem();
return A;
}
}
int Exp(AltP) int AltP;
{/*$(1*/
int Exits = 0, A;
do/*$(2*/{ A = Prim();
if (Ch == '|' || Ch == ')' || Ch == Endstreamch)
{ Exits = Join(Exits, A);
if (Ch != '|') return Exits;
Aux[AltP] = PatP;
AltP = PatP;
Nextitem();
}
else Setexits(A, PatP);
}/*$)2*/ while (TRUE);
}/*$)1*/
Setexits(List, Val) int List, Val; {
int A;
while (List != 0) {
A = Aux[List];
Aux[List] = Val;
List = A;
}
}
int Join(A, B) int A, B;
{
int T = A;
if (A == 0) return B;
while (Aux[A] != 0) A = Aux[A];
Aux[A] = B;
return T;
}
int CmplPat(Pattern, CmplPattern) char *Pattern, *CmplPattern;
{
int I; /* BCPL local */
Pat = Pattern; Aux = CmplPattern;
PatP = 0; Patlen = Pat[0]; /** this is a BSTR!!! **/
Errflag = FALSE;
for (I = 0; I <= Patlen; I++) Aux[I] = 0;
Rch();
Setexits(Exp(0), 0);
return !Errflag;
}