www.mikrocontroller.net

Forum: Compiler & IDEs Wörter parsen


Autor: Stefan Gemmel (steg13)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Walter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
kann mir gerade nicht vorstellen wie du mit case Strings vergleichst ...

Autor: Winne (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Stefan Gemmel (steg13)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Wolfgang Horn (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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


Autor: Stock Hecht (winkelmesser)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: TheMason (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Max (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: NN (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
suche mal nach flex und bison. damit kannst du dir einen richtigen 
parser erstellen. wird im comilerbau verwendet!

Autor: A.K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Stefan Gemmel (steg13)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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.

Autor: Stefan Gemmel (steg13)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Sardaukar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: TheMason (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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).

Autor: Sardaukar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.


Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Uhu Uhuhu (uhu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ?






Autor: Stefan Gemmel (steg13)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.