C design della macchina di stato

Sto realizzando un piccolo progetto in misto C e C ++. Sto costruendo una piccola macchina da stato al centro di uno dei miei thread di lavoro.

Mi stavo chiedendo se i tuoi guru su SO condividessero le tue tecniche di progettazione delle macchine di stato.

NOTA: Sono principalmente dopo tecniche di implementazione collaudate.

AGGIORNATO: Sulla base di tutti gli ottimi input raccolti su SO, ho optato per questa architettura:

inserisci la descrizione dell'immagine qui

Le macchine di stato che ho progettato in precedenza (C, non C ++) sono tutte discese da un struct array e un loop. La struttura consiste fondamentalmente in uno stato e un evento (per la ricerca) e una funzione che restituisce il nuovo stato, qualcosa come:

 typedef struct { int st; int ev; int (*fn)(void); } tTransition; 

Quindi definisci i tuoi stati e eventi con semplici definizioni (gli ANY sono marcatori speciali, vedi sotto):

 #define ST_ANY -1 #define ST_INIT 0 #define ST_ERROR 1 #define ST_TERM 2 : : #define EV_ANY -1 #define EV_KEYPRESS 5000 #define EV_MOUSEMOVE 5001 

Quindi definisci tutte le funzioni chiamate dalle transizioni:

 static int GotKey (void) { ... }; static int FsmError (void) { ... }; 

Tutte queste funzioni sono scritte in modo da non accettare variabili e restituire il nuovo stato per la macchina a stati. In questo esempio le variabili globali vengono utilizzate per passare qualsiasi informazione nelle funzioni di stato dove necessario.

L’uso dei globals non è così male come sembra dato che l’FSM è solitamente bloccato all’interno di una singola unità di compilazione e tutte le variabili sono statiche per quell’unità (motivo per cui ho usato le virgolette su “globale” sopra – sono più condivise all’interno del FSM, che veramente globale). Come con tutti i globals, richiede attenzione.

L’array transitions definisce quindi tutte le transizioni possibili e le funzioni che vengono richiamate per tali transizioni (incluso l’ultimo catch-all):

 tTransition trans[] = { { ST_INIT, EV_KEYPRESS, &GotKey}, : : { ST_ANY, EV_ANY, &FsmError} }; #define TRANS_COUNT (sizeof(trans)/sizeof(*trans)) 

Ciò significa: se sei nello stato ST_INIT e ricevi l’evento EV_KEYPRESS , effettua una chiamata a GotKey .

Il funzionamento dell’FSM diventa quindi un ciclo relativamente semplice:

 state = ST_INIT; while (state != ST_TERM) { event = GetNextEvent(); for (i = 0; i < TRANS_COUNT; i++) { if ((state == trans[i].st) || (ST_ANY == trans[i].st)) { if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) { state = (trans[i].fn)(); break; } } } } 

Come accennato sopra, si noti l'uso di ST_ANY come wild-card, consentendo a un evento di chiamare una funzione indipendentemente dallo stato corrente. EV_ANY funziona anche in modo simile, consentendo a qualsiasi evento in uno stato specifico di chiamare una funzione.

