Re: Pattern Matching

#include <string.h>
#include <stdlib.h>
#include <stdio.h>


#define M       128
#define K       128
int     N;
int     j;
int     l;

int expression ();
int term ();
int factor ();
void ststate (int, char, int, int);
void dequeinit ();

char p [] = "B*(AC)";
char a [] = "BBBAC";

char ch[M];
int next1 [M];
int next2 [M];
int state;

int queptr;
int stackptr;
int deque [K];

int l = 0;

int scan () {

  if (a [l] == ' ')
    return -1;

  return a [l++];
}

void dequeinit () {
    queptr = 0;
    stackptr = 0;
}

void push (int v) {
    deque [stackptr] = v;
    stackptr++;
}

int pop () {
    if (stackptr > 0)
    stackptr--;
    return deque [stackptr];
}

void put (int v) {
    deque [stackptr] = v;
    stackptr++;
}

int get () {
    int v;

    v = deque [queptr];
    queptr++;
    return v;
}

int dequeempty () {
    if (queptr >= stackptr)
        return 1;
    else
        return 0;
}


int letter (char v) {
    return((v >= 'A') \&amp;\&amp; (v <= 'Z'));
}

void error () {
    printf ("Fehler");
}

void ststate (int st, char c, int n1, int n2) {
    ch [st] = c;
    next1 [st] = n1;
    next2 [st] = n2;
}

int expression () {
    int t1, t2, r;

    t1 = term ();
    r = t1;

    if (p [j] == '+') {
        j++;
        state++;
        t2 = state;
        r = t2;
        state++;
        ststate (t2, ' ', expression(), t1);
        ststate (t2-1, ' ', state, state);
    }
    return r;
}

int term () {
    int t, r;
    r = factor ();

    if (( p [j] == '(') || letter (p [j]))
        t = term ();
    return r;
}

int factor () {
    int t1, t2, r;

    t1 = state;

    if (p [j] == '(') {
        j++;
        t2 = expression ();
        if (p [j] == ')')
            j++;
        else
            error ();
    }
    else if (letter (p [j])) {
        ststate (state, p[j], state+1, state+1);
        t2 = state;
        j++;
        state++;
    }
    else
        error ();
    if (p [j] != '*')
        r = t2;
    else
    {
        ststate (state,  ' ', state+1, t2);
        r = state;
        next1 [t1-1] = state;
        j++;
        state++;
    }
    return r;
}

int match (char *a) {
    int n1, n2;
    int c;

    int j = 0;
    N = strlen (a), state = next1 [0];

    dequeinit ();
    put (scan ());

    while ((c = scan ()) != -1) {
        putchar (c);
        if (state == c) {
            j++;
            put (c);
        }
        else if (ch [state] == a [j])
            put (next1 [state]);
        else if (ch [state] == ' ') {
            n1 = next1 [state];
            n2 = next2 [state];
            push (n1);
            if (n1 != n2)
                push (n2);
        }
        if (dequeempty () || j == N)
            return 0;
        state = pop ();
    }
    return j;
}

void printstates () {
    int i;
    for (i = 0;  i < state;  i++) {
        printf ("%i %c %i %in", i, ch [i], next1 [i], next2 [i]);
    }
}

int matchall (char *a) {
    j = 0;
    state = 1;
    next1 [0] = expression ();
    ststate (0, ' ', next1 [0], next2 [0]);
    ststate (state, ' ', 0, 0);
    printstates ();
    getchar ();
    while (*a != ' ')
        printf ("%d ", match (a++));
    printf ("n");
}

int main (void) {
    matchall (a);
}