Implementierungstechniken für FSM-Staaten

Question

Wie gehen Sie über FSM Implementierung (EDIT: Finite State Machine) Staaten? Ich denke, in der Regel um eine FSM wie eine Reihe von Funktionen, ein Dispatcher, und ein Gewinde, wie der aktuellen Fahrzustand anzuzeigen. Das heißt, ich blockierende Aufrufe zu Funktionen / functors darstellen Staaten.

Gerade jetzt habe ich eine in einem anderen Stil umgesetzt, wo I noch repräsentieren Staaten mit der Funktion (Objekt) s, aber der Faden nur ruft eine state->step() Methode, die versucht zurückzukehren schnellstens. Im Fall, dass der Zustand beendet und ein Übergang stattfinden soll, bedeutet dies, dass sich entsprechend. Ich würde dies nennen das ‚Polling‘ Stil, da die Funktionen meist aussehen wie:

void step()
{
  if(!HaveReachedGoal)
  {
    doWhateverNecessary();
    return; // get out as fast as possible
  }
  // ... test perhaps some more subgoals
  indicateTransition();
}

Ich bin mir bewusst, dass es sich um eine FSM innerhalb einer FSM ist.

Es fühlt sich eher simpel, aber es hat gewisse Vorteile. Während ein Thread blockiert wird, oder in einer Art gehalten von while (!CanGoForward)checkGoForward(); Schleife kann umständlich und unhandlich sein, die Abfrage fühlte sich viel leichter zu debuggen. Das ist, weil die FSM Objekt wieder die Kontrolle nach jeder Schritt, und setzt einige Debug-Informationen aus ist ein Kinderspiel.

Nun, ich von meiner Frage bin abweichend: Wie Sie implementieren Staaten von FSMs?

Answer 1

Der Staat Design Muster ist ein interessanter Weg, um eine FSM der Implementierung:

http://en.wikipedia.org/wiki/State_pattern

Es ist eine sehr saubere Art und Weise die FSM der Umsetzung, aber es kann chaotisch auf der Komplexität Ihrer FSM abhängig sein (aber nicht die Menge von Staaten). Allerdings sind die Vorteile, dass:

• Sie beseitigen Code-Duplizierung (vor allem, wenn / else-Anweisungen)
• Es ist einfacher, mit neuen Staaten zu verlängern
• haben Ihre Klassen besseren Zusammenhalt so alle damit verbundenen Logik an einem Ort - das ist auch der Code besser Schrift Tests für machen sollte
.

Es ist eine Java und C ++ Implementierung auf dieser Seite:

http://www.vincehuston.org/dp/state.html

Answer 2

Es gibt immer was ich den Flying Spaghetti Monster Stil nennen FSMs der Umsetzung (FSM-Stil FSMs): lotsa gotos verwenden. Zum Beispiel:

state1:
  do_something();
  goto state2;

state2:
  if (condition) goto state1;
  else           goto state3;

state3:
  accept;

Sehr schön Spaghetti-Code: -)

Answer 3

ich habe es als eine Tabelle, ein flaches Array im Speicher, ist jede Zelle ein Zustand. Bitte haben Sie einen Blick auf die cvs Quelle der dem verlassenen DFA Projekt . Für Beispiel :

class DFA {
    DFA();
    DFA(int mychar_groups,int mycharmap[256],int myi_state);
    ~DFA();
    void add_trans(unsigned int from,char sym,unsigned int to);
    void add_trans(unsigned int from,unsigned int symn,unsigned int to);
    /*adds a transition between state from to state to*/
    int add_state(bool accepting=false);
    int to(int state, int symn);
    int to(int state, char sym);
    void set_char(char used_chars[],int);
    void set_char(set<char> char_set);
    vector<int > table; /*contains the table of the dfa itself*/
    void normalize();

    vector<unsigned int> char_map;
    unsigned int char_groups; /*number of characters the DFA uses,
                    char_groups=0 means 1 character group is used*/
    unsigned int i_state; /*initial state of the DFA*/
    void switch_table_state(int first,int sec);
    unsigned int num_states;
    set<int > accepting_states;
};

Aber das war für einen sehr spezifischen Bedarf (Matching reguläre Ausdrücke)

Answer 4

Ich erinnere mich an meine erste FSM-Programm. Ich schrieb es in C mit einem sehr einfachen Schalter Erklärung. Der Wechsel von einem Zustand in einer anderen oder nach bis zum nächsten Zustand schien natürlich.

Dann fortgeschritten ich einen Tabellen-Lookup-Ansatz verwenden . Ich konnte einige sehr allgemeine Codierung Stil mit diesem Ansatz schreiben. Allerdings war ich ein paar Mal erwischt, wenn die Anforderungen geändert und ich muss einige zusätzliche Veranstaltungen unterstützen.

Ich habe keine FSMs in letzter Zeit geschrieben. Der letzte, den ich schrieb, war für ein Comms in C ++ Modul, wo ich eine „ Zustand Entwurfsmuster “, der in Verbindung mit einem „ Befehlsmuster “ (Aktion).

Answer 5

Wenn Sie eine komplexe Zustandsmaschine zu schaffen, dann sollten Sie SMC - die State Machine Compiler. Dies nimmt eine Textdarstellung einer Zustandsmaschine und kompiliert sie in die Sprache Ihrer Wahl - es unterstützt Java, C, C ++, C #, Python, Ruby, Scala und viele andere

.