next up previous
Nächste Seite: Re: Pattern Matching Aufwärts: Graphen, Schaltwerke und Zahlen Vorherige Seite: Re: Pattern Matching

Re: Pattern Matching

Wenn sie den Code so nehmen, dann tut er! Geil, so tut er. Sie müssen am Besten in init() die Zeichen durch SHARP ersetzen sonst geht es nicht, weil, wenn die Kontrollzustände erzeugt werden, wird ihnen nicht expliziet # zu gewiesen. Dann geht es nicht, wenn man es so lässt, ansonsten schon 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define X   1024
#define END -1
#define CONTROLSTATE    '#'

int state1 [X];
int state2 [X];
int v[X];
char text [] = "bcabcbcbca";
//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))";
//ar expr [] = "[[[aq,f],b],[c,d]]";
//char expr [] = "[a,[b,c]]";
/*
success
(0, (1, 2))
(1, (a, 6, 6))
(2, (3, 4))
(3, (b, 5, 5))
(4, (c, 5, 5))
(5, (6, 6))
(6, (0, 0))
(7, (0, 0))
*/

//char expr [] = "[a,b]";
/*
success
(0, (1, 2))
(1, (a, 3, 3))
(2, (b, 3, 3))
(3, (0, 0))
(4, (0, 0))

*/
//char expr [] = "[a,[b,c]]";
/*
success
(0, (1, 2))
(1, (a, 6, 6))
(2, (3, 4))
(3, (b, 5, 5))
(4, (c, 5, 5))
(5, (6, 6))
(6, (0, 0))
(7, (0, 0))
*/
//char expr [] = "[[a,b],c]";
/*
success
(0, (1, 5))
(1, (2, 3))
(2, (a, 4, 4))
(3, (b, 4, 4))
(4, (6, 6))
(5, (c, 6, 6))
(6, (0, 0))
(7, (0, 0))
*/
//char expr [] = "[[a,b],[c,d]]";
/*
success
(0, (1, 5))
(1, (2, 3))
(2, (a, 4, 4))
(3, (b, 4, 4))
(4, (9, 9))
(5, (6, 7))
(6, (c, 8, 8))
(7, (d, 8, 8))
(8, (9, 9))
(9, (0, 0))
(10, (0, 0))
*/
//[a,b,c,d]
//char expr [] = "[a,[b,[c,d]]]";
/*
success
(0, (1, 2))
(1, (a, 9, 9))
(2, (3, 4))
(3, (b, 8, 8))
(4, (5, 6))
(5, (c, 7, 7))
(6, (d, 7, 7))
(7, (8, 8))
(8, (9, 9))
(9, (0, 0))
(10, (0, 0))
*/
//char expr [] = "[a,[[b,c],d]]";
/*
success
(0, (1, 2))
(1, (a, 9, 9))
(2, (3, 7))
(3, (4, 5))
(4, (b, 6, 6))
(5, (c, 6, 6))
(6, (8, 8))
(7, (d, 8, 8))
(8, (9, 9))
(9, (0, 0))
(10, (0, 0))

*/
//char expr [] = "[[[a,b],c],d]";
/*
success
(0, (1, 8))
(1, (2, 6))
(2, (3, 4))
(3, (a, 5, 5))
(4, (b, 5, 5))
(5, (7, 7))
(6, (c, 7, 7))
(7, (9, 9))
(8, (d, 9, 9))
(9, (0, 0))
(10, (0, 0))
*/

//char expr [] = "[[a,b],[c,[d,e]]]";
/*
success
(0, (1, 5))
(1, (2, 3))
(2, (a, 4, 4))
(3, (b, 4, 4))
(4, (12, 12))
(5, (6, 7))
(6, (c, 11, 11))
(7, (8, 9))
(8, (d, 10, 10))
(9, (e, 10, 10))
(10, (11, 11))
(11, (12, 12))
(12, (0, 0))
(13, (0, 0))
*/
//char expr [] = "[[a,b],[[c,d],e]]";
/*
success
(0, (1, 5))
(1, (2, 3))
(2, (a, 4, 4))
(3, (b, 4, 4))
(4, (12, 12))
(5, (6, 10))
(6, (7, 8))
(7, (c, 9, 9))
(8, (d, 9, 9))
(9, (11, 11))
(10, (e, 11, 11))
(11, (12, 12))
(12, (0, 0))
(13, (0, 0))
*/
//char expr [] = "[[a,b],[c,[d,e]]]";
/*
success
(0, (1, 5))
(1, (2, 3))
(2, (a, 4, 4))
(3, (b, 4, 4))
(4, (12, 12))
(5, (6, 7))
(6, (c, 11, 11))
(7, (8, 9))
(8, (d, 10, 10))
(9, (e, 10, 10))
(10, (11, 11))
(11, (12, 12))
(12, (0, 0))
(13, (0, 0))
*/
//char expr [] = "[[[a,b],c],[d,e]]";
/*
success
(0, (1, 8))
(1, (2, 6))
(2, (3, 4))
(3, (a, 5, 5))
(4, (b, 5, 5))
(5, (7, 7))
(6, (c, 7, 7))
(7, (12, 12))
(8, (9, 10))
(9, (d, 11, 11))
(10, (e, 11, 11))
(11, (12, 12))
(12, (0, 0))
(13, (0, 0))
*/
//char expr [] = "[[[*(aqqq),bqqq],cqq],[dqqq,eqqq]]";
/*
success
(0, (1, 16))
(1, (2, 12))
(2, (3, 7))
(3, (a, 4, 4))
(4, (q, 5, 5))
(5, (q, 6, 6))
(6, (q, 11, 11))
(7, (b, 8, 8))
(8, (q, 9, 9))
(9, (q, 10, 10))
(10, (q, 11, 11))
(11, (15, 15))
(12, (c, 13, 13))
(13, (q, 14, 14))
(14, (q, 15, 15))
(15, (26, 26))
(16, (17, 21))
(17, (d, 18, 18))
(18, (q, 19, 19))
(19, (q, 20, 20))
(20, (q, 25, 25))
(21, (e, 22, 22))
(22, (q, 23, 23))
(23, (q, 24, 24))
(24, (q, 25, 25))
(25, (26, 26))
(26, (0, 0))
(27, (0, 0))
*/
//char expr [] = "abcdefgh";
//char expr [] = "abcd";
int i = 0;
int x = 0;

