Re: Pattern Matching

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

#define X   1024
#define END -1

char statechar [X];
int x;

int initstates () {
    int l;

    for (l = 0;  l < X;  l++) {
        statechar [l] = ' ';
    }

}

int jx = 0;

char text [] = "de";

//char expr [] = "abc*de[fasd,asddsr]qdsda*ghijk";
//char expr [] = "[*([[[([a,[[[p,q*],ca],[d,*(ead)]]]f*(mmm(nnn)mm)),a],asd],semdu]),*poller]";
//char expr [] = "[*([[[([a,[[[p,*(q)],ca],[d,*(ead)]]]f*(mmm(nnn)mm)),a],asd],semdu]),*poller]";
//char expr [] = "*(mmm(nnn)mm)";
//char expr [] = "a(b*(*(cd)aaa)(efg))";
char expr [] = "[[a,b],[c,d]]e";
//char expr [] = "abcd";
int i = 0;

char gettoken () {
    return expr [i++];
}
void tokenback () {
    i--;
}

/*
aaaa
aaaaaa
aaaaaaa
aaaaaaaa()
*/

int stream ();
int followed ();
int compound ();
int or_operator ();
int repeat_operator ();

#define     IF_BEGIN            0
#define     IF_ELSE             1
#define     IF_END              2
#define     REPEAT_BEGIN        3
#define     ROUND_BRACKET_OPEN  4
#define     ROUND_BRACKET_CLOSE 5

int or_operator () {
    int ch;
    if ((ch = gettoken ()) == '[') {
        statechar [x] = IF_BEGIN;
        x++;
        or_operator ();
        if (gettoken () != ',') {
            fprintf (stderr, "Komma vergessen");
            exit (1);
        }
        statechar [x] = IF_ELSE;
        x++;
        or_operator ();
        if ((ch = gettoken ()) != ']') {
            fprintf (stderr, "Klammer vergessen ]");
            exit (1);
        }
        statechar [x] = IF_END;
        x++;
        repeat_operator ();
    }
    else {
        tokenback ();
        repeat_operator ();
    }
}


int repeat_operator () {
    if (gettoken () == '*') {
        statechar [x] = REPEAT_BEGIN;
        x++;
        stream ();
    }
    else {
        tokenback ();
        stream ();
    }
}

int stream () {
    int r = 0;
    r = compound ();
    r |= followed ();
    if (r) {
        or_operator();
    }
}

int followed () {
    int ch = gettoken ();
    int st, xtmp;
    if ((ch >= 'a') \&amp;\&amp; (ch <= 'z')) {
        statechar [x] = ch;
        x = x+1;
        or_operator ();
        return 1;
    }
    else {
        tokenback ();
        return 0;
    }
}

int compound () {
    int ch;
    if (gettoken () == '(') {
        statechar [x] = ROUND_BRACKET_OPEN;
        x++;
        or_operator ();
        if ((ch = gettoken ()) != ')') {
            fprintf (stderr, "fehler klammer vergessen %c %in", expr [i], i);
            exit (1);
        }
        statechar [x] = ROUND_BRACKET_CLOSE;
        x++;
        return 1;
    }
    else {
        tokenback ();
        return 0;
    }
}

int realstates1 [1024];
int realstates2 [1024];
int realstateschar [1024];


#define STACKLASTWASLABEL           0
#define STACKXREALLOOPLABEL         1
#define STACKXREALIFBEGIN           2
#define STACKXREALELSEBEGIN         3

#define REALEND                 -1

int stacks [32][1024];
int stacksp [32];

void push (int stackid, int state) {
  stacks [stackid][stacksp[stackid]++] = state;
}

int pop (int stackid) {
  stacksp [stackid]--;
  return stacks [stackid][stacksp[stackid]];
}

int emptystack (int stackid) {
    return (stacksp[stackid] == 0);
}

#define CONTROLSTATE    '#'

void automatgen ( ) {
    int xi = 0;
    int xreal = 0;
    int itwas = 0;
    int tmp;

    for (xi = 0; xi <= x;  ) {
        if ((statechar [xi] >= 'a') \&amp;\&amp; (statechar [xi] <= 'z')) {
            realstates1 [xreal] = xreal+1;
            realstates2 [xreal] = xreal+1;
            realstateschar [xreal] = statechar [xi];
            xreal++;
        }
        else if (statechar [xi] == ROUND_BRACKET_OPEN) {
            push (STACKLASTWASLABEL, ROUND_BRACKET_OPEN);
        }
        else if (statechar [xi] == REPEAT_BEGIN) {
            xi++;
            if (statechar [xi] == ROUND_BRACKET_OPEN) {
                push (STACKXREALLOOPLABEL, xreal);
                push (STACKLASTWASLABEL, REPEAT_BEGIN);
            }
            else if ((statechar [xi] >= 'a') \&amp;\&amp; (statechar [xi] <= 'z')) {
                realstates1 [xreal] = xreal+1;
                realstates2 [xreal] = xreal+1;
                realstateschar [xreal] = statechar [xi];
                xreal++;
                realstates1 [xreal] = xreal+1;
                realstates2 [xreal] = xreal-1;
                realstateschar [xreal] = CONTROLSTATE;
                xreal++;
            }
        }
        else if (statechar [xi] == ROUND_BRACKET_CLOSE) {
            if ((itwas = pop (STACKLASTWASLABEL)) == REPEAT_BEGIN) {
                realstateschar [xreal] = CONTROLSTATE;
                realstates1 [xreal] = pop (STACKXREALLOOPLABEL);
                realstates2 [xreal] = xreal+1;
                xreal++;
            }
            else if (itwas = ROUND_BRACKET_OPEN);
        }
        else if (statechar [xi] == IF_BEGIN) {
            realstateschar [xreal] = CONTROLSTATE;
            realstates1 [xreal] = xreal+1;
            push (STACKXREALIFBEGIN, xreal);
            xreal++;
        }
        else if (statechar [xi] == IF_ELSE) {
            realstates2 [tmp = pop (STACKXREALIFBEGIN)] = xreal;
            push (STACKXREALELSEBEGIN, xreal-1);
        }
        else if (statechar [xi] == IF_END) {
            realstateschar [xreal] = CONTROLSTATE;
            realstates1 [xreal] = xreal+1;
            realstates2 [xreal] = xreal+1;
            realstates2 [tmp = pop (STACKXREALELSEBEGIN)] = xreal;
            realstates1 [tmp] = xreal;
            xreal++;
        }
        xi++;
    }
    realstateschar [xreal] = '\$';
    realstates1 [xreal] = REALEND;
    realstates2 [xreal] = REALEND;


    int k;
    for (k = 0;  k <= xreal;  k++) {
        printf ("%i, ", k);
        if ((realstateschar [k] >= 'a') \&amp;\&amp; (realstateschar [k] <= 'z'))
          printf ("%c, ", realstateschar [k]);
        printf ("(%c, ", realstateschar [k]);
        printf ("%i, ", realstates1 [k]);
        printf ("%i)n", realstates2 [k]);
    }

}



int automat (int xreal, int xtext) {
    int flag = 0;

    if (strlen (text) <= xtext)
      return 1;
    if (realstateschar [xreal] == CONTROLSTATE) {
      if (realstates1 [xreal] == realstates2 [xreal])
        flag = automat (realstates1 [xreal], xtext);
      else
        flag = automat (realstates1 [xreal], xtext) || automat (realstates2 [xreal], xtext);
    }
    else if ((realstateschar [xreal] >= 'a') \&amp;\&amp; (realstateschar [xreal] <= 'z'))  {
      if (realstateschar [xreal] == text [xtext])
        flag = 1;
      if (realstates1 [xreal] == realstates2 [xreal])
        flag \&amp;= automat (realstates1 [xreal], xtext+1);
      else
        flag \&amp;= (automat (realstates1 [xreal], xtext+1) || automat (realstates2 [xreal], xtext+1));
    }
    return flag;
}



int main (void) {
    int k, l;
    initstates ();
    or_operator (0);

    for (l = 0;  l <= x;  l++) {
        if (statechar [l] == ROUND_BRACKET_OPEN)
            printf ("(ROUND_BRACKET_OPEN, %2i)n", l);
        else if (statechar [l] == ROUND_BRACKET_CLOSE)
            printf ("(ROUND_BRACKET_CLOSE, %2i)n", l);
        else if (statechar [l] == REPEAT_BEGIN)
            printf ("(REPEAT_BEGIN, %2i)n", l);
        else
            printf ("(%2c %2i)n", statechar [l], l);
    }
    automatgen ();
    printf ("%in", automat (0, 0));
}