máquinas de estados tutoriales [cerrada]

https://stackoverflow.com/questions/1371460

21-09-2019
|

Pregunta

Me pregunto si alguien sabe de algunos buenos tutoriales en Internet para el desarrollo de las máquinas de estado. O libros electrónicos?

Estoy empezando a trabajar en máquinas de estado y sólo necesita algo general me refiero a.

Solución

Las máquinas de estado son muy simples en C si se utiliza punteros de función.

Básicamente se necesitan 2 arrays - uno para los punteros de función del estado y uno para las reglas de transición de estados. Cada función de estado devuelve el código, búsqueda en la tabla de transición de estado por estado y código de retorno para encontrar el siguiente estado y luego simplemente ejecutarlo.

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;
}

No pongo función lookup_transitions() ya que es trivial.

Esa es la forma en que hago las máquinas de estado durante años.

Otros consejos

Yo prefiero el uso de punteros de función por las declaraciones switch gigantescas, pero en contraste con la respuesta de normalmente no utilizo códigos de retorno explícitas o tablas de transición.

Además, en la mayoría de los casos usted querrá un mecanismo para pasar a lo largo de datos adicionales. He aquí un ejemplo de máquina de estado:

#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);
}

Las máquinas de estado no son algo que inherentemente necesita un tutorial que ser explicado o incluso utilizado. Lo que sugiero es que se echa un vistazo a los datos y la forma en que se deben analizar.

Por ejemplo, tuve que analizar el protocolo de datos para una Cerca computadora de vuelo del globo espacial , se almacenan los datos en la tarjeta SD en un formato específico (binario) que debía ser analizada a cabo en un archivo de coma separados. Usando una máquina de estados para este que tiene más sentido ya que dependiendo de lo que el siguiente bit de información es que tenemos que cambiar lo que está analizando.

El código está escrito en C ++, y está disponible como ParseFCU . Como se puede ver, se detecta por primera vez la versión que está analizando, y desde allí se entra dos máquinas de estados diferentes.

Se entra en la máquina de estados en un conocido buen estado, en ese momento cuando empezamos a analizar y en función de lo que nos encontramos con personajes que ya sea en movimiento al siguiente estado, o volver a un estado anterior. Básicamente, esto permite que el código de auto-adaptarse a la forma en que se almacenan los datos y si es o no seguro existe dato alguno incluso.

En mi ejemplo, la cadena de GPS no es un requisito para la computadora de vuelo para iniciar sesión, por lo que el procesamiento de la cadena de GPS puede ser saltado si se constata que los bytes que terminan por esa sola escritura de registro.

Las máquinas de estado son fáciles de escribir, y en general siguen la regla que debe fluir. De entrada a través del sistema debe fluir con cierta facilidad de estado a estado.

Por desgracia, la mayoría de los artículos en las máquinas de estado se escriben para C ++ u otros lenguajes que tienen el apoyo directo para el polimorfismo ya que es agradable para modelar los estados en una implementación FSM como clases que se derivan de una clase de estado abstracto.

Sin embargo, es bastante fácil de implementar máquinas de estado en C usando cualquiera de los interruptores declaraciones a eventos de despacho a los estados (por FSM simples, que prácticamente código correcto hacia arriba) o el uso de tablas para asignar eventos a las transiciones de estado.

Hay un par de sencillos, pero los artículos decentes en un marco básico para las máquinas de estado en C aquí:

Editar : Sitio "bajo mantenimiento", vínculos de archivo web:

máquinas de estado basada en la declaración switch menudo utilizan un conjunto de macros a 'esconder' la mecánica de la declaración switch (o utilizan un conjunto de declaraciones if / then / else en lugar de un switch) y hacen lo que equivale a un "FSM lenguaje" para la descripción de la máquina de estado en la fuente de C. Yo personalmente prefiero el enfoque basado en tablas, pero estos ciertamente tener mérito, son ampliamente utilizados, y pueden ser efectivos, especialmente para las MEF simples.

Un marco de este tipo se describe por Steve Rabin en " juego Gemas de programación" Capítulo 3.0 (Diseño de un robusto motor AI general) .

Un conjunto similar de macros se discute aquí:

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

Si también está interesado en C ++ implementaciones de máquina de estados que hay mucho más que se puede encontrar. Voy a publicar punteros si está interesado.

en tiempo real de modelado orientado a objetos fue fantástico (publicado en 1994 y ahora la venta por tan sólo 81 centavos de dólar, más $ 3.99 envío).

Esto es todo lo que necesita saber.

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;
    }
}

Hay una gran cantidad de lección para aprender handcrafting máquinas de estado en C, pero me dejó también sugieren Ragel compilador máquina de estados:

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

Tiene forma muy simple de definir las máquinas de estado y luego se puede generar gráficos, generar código en diferentes estilos (basada en tablas,-goto conducido), analizar el código si quieres, etc, y que es de gran alcance, puede ser utilizado en el código de producción para varios protocolos.

Las máquinas de estado puede ser muy compleja para un problema complejo. También están sujetos a errores inesperados. Se puede convertir en una pesadilla si alguien se encuentra con un error o necesita cambiar la lógica en el futuro. También son difíciles de seguir y de depuración sin el diagrama de estados. La programación estructurada es mucho mejor (por ejemplo, es probable que no se utiliza una máquina de estado a nivel de la línea principal). Se puede utilizar la programación estructurada, incluso en el contexto de interrupciones (que es donde se suelen utilizar máquinas de estado). Ver este artículo "Macros para simular múltiples tareas / bloqueo de código al nivel de interrupción " encontrar en codeproject.com.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow