Tutorials zu Zustandsmaschinen [closed]

Question 1

Ich frage mich nur, ob jemand einige gute Tutorials im Internet für die Entwicklung von Zustandsmaschinen kennt. Oder E-Books?

Ich fange an, an Zustandsmaschinen zu arbeiten und brauche nur etwas Allgemeines, um loszulegen.

Question 2

Zustandsmaschinen sind in C sehr einfach, wenn Sie Funktionszeiger verwenden.

Grundsätzlich benötigen Sie 2 Arrays – eines für Zustandsfunktionszeiger und eines für Zustandsübergangsregeln. Jede Zustandsfunktion gibt den Code zurück, Sie suchen die Zustandsübergangstabelle nach Zustand und Rückkehrcode, um den nächsten Zustand zu finden und ihn dann einfach auszuführen.

int entry_state(void);
int foo_state(void);
int bar_state(void);
int exit_state(void);

/* array and enum below must be in sync! */
int (* state[])(void) = { entry_state, foo_state, bar_state, exit_state};
enum state_codes { entry, foo, bar, end};

enum ret_codes { ok, fail, repeat};
struct transition {
    enum state_codes src_state;
    enum ret_codes   ret_code;
    enum state_codes dst_state;
};
/* transitions from end state aren't needed */
struct transition state_transitions[] = {
    {entry, ok,     foo},
    {entry, fail,   end},
    {foo,   ok,     bar},
    {foo,   fail,   end},
    {foo,   repeat, foo},
    {bar,   ok,     end},
    {bar,   fail,   end},
    {bar,   repeat, foo}};

#define EXIT_STATE end
#define ENTRY_STATE entry

int main(int argc, char *argv[]) {
    enum state_codes cur_state = ENTRY_STATE;
    enum ret_codes rc;
    int (* state_fun)(void);

    for (;;) {
        state_fun = state[cur_state];
        rc = state_fun();
        if (EXIT_STATE == cur_state)
            break;
        cur_state = lookup_transitions(cur_state, rc);
    }

    return EXIT_SUCCESS;
}

Ich lege nicht lookup_transitions() funktionieren, da es trivial ist.

So mache ich seit Jahren Zustandsmaschinen.

Question 3

Ich bevorzuge die Verwendung von Funktionszeigern gegenüber gigantisch switch Anweisungen, aber im Gegensatz zur Antwort von qrdl verwende ich normalerweise keine expliziten Rückgabecodes oder Übergangstabellen.

Außerdem möchten Sie in den meisten Fällen einen Mechanismus, um zusätzliche Daten weiterzugeben. Hier ist ein Beispiel für eine Zustandsmaschine:

#include <stdio.h>

struct state;
typedef void state_fn(struct state *);

struct state
{
    state_fn * next;
    int i; // data
};

state_fn foo, bar;

void foo(struct state * state)
{
    printf("%s %i\n", __func__, ++state->i);
    state->next = bar;
}

void bar(struct state * state)
{
    printf("%s %i\n", __func__, ++state->i);
    state->next = state->i < 10 ? foo : 0;
}

int main(void)
{
    struct state state = { foo, 0 };
    while(state.next) state.next(&state);
}

Question 4

Leider sind die meisten Artikel über Zustandsautomaten für C++ oder andere Sprachen geschrieben, die Polymorphismus direkt unterstützen, da es schön ist, die Zustände in einer FSM-Implementierung als Klassen zu modellieren, die von einer abstrakten Zustandsklasse abgeleitet sind.

Es ist jedoch ziemlich einfach, Zustandsmaschinen in C zu implementieren, indem Sie entweder switch-Anweisungen verwenden, um Ereignisse an Zustände zu senden (für einfache FSMs codieren sie ziemlich direkt) oder Tabellen verwenden, um Ereignisse Zustandsübergängen zuzuordnen.

Hier gibt es ein paar einfache, aber anständige Artikel über ein grundlegendes Framework für Zustandsmaschinen in C:

Bearbeiten: Website “in Wartung”, Webarchiv-Links:

