der Uart emfängt Zeichen (Interrupt gesteuert). Die emfangen Zeichen sollen mit bekannten Wörtern verglichen werden. Die Wörter enden mit CR LF Wie macht man sowas in GCC (Mega8). Ich habe es umständlich mit Case-Anweisungen gemacht. Sicher geht das einfacher.
macht sich dumm ohne Startzeichen (z.B. STX(02 hex) ) aber geht natürlich auch nur suchst du länger. weil du nach jedem zeichen kontrollieren must. zum zuordnen/filtern ist case schon optimal.
Ich habe mir einen Zustandsautomaten gemalt und versucht umzusetzen
angenommen ich erwarte die Wörter "ja" oder "nein".
(Pseudocode)
Start: Zustand 0
Case Zustand 0
- wenn "j"-> Zustand 1; wenn n-> Zustand 3; sonst Zustand 0
Case Zustand 1
- wenn "a"-> Zustand 2 ("ja" empfangen); sonst Zustand 0
Case Zustand 3
- wenn "e"-> Zustand 4; sonst Zustand 0
Case Zustand 4
- wenn "i"-> Zustand 5; sonst Zustand 0
Case Zustand 5
- wenn "n"-> Zustand 6 ("nein" empfangen); sonst Zustand 0
ich polle den Zustand und setze ihn wieder 0
Das Problem: der Code ist nicht einfach erweiterbar. Z.B. in der Art
dass ich eine Tabelle habe und dort Wörter dazu schreibe
Hi, Stefan, Du: "Die emfangen Zeichen sollen mit bekannten Wörtern verglichen werden. Wie macht man sowas in GCC (Mega8)." Ich mache es für mein Dutzend Kommandos mit einer Wörterliste, je Token ein String, und dann in einer for-Schleife vergleichen mit strncmp(). Ein Startzeichen ist vorgesehen, damit ich die Token im empfangenen Kommandostring an bekannter Stelle finde. In der Meßtechnik gehört ja noch mehr dazu wie das Auswerten von Parametern. Mein Atmega8 wird damit schon zu >60% ausgelastet. Für Anwendungen mit Atmega8 verwende ich keien Kommandos mit Token, sondern eine Kommandozahl. Ciao Wolfgang Horn
Vor 5 Jahren hätte ich gesagt:"Implementiere einen Generator, der dir deine Zustandstabelle erzeugt". Heute sind solche Generatoren out, und Objektorientierung ist in (Hilft dir aber nix beim Atmega8).
@stefan mal einen ansatz : mach dir zu deiner wortliste ein bitfeld in dem jedes bit ein wort repräsentiert. nimm dir einen zähler der die buchstaben seit dem letzten cr/lf zählt. kommt nun ein zeichen an prüfst du (bei jedem deiner wörter) : - ob dein zeichenzähler kleiner ist als als die länge des wortes. - stimmt ein wort (zeichen an aktueller zähler) nicht mehr überein mit deinem zeichen setzt du das bit des wortes auf 0, sonst bleibt es auf 1 (also erst alle bits mit 1 initialisieren). nach jedem zeichen zählst du die bits die 1 sind. ist nur noch 1 bit übrig ist es wahrscheinlich das gesuchte wort und du mußt nur noch abwarten bis alle zeichen des wortes "erfüllt" sind. dann kannst du das wort als "angekommen" betrachten und von mir aus ein token auf dem stack legen. beispiel : wortliste : 1 -> "abc" 2 -> "help" 3 -> "viel" 4 -> "variable" 5 -> "version" du tippst das wort "version ein" -> v -> bits vorher 11111, nachher 00111 e -> bits vorher 00111, nachher 00001 r -> bits vorher 00001, nachher 00001 s -> bits vorher 00001, nachher 00001 i -> bits vorher 00001, nachher 00001 o -> bits vorher 00001, nachher 00001 n -> bits vorher 00001, nachher 00001, zeichenzähler = länge von "version" -> token gefunden. ich verwende diesen algorithmus schon seit einiger zeit und er funktioniert prächtig. werde (sobald ich zeit und lust habe) diesen algorithmus mal vorstellen. allerdings ist der quellcode etwas schwere kost (verwende intensiv den präprozessor, dafür kann das teil aber komplette befehlszeilen erkennen [mit parametern] und braucht relativ wenig ressourcen) hoffe ich konnte helfen gruß rene
Hallo Stefan, ich beschäftige mich gerade mit dem selben Problem und es gibt eigentliche viele Ansatzmöglichkeiten. Zunächst einmal habe ich eine Vergleichstabelle der möglichen Worte auf dem ATMega8, außerdem wird die empfangene Sringfolge im ATMega gespeichert bis z.B. ein 0x20 (Leerzeichen) folgt. Dann muss diese Folge mit der Tabelle verglichen werden. Dazu vergleicht man halt alle Anfangszeichen der Tabelle mit dem ersten empfangen Zeichen des Wortes ist es gleich vergleicht man das 2., 3. usw. kommt ein falsches geht es in die nächste TAbellenzeile und es beginnt von vorne (dauert evtl lange aber funktioniert :-D) Eine weitere Möglichkeit die mir eingefallen ist, wäre die empfangene Stringlänge mit der gespeicherten Stringlänge in der Tabelle zu vergleichen dadurch fallen schon einige Wörter weg und die Funktion wird beschleunigt. Wie du siehst gibt es einige Möglichkeiten, die passende findest du am besten für dich ;-) bei interesse post ich meine funktion gern wenn du willst. Gruß Max
suche mal nach flex und bison. damit kannst du dir einen richtigen parser erstellen. wird im comilerbau verwendet!
Flex/Bison sind freilich der schnellste Weg, die Speicher vom Mega8 vollzukriegen. Zumal man reichlich drin schweinigeln müsste, um die Tabellen ins ROM zu kriegen und dort auch zu lassen.
@rene ich hatte noch keine Zeit deine Variante zu testen. @max deine Programm würde mich interessieren, mit Tabellen habe ich ausser beim Durcharbeiten des Tutorial noch nix gemacht.
@Stefan Gemmel: Soll der Code wenig Programmspeicher oder wenig Rechzeit verbrauchen? Sind die einzelnen Wörter durch Begrenzungszeichen (Leerzeichen, Kommata, Zeilenvorschübe o.ä.) getrennt? Falls du nur die Geschwindigkeit optimieren möchtest, liegst du mit dem endlichen Automaten richtig, da dieser auch bei großem Wortschatz immer etwa die gleiche Zeit für die Verarbeitung jedes Zeichens der Eingabe benötigt. Mit einem Automaten können auch problemlos Wörter in einem Eingabestrom erkannt werden, wenn deren Anfang und Ende nicht durch Begrenzungszeichen gekennzeichnet sind. Allerdings kann die Anzahl der Zustände und damit der Programmcode mit wachsender Anzahl Wörter sehr groß werden. Wenn der benötigte Programmspeicherplatz minimiert werden soll, ist ein direkter Vergleich mit den vorgegebenen Wörtern, die dann in einer Tabelle stehen, vorzuziehen. Aber auch hier gibt es viele Möglichkeiten, die Anzahl der benötigten Vergleichoperationen zu reduzieren. Die Beiträge von TheMason und Max zeigen in diese Richtung. Bei sehr vielen Wörtern kannst du auch eine Binärsuche in Erwägung ziehen, da bei dieser der Rechenaufwand nur mit dem Logarithmus der Wortanzahl wächst. Die Wortliste muss dazu sortiert vorliegen, was aber kein Problem sein sollte, da sie sich ja nicht ändert (und selbst wenn: auch dafür gibt es effiziente Algorithmen). @Stock Hecht: > Vor 5 Jahren hätte ich gesagt:"Implementiere einen Generator, der > dir deine Zustandstabelle erzeugt". Heute sind solche Generatoren > out, und Objektorientierung ist in (Hilft dir aber nix beim > Atmega8). Häääh??? Versteh' ich überhaupt nicht. Macht die Objektorientierung solche Generatoren etwa überflüssig? Ich sehen da keinen Zusammenhang. Und wieso hilft das nicht beim ATmega8? Also ich würde den Automaten (ob als Tabelle oder als Case-Anweisung) auch 5 Jahre später lieber generieren lassen, als sie selbst zu schreiben.
ich habe eigentlich genügend Rechenzeit und genügend Programmspeicher. Es geht darum, dass der Code (bzw. die Wörter) von jedem Anfänger selbst geändert werden können. Das ist ja bei meinem Case schon bei 3 Wörtern zu unübersichtlich. Ich hätte gerne ne Headerdatei wo die Wörter in Klartext drin stehen. Dann ein Eingangsspeicher wo drin steht: zuletzt Wort 4 der Liste empfangen. Die Wörter haben kein Anfangszeichen, enden aber mit CR LF. Ich denke es bleibt so bei etwa 5 Wörtern.
Dann beschäftige dich mal damit, wie du im Eingangsstrom
einzelne Wörter herausfischt.
Da deine Wörter alle mit CR LF enden, sollte das auch
kein Problem sein:
Du machst dir ein char-Array und fügst dort solange
den nächsten empfangenen Character ein, bis im Eingangsstrom
CR auftaucht (LF ignorierst du ganz einfach).
Hast du das CR gefunden, dann kommt an die Zeichen im char
Array hinten noch ein '\0' hinten dran um daraus einen
String zu machen.
Damit hast du dann das Wort als String im Speicher liegen.
Um diesen String dann in einer Tabelle zu suchen:
char* Words[] = { "Wort1",
"Wort2",
"Wort3",
"Ende" };
#define NR_WORDS (sizeof(Words)/sizeof(*Words))
int Find( char* Word )
{
uint8_t i;
for( i = 0; i < NR_WORDS; ++i ) {
if( strcmp( Word, Words[i] ) == 0 )
return i;
}
return -1;
}
Kriegst du den Teil mit dem Empfangen und Sammeln der Zeichen
in einem globalen char Array hin?
Ich würd mir einfach einen Ringbuffer bauen, in dem alle seriellen Bytes landen (Ringbuffergröße = max. Länge eines Deiner Worte + 2 für CR LF). Sobald das LF erkant wird, nimmst Du den Ringbuffer und vergleichst der Reihe nach mit Deinen Worten und die Sonne scheint wieder!
Sardaukar wrote: > Ich würd mir einfach einen Ringbuffer bauen, in dem alle seriellen Bytes > landen (Ringbuffergröße = max. Länge eines Deiner Worte + 2 für CR LF). > Sobald das LF erkant wird, nimmst Du den Ringbuffer und vergleichst der > Reihe nach mit Deinen Worten und die Sonne scheint wieder! Na ja, so simpel ist das auch wieder nicht. Das Problem ensteht, wenn das Wort im Ringbuffer einen Wrap-Around macht. Also vorher aus dem Ringbuffer in einen normalen linearen Array umkopieren.
@stefan also wenns wirklich nur etwa fünf wörter sind, würde ich einfach nur einen einfachen strcmp/strncmp machen. alles andere wäre zwar auch machbar, aber würde deutlich mehr aufwand bedeuten. zumal wenn du sowieso weißt das nur ein wort pro zeile und jede zeile mit cr/lf abgeschlossen wird, ist strcmp/strncmp sicherlich schneller implementier (braucht gegenüber einer optimierten lösung sicherlich länger, aber der aufwand würde sich bei den einfachen rahmenbedingungen einfach nicht lohnen) wenn du in einem text-byte-strom wörter erkennen musst (mehrere trennzeichen, endekennzeichen und dergleichen) dann wirds etwas komplizierter und dann macht es sinn einen anderen weg zu gehen. vor allem wenn dann mehr als 5 oder 10 wörter auftauchen können (oder von mir aus auch hexa-zahlen/dezimalzahlen/strings und dergleichen).
@Karl Heinz So hatte ich das eh gemeint. Ist wohl nicht ganz richtig ausgedrückt gewesen. Bei der geringen Anzahl an Worten würd ich eher dazu tendieren einen memcmp zu verwenden als ein strcmp. Wenn mich nicht alles täuscht, dann braucht die string.h schon mehr Ressourcen als die memory.h. Allerdings reicht bei der überschaubaren Anzahl an Zeichen auch eine selbst geschnitze compare Funktion.
TheMason wrote: > @stefan > (braucht gegenüber einer optimierten lösung sicherlich länger, Da bin ich mir bei 5 Wörtern noch nicht mal sicher. Ich denke dass der Overhead bei anderen Lösungen (Hashtabelle, binäres Suchen) größer ist als eine lineare Suche dauert. Im Schnitt sollte er bei 5 Wörtern den gesuchten String ja nach dem 2.ten strcmp haben. Und so dämlich ist strcmp auch wieder nicht, dass es den String komplett durchgeht, auch wenn die ersten Buchstaben sich schon voneinander unterscheiden. > wenn du in einem text-byte-strom wörter erkennen musst (mehrere > trennzeichen, endekennzeichen und dergleichen) dann wirds etwas > komplizierter und dann macht es sinn einen anderen weg zu gehen. vor > allem wenn dann mehr als 5 oder 10 wörter auftauchen können (oder von > mir aus auch hexa-zahlen/dezimalzahlen/strings und dergleichen). Kommt auch immer darauf an, wer am anderen Ende der Leitung die Wörter einspeist. Wenn das ein Mensch ist, dann kann man schon etwas mehr Aufwand treiben. Aber auch hier: Wie du schon richtig sagst - Bei 5 unterschiedlichen Wörtern lohnt sich das alles noch nicht.
Sardaukar wrote: > @Karl Heinz > So hatte ich das eh gemeint. Ist wohl nicht ganz richtig ausgedrückt > gewesen. > > Bei der geringen Anzahl an Worten würd ich eher dazu tendieren einen > memcmp zu verwenden als ein strcmp. Warum willst du dir selbst das Leben schwer machen. strcmp() berücksichtigt unterschiedliche String-Längen, memcmp() nicht. > Wenn mich nicht alles täuscht, dann > braucht die string.h schon mehr Ressourcen als die memory.h. Quatsch. Ein *.h braucht überhaupt keine 'Resourcen' (ausser vielleicht die Symboltable des Compilers, aber die zählt nicht). In einem *.h File steht nur drinnen, welche Funktionen in der Standard- Library enthalten sind und wie sie aufgerufen werden. Dein Programm wird immer gegen die Standard Library gelinkt und der Linker holt sich aus der Library die Funktionen raus, die er braucht. Beim gcc gibt es noch einen Sonderfall: Der Linker holt nicht Funktionen sondern Module aus der Library. Wenn die Libraryersteller jetzt nicht allzusehr geschlafen haben, dann haben sie Funktionen wie strlen(), strcmp(), ... in jeweils ein eigenes Modul gepackt oder zumindest eine sinnvolle Verteilung in Module gewählt. > Allerdings reicht bei der überschaubaren Anzahl an Zeichen auch eine > selbst geschnitze compare Funktion. Das Rad neu erfinden? Wozu Ein strcmp ist eine simple Funktion. Die kannst du selbst auch nicht kürzer schreiben.
Ich würde mir einen Suchbaum konstruieren: 1. Die Worte alphabetisch sortieren 2. Gruppen mit gleichen Wortanfängen separieren Für die Wortanfänge wird eine Erkennungsroutine gebaut, die zum passenden Unterbaum verzweigt. Falls kein Folgebaum mehr vorhanden ist, ist das Wort entweder erkannt, oder - falls das Eingabewort noch Zeichen enthält - trat ein Fehler auf. 3. Die bereits erkannten Wortanfänge abtrennen und für jede Gruppe mit gleichem Anfang eine neue Teiltabelle bauen und für jede das Verfahren wiederholen, bis nichts mehr übrig ist. Im Prinzip ist das die Konstruktion eines Automaten, dessen Zustand durch den Zeiger auf einen (Teil-) Suchbaum repräsentiert ist.
Wie bereits erwähnt wurde brauchst du eine Möglichkeit bei einem fehlgeschlagenen Vergleich das letzte Zeichen zurückzulegen. Dafür kennt man "ungetc()". Nur so kann "+=" von "++" unterschieden werden. strcmp reicht eigentlich aus. Dann brauchst du noch eine Delimiterset in form eines einfachen array. Da stehen alle Zeichen drin, die als whitespace gewertet werden. Du prüfst ab, ob das nächste Zeichen im delimiterspace steht mit strpos()>=0. Wenn ja, dann hast du möglicherweise ein Token erwischt -> strcmp(). Das Token bekommt eine id also eine Zahl. Zukünftig hast du es dann nur noch mit Zahlen zu tun. (Hash-)Tables lohnen sich erst ab einem gewissen Umfang. Mit linearer Suche solltest du anfangen. Dies ist dann das Scannermodul. Was fängst du damit an? Gibt es einen AST ?
erst mal vielen Dank für die vielen guten Vorschläge. Ich hatte (bei dem tollen Wetter) noch keine Zeit was zu testen. Wird ne zeitlang dauern bis ich alles verdaut habe. Ich schreibe dann aber auf jeden Fall wie ichs gemacht habe.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.