Existe-t-il un modèle typique de mise en œuvre d'un automate à états ?

Question

Nous devons implémenter une machine à états simple dans C .
Une déclaration d'interrupteur standard est-elle la meilleure solution ?
Nous avons une situation actuelle (état) et un déclencheur pour la transition.

switch(state)
{
  case STATE_1:
     state = DoState1(transition);
     break;
  case STATE_2:
     state = DoState2(transition);
     break;
}
...
DoState2(int transition)
{
   // Do State Work
   ...
   if(transition == FROM_STATE_2) {
     // New state when doing STATE 2 -> STATE 2
   }
   if(transition == FROM_STATE_1) {
    // New State when moving STATE 1 -> STATE 2
   }
   return new_state;
}

Y a-t-il un meilleur moyen pour les machines à états simples

EDIT : Pour le C++, je pense que le Boost Carte d'état la bibliothèque pourrait être la solution. Cependant, elle ne pas aide avec le C. Concentrons-nous sur le cas d'utilisation du C.

Answer 1

Je préfère utiliser une approche basée sur des tableaux pour la plupart des machines à états :

typedef enum { STATE_INITIAL, STATE_FOO, STATE_BAR, NUM_STATES } state_t;
typedef struct instance_data instance_data_t;
typedef state_t state_func_t( instance_data_t *data );

state_t do_state_initial( instance_data_t *data );
state_t do_state_foo( instance_data_t *data );
state_t do_state_bar( instance_data_t *data );

state_func_t* const state_table[ NUM_STATES ] = {
    do_state_initial, do_state_foo, do_state_bar
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    return state_table[ cur_state ]( data );
};

int main( void ) {
    state_t cur_state = STATE_INITIAL;
    instance_data_t data;

    while ( 1 ) {
        cur_state = run_state( cur_state, &data );

        // do other program logic, run other state machines, etc
    }
}

Cela peut bien sûr être étendu pour prendre en charge plusieurs machines à états, etc. Les actions de transition peuvent également être prises en compte :

typedef void transition_func_t( instance_data_t *data );

void do_initial_to_foo( instance_data_t *data );
void do_foo_to_bar( instance_data_t *data );
void do_bar_to_initial( instance_data_t *data );
void do_bar_to_foo( instance_data_t *data );
void do_bar_to_bar( instance_data_t *data );

transition_func_t * const transition_table[ NUM_STATES ][ NUM_STATES ] = {
    { NULL,              do_initial_to_foo, NULL },
    { NULL,              NULL,              do_foo_to_bar },
    { do_bar_to_initial, do_bar_to_foo,     do_bar_to_bar }
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    state_t new_state = state_table[ cur_state ]( data );
    transition_func_t *transition =
               transition_table[ cur_state ][ new_state ];

    if ( transition ) {
        transition( data );
    }

    return new_state;
};

L'approche basée sur les tableaux est plus facile à maintenir et à étendre et plus simple à mettre en correspondance avec les diagrammes d'état.

Answer 2

Vous avez peut-être vu ma réponse à une autre question C où j'ai mentionné le FSM ! Voici comment je procède :

FSM {
  STATE(x) {
    ...
    NEXTSTATE(y);
  }

  STATE(y) {
    ...
    if (x == 0) 
      NEXTSTATE(y);
    else 
      NEXTSTATE(x);
  }
}

Avec les macros suivantes définies

#define FSM
#define STATE(x)      s_##x :
#define NEXTSTATE(x)  goto s_##x

Elle peut être modifiée pour s'adapter au cas particulier. Par exemple, vous pouvez avoir un fichier FSMFILE que vous voulez piloter votre FSM, vous pouvez donc incorporer l'action de lire la char suivante dans la macro elle-même :

#define FSM
#define STATE(x)         s_##x : FSMCHR = fgetc(FSMFILE); sn_##x :
#define NEXTSTATE(x)     goto s_##x
#define NEXTSTATE_NR(x)  goto sn_##x

Vous avez maintenant deux types de transitions : l'une passe à un état et lit un nouveau caractère, l'autre passe à un état sans consommer d'entrée.

Vous pouvez également automatiser la gestion des EOF avec quelque chose comme :

#define STATE(x)  s_##x  : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
                             goto sx_endfsm;\
                  sn_##x :

#define ENDFSM    sx_endfsm:

L'avantage de cette approche est que vous pouvez directement traduire un diagramme d'état que vous dessinez en code fonctionnel et, inversement, vous pouvez facilement dessiner un diagramme d'état à partir du code.

Dans d'autres techniques d'implémentation de FSM, la structure des transitions est enfouie dans des structures de contrôle (while, if, switch ...) et contrôlée par la valeur des variables (typiquement un state ) et il peut s'avérer complexe de relier le beau diagramme à un code alambiqué.

J'ai appris cette technique dans un article paru dans le grand magazine "Computer Language" qui, malheureusement, n'est plus publié.

Answer 3

Il y a aussi le grille logique ce qui est plus facile à maintenir lorsque la machine à états devient plus grande.

Answer 4

Pour une machine à états simple, il suffit d'utiliser une instruction switch et un type enum pour votre état. Effectuez vos transitions dans l'instruction switch en fonction de votre entrée. Dans un programme réel, vous changerez évidemment le "if(input)" pour vérifier vos points de transition. J'espère que cela vous aidera.

typedef enum
{
    STATE_1 = 0,
    STATE_2,
    STATE_3
} my_state_t;

my_state_t state = STATE_1;

void foo(char input)
{
    ...
    switch(state)
    {
        case STATE_1:
            if(input)
                state = STATE_2;
            break;
        case STATE_2:
            if(input)
                state = STATE_3;
            else
                state = STATE_1;
            break;
        case STATE_3:
            ...
            break;
    }
    ...
}

Answer 5

Considérez également le travail de Miro Samek et son site web .