switch Anweisungsbasierte Zustandsautomaten verwenden oft eine Reihe von Makros, um die Mechanik des zu „verbergen“. switch -Anweisung (oder verwenden Sie eine Reihe von if/then/else Aussagen statt a switch) und machen so etwas wie eine “FSM-Sprache” zum Beschreiben der Zustandsmaschine in C-Quelle. Ich persönlich bevorzuge den tabellenbasierten Ansatz, aber diese haben sicherlich Vorteile, sind weit verbreitet und können insbesondere für einfachere FSMs effektiv sein.

Ein solches Framework wird von Steve Rabin in skizziert „Edelsteine für die Spielprogrammierung“ Kapitel 3.0 (Entwurf einer allgemeinen robusten KI-Engine).

Ein ähnlicher Satz von Makros wird hier besprochen:

https://contrarymotion.net/2008/02/12/some-code-snippets-for-a-simple-c-state-machine/

Wenn Sie auch an Implementierungen von C++-Zustandsautomaten interessiert sind, gibt es noch viel mehr zu finden. Ich werde Hinweise posten, wenn Sie interessiert sind.

Question 5

Zustandsmaschinen sind nicht etwas, das von Natur aus ein Tutorial benötigt, um erklärt oder sogar verwendet zu werden. Was ich vorschlage, ist, dass Sie sich die Daten ansehen und wie sie analysiert werden müssen.

Zum Beispiel musste ich das Datenprotokoll für a analysieren Near Space Ballonflugcomputer, es speicherte Daten auf der SD-Karte in einem bestimmten Format (binär), das in eine kommagetrennte Datei analysiert werden musste. Die Verwendung einer Zustandsmaschine dafür ist am sinnvollsten, da wir je nachdem, was die nächste Information ist, ändern müssen, was wir analysieren.

Der Code wurde mit C++ geschrieben und ist verfügbar als ParseFCU. Wie Sie sehen können, erkennt es zuerst, welche Version wir parsen, und tritt von dort aus in zwei verschiedene Zustandsmaschinen ein.

Es tritt in einem bekanntermaßen guten Zustand in die Zustandsmaschine ein, an diesem Punkt beginnen wir mit dem Parsen und je nachdem, auf welche Zeichen wir stoßen, gehen wir entweder zum nächsten Zustand über oder kehren zu einem vorherigen Zustand zurück. Dadurch kann sich der Code im Wesentlichen selbst an die Art und Weise anpassen, wie die Daten gespeichert werden, und ob bestimmte Daten überhaupt existieren oder nicht.

In meinem Beispiel ist die GPS-Zeichenfolge für den Flugcomputer nicht zum Protokollieren erforderlich, sodass die Verarbeitung der GPS-Zeichenfolge übersprungen werden kann, wenn die Endbytes für diesen einzelnen Protokollschreibvorgang gefunden werden.

Zustandsmaschinen sind einfach zu schreiben, und im Allgemeinen folge ich der Regel, dass sie fließen sollte. Eingaben, die durch das System gehen, sollten mit einer gewissen Leichtigkeit von Zustand zu Zustand fließen.

Question 6

Das ist alles, was Sie wissen müssen.

int state = 0;
while (state < 3)
{
    switch (state)
    {
        case 0:
            // Do State 0 Stuff
            if (should_go_to_next_state)
            {
                state++;
            }
            break;
        case 1:
            // Do State 1 Stuff    
            if (should_go_back) 
            {
                state--;
            }    
            else if (should_go_to_next_state) 
            {
                state++;
            }
            break;
        case 2:
            // Do State 2 Stuff    
            if (should_go_back_two) 
            {
                state -= 2;
            }    
            else if (should_go_to_next_state) 
            {
                state++;
            }
            break;
        default:
            break;
    }
}

Question 7

Real-Time Object-Oriented Modeling war fantastisch (1994 veröffentlicht und jetzt für nur 81 Cent plus 3,99 $ Versand erhältlich).

Question 8

Es gibt eine Menge Lektionen, um Zustandsmaschinen in C herzustellen, aber lassen Sie mich auch den Ragel-Zustandsmaschinen-Compiler vorschlagen:

http://www.complang.org/ragel/

Es hat eine recht einfache Art, Zustandsmaschinen zu definieren, und dann können Sie Diagramme generieren, Code in verschiedenen Stilen generieren (tabellengesteuert, gotogesteuert), diesen Code analysieren, wenn Sie möchten usw. Und es ist leistungsstark und kann in der Produktion verwendet werden Code für verschiedene Protokolle.