#include <stdio.h> #include <stdlib.h> #include <string.h> #define X 2048 #define MAX_LINES 2048 #define END -1 #define REALEND -2 #define CONTROLSTATE -3 #define OPERATIONSTATESUBSTITUTE -14 #define OPERATIONSTATESUBSTITUTEWITH -15 #define OPERATIONSTATEFIND -16 #define OPERATIONSTATEEND -17 #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_SLASH -13 #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_SLASH '/' #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 eingegeben oder sie haben Parameter fehlerhaft 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 = NULL; int *state2 = NULL; int *v = NULL; char *text; int i = 0; int x = 0; int statexn = 0; char *expr = NULL; int initstates () { int l; for (l = 0; l < X; l++) { v [l] = CONTROLSTATE; state1 [l] = state2 [l] = 0; } } void allocstates () { int k; if (x == 0) { if ((void *)state2 == NULL) { if ((state1 = (int *) malloc (sizeof (int) * X)) == NULL) { fprintf (stderr, errmsg[ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } if ((state2 = (int *) malloc (sizeof (int) * X)) == NULL) { fprintf (stderr, errmsg[ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } if ((v = (int *) malloc (sizeof (int) * X)) == NULL) { fprintf (stderr, errmsg[ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } for (k = 0; k < X; k++) v [k] = CONTROLSTATE; statexn = X; return; } else { if ((state1 = (int *) realloc (state1, sizeof (int) * (X + statexn))) == NULL) { fprintf (stderr, errmsg[ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } if ((state2 = (int *) realloc (state2, sizeof (int) * (X + statexn))) == NULL) { fprintf (stderr, errmsg[ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } if ((v = (int *) realloc (v, sizeof (int) * (X + statexn))) == NULL) { fprintf (stderr, errmsg[ERR_SYS_NOT_ENOUGH_MEMORY_INDEX], errtopmsg [ERR_SYS]); exit (ERR_SYS); } for (k = statexn; k < (statexn + X); k++) v [k] = CONTROLSTATE; statexn += X; return; } } return; } 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_SLASH) { i++; return LEX_SLASH; } 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 operations (); 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; } void string () { int ch; while (((ch = gettoken ()) != END) \&\& ((ch >= ASCIIMIN) \&\& (ch <= ASCIIMAX))) { allocstates (); state1 [x] = x+1; state2 [x] = x+1; v [x] = ch; x++; } allocstates (); state1 [x] = 0; state2 [x] = 0; v [x] = CONTROLSTATE; allocstates (); x++; tokenback (); } void operations () { int ch; if ((ch = gettoken ()) == LEX_SLASH) { if ((ch = gettoken ()) == 's') { allocstates (); state1 [x] = x+1; state2 [x] = x+1; v [x] = OPERATIONSTATESUBSTITUTE; x++; if ((ch = gettoken ()) != LEX_SLASH) { fprintf (stderr, errmsg [ERR_PROG_USAGE_WRONG_ARGS_INDEX], errtopmsg [ERR_USAGE]); exit (ERR_USAGE); } or_operator (); if ((ch = gettoken ()) != LEX_SLASH) { fprintf (stderr, errmsg [ERR_PROG_USAGE_WRONG_ARGS_INDEX], errtopmsg [ERR_USAGE]); exit (ERR_USAGE); } x++; allocstates (); state1 [x] = x+1; state2 [x] = x+1; v [x] = OPERATIONSTATESUBSTITUTEWITH; x++; string (); if ((ch = gettoken ()) != LEX_SLASH) { fprintf (stderr, errmsg [ERR_PROG_USAGE_WRONG_ARGS_INDEX], errtopmsg [ERR_USAGE]); exit (ERR_USAGE); } allocstates (); state1 [x] = x+1; state2 [x] = x+1; v [x] = OPERATIONSTATEEND; x++; operations (); } else if (ch == 'f') { if ((ch = gettoken ()) != LEX_SLASH) { fprintf (stderr, errmsg [ERR_PROG_USAGE_WRONG_ARGS_INDEX], errtopmsg [ERR_USAGE]); exit (ERR_USAGE); } or_operator (); if ((ch = gettoken ()) != LEX_SLASH) { fprintf (stderr, errmsg [ERR_PROG_USAGE_WRONG_ARGS_INDEX], errtopmsg [ERR_USAGE]); exit (ERR_USAGE); } } else { fprintf (stderr, errmsg [ERR_PROG_USAGE_WRONG_ARGS_INDEX], errtopmsg [ERR_USAGE]); exit (ERR_USAGE); } } else if (ch != LEX_END){ fprintf (stderr, errmsg [ERR_PROG_USAGE_WRONG_ARGS_INDEX], errtopmsg [ERR_USAGE]); exit (ERR_USAGE); } } 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) { allocstates (); 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); } allocstates (); 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) { allocstates (); 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) { allocstates (); x1 = compound (); y.begin = x1.begin; y.mid = x; x++; allocstates (); 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)) { allocstates (); 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, int); int to; int outerautomat (int xtext) { int fromto; int xy; for (xy = 0, fromto = 1; xtext < strlen (text); xtext += fromto) { if (xy < x) { while ((v [xy] == CONTROLSTATE) \&\& (state1 [xy] == 0) \&\& (state2 [xy] == 0)) xy++; if (v [xy] == OPERATIONSTATESUBSTITUTE) { xy++; if (automat (xy, xtext) == 0) { while (v [xy] != OPERATIONSTATEEND) xy++; xy++; while (v [xy] == CONTROLSTATE) xy++; fromto = 0; } else { while (v [xy] != OPERATIONSTATESUBSTITUTEWITH) xy++; xy++; while ((state1 [xy] != 0) \&\& (state2 [xy] != 0)) { printf ("%c", v[xy]); xy = state1 [xy]; } xy = 0; fromto = (to - xtext)+1; } } } else if (xy >= x) { printf ("%c", text [xtext]); fromto = 1; xy = 0; } } } int automat (int xreal, int xtext) { int exists = 0; if ((strlen (text) <= xtext) || (state1 [xreal] == 0)) { to = 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] >= ASCIIMIN) \&\& (v [xreal] <= ASCIIMAX)) { if (v [xreal] == text [xtext]) { exists = 1; } else if (v [xreal] != text [xtext]) return 0; 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 (); operations (); //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); } } } 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, %i))n", k, v[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++; }*/ outerautomat (0); exit (ERR_NO_ERR_NORMAL); } */