char expr [] = "*(*(bc)a)";
//char expr [] = "*(*(ab)c)ab*(ab)";
//char expr [] = "*(ab)";


int initstates () {
    int l;

    for (l = 0;  l < X;  l++) {
        v [l] = '#';
        state1 [l] = state2 [l] = 0;
    }

}


int gettoken () {
    if (i >= (strlen (expr)))
      return -1;
    printf ("-------------------------------n");
    printf ("%cn", expr [i]);
    printf ("-------------------------------n");
    return expr [i++];
}
void tokenback () {
    i--;
}

struct fracture {
    int begin;
    int mid;
    int end;
    int tail;
    int d1_begin;
    int d2_begin;
    int d3_begin;
    int d1_end;
    int d2_end;
    int d3_end;
    int exists;
};

struct fracture stream ();
struct fracture followed ();
struct fracture compound ();
struct fracture or_operator ();
struct fracture repeat_operator ();
struct fracture fracinit ();

void debug (char fname [], struct fracture ret) {
  int k;
  printf ("=====================================n");
  printf ("function name:tt%sn", fname);
  printf ("y.begin:tt %3in", ret.begin);
  printf ("y.end:tt %3in", ret.end);
  printf ("y.d1_begin:tt %3in", ret.d1_begin);
  printf ("y.d1_end:tt %3in", ret.d1_end);
  printf ("y.d2_begin:tt %3in", ret.d2_begin);
  printf ("y.d2_end:tt %3in", ret.d2_end);
  printf ("y.exists:tt %2in", ret.exists);
  printf ("x:ttt (%3i, (%i, %i))n", x, state1 [x], state2 [x]);
  printf ("=====================================n");
  for (k = 0;  k <= x;  k++) {
      if ((v[k] >= 'a') \&amp;\&amp; (v[k] <= 'z'))
        printf ("(%i, (%c, %i, %i))n", k, v[k], state1 [k], state2 [k]);
      else
        printf ("(%i, (%i, %i))n", k, state1 [k], state2 [k]);
  }
  printf ("=====================================n");
  //getchar ();
}

struct fracture fracinit () {
  struct fracture x;
  x.begin = 0;
  x.mid = 0;
  x.end = 0;
  x.tail = 0;
  x.d1_begin = 0;
  x.d1_end = 0;
  x.d2_begin = 0;
  x.d2_end = 0;
  x.d3_begin = 0;
  x.d3_end = 0;
  x.exists = 0;
  return x;
}

struct fracture or_operator () {
    int ch;
    struct fracture x1 = fracinit ();
    struct fracture x2 = fracinit ();
    struct fracture x3 = fracinit ();
    struct fracture y = fracinit ();

    if ((ch = gettoken ()) == '[') {
        y.begin = x;
        x++;
        x1 = or_operator ();

        if ((ch = gettoken ()) != ',') {
            fprintf (stderr, "Komma vergessen %c", ch);
            exit (1);
        }
        y.d1_begin = x1.begin;
        y.d1_end = x1.end;

        x2 = or_operator ();
        y.d2_begin = x2.begin;
        y.d2_end = x2.end;
        if ((ch = gettoken ()) != ']') {
            fprintf (stderr, "Klammer vergessen ]");
            exit (1);
        }
        y.end = x;
        x++;


        state1 [y.begin] = x1.begin;
        state2 [y.begin] = x2.begin;
        state1 [x1.end] = y.end;
        state2 [x1.end] = y.end;
        state1 [x2.end] = y.end;
        state2 [x2.end] = y.end;
        x3 = or_operator ();
        if (x3.begin != 0) {
          state1 [y.end] = x+1;
          state2 [y.end] = x+1;
          x++;
          y.end = x;
          y.tail = x3.begin;
          state1 [y.end] = y.tail;
          state2 [y.end] = y.tail;
        }
        debug ("or_operator", y);
        return y;
    }
    else if (ch == -1)
      return fracinit ();
    else {
        tokenback ();
        y = repeat_operator ();
        if (y.exists != 0)
          or_operator ();
        debug ("or_operator", y);
        return y;
    }
}


