Parser programmieren

Bigwill

Ich will für ein Projekt, in welchem man über eine Com-Schnittstelle mit einem Roboter kommuniziert einen Parser für die Kommunikationsbefehle programmieren und vorm übermitteln dieser befehle an den Roboter die Richtigkeit der Syntax zu überprüfen.

Allerdings habe ich keine Ahnung von Parsern und das was ich bis jetzt in der Hilfe und bei Google gefunden hat, hat mich entweder erschlagen oder net wirklich geholfen, deshalb stell ich hier jetzt mal ein paar Fragen.

1. Wie vergleiche ich am besten den zu parsenden Text char* mit den Befehlen (Damit das ganze ziemlich schnell ist?)

2. Wie legt man die Befehle ab, ich dachte an eine aufsteigend sortierte Liste?

3. Dauert das nicht ziemlich lange jedes Wort mit mit der kompleten Befehlsliste zu vergleichen?

ich such inzwischen mal weiter in Google.

*aleph_0

Falls dein C++-Compiler keine Probleme mit Templates hat, würde ich Spirit dafür nehmen.

Bigwill

Ich konnte dem jetzt nicht ganz entnehmen, ob ich das einfach so einsetzen darf. Schließlich ist mein Projekt(auf Arbeit) ja kommerziell.

Falls ich darf, würde mich die Klärun der fragen natürlich trotzdem noch interessieren.

Aber danke schonmal für den Link.

rüdiger

jo, kannst du benutzen, das spirit zu boost gehört, muss die genutze Lizenz folgenden Lizenz Anforderungen unterliegen

http://www.boost.org/more/lib_guide.htm#License

Bigwill

Wären also nur noch meine Fragen oben zu beantworten, weil ichs trotzdem mal gerne probieren möchte selber umzusetzen.

Jester

Das kommt sehr auf die Syntax der Sprache an, sowas kann beliebig kompliziert werden. Aber auch relativ einfach.

Also zunächst mußt Du die Eingabe in Tokens zerlegen. Also irgendwie entscheiden, wo Du den Text-Strom auftrennst.

in C++ zum Beispiel:

int x=a+b;

da liest der Compiler nicht 'int', 'x=a+b'
sondern 'int', 'x', '=', 'a', '+' , 'b'
er trennt also sinnvoll auf. Da Variablennamen kein '+' enthalten können muß der Bezeichner dort fertig sein und das + gehört zu was anderem. Also erstmal Tokens basteln. Da gibts auch fertige Sachen in der C++ Lib.

Anschließend mußte prüfen. ob die Tokens denn so wie sie da kommen Sinn machen. Eben von der Reihenfolge her und so.
Dafür ist wahrscheinlich ein Automat geeignet (dies ist der Punkte wo für komplexere Sprachen ganz üble andere Dinge notwendig sind), daher solltest Du dazu mal was lesen.
Im Prinzip ist ein Automat eine Art Maschine (abstrakt, gibts nicht wirklich), sie befindet sich immer in einem gewissen Zustand. Wenn sie eine Eingabe erhält, dann kann sie eine Ausgabe tätigen und den Zustand wechseln. Das geschieht abhängig vom aktuellen Zustand, sodaß der Automat je nach Zustand unterschiedlich auf Eingaben reagieren kann.
Dann gibt es noch Finalzustände, wenn der Automat nach Eingabe Deiner Befehlskette in einem Finalzustand ist, dann heißt das, die Eingabe wurde akzeptiert und ist damit okay. Den Automat mußte Dir halt auf Papier mal bauen. Da gibts mit Sicherheit ne Menge Infos im Netz dazu.

Ein einfaches Beispiel noch, der Getränkeautomat:

Er hat zwei Zustände: 1. Warten auf Geld, 2. Auswahl des Getränks

er startet im Zustand warten auf Geld, wenn jetzt jemand auf die Auswahlknöpfe drückt, dann tut er nichts (oder gibt ne Meldung aus, daß erst Geld rein muß) und bleibt im Wartezustand.

Schmeißt aber jemand Geld rein, dann wechselt er in Zustand2 und sagt man soll sich was aussuchen.

Im Zustand2 gibt es zwei Möglichkeiten: Entweder ich drücke auf Rückgabe, dann krieg ich das Geld wieder raus, oder ich drücke auf eine Auswahltaste für ein Getränk und erhalte dieses.

In beiden Fällen wechselt der Automat in den Zustand 1 zurück.

Wie gesagt, es gibt dazu ne Menge Infos im Netz. Außerdem kann man sich das graphisch sehr schön veranschaulichen, da ist dann alles sehr einfach.

Zum Abschluß nochmal ein paar Suchwörter:

Automatentheorie, deterministische endliche Automaten (DEA), DFA, NFA

MfG Jester

junix

Äh hab ich dich richtig verstanden? Du Sprichst von einer State-Machine oder?

-junix

Jester

Jo, für die Leute die Anglizismen mögen.

junix

Das hat nix mit dem Mögen von Anglizismen zu tun. State-Machine ist nunmal der korrekte Begriff. Hättest du statt "Automat" (worunter sich niemand was vorstellen kann) State-machine geschrieben, hätte ich nicht deine Beschreibung lesen brauchen, wonach ich immer noch nicht sicher war ob ich wirklich das Selbe meine... Ausserdem gibt State-Machine einen wunderschönen Suchbegriff ab, der Präzis das zu Tage fördert, was du willst... Such mal im Google nach Automat (o;

In diesem Thread hier kams grad auch zu der Bemerkung "Interessant, dass so simple Dinge so komplizierte Namen haben". Shade hat darauf ne gute Antwort geliefert, die auch ier ihre Gültigkeit besitzt.

-junix

Bashar

junix schrieb:

State-Machine ist nunmal der korrekte Begriff. Hättest du statt "Automat" (worunter sich niemand was vorstellen kann)

Du solltest nicht von dir auf andere schließen. Automat ist der übliche Fachbegriff.

junix

Naja hier in der Schweiz hab ich den Begriff "Automat" anstelle von state-Machine noch nie angetroffen... aber egal..

-junix

Deutsch: Automat
Englisch: State-Machine

So einfach ist das.

Bashar

Deutsch: Zustandsmaschine
Englisch: Automaton

steht sogar bei leo.org

finite state machine [abbr.: FSM] [comp.] -> endlicher Automat

Jester

Die englischen Fachbegriffe sind meines Wissens:

DFA (Deterministic Finite Automaton) und NFA (Nondeterministic Finite Automaton)

State-Machine habe ich des öfteren schon von Leuten gehört, die sowas immer wieder mal implementieren, aber sonst keine Theorie dazu gemacht haben.
Das scheint so der gängige Name für Praktiker zu sein.

Außerdem liefern die von mir angegebenen Suchbegriffe durchaus gute Ergebnisse bei google.
Wenn Du zu Automat noch Informatik dazuschreibst bringt google auch schon ganz ordentliche Sachen. Insofern scheint mir Shades Einwand hier nicht zu greifen