Può anche garantire che, se si raggiunge la fine della serie di transizioni, si ottiene un errore che indica che FSM non è stato ST_ANY/EV_ANY correttamente (utilizzando la combinazione ST_ANY/EV_ANY .

Ho utilizzato un codice simile per questo su un gran numero di progetti di comunicazione, come l'implementazione precoce di stack di comunicazione e protocolli per sistemi embedded. Il grande vantaggio era la sua semplicità e relativa facilità nel cambiare l'array di transizioni.

Non ho dubbi che ci saranno astrazioni di livello superiore che potrebbero essere più adatte al giorno d'oggi, ma ho il sospetto che si riducano a questo stesso tipo di struttura.


E, come ldog stati di ldog in un commento, è ansible evitare del tutto le globali passando un puntatore di struttura a tutte le funzioni (e utilizzandolo nel ciclo degli eventi). Ciò consentirà a più macchine a stati di funzionare parallelamente senza interferenze.

Basta creare un tipo di struttura che trattiene i dati specifici della macchina (lo stato al minimo indispensabile) e usa quello al posto dei globali.

La ragione per cui raramente ho fatto questo è semplicemente perché la maggior parte delle macchine di stato che ho scritto sono state tipi singleton (ad esempio, una sola volta, all'avvio del processo, lettura del file di configurazione per esempio), non avendo bisogno di eseguire più di un'istanza . Ma ha valore se è necessario eseguire più di uno.

Le altre risposte sono buone, ma un’implementazione molto “leggera” che ho usato quando la macchina di stato è molto semplice assomiglia a:

 enum state { ST_NEW, ST_OPEN, ST_SHIFT, ST_END }; enum state current_state = ST_NEW; while (current_state != ST_END) { input = get_input(); switch (current_state) { case ST_NEW: /* Do something with input and set current_state */ break; case ST_OPEN: /* Do something different and set current_state */ break; /* ... etc ... */ } } 

Lo userei quando la macchina di stato è abbastanza semplice che l’approccio della tabella di transizione del puntatore e dello stato della funzione è eccessivo. Questo è spesso utile per l’analisi carattere per carattere o parola per parola.

Perdonami per aver infranto ogni regola dell’informatica, ma una macchina a stati è una delle poche (posso contare solo due posti in meno) in cui una dichiarazione goto non è solo più efficace, ma rende anche il tuo codice più pulito e più facile da leggere. Poiché le istruzioni goto si basano su etichette, puoi nominare i tuoi stati invece di dover tenere traccia di un pasticcio di numeri o utilizzare un enum. Rende anche molto più pulito il codice in quanto non è necessario tutto il cruft aggiuntivo di puntatori di funzione o enormi istruzioni switch e cicli while. Ho già detto che è più efficiente?

Ecco come potrebbe essere una macchina a stati:

 void state_machine() { first_state: // Do some stuff here switch(some_var) { case 0: goto first_state; case 1: goto second_state; default: return; } second_state: // Do some stuff here switch(some_var) { case 0: goto first_state; case 1: goto second_state; default: return; } } 

Hai un’idea generale. Il punto è che è ansible implementare la macchina a stati in modo efficace e che è relativamente facile da leggere e urla al lettore che sta guardando una macchina a stati. Nota che se stai usando le istruzioni goto , devi comunque stare attento dato che è molto facile spararti nel piede mentre lo fai.

Potresti considerare lo State Machine Compiler http://smc.sourceforge.net/

Questa splendida utility open source accetta una descrizione di una macchina a stati in un linguaggio semplice e la compila in una qualsiasi di una dozzina di lingue, incluse C e C ++. L’utilità stessa è scritta in Java e può essere inclusa come parte di una build.

Il motivo per farlo, piuttosto che la codifica manuale usando il pattern GoF State o qualsiasi altro approccio, è che una volta che la macchina di stato è espressa come codice, la struttura sottostante tende a scomparire sotto il peso del boilerplate che deve essere generato per supportarlo. L’utilizzo di questo approccio ti offre un’eccellente separazione delle preoccupazioni e tieni la struttura della tua macchina di stato ‘visibile’. Il codice generato automaticamente entra in moduli che non è necessario toccare, in modo da poter tornare indietro e armeggiare con la struttura della macchina di stato senza influire sul codice di supporto che hai scritto.

Scusate, sono troppo entusiasta, e senza dubbio ho messo tutti fuori. Ma è un’utilità di prim’ordine e ben documentata.

Assicurati di controllare il lavoro di Miro Samek (blog State Space , sito web State Machines & Tools ), i cui articoli sul C / C ++ Users Journal erano fantastici.

Il sito Web contiene un’implementazione completa (C / C ++) sia in licenza open source che commerciale di un framework di macchine a stati (QP Framework) , un gestore di eventi (QEP) , uno strumento di modellazione di base (QM) e uno strumento di tracciamento (QSpy) che consente di disegnare macchine di stato, creare codice ed eseguirne il debug.

Il libro contiene una spiegazione esauriente sul / cosa dell’implementazione e su come usarlo ed è anche un grande materiale per comprendere i fondamenti delle macchine a stati gerarchici e finiti.

Il sito Web contiene inoltre collegamenti a diversi pacchetti di supporto della scheda per l’utilizzo del software con piattaforms incorporate.

Ho fatto qualcosa di simile a ciò che descrive paxdiablo, ma invece di una serie di transizioni di stato / evento, ho impostato una matrice bidimensionale di puntatori di funzione, con il valore di evento come indice di un asse e il valore dello stato corrente come l’altro. Quindi chiamo state = state_table[event][state](params) e succede la cosa giusta. Le celle che rappresentano combinazioni di stato / evento non valide ottengono un puntatore a una funzione che lo dice, naturalmente.

Ovviamente, questo funziona solo se i valori di stato e di evento sono entrambi intervalli contigui e iniziano da 0 o abbastanza vicini.

Nel suo articolo, Stefan Heinzmann fornisce un “framework” molto bello basato su template.

Poiché non c’è alcun collegamento a un download di codice completo nell’articolo, mi sono preso la libertà di incollare il codice in un progetto e verificarlo. La roba qui sotto è testata e include i pochi pezzi mancanti, ma molto più ovvi.

L’innovazione principale qui è che il compilatore sta generando un codice molto efficiente. Le azioni di entrata / uscita vuote non hanno costi. Le azioni di entrata / uscita non vuote sono in linea. Il compilatore sta anche verificando la completezza dello statechart. Le azioni mancanti generano errori di collegamento. L’unica cosa che non viene catturata è la Top::init mancante.

Questa è un’alternativa molto bella all’implementazione di Miro Samek, se si può vivere senza ciò che manca – questo è lontano dall’implementazione di uno Statechart UML completo, sebbene implementa correttamente la semantica UML, mentre il codice di progettazione di Samek non gestisce exit / transition / azioni di entrata nell’ordine corretto.

Se questo codice funziona per quello che devi fare e hai un compilatore C ++ decente per il tuo sistema, probabilmente funzionerà meglio dell’implementazione C / C ++ di Miro. Il compilatore genera per te una implementazione della macchina di stato di transizione O (1) appiattita. Se la verifica dell’output dell’assieme conferma che le ottimizzazioni funzionano come desiderato, ci si avvicina alle prestazioni teoriche. La parte migliore: è un codice relativamente piccolo e facile da capire.

 #ifndef HSM_HPP #define HSM_HPP // This code is from: // Yet Another Hierarchical State Machine // by Stefan Heinzmann // Overload issue 64 december 2004 // http://accu.org/index.php/journals/252 /* This is a basic implementation of UML Statecharts. * The key observation is that the machine can only * be in a leaf state at any given time. The composite * states are only traversed, never final. * Only the leaf states are ever instantiated. The composite * states are only mechanisms used to generate code. They are * never instantiated. */ // Helpers // A gadget from Herb Sutter's GotW #71 -- depends on SFINAE template class IsDerivedFrom { class Yes { char a[1]; }; class No { char a[10]; }; static Yes Test(B*); // undefined static No Test(...); // undefined public: enum { Res = sizeof(Test(static_cast(0))) == sizeof(Yes) ? 1 : 0 }; }; template class Bool {}; // Top State, Composite State and Leaf State template  struct TopState { typedef H Host; typedef void Base; virtual void handler(Host&) const = 0; virtual unsigned getId() const = 0; }; template  struct CompState; template  > > struct CompState : B { typedef B Base; typedef CompState This; template  void handle(H& h, const X& x) const { Base::handle(h, x); } static void init(H&); // no implementation static void entry(H&) {} static void exit(H&) {} }; template  struct CompState > : TopState { typedef TopState Base; typedef CompState This; template  void handle(H&, const X&) const {} static void init(H&); // no implementation static void entry(H&) {} static void exit(H&) {} }; template  > > struct LeafState : B { typedef H Host; typedef B Base; typedef LeafState This; template  void handle(H& h, const X& x) const { Base::handle(h, x); } virtual void handler(H& h) const { handle(h, *this); } virtual unsigned getId() const { return id; } static void init(H& h) { h.next(obj); } // don't specialize this static void entry(H&) {} static void exit(H&) {} static const LeafState obj; // only the leaf states have instances }; template  const LeafState LeafState::obj; // Transition Object template  // Current, Source, Target struct Tran { typedef typename C::Host Host; typedef typename C::Base CurrentBase; typedef typename S::Base SourceBase; typedef typename T::Base TargetBase; enum { // work out when to terminate template recursion eTB_CB = IsDerivedFrom::Res, eS_CB = IsDerivedFrom::Res, eS_C = IsDerivedFrom::Res, eC_S = IsDerivedFrom::Res, exitStop = eTB_CB && eS_C, entryStop = eS_C || eS_CB && !eC_S }; // We use overloading to stop recursion. // The more natural template specialization // method would require to specialize the inner // template without specializing the outer one, // which is forbidden. static void exitActions(Host&, Bool) {} static void exitActions(Host&h, Bool) { C::exit(h); Tran::exitActions(h, Bool()); } static void entryActions(Host&, Bool) {} static void entryActions(Host& h, Bool) { Tran::entryActions(h, Bool()); C::entry(h); } Tran(Host & h) : host_(h) { exitActions(host_, Bool()); } ~Tran() { Tran::entryActions(host_, Bool()); T::init(host_); } Host& host_; }; // Initializer for Compound States template  struct Init { typedef typename T::Host Host; Init(Host& h) : host_(h) {} ~Init() { T::entry(host_); T::init(host_); } Host& host_; }; #endif // HSM_HPP 

Segue il codice di prova.

 #include  #include "hsm.hpp" #include "hsmtest.hpp" /* Implements the following state machine from Miro Samek's * Practical Statecharts in C/C++ * * |-init-----------------------------------------------------| * | s0 | * |----------------------------------------------------------| * | | * | |-init-----------| |-------------------------| | * | | s1 |---c--->| s2 | | * | |----------------|< --c----|-------------------------| | * | | | | | | * |<-d-| |-init-------| | | |-init----------------| | | * | | | s11 |<----f----| | s21 | | | * | /--| |------------| | | |---------------------| | | * | a | | | | | | | | | * | \->| | |------g--------->|-init------| | | | * | | |____________| | | |-b->| s211 |---g--->| * | |----b---^ |------f------->| | | | | * | |________________| | |< -d-|___________|<--e----| * | | |_____________________| | | * | |_________________________| | * |__________________________________________________________| */ class TestHSM; typedef CompState Top; typedef CompState S0; typedef CompState S1; typedef LeafState S11; typedef CompState S2; typedef CompState S21; typedef LeafState S211; enum Signal { A_SIG, B_SIG, C_SIG, D_SIG, E_SIG, F_SIG, G_SIG, H_SIG }; class TestHSM { public: TestHSM() { Top::init(*this); } ~TestHSM() {} void next(const TopState& state) { state_ = &state; } Signal getSig() const { return sig_; } void dispatch(Signal sig) { sig_ = sig; state_->handler(*this); } void foo(int i) { foo_ = i; } int foo() const { return foo_; } private: const TopState* state_; Signal sig_; int foo_; }; bool testDispatch(char c) { static TestHSM test; if (c< 'a' || 'h' template inline void State::handle(TestHSM& h, const X& x) const HSMHANDLER(S0) { switch (h.getSig()) { case E_SIG: { Tran t(h); printf("s0-E;"); return; } default: break; } return Base::handle(h, x); } HSMHANDLER(S1) { switch (h.getSig()) { case A_SIG: { Tran t(h); printf("s1-A;"); return; } case B_SIG: { Tran t(h); printf("s1-B;"); return; } case C_SIG: { Tran t(h); printf("s1-C;"); return; } case D_SIG: { Tran t(h); printf("s1-D;"); return; } case F_SIG: { Tran t(h); printf("s1-F;"); return; } default: break; } return Base::handle(h, x); } HSMHANDLER(S11) { switch (h.getSig()) { case G_SIG: { Tran t(h); printf("s11-G;"); return; } case H_SIG: if (h.foo()) { printf("s11-H"); h.foo(0); return; } break; default: break; } return Base::handle(h, x); } HSMHANDLER(S2) { switch (h.getSig()) { case C_SIG: { Tran t(h); printf("s2-C"); return; } case F_SIG: { Tran t(h); printf("s2-F"); return; } default: break; } return Base::handle(h, x); } HSMHANDLER(S21) { switch (h.getSig()) { case B_SIG: { Tran t(h); printf("s21-B;"); return; } case H_SIG: if (!h.foo()) { Tran t(h); printf("s21-H;"); h.foo(1); return; } break; default: break; } return Base::handle(h, x); } HSMHANDLER(S211) { switch (h.getSig()) { case D_SIG: { Tran t(h); printf("s211-D;"); return; } case G_SIG: { Tran t(h); printf("s211-G;"); return; } } return Base::handle(h, x); } #define HSMENTRY(State) \ template<> inline void State::entry(TestHSM&) { \ printf(#State "-ENTRY;"); \ } HSMENTRY(S0) HSMENTRY(S1) HSMENTRY(S11) HSMENTRY(S2) HSMENTRY(S21) HSMENTRY(S211) #define HSMEXIT(State) \ template<> inline void State::exit(TestHSM&) { \ printf(#State "-EXIT;"); \ } HSMEXIT(S0) HSMEXIT(S1) HSMEXIT(S11) HSMEXIT(S2) HSMEXIT(S21) HSMEXIT(S211) #define HSMINIT(State, InitState) \ template<> inline void State::init(TestHSM& h) { \ Init i(h); \ printf(#State "-INIT;"); \ } HSMINIT(Top, S0) HSMINIT(S0, S1) HSMINIT(S1, S11) HSMINIT(S2, S21) HSMINIT(S21, S211) 

La tecnica che mi piace per le macchine a stati (almeno quelle per il controllo del programma) è quella di utilizzare i puntatori di funzione. Ogni stato è rappresentato da una funzione diversa. La funzione accetta un simbolo di input e restituisce il puntatore alla funzione per lo stato successivo. I monitor centrali del ciclo di invio prendono l’input successivo, lo alimentano allo stato corrente e elaborano il risultato.

La digitazione su di esso diventa un po ‘strana, poiché C non ha un modo per indicare i tipi di puntatori di funzione che si restituiscono, quindi le funzioni di stato restituiscono void* . Ma puoi fare qualcosa del genere:

 typedef void* (*state_handler)(input_symbol_t); void dispatch_fsm() { state_handler current = initial_handler; /* Let's assume returning null indicates end-of-machine */ while (current) { current = current(get_input); } } 

Quindi le tue singole funzioni di stato possono triggersre il loro input per elaborare e restituire il valore appropriato.

Caso più semplice

 enum event_type { ET_THIS, ET_THAT }; union event_parm { uint8_t this; uint16_t that; } static void handle_event(enum event_type event, union event_parm parm) { static enum { THIS, THAT } state; switch (state) { case THIS: switch (event) { case ET_THIS: // Handle event. break; default: // Unhandled events in this state. break; } break; case THAT: // Handle state. break; } } 

Punti: lo stato è privato, non solo per l’unità di compilazione, ma anche per l’event_handler. Casi particolari possono essere gestiti separatamente dall’interruttore principale utilizzando qualsiasi costrutto ritenuto necessario.

Caso più complesso

Quando lo switch diventa più grande di un paio di schermate piene, dividilo in funzioni che gestiscono ogni stato, usando una tabella di stato per cercare direttamente la funzione. Lo stato è ancora privato per il gestore dell’evento. Le funzioni del gestore di stato restituiscono lo stato successivo. Se necessario, alcuni eventi possono ancora ricevere un trattamento speciale nel gestore dell’evento principale. Mi piace lanciare pseudo-eventi per l’entrata e l’uscita dallo stato e forse lo stato di avvio della macchina:

 enum state_type { THIS, THAT, FOO, NA }; enum event_type { ET_START, ET_ENTER, ET_EXIT, ET_THIS, ET_THAT, ET_WHATEVER, ET_TIMEOUT }; union event_parm { uint8_t this; uint16_t that; }; static void handle_event(enum event_type event, union event_parm parm) { static enum state_type state; static void (* const state_handler[])(enum event_type event, union event_parm parm) = { handle_this, handle_that }; enum state_type next_state = state_handler[state](event, parm); if (NA != next_state && state != next_state) { (void)state_handler[state](ET_EXIT, 0); state = next_state; (void)state_handler[state](ET_ENTER, 0); } } 

Non sono sicuro di aver individuato la syntax, in particolare per quanto riguarda la serie di puntatori di funzione. Non ho eseguito nulla di tutto ciò attraverso un compilatore. Dopo aver esaminato, ho notato che mi sono dimenticato di scartare esplicitamente lo stato successivo quando si gestiscono gli pseudo eventi (la parentesi (vuota) prima della chiamata a state_handler ()). Questo è qualcosa che mi piace fare anche se i compilatori accettano l’omissione in silenzio. Indica ai lettori del codice che “sì, volevo davvero chiamare la funzione senza usare il valore restituito”, e potrebbe impedire agli strumenti di analisi statici di avvertire al riguardo. Può essere idiosincratico perché non ricordo di aver visto nessun altro fare questo.

Punti: aggiungere un minimo di complessità (controllando se lo stato successivo è diverso dalla corrente), può evitare di duplicare il codice altrove, perché le funzioni del gestore di stato possono godere degli pseudo eventi che si verificano quando uno stato viene inserito e lasciato. Ricordare che lo stato non può cambiare quando si gestiscono gli pseudo eventi, perché il risultato del gestore di stato viene scartato dopo questi eventi. Ovviamente puoi scegliere di modificare il comportamento.

Un gestore di stato apparirebbe così:

 static enum state_type handle_this(enum event_type event, union event_parm parm) { enum state_type next_state = NA; switch (event) { case ET_ENTER: // Start a timer to do whatever. // Do other stuff necessary when entering this state. break; case ET_WHATEVER: // Switch state. next_state = THAT; break; case ET_TIMEOUT: // Switch state. next_state = FOO; break; case ET_EXIT: // Stop the timer. // Generally clean up this state. break; } return next_state; } 

Più complessità

Quando l’unità di compilazione diventa troppo grande (qualsiasi cosa tu pensi che sia, dovrei dire circa 1000 righe), metti ciascun gestore di stato in un file separato. Quando ciascun gestore di stati diventa più lungo di un paio di schermate, suddividere ciascun evento in una funzione separata, in modo simile al modo in cui l’interruttore di stato è stato suddiviso. Puoi farlo in molti modi, separatamente dallo stato o usando una tabella comune, o combinando vari schemi. Alcuni di loro sono stati coperti qui da altri. Ordina le tue tabelle e usa la ricerca binaria se la velocità è un requisito.

Programmazione generica

Mi piacerebbe che il preprocessore si occupasse di problemi come l’ordinamento delle tabelle o persino la generazione di macchine di stato dalle descrizioni, permettendoti di “scrivere programmi sui programmi”. Credo che questo sia ciò che le persone Boost stanno sfruttando per i modelli C ++, ma trovo la syntax criptica.

Tavoli bidimensionali

Ho usato tabelle stato / evento in passato, ma devo dire che per i casi più semplici non le trovo necessarie e preferisco la chiarezza e la leggibilità dell’istruzione switch anche se si estende oltre una schermata completa. Per i casi più complessi le tabelle diventano rapidamente sfuggite di mano come altri hanno notato. Gli idiomi che presento qui ti permettono di aggiungere un gran numero di eventi e stati quando ne hai voglia, senza dover mantenere una tabella che consuma memoria (anche se potrebbe essere una memoria di programma).

disconoscimento

Esigenze speciali possono rendere questi idiomi meno utili, ma li ho trovati molto chiari e mantenibili.

Estremamente testato, ma divertente da codificare, ora in una versione più raffinata della mia risposta originale; le versioni aggiornate possono essere trovate su mercurial.intuxication.org :

sm.h

 #ifndef SM_ARGS #error "SM_ARGS undefined: " \ "use '#define SM_ARGS (void)' to get an empty argument list" #endif #ifndef SM_STATES #error "SM_STATES undefined: " \ "you must provide a list of comma-separated states" #endif typedef void (*sm_state) SM_ARGS; static const sm_state SM_STATES; #define sm_transit(STATE) ((sm_state (*) SM_ARGS)STATE) #define sm_def(NAME) \ static sm_state NAME ## _fn SM_ARGS; \ static const sm_state NAME = (sm_state)NAME ## _fn; \ static sm_state NAME ## _fn SM_ARGS 

example.c

 #include  #define SM_ARGS (int i) #define SM_STATES EVEN, ODD #include "sm.h" sm_def(EVEN) { printf("even %i\n", i); return ODD; } sm_def(ODD) { printf("odd %i\n", i); return EVEN; } int main(void) { int i = 0; sm_state state = EVEN; for(; i < 10; ++i) state = sm_transit(state)(i); return 0; } 

Mi è piaciuta la risposta di paxdiable e ho deciso di implementare tutte le funzionalità mancanti per la mia applicazione come le variabili di guardia e i dati specifici dei computer di stato.

Ho caricato la mia implementazione in questo sito per condividerla con la community. È stato testato utilizzando IAR Embedded Workbench per ARM.

https://sourceforge.net/projects/compactfsm/

Another interesting open source tool is Yakindu Statechart Tools on statecharts.org . It makes use of Harel statecharts and thus provides hierarchical and parallel states and generates C and C++ (as well as Java) code. It does not make use of libraries but follows a ‘plain code’ approach. The code basically applies switch-case structures. The code generators can also be customized. Additionally the tool provides many other features.

Coming to this late (as usual) but scanning the answers to date I thinks something important is missing;

I have found in my own projects that it can be very helpful to not have a function for every valid state/event combination. I do like the idea of effectively having a 2D table of states/events. But I like the table elements to be more than a simple function pointer. Instead I try to organize my design so at it’s heart it comprises a bunch of simple atomic elements or actions. That way I can list those simple atomic elements at each intersection of my state/event table. The idea is that you don’t have to define a mass of N squared (typically very simple) functions. Why have something so error-prone, time consuming, hard to write, hard to read, you name it ?

I also include an optional new state, and an optional function pointer for each cell in the table. The function pointer is there for those exceptional cases where you don’t want to just fire off a list of atomic actions.

You know you are doing it right when you can express a lot of different functionality, just by editing your table, with no new code to write.

Alrght, I think mine’s just a little different from everybody else’s. A little more separation of code and data than I see in the other answers. I really read up on the theory to write this, which implements a full Regular-language (without regular expressions, sadly). Ullman, Minsky, Chomsky. Can’t say I understood it all, but I’ve drawn from the old masters as directly as possible: through their words.

I use a function pointer to a predicate that determines the transition to a ‘yes’ state or a ‘no’ state. This facilitates the creation of a finite state acceptor for a regular language that you program in a more assembly-language-like manner. Please don’t be put-off by my silly name choices. ‘czek’ == ‘check’. ‘grok’ == [go look it up in the Hacker Dictionary].

So for each iteration, czek calls a predicate function with the current character as argument. If the predicate returns true, the character is consumed (the pointer advanced) and we follow the ‘y’ transition to select the next state. If the predicate returns false, the character is NOT consumed and we follow the ‘n’ transition. So every instruction is a two-way branch! I must have been reading The Story of Mel at the time.

This code comes straight from my postscript interpreter , and evolved into its current form with much guidance from the fellows on comp.lang.c. Since postscript basically has no syntax (only requiring balanced brackets), a Regular Language Accepter like this functions as the parser as well.

 /* currentstr is set to the start of string by czek and used by setrad (called by israd) to set currentrad which is used by israddig to determine if the character in question is valid for the specified radix -- a little semantic checking in the syntax! */ char *currentstr; int currentrad; void setrad(void) { char *end; currentrad = strtol(currentstr, &end, 10); if (*end != '#' /* just a sanity check, the automaton should already have determined this */ || currentrad > 36 || currentrad < 2) fatal("bad radix"); /* should probably be a simple syntaxerror */ } /* character classes used as tests by automatons under control of czek */ char *alpha = "0123456789" "ABCDE" "FGHIJ" "KLMNO" "PQRST" "UVWXYZ"; #define EQ(a,b) a==b #define WITHIN(a,b) strchr(a,b)!=NULL int israd (int c) { if (EQ('#',c)) { setrad(); return true; } return false; } int israddig(int c) { return strchrnul(alpha,toupper(c))-alpha <= currentrad; } int isdot (int c) {return EQ('.',c);} int ise (int c) {return WITHIN("eE",c);} int issign (int c) {return WITHIN("+-",c);} int isdel (int c) {return WITHIN("()<>[]{}/%",c);} int isreg (int c) {return c!=EOF && !isspace(c) && !isdel(c);} #undef WITHIN #undef EQ /* the automaton type */ typedef struct { int (*pred)(int); int y, n; } test; /* automaton to match a simple decimal number */ /* /^[+-]?[0-9]+$/ */ test fsm_dec[] = { /* 0*/ { issign, 1, 1 }, /* 1*/ { isdigit, 2, -1 }, /* 2*/ { isdigit, 2, -1 }, }; int acc_dec(int i) { return i==2; } /* automaton to match a radix number */ /* /^[0-9]+[#][a-Z0-9]+$/ */ test fsm_rad[] = { /* 0*/ { isdigit, 1, -1 }, /* 1*/ { isdigit, 1, 2 }, /* 2*/ { israd, 3, -1 }, /* 3*/ { israddig, 4, -1 }, /* 4*/ { israddig, 4, -1 }, }; int acc_rad(int i) { return i==4; } /* automaton to match a real number */ /* /^[+-]?(d+(.d*)?)|(d*.d+)([eE][+-]?d+)?$/ */ /* represents the merge of these (simpler) expressions [+-]?[0-9]+\.[0-9]*([eE][+-]?[0-9]+)? [+-]?[0-9]*\.[0-9]+([eE][+-]?[0-9]+)? The complexity comes from ensuring at least one digit in the integer or the fraction with optional sign and optional optionally-signed exponent. So passing isdot in state 3 means at least one integer digit has been found but passing isdot in state 4 means we must find at least one fraction digit via state 5 or the whole thing is a bust. */ test fsm_real[] = { /* 0*/ { issign, 1, 1 }, /* 1*/ { isdigit, 2, 4 }, /* 2*/ { isdigit, 2, 3 }, /* 3*/ { isdot, 6, 7 }, /* 4*/ { isdot, 5, -1 }, /* 5*/ { isdigit, 6, -1 }, /* 6*/ { isdigit, 6, 7 }, /* 7*/ { ise, 8, -1 }, /* 8*/ { issign, 9, 9 }, /* 9*/ { isdigit, 10, -1 }, /*10*/ { isdigit, 10, -1 }, }; int acc_real(int i) { switch(i) { case 2: /* integer */ case 6: /* real */ case 10: /* real with exponent */ return true; } return false; } /* Helper function for grok. Execute automaton against the buffer, applying test to each character: on success, consume character and follow 'y' transition. on failure, do not consume but follow 'n' transition. Call yes function to determine if the ending state is considered an acceptable final state. A transition to -1 represents rejection by the automaton */ int czek (char *s, test *fsm, int (*yes)(int)) { int sta = 0; currentstr = s; while (sta!=-1 && *s) { if (fsm[sta].pred((int)*s)) { sta=fsm[sta].y; s++; } else { sta=fsm[sta].n; } } return yes(sta); } /* Helper function for toke. Interpret the contents of the buffer, trying automatons to match number formats; and falling through to a switch for special characters. Any token consisting of all regular characters that cannot be interpreted as a number is an executable name */ object grok (state *st, char *s, int ns, object *src, int (*next)(state *,object *), void (*back)(state *,int, object *)) { if (czek(s, fsm_dec, acc_dec)) { long num; num = strtol(s,NULL,10); if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) { error(st,limitcheck); /* } else if (num > INT_MAX || num < INT_MIN) { */ /* error(limitcheck, OP_token); */ } else { return consint(num); } } else if (czek(s, fsm_rad, acc_rad)) { long ra,num; ra = (int)strtol(s,NULL,10); if (ra > 36 || ra < 2) { error(st,limitcheck); } num = strtol(strchr(s,'#')+1, NULL, (int)ra); if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) { error(st,limitcheck); /* } else if (num > INT_MAX || num < INT_MAX) { */ /* error(limitcheck, OP_token); */ } else { return consint(num); } } else if (czek(s, fsm_real, acc_real)) { double num; num = strtod(s,NULL); if ((num==HUGE_VAL || num==-HUGE_VAL) && errno==ERANGE) { error(st,limitcheck); } else { return consreal(num); } } else switch(*s) { case '(': { int c, defer=1; char *sp = s; while (defer && (c=next(st,src)) != EOF ) { switch(c) { case '(': defer++; break; case ')': defer--; if (!defer) goto endstring; break; case '\\': c=next(st,src); switch(c) { case '\n': continue; case 'a': c = '\a'; break; case 'b': c = '\b'; break; case 'f': c = '\f'; break; case 'n': c = '\n'; break; case 'r': c = '\r'; break; case 't': c = '\t'; break; case 'v': c = '\v'; break; case '\'': case '\"': case '(': case ')': default: break; } } if (sp-s>ns) error(st,limitcheck); else *sp++ = c; } endstring: *sp=0; return cvlit(consstring(st,s,sp-s)); } case '< ': { int c; char d, *x = "0123456789abcdef", *sp = s; while (c=next(st,src), c!='>' && c!=EOF) { if (isspace(c)) continue; if (isxdigit(c)) c = strchr(x,tolower(c)) - x; else error(st,syntaxerror); d = (char)c < < 4; while (isspace(c=next(st,src))) /*loop*/; if (isxdigit(c)) c = strchr(x,tolower(c)) - x; else error(st,syntaxerror); d |= (char)c; if (sp-s>ns) error(st,limitcheck); *sp++ = d; } *sp = 0; return cvlit(consstring(st,s,sp-s)); } case '{': { object *a; size_t na = 100; size_t i; object proc; object fin; fin = consname(st,"}"); (a = malloc(na * sizeof(object))) || (fatal("failure to malloc"),0); for (i=0 ; objcmp(st,a[i]=toke(st,src,next,back),fin) != 0; i++) { if (i == na-1) (a = realloc(a, (na+=100) * sizeof(object))) || (fatal("failure to malloc"),0); } proc = consarray(st,i); { size_t j; for (j=0; j= nbuf-1) return false; *s++ = c; } *s = 0; if (!isspace(c) && c != EOF) back(st,c,src); /* eat interstice */ return true; } /* Helper function for Stoken Ftoken. Read a token from src using next and back. Loop until having read a bona-fide non-whitespace non-comment character. Call puff to read into buffer up to next delimiter or space. Call grok to figure out what it is. */ #define NBUF MAXLINE object toke (state *st, object *src, int (*next)(state *, object *), void (*back)(state *, int, object *)) { char buf[NBUF] = "", *s=buf; int c,sta = 1; object o; do { c=next(st,src); //if (c==EOF) return null; if (c=='%') { if (DUMPCOMMENTS) fputc(c, stdout); do { c=next(st,src); if (DUMPCOMMENTS) fputc(c, stdout); } while (c!='\n' && c!='\f' && c!=EOF); } } while (c!=EOF && isspace(c)); if (c==EOF) return null; *s++ = c; *s = 0; if (!isdel(c)) sta=puff(st, s,NBUF-1,src,next,back); if (sta) { o=grok(st,buf,NBUF-1,src,next,back); return o; } else { return null; } } 

boost.org comes with 2 different state chart implementations:

  • Meta State Machine
  • Statechart

As always, boost will beam you into template hell.

The first library is for more performance-critical state machines. The second library gives you a direct transition path from a UML Statechart to code.

Here’s the SO question asking for a comparison between the two where both of the authors respond.

This series of Ars OpenForum posts about a somewhat complicated bit of control logic includes a very easy-to-follow implementation as a state machine in C.

Saw this somewhere

 #define FSM #define STATE(x) s_##x : #define NEXTSTATE(x) goto s_##x FSM { STATE(x) { ... NEXTSTATE(y); } STATE(y) { ... if (x == 0) NEXTSTATE(y); else NEXTSTATE(x); } } 

Given that you imply you can use C++ and hence OO code, I would suggest evaluating the ‘GoF’state pattern (GoF = Gang of Four, the guys who wrote the design patterns book which brought design patterns into the limelight).

It is not particularly complex and it is widely used and discussed so it is easy to see examples and explanations on line.

It will also quite likely be recognizable by anyone else maintaining your code at a later date.

If efficiency is the worry, it would be worth actually benchmarking to make sure that a non OO approach is more efficient as lots of factors affect performance and it is not always simply OO bad, functional code good. Similarly, if memory usage is a constraint for you it is again worth doing some tests or calculations to see if this will actually be an issue for your particular application if you use the state pattern.

The following are some links to the ‘Gof’ state pattern, as Craig suggests:

Your question is quite generic,
Here are two reference articles that might be useful,

  1. Embedded State Machine Implementation

    This article describes a simple approach to implementing a state machine for an embedded system. For purposes of this article, a state machine is defined as an algorithm that can be in one of a small number of states. A state is a condition that causes a prescribed relationship of inputs to outputs, and of inputs to next states.
    A savvy reader will quickly note that the state machines described in this article are Mealy machines. A Mealy machine is a state machine where the outputs are a function of both present state and input, as opposed to a Moore machine, in which the outputs are a function only of state.

    • Coding State Machines in C and C++

      My preoccupation in this article is with state-machine fundamentals and some straightforward programming guidelines for coding state machines in C or C++. I hope that these simple techniques can become more common, so that you (and others) can readily see the state-machine structure right from the source code.

I have used State Machine Compiler in Java and Python projects to with success.

This is an old post with lots of answers, but I thought I’d add my own approach to the finite state machine in C. I made a Python script to produce the skeleton C code for any number of states. That script is documented on GituHub at FsmTemplateC

This example is based on other approaches I’ve read about. It doesn’t use goto or switch statements but instead has transition functions in a pointer matrix (look-up table). The code relies on a big multi-line initializer macro and C99 features (designated initializers and compound literals) so if you don’t like these things, you might not like this approach.

Here is a Python script of a turnstile example which generates skeleton C-code using FsmTemplateC :

 # dict parameter for generating FSM fsm_param = { # main FSM struct type string 'type': 'FsmTurnstile', # struct type and name for passing data to state machine functions # by pointer (these custom names are optional) 'fopts': { 'type': 'FsmTurnstileFopts', 'name': 'fopts' }, # list of states 'states': ['locked', 'unlocked'], # list of inputs (can be any length > 0) 'inputs': ['coin', 'push'], # map inputs to commands (next desired state) using a transition table # index of array corresponds to 'inputs' array # for this example, index 0 is 'coin', index 1 is 'push' 'transitiontable': { # current state | 'coin' | 'push' | 'locked': ['unlocked', ''], 'unlocked': [ '', 'locked'] } } # folder to contain generated code folder = 'turnstile_example' # function prefix prefix = 'fsm_turnstile' # generate FSM code code = fsm.Fsm(fsm_param).genccode(folder, prefix) 

The generated output header contains the typedefs:

 /* function options (EDIT) */ typedef struct FsmTurnstileFopts { /* define your options struct here */ } FsmTurnstileFopts; /* transition check */ typedef enum eFsmTurnstileCheck { EFSM_TURNSTILE_TR_RETREAT, EFSM_TURNSTILE_TR_ADVANCE, EFSM_TURNSTILE_TR_CONTINUE, EFSM_TURNSTILE_TR_BADINPUT } eFsmTurnstileCheck; /* states (enum) */ typedef enum eFsmTurnstileState { EFSM_TURNSTILE_ST_LOCKED, EFSM_TURNSTILE_ST_UNLOCKED, EFSM_TURNSTILE_NUM_STATES } eFsmTurnstileState; /* inputs (enum) */ typedef enum eFsmTurnstileInput { EFSM_TURNSTILE_IN_COIN, EFSM_TURNSTILE_IN_PUSH, EFSM_TURNSTILE_NUM_INPUTS, EFSM_TURNSTILE_NOINPUT } eFsmTurnstileInput; /* finite state machine struct */ typedef struct FsmTurnstile { eFsmTurnstileInput input; eFsmTurnstileCheck check; eFsmTurnstileState cur; eFsmTurnstileState cmd; eFsmTurnstileState **transition_table; void (***state_transitions)(struct FsmTurnstile *, FsmTurnstileFopts *); void (*run)(struct FsmTurnstile *, FsmTurnstileFopts *, const eFsmTurnstileInput); } FsmTurnstile; /* transition functions */ typedef void (*pFsmTurnstileStateTransitions)(struct FsmTurnstile *, FsmTurnstileFopts *); 
  • enum eFsmTurnstileCheck is used to determine whether a transition was blocked with EFSM_TURNSTILE_TR_RETREAT , allowed to progress with EFSM_TURNSTILE_TR_ADVANCE , or the function call was not preceded by a transition with EFSM_TURNSTILE_TR_CONTINUE .
  • enum eFsmTurnstileState is simply the list of states.
  • enum eFsmTurnstileInput is simply the list of inputs.
  • The FsmTurnstile struct is the heart of the state machine with the transition check, function lookup table, current state, commanded state, and an alias to the primary function that runs the machine.
  • Every function pointer (alias) in FsmTurnstile should only be called from the struct and has to have its first input as a pointer to itself so as to maintain a persistent state, object-oriented style.

Now for the function declarations in the header:

 /* fsm declarations */ void fsm_turnstile_locked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_locked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_unlocked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_unlocked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts); void fsm_turnstile_run (FsmTurnstile *fsm, FsmTurnstileFopts *fopts, const eFsmTurnstileInput input); 

Function names are in the format {prefix}_{from}_{to} , where {from} is the previous (current) state and {to} is the next state. Note that if the transition table does not allow for certain transitions, a NULL pointer instead of a function pointer will be set. Finally, the magic happens with a macro. Here we build the transition table (matrix of state enums) and the state transition functions look up table (a matrix of function pointers):

 /* creation macro */ #define FSM_TURNSTILE_CREATE() \ { \ .input = EFSM_TURNSTILE_NOINPUT, \ .check = EFSM_TURNSTILE_TR_CONTINUE, \ .cur = EFSM_TURNSTILE_ST_LOCKED, \ .cmd = EFSM_TURNSTILE_ST_LOCKED, \ .transition_table = (eFsmTurnstileState * [EFSM_TURNSTILE_NUM_STATES]) { \ (eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \ EFSM_TURNSTILE_ST_UNLOCKED, \ EFSM_TURNSTILE_ST_LOCKED \ }, \ (eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \ EFSM_TURNSTILE_ST_UNLOCKED, \ EFSM_TURNSTILE_ST_LOCKED \ } \ }, \ .state_transitions = (pFsmTurnstileStateTransitions * [EFSM_TURNSTILE_NUM_STATES]) { \ (pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \ fsm_turnstile_locked_locked, \ fsm_turnstile_locked_unlocked \ }, \ (pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \ fsm_turnstile_unlocked_locked, \ fsm_turnstile_unlocked_unlocked \ } \ }, \ .run = fsm_turnstile_run \ } 

When creating the FSM, the macro FSM_EXAMPLE_CREATE() has to be used.

Now, in the source code every state transition function declared above should be populated. The FsmTurnstileFopts struct can be used to pass data to/from the state machine. Every transition must set fsm->check to be equal to either EFSM_EXAMPLE_TR_RETREAT to block it from transitioning or EFSM_EXAMPLE_TR_ADVANCE to allow it to transition to the commanded state. A working example can be found at (FsmTemplateC)[ https://github.com/ChisholmKyle/FsmTemplateC%5D .

Here is the very simple actual usage in your code:

 /* create fsm */ FsmTurnstile fsm = FSM_TURNSTILE_CREATE(); /* create fopts */ FsmTurnstileFopts fopts = { .msg = "" }; /* initialize input */ eFsmTurnstileInput input = EFSM_TURNSTILE_NOINPUT; /* main loop */ for (;;) { /* wait for timer signal, inputs, interrupts, whatever */ /* optionally set the input (my_input = EFSM_TURNSTILE_IN_PUSH for example) */ /* run state machine */ my_fsm.run(&my_fsm, &my_fopts, my_input); } 

All that header business and all those functions just to have a simple and fast interface is worth it in my mind.

You could use the open source library OpenFST .

OpenFst is a library for constructing, combining, optimizing, and searching weighted finite-state transducers (FSTs). Weighted finite-state transducers are automata where each transition has an input label, an output label, and a weight. The more familiar finite-state acceptor is represented as a transducer with each transition’s input and output label equal. Finite-state acceptors are used to represent sets of strings (specifically, regular or rational sets); finite-state transducers are used to represent binary relations between pairs of strings (specifically, rational transductions). The weights can be used to represent the cost of taking a particular transition.

 void (* StateController)(void); void state1(void); void state2(void); void main() { StateController=&state1; while(1) { (* StateController)(); } } void state1(void) { //do something in state1 StateController=&state2; } void state2(void) { //do something in state2 //Keep changing function direction based on state transition StateController=&state1; } 

I personally use self referencing structs in combination with pointer arrays. I uploaded a tutorial on github a while back, link:

https://github.com/mmelchger/polling_state_machine_c

Note: I do realise that this thread is quite old, but I hope to get input and thoughts on the design of the state-machine as well as being able to provide an example for a possible state-machine design in C.