#include <stdio.h> #include <stdlib.h> #include <string.h> #define X 1024 #define MAX_LINES 2048 #define END -1 #define REALEND -2 #define CONTROLSTATE -3 #define ASCIIMIN 0 #define ASCIIMAX 255 #define LEX_ROUND_BRACKET_OPEN -4 #define LEX_ROUND_BRACKET_CLOSE -5 #define LEX_SQUARE_BRACKET_OPEN -6 #define LEX_SQUARE_BRACKET_CLOSE -7 #define LEX_COMMA -8 #define LEX_STAR -9 #define LEX_DOT -10 #define LEX_END -11 #define LEX_EMPTY -12 #define LEX_A 'a' #define LEX_B 'b' #define LEX_F 'f' #define LEX_N 'n' #define LEX_R 'r' #define LEX_T 't' #define LEX_V 'v' #define C_STRING_END 0 #define C_ROUND_BRACKET_OPEN '(' #define C_ROUND_BRACKET_CLOSE ')' #define C_SQUARE_BRACKET_OPEN '[' #define C_SQUARE_BRACKET_CLOSE ']' #define C_STAR '*' #define C_COMMA ',' #define C_BACKSLASH '\' #define C_DOT '.' #define C_A 'a' #define C_B 'b' #define C_F 'f' #define C_N 'n' #define C_R 'r' #define C_T 't' #define C_V 'v' #define BUF_INPUT_SIZE 2048 #define ERR_NO_ERR_NORMAL 0 #define ERR_USAGE 1 #define ERR_PARSE 2 #define ERR_SYS 3 #define ERR_NO_ERROR_USER 4 #define ERR_PARSE_FORGOT_COMMA_IN_OR_INDEX 0 #define ERR_PARSE_FORGOT_SQUARE_BRACKET_CLOSE_IN_OR_INDEX 1 #define ERR_PARSE_FORGOT_ROUND_BRACKET_CLOSE_INDEX 2 #define ERR_PROG_USAGE_WRONG_ARGS_INDEX 3 #define ERR_SYS_NOT_ENOUGH_MEMORY_INDEX 4 #define ERR_PARSE_FORGOT_COMMA_IN_OR_MSG "%s Sie haben das Komma bei Alternative vergessenn" #define ERR_PARSE_FORGOT_SQUARE_BRACKET_CLOSE_IN_OR_MSG "%s Sie haben vergessen bei der Alternative die Klammer zu schliessenn" #define ERR_PARSE_FORGOT_ROUND_BRACKET_CLOSE_MSG "%s fehler klammer vergessen %c %in" #define ERR_PROG_USAGE_WRONG_ARGS_MSG "%s Sie haben die falsche Anzahl an Parametern eingegebenn" #define ERR_SYS_NOT_ENOUGH_MEMORY_MSG "Nicht genug Arbeitsspeicher vorhanden" #define ERR_TOP_NO_ERROR_NORMAL_MSG "Das Programm l"auft korrekt" #define ERR_TOP_USAGE_ERROR_MSG "Fehler bei der Verwendung des Programms: " #define ERR_TOP_PARSER_ERROR_MSG "Parser Error: " #define ERR_TOP_SYS_ERROR_MSG "System Error: " #define ERR_TOP_NO_ERROR_USER_MSG "User Message: " #define HLP_MSG_0_MSG "%s %s: Zeigt diese hilfe ann" #define HLP_MSG_SEARCH_MSG "%s <PATTERN> Sucht nach dem Muster <PATTERN> im Textn" #define USER_MSG_FOUND "%s Das Suchmuster wurde gefundenn" #define USER_MSG_NOT_FOUND "%s Das Suchmuster wurde nicht gefundenn" #define USER_MSG_LINE "%s Zeile: %i, Spalte: %in" #define PARAMETER_0_HELP_STR "--help" #define PARAMETER_SEARCH_STR "--search" #define MIN_ARGC 2 #define MAX_ARGC 3 #define HLP_MSG_0_INDEX 0 #define HLP_MSG_SEARCH_INDEX 1 #define HLP_MSG_MAX_INDEX 1 #define PARAMETER_0_HELP_INDEX 0 #define PARAMETER_SEARCH_INDEX 1 #define PARAMETER_MAX_INDEX 1 #define USER_MSG_FOUND_INDEX 0 #define USER_MSG_NOT_FOUND_INDEX 1 #define USER_MSG_LINE_INDEX 2 #define CODE_FOUND 1 #define CODE_NOT_FOUND 0 const char errtopmsg [][128] = {ERR_TOP_NO_ERROR_NORMAL_MSG, ERR_TOP_USAGE_ERROR_MSG , ERR_TOP_PARSER_ERROR_MSG, ERR_TOP_SYS_ERROR_MSG, ERR_TOP_NO_ERROR_USER_MSG}; const char errmsg [][256] = {ERR_PARSE_FORGOT_COMMA_IN_OR_MSG, ERR_PARSE_FORGOT_SQUARE_BRACKET_CLOSE_IN_OR_MSG, ERR_PARSE_FORGOT_ROUND_BRACKET_CLOSE_MSG, ERR_PROG_USAGE_WRONG_ARGS_MSG, ERR_SYS_NOT_ENOUGH_MEMORY_MSG }; const char helpmsg [][256] = {HLP_MSG_0_MSG, HLP_MSG_SEARCH_MSG}; const char parameterstr [][32] = {PARAMETER_0_HELP_STR, PARAMETER_SEARCH_STR}; const char usermsg [][256] = {USER_MSG_FOUND, USER_MSG_NOT_FOUND, USER_MSG_LINE}; int state1 [X]; int state2 [X]; int v[X]; char *text; //char text [] = "ababcdcdfgfg"; //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 [] = "[*([[[*(ab),*(cd)],e],[fg,*(hi)]]),x]n"; /* 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 = NULL; //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] = CONTROLSTATE; state1 [l] = state2 [l] = 0; } } int gettoken () { if ((expr [i] == C_STRING_END)) return LEX_END; else if (expr [i] == C_ROUND_BRACKET_OPEN) { i++; return LEX_ROUND_BRACKET_OPEN; } else if (expr [i] == C_ROUND_BRACKET_CLOSE) { i++; return LEX_ROUND_BRACKET_CLOSE; } else if (expr [i] == C_SQUARE_BRACKET_OPEN) { i++; return LEX_SQUARE_BRACKET_OPEN; } else if (expr [i] == C_SQUARE_BRACKET_CLOSE) { i++; return LEX_SQUARE_BRACKET_CLOSE; } else if (expr [i] == C_STAR) { i++; return LEX_STAR; } else if (expr [i] == C_COMMA) { i++; return LEX_COMMA; } else if (expr [i] == C_DOT) { i++; return LEX_DOT; } else if (expr [i] == C_BACKSLASH) { i++; if (expr [i] == C_A) { i++; return LEX_A; } else if (expr [i] == C_B) { i++; return LEX_B; } else if (expr [i] == C_F) { i++; return LEX_F; } else if (expr [i] == C_N) { i++; return LEX_N; } else if (expr [i] == C_R) { i++; return LEX_R; } else if (expr [i] == C_T) { i++; return LEX_T; } else if (expr [i] == C_V) { i++; return LEX_V; } return expr [i++]; } else if ((expr [i] >= ASCIIMIN) \&\& (expr [i] <= ASCIIMAX)) { return expr [i++]; } } int tokenback_rec_mask1(int); int tokenback_rec_mask2(int); int tokenback_rec_mask1 (int j) { if (expr [j] == '\') return tokenback_rec_mask2 (j-1); else return 1; } int tokenback_rec_mask2 (int j) { if (expr [j] == '\') return tokenback_rec_mask1 (j-1); else return 0; } void tokenback () { i-=(2-tokenback_rec_mask1(i-2)); } 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') \&\& (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 ()) == LEX_SQUARE_BRACKET_OPEN) { y.begin = x; x++; x1 = or_operator (); if ((ch = gettoken ()) != LEX_COMMA) { fprintf (stderr, errmsg [ERR_PARSE_FORGOT_COMMA_IN_OR_INDEX], errtopmsg [ERR_PARSE]); 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 ()) != LEX_SQUARE_BRACKET_CLOSE) { fprintf (stderr, errmsg [ERR_PARSE_FORGOT_SQUARE_BRACKET_CLOSE_IN_OR_INDEX], errtopmsg [ERR_PARSE]); 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 == LEX_END) 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 ()) == LEX_STAR) { 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 == LEX_END) 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 (); if ((ch >= ASCIIMIN) \&\& (ch <= ASCIIMAX)) { 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 == LEX_END) 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 () == LEX_ROUND_BRACKET_OPEN) { x1 = or_operator (); if ((ch = gettoken ()) != LEX_ROUND_BRACKET_CLOSE) { fprintf (stderr, errmsg[ERR_PARSE_FORGOT_ROUND_BRACKET_CLOSE_INDEX], errtopmsg [ERR_PARSE], expr [i], i); exit (1); } x1.exists = 1; debug ("compound", x1); return x1; } else if (ch == LEX_END) 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) || (xreal > x-2)) 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] >= ASCIIMIN) \&\& (v [xreal] <= ASCIIMAX)) { if (v [xreal] == text [xtext]) { exists = 1; } if (state1 [xreal] == state2 [xreal]) exists \&= automat (state1 [xreal], xtext+1); else exists \&= (automat (state1 [xreal], xtext+1) || automat (state2 [xreal], xtext+1)); } return exists; } void main (int argc, char *argv[]) { int h; int k, l; int ch; char textbuf [BUF_INPUT_SIZE]; char *p; int t1, t2; int line = 0; int *lines; int lineindicator = 0; int columnindicator = 0; int lineindicatorindex = 0; if (!((argc >= MIN_ARGC) \&\& (argc <= MAX_ARGC))) { fprintf (stderr, errmsg [ERR_PROG_USAGE_WRONG_ARGS_INDEX], errtopmsg [ERR_USAGE]); fprintf (stderr, helpmsg [HLP_MSG_0_INDEX], argv [0], parameterstr [PARAMETER_0_HELP_INDEX] ); exit (ERR_USAGE); } if (argc == 2) { if (strcmp (argv [1], parameterstr [PARAMETER_0_HELP_INDEX]) == 0) { fprintf (stderr, helpmsg [HLP_MSG_0_INDEX], argv [0], parameterstr [PARAMETER_0_HELP_INDEX] ); for (h = 1; h <= PARAMETER_MAX_INDEX; h++) fprintf (stderr, helpmsg [h], parameterstr [h]); } } else if (argc == 3) { if (strcmp (argv [1], parameterstr [PARAMETER_SEARCH_INDEX]) == 0) { if ((expr = (char *)malloc (sizeof (char) * strlen(argv [2]))) == NULL) { fprintf (stderr, errmsg [ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } strcpy (expr, argv [2]); } } initstates (); or_operator (); //printf ("successn"); if ((text = (char *)malloc (sizeof(char)*BUF_INPUT_SIZE)) == NULL) { fprintf (stderr, errmsg [ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } if ((lines = (int *) malloc (sizeof (int) * BUF_INPUT_SIZE)) == NULL) { fprintf (stderr, errmsg [ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } t1 = 0; text [0] = 0; do { //if (fgets (textbuf, BUF_INPUT_SIZE, stdin) == NULL) //break; p = textbuf; t2 = 0; while (((ch = fgetc (stdin)) != EOF) \&\& (t2 < BUF_INPUT_SIZE)) { *p = ch; if (ch == 'n') { lines[line] = t1+t2; line++; } p++; t2++; if (((line % BUF_INPUT_SIZE) == 0) \&\& (line != 0)) { if ((lines = realloc (lines, (line+BUF_INPUT_SIZE) * sizeof (int))) == NULL) { fprintf (stderr, errmsg [ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } } } *p = 0; t2++; t1 = t1 + t2; strcat (text, textbuf); if (t2 >= BUF_INPUT_SIZE) { if ((text = realloc (text, t1+BUF_INPUT_SIZE)) == NULL) { fprintf (stderr, errmsg [ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } printf ("%in", t1+BUF_INPUT_SIZE); } } while (strlen(textbuf) > 0); //printf (text); for (k = 0; k <= x; k++) { if ((v[k] >= 'a') \&\& (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]); } for (k = 0, lineindicator = 0, lineindicatorindex = 0; k < strlen (text); k++) { if (k == lines[lineindicatorindex+1]) { lineindicator = lines [lineindicatorindex]; columnindicator = 0; lineindicatorindex++; } if (automat(0,k) == CODE_FOUND) { fprintf (stdout, usermsg [USER_MSG_FOUND_INDEX], errtopmsg [ERR_NO_ERROR_USER] ); fprintf (stdout, usermsg [USER_MSG_LINE_INDEX], errtopmsg [ERR_NO_ERROR_USER], lineindicatorindex, columnindicator); } columnindicator++; } exit (ERR_NO_ERR_NORMAL); }