Von der DEA zum Quellcode, wie geht man am besten vor?
-
Ich will aus einem String überflüssige Leerzeilen entfernen, also Leerzeilen die zuviel sind bzw. mehrfach vorhanden sind und das Ergebnis in einen zweiten String (hier ziel genannt) kopieren.
Bsp:
s = "Hallo du da am Eingang.\n";Nun könnte man dafür einen DEA bauen, der bei q0 bleibt solange kein Leerzeichen eingegeben wird.
Und erst wenn das erste Leerzeichen kommt, dann soll er nach q1 gehen.
Wenn nach q1 nun noch ein Leerzeichen kommt, dann geht es nach q2 und im Zustand q2 wird das aktuelle Zeichen aus dem String entfernt, sollte aber nach q1 kein Leerzeichen kommen, dann geht es zurück nach q0.
Das gleiche gilt, wenn bei q2 kein Leerzeichen mehr kommt, auch dann geht es nach q0 zurück.
Und falls ein EOF bzw. \n Stringende kommt, dann geht es nach q3, das ist der finale Zustand.Und fertig ist mein endlicher Automat.
In Tupel Notation also: (ich hoffe es ist richtig oder fehlt hier noch ein Zustand q4 in dem das aktuelle Zeichen in den zweiten String kopiert wird? (siehe unten))
A = ({q0, q1, q2, q3}, ASCII, {(q0," ")=q1, (q0," ")=q2, (q1, !" ")=q0, (q2, !" ")=q0, (q0,"\n")=q3}, q0, q3)So schön ist die Theorie, aber wie gelangt man von diesem theoretischen Konstrukt zum Quellcode?
Ich dachte da an ne For Schleife, daß den String von vorne bis nach hinten durchläuft und bei jedem Iterationsschritt wird geprüft, ob es ein Leerzeichen ist und wenn dies Zutrifft, dann wandert das Programm in Zustand q2.
C99 Code:
ACHTUNG der Code ist FEHLERHAFT!
#define TRUE 1 #define FALSE 0 ... int cp; // Zeichen in Ziel String kopieren? char s, ziel; int i, z=0; for (i=0; i < (strlen(s)-1); i++) { cp = TRUE; if (s[i] == ' ') { // Hier befinden wir uns nun im Zustang q1 if (cp) // Hier retten wir mal das erste Leerzeichen in den 2. String { ziel[z] = s[i]; z++; cp = FALSE; // Zeichen darf unten nicht noch einmal übernommen werden } i++; if (s[i] == ' ') { // Zustand q2 cp = FALSE; // Zeichen wird unten nicht übernommen } } if (cp) { ziel[z] = s[i]; z++; } } ziel[z] = '\n'Wie man an dem fehlerhaften Code leicht sehen kann, gibt es hier mehrere Probleme.
1. Sobald man sich im Zustand q2 befindet müßte man hier gemäß DEA i in einer Schleife mehrmals iterieren bis eben ein anderes Zeichen als das Leerzeichen kommt.2. Aber wenn man Punkt 1 befolgt oder das Programm so läßt wie es ist, dann wird i zu oft einmal im If Block und ein weiteres mal in der ersten For Schleife iteriert, so daß mindestens das erste Zeichen das nach einer Vielzahl von Leerzeichen folgt nicht übernommen wird.
Wie man also sieht, stößt man hier auf mehrere Probleme wenn man versucht einen DEA 1:1 in ein Programm umzumünzen.
Natürlich wäre die Schleife viel einfacher zu realisieren, wenn man den DEA komplett ignoriert und einfach die Zeichen auf normalerweise durchwandert und dann entsprechend das Zeichen übernimmt oder dies sein läßt, aber das sollte hier jetzt nicht die Aufgabe sein.Die Aufgabe sollte hier sein, den DEA sauber in C99 umzusetzen.
Wie geht ihr hier vor, wie würdet ihr das machen?So daß am Ende also im Ziel String gemäß der Eingabe oben folgendes drinsteht:
"Hallo du da am Eingang.\n"
-
Ich habe mal eine Grafik vom DEA erstellt:
http://img547.imageshack.us/img547/271/dea.png
Wenn ich nun im DEA aber auch das kopieren des aktuellen Zeichens in den anderen String berücksichtigen würde, dann würde ich ja von q0 und q1 auf ein q4 mit einer Pfeilbezeichnung "Kopieren" verweisen müssen, aber der Schritt "kopieren" ist ja jetzt nun kein Iterationsschritt der Eingabezeichenfolge.
So gesehen müßte q4 also wegbleiben, oder?Für q3 als finalen Zustand fehlt übrigens eine doppelte Umrandung, das lag aber an den Einschränkungen der Software.
Die DEA Grafik habe ich mit JFLAP erstellt, das ist ne recht brauchbare Software zum Zeichnen von DEA Grafiken.
http://www.jflap.org/
-
ich hoffe du verbringst nicht zu viel zeit damit DEA zeichnungen anzufertigen? der code ist mieserabel. such doch mal im ansi c forum das wurde schon des öfteren gelöst.
-
Korrigierte DEA Grafik:
http://img835.imageshack.us/img835/8166/dean.png
Ich habe nochmal die DEA Grafik überarbeitet, hier ist die korrigierte Version. Diesmal auch mit dem Start und Endzustand.
Das Programm konnte das doch.
-
--- schrieb:
ich hoffe du verbringst nicht zu viel zeit damit DEA zeichnungen anzufertigen? der code ist mieserabel. such doch mal im ansi c forum das wurde schon des öfteren gelöst.
Wie bereits geschrieben, mir geht es hier jetzt nicht um die beste Codelösung, sondern um die Umsetzung der DEA in Code.
Das das vom Code her unter Ignoranz der DEA besser geht, weiß ich auch. Das schrieb ich ja auch.
-
Um, mir ist gerade aufgefallen, daß ich ständig ein \n newline Zeichen für die DEA Beschreibung und Grafik genommen habe, aber ich denke es ist klar, daß ein Leerzeichen gemeint ist.
Und von diesem typischen Leerzeichenersatz (Blank), also dieser Unterstrich der an den Seiten nach oben geht weiß ich auch nicht die Unicodenummer.
Von daher muß das \n hier halt als Leerzeichen herhalten.
-
#include <stdio.h> #include <stdlib.h> int main(void) { char in[] = "ha ha ha ha ha ha"; char *i = in; char *p = in; char c; while((c = *p++)){ if(c!=' ' || *p!=' ') *i++ = c; } *i=0; printf(in); return 0; }na dann mal mal weiter an deiner DEA
-
Ich habe nochmal eine korrigierte Fassung der DEA Grafik hochgeladen.
Das Newlinezeichen als Leerzeichensubstitution lasse ich so bestehen.
-
Ich habe nochmal eine korrigierte Fassung der DEA Grafik hochgeladen.
http://img267.imageshack.us/img267/1221/deaw.png
-
-
so sollts doch reichen? schrieb:
der passende code:
int main(void) { char in[] = "ha ha ha ha ha ha"; char *i = in; char *p = in; char c; while(1){//q0 c = *p++; if(c==' '){//goto q1 while(1){ c = *p++; if(c!=' '){ p--; break;//goto q0 } } }else if(c==0){//goto q3 break; }else *i++ = c; } *i=0; printf(in); return 0; }
-
int main(void) { char in[] = "ha ha ha ha ha ha"; char *i = in; char *p = in; char c; while(1){//q0 c = *p++; if(c==' '){//goto q1 while(1){ c = *p++; if(c!=' '){ break;//goto q0 } } }else if(c==0){//goto q3 break; } *i++ = c; } *i=0; printf(in); return 0; }
-
der letzte post war falsch bei sowas wie " \0"!
-
so sollts doch reichen? schrieb:
Nein, denn in q1 wird ja mindestens 1 Leerzeichen übernommen.
Wenn du also in q1 verbleibst und kein q2 einführst, dann übernimmst du alle leerzeichen.Denn von wo soll bei deiner DEA bzw, die State Machine denn Wissen, wann ein Leerzeichen zu übernehmen ist und wann nicht?
-
so hab ich doch auch nur Q0,Q1,Q2
#include <stdio.h> #include <stdlib.h> int main(void) { char in[] = "ha ha ha ha ha ha"; char *i = in; char *p = in; char c; Q0: while(1){ c = *i++ = *p++; if(c==0){ goto Q2; }else if(c==' '){ goto Q1; } } Q1: while(*p==' '){ p++; } goto Q0; Q2: printf(in); return 0; }
-
also ich denke mir ist klar warum man 4 knoten braucht
#include <stdio.h> #include <stdlib.h> enum{S_COPY_CHAR,S_SPACE,S_END,S_SPACE_SPACE}; int main(void) { char in[] = "ha ha ha ha ha ha"; char *i = in; char *p = in; char c; char state = S_COPY_CHAR; while(1){ switch(state){ case S_COPY_CHAR: c = *i++ = *p++; switch(c){ case 0 : state = S_END; break; case ' ': state = S_SPACE; break; } break; case S_SPACE: c = *p++; switch(c){ case ' ': /*state = S_SPACE_SPACE;*/ break; default : state = S_SPACE_SPACE; break; } break; case S_SPACE_SPACE: p--; state = S_COPY_CHAR; break; case S_END: puts(in); return 0; break; } } }
-
rolleyes schrieb:
int main(void) { char in[] = "ha ha ha ha ha ha"; char *i = in; char *p = in; char c; while(1){//q0 c = *p++; if(c==' '){//goto q1 while(1){ c = *p++; if(c!=' '){ break;//goto q0 } } }else if(c==0){//goto q3 break; } *i++ = c; } *i=0; printf(in); return 0; }Wie sicherst du denn bei dir die Leerzeichen?
Bei deinem Code werden die komplett ignoriert, und wenn man deinen Code in so etwas ändert:#include <stdio.h> int main(void) { char in[] = "ha ha ha ha ha ha"; char *i = in; char *p = in; char c; while(1){//q0 c = *p++; if(c==' '){//goto q1 while(1){ c = *p++; if(c!=' '){ break;//goto q0 } } *i++ = c; }else if(c=='\0'){//goto q3 break; } *i++ = c; } *i=0; printf("%s",in); return 0;Dann werden die Leerzeichen auch nicht gesichert, weil sich die Breakanweisung auf die erste while Schleife bezieht und nicht auf die zweite.
Fügt man das *i++ = c; vor der geschleiften Klammer ein, dann werden wieder zu viele Leerzeichen gesichert.
-
ich auch schrieb:
Ich habe nochmal eine korrigierte Fassung der DEA Grafik hochgeladen.
http://img267.imageshack.us/img267/1221/deaw.pngDeine DEA wird immer von q2 nach q0 springen.
D.h. das passiert bei dir schon bei der ersten 0.
Wenn aber darauf eine zweite 0 kommt, dann bist du schon wieder bei q0.Und das kann so nicht richtig sein.
Eigentlich mußt du in q1 so lange verbleiben, bis die letzte 0 kommt und dann wird mit dieser 0 nach q2 gesprungen.Da das AFAIK so aber bei einer DEA nicht realisierbar ist, müßte man das irgendwie anders lösen.
Im Prinzip braucht man so etwas:http://img526.imageshack.us/img526/2161/deaproblem.png
Kennt sich hier jemand besonders gut mit DEAs aus und wie man das genannte Problem korrekt in ein DEA Diagramm realisiert?
-
Der letzte DEA hat das Problem, dass er fordert, dass nach dem Leerzeichen unbeding nochmal ein Zeichen kommen muss, dass keins ist.
Ich würde sagen wir brauchen drei Zustände:
A: letztes gelesenes Zeichen war kein Leerzeichen
B: letztes gelesenes Zeichen war Leerzeichen
C: FinalzustandA ist der Startzustand
- Bei Eingabe von \0 geht es sowohl von A, als auch von B zu C, das Zeichen wird dabei mit ausgegeben.
- Eingabe eines Nicht-Leerzeichens geht von A nach A (und gibt das Zeichen aus) und von B nach A (und gibt das Zeichen aus).
Eingabe eines Leerzeichens führt von A nach B (das Zeichen wird ausgegeben)
Eingabe eines Leerzeichens führt von B nach B (das Zeichen wird *nicht* ausgegeben).Das sollte es doch schon tun, oder?
-
Du meinst so:
-
Wenn man das in Code umsetzt, dann würde es wohl eher so wie automatos Code aussehen, also in Form einer State Machine, anstatt eines Parsers der ne Schleife durchläuft.
Richtig?