struct fracture repeat_operator () {
    int ch;
    struct fracture y = fracinit ();
    struct fracture x1 = fracinit ();

    if ((ch = gettoken ()) == '*') {
        x1 = compound ();
        y.begin = x1.begin;
        y.mid = x;
        x++;
        y.end = x;
        x++;
        state1 [x1.end] = y.mid;
        state2 [x1.end] = y.mid;

        state1 [y.end] = y.end+1;
        state2 [y.end] = y.end+1;
        state1 [x1.end] = x1.end+1;
        state2 [x1.end] = x1.end+1;
        state1 [y.mid] = x1.begin;
        state2 [y.mid] = y.end;
        // Den zweiten Zustand der muss auf das naechste zeigen
        stream ();
        debug ("repeat_operator", y);
        y.exists = 1;
        return y;
    }
    else if (ch == -1)
      return fracinit ();
    else {
        tokenback ();
        y = stream ();
        debug ("repeat_operator", y);
        return y;
    }
}
struct fracture stream () {
    struct fracture x1 = fracinit ();
    struct fracture x2 = fracinit ();
    struct fracture x3 = fracinit ();
    struct fracture y = fracinit ();

    x1 = compound ();
    x2 = followed ();

    //state1 [x1.end] = x2.begin;

    //stream ();
    if (x1.exists || x2.exists)  {
      or_operator ();/*
      x3 = or_operator ();
      if (x2.exists) {
        state1 [x2.end] = x3.begin;
      }
      else {
        state1 [x1.end] = x3.begin;
      }*/
    }

    debug ("stream", y);
    y = x2;
    return y;
}

struct fracture followed () {
    struct fracture x1 = fracinit ();
    struct fracture y = fracinit ();

    int ch = gettoken ();
    printf ("%cn", ch);


    if ((ch >= 'a') \&amp;\&amp; (ch <= 'z')) {
        v [x] = ch;
        y.begin = x;
        x = x+1;

        x1 = or_operator ();
        if (x1.end == 0) {
          y.end = y.begin;
          y.exists = 1;
        }
        else {
          y.d1_begin = x1.begin;
          y.end = x1.end;
          y.exists = 1;
        }
        state1 [y.begin] = x1.begin;
        state2 [y.begin] = x1.begin;
        state1 [y.end] = y.end+1;
        state2 [y.end] = y.end+1;

        debug ("followed", y);
        return y;
    }
    else if (ch == -1)
      return fracinit ();
    else {
        y.exists = 0;
        tokenback ();
        y = fracinit ();
        debug ("followed", y);
        return y;
    }
}

struct fracture compound () {
    struct fracture x1 = fracinit ();
    int ch;
    if (gettoken () == '(') {
        x1 = or_operator ();
        if ((ch = gettoken ()) != ')') {
            fprintf (stderr, "fehler klammer vergessen %c %in", expr [i], i);
            exit (1);
        }
        x1.exists = 1;

        debug ("compound", x1);
        return x1;
    }
    else if (ch == -1)
      return fracinit ();
    else {
        x1.exists = 0;
        tokenback ();
        debug ("compound---", x1);
        return x1;
    }
}



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

    if (strlen (text) <= xtext)
      return 1;
    if (v [xreal] == CONTROLSTATE) {
      if (state1 [xreal] == state2 [xreal])
        exists = automat (state1 [xreal], xtext);
      else
        exists = automat (state1 [xreal], xtext) || automat (state2 [xreal], xtext);
    }
    else if ((v [xreal] >= 'a') \&amp;\&amp; (v [xreal] <= 'z'))  {
      if (v [xreal] == text [xtext]) {

        exists = 1;
      }
      if (state1 [xreal] == state2 [xreal])
        exists \&amp;= automat (state1 [xreal], xtext+1);
      else
        exists \&amp;= (automat (state1 [xreal], xtext+1) || automat (state2 [xreal], xtext+1));
    }
    return exists;
}



int main (void) {
    int k, l;

    initstates ();
    or_operator ();

    printf ("successn");

    for (k = 0;  k <= x;  k++) {
      if ((v[k] >= 'a') \&amp;\&amp; (v[k] <= 'z'))
        printf ("(%i, (%c, %i, %i))n", k, v[k], state1 [k], state2 [k]);
      else
        printf ("(%i, (%i, %i))n", k, state1 [k], state2 [k]);
    }

    printf ("%in", automat(0,0));
}