Diseño de máquina de estado C [cerrado]

193

Estoy elaborando un pequeño proyecto en C y C ++ mixtos. Estoy construyendo una máquina de estado pequeña en el corazón de uno de mis hilos de trabajo.

Me preguntaba si ustedes, los gurús de SO, compartirían sus técnicas de diseño de máquinas de estado.

NOTA: Estoy principalmente después de técnicas de implementación probadas.

ACTUALIZADO: Basado en toda la gran aportación recopilada en SO, me he decidido por esta arquitectura:

An event pump points to an event integrator which points to a dispatcher. The dispatcher points to 1 through n actions which point back to the event integrator. A transition table with wildcards points to the dispatcher.

jldupont
fuente
44
Las respuestas aquí son muy buenas. También mire esta pregunta duplicada que también tiene varias buenas respuestas: stackoverflow.com/questions/1371460/state-machines-tutorials
Michael Burr el
2
Esto también es interesante: stackoverflow.com/questions/133214/…
Daniel Daranas el
Ver también esta pregunta .
Daniel Daranas

Respuestas:

170

Las máquinas de estado que he diseñado antes (C, no C ++) se han reducido a una structmatriz y un bucle. La estructura consiste básicamente en un estado y evento (para búsqueda) y una función que devuelve el nuevo estado, algo así como:

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

Luego, define sus estados y eventos con definiciones simples (los ANYque son marcadores especiales, ver más abajo):

#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

Luego define todas las funciones que son llamadas por las transiciones:

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

Todas estas funciones están escritas para no tomar variables y devolver el nuevo estado para la máquina de estados. En este ejemplo, las variables globales se utilizan para pasar cualquier información a las funciones de estado cuando sea necesario.

Usar globals no es tan malo como parece, ya que el FSM generalmente está encerrado dentro de una sola unidad de compilación y todas las variables son estáticas en esa unidad (es por eso que usé citas alrededor de "global" arriba, son más compartidas dentro del FSM, que verdaderamente global). Como con todos los globales, requiere cuidado.

La matriz de transiciones luego define todas las transiciones posibles y las funciones que se llaman para esas transiciones (incluida la última captura general):

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

Lo que eso significa es: si está en el ST_INITestado y recibe el EV_KEYPRESSevento, llame al GotKey.

El funcionamiento del FSM se convierte en un ciclo relativamente simple:

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

Como se mencionó anteriormente, tenga en cuenta el uso de ST_ANYcomo comodines, lo que permite que un evento llame a una función sin importar el estado actual.EV_ANYtambién funciona de manera similar, permitiendo que cualquier evento en un estado específico llame a una función.

También puede garantizar que, si llega al final de la matriz de transiciones, obtiene un error que indica que su FSM no se ha creado correctamente (mediante el uso de la ST_ANY/EV_ANYcombinación.

He utilizado un código similar para esto en muchos proyectos de comunicaciones, como una implementación temprana de pilas de comunicaciones y protocolos para sistemas integrados. La gran ventaja era su simplicidad y relativa facilidad para cambiar la matriz de transiciones.

No tengo dudas de que habrá abstracciones de nivel superior que pueden ser más adecuadas hoy en día, pero sospecho que todas se reducirán a este mismo tipo de estructura.


Y como ldog dice en un comentario, puede evitar las variables globales pasando un puntero de estructura a todas las funciones (y usándolo en el bucle de eventos). Esto permitirá que varias máquinas de estado funcionen una al lado de la otra sin interferencia.

Simplemente cree un tipo de estructura que contenga los datos específicos de la máquina (estado como mínimo) y úselos en lugar de los globales.

La razón por la que rara vez lo he hecho es simplemente porque la mayoría de las máquinas de estado que he escrito han sido de tipo único (por ejemplo, al inicio del proceso, lectura de archivos de configuración, por ejemplo), sin necesidad de ejecutar más de una instancia . Pero tiene valor si necesita ejecutar más de uno.

paxdiablo
fuente
24
Un interruptor gigante mezcla el código con el FSM. Incluso si solo hay una llamada de función por transición, todavía hay algo de código, y es fácil para alguien abusar de eso simplemente agregando una pequeña transición de 4 líneas en línea. gallina de diez líneas. Luego se sale de control. Con la matriz de estructura, el FSM se mantiene limpio: puede ver cada transición y el efecto (función). Y cuando empecé enumeraciones eran un destello en el ojo de la ISO, la escritura de código de 6809 plataformas integradas con los compiladores que eran, digamos, menos que perfecto :-)
paxdiablo
55
Tienes razón, las enumeraciones serían mejores, pero todavía prefiero tener el FSM como una matriz de estructura. Entonces todo se ejecuta por datos en lugar de código (bueno, hay algo de código, pero la posibilidad de rellenar ese bucle FSM que di es escasa).
paxdiablo
2
Esto es bueno, para las máquinas de estado de control de proceso solía agregar siempre tres subestados (posiblemente vacíos) para cada estado, de modo que la llamada para una función de estado se convertiría en GotKey (subestado), donde el subestado sería: - SS_ENTRY - SS_RUN - SS_EXIT Básicamente, la función de estado se llama con un subestado SS_ENTRY en la entrada, para que el estado pueda reconstruir un estado (por ejemplo, posiciones de actuadores). Si bien no hay transición, se pasa el valor del subestado SS_RUN. Tras la transición, se llama a la función de estado con el subestado SS_EXIT, para que pueda realizar cualquier limpieza (por ejemplo, desasignar recursos).
Metiu
13
Usted mencionó que comparte datos utilizando globales, pero probablemente sería más claro si define las funciones de estado int (*fn)(void*);donde void*está el puntero a los datos que cada función de estado toma como parámetro. Entonces las funciones de estado pueden usar los datos o ignorarlos.
ldog
13
Utilizo la misma separación de datos / código para escribir FSM, excepto que nunca se me ocurrió introducir estados 'comodín'. ¡Idea interesante! Sin embargo, iterar la matriz de transiciones puede ser costoso si tiene muchos estados (que fue el caso para mí ya que el código C se generó automáticamente). En tales situaciones, sería más eficiente tener una matriz de transiciones por estado. Entonces, un estado ya no es un valor de enumeración, sino una tabla de transición. De esa manera, no tiene que iterar sobre todas las transiciones en la máquina, sino solo aquellas que son relevantes para el estado actual.
Frerich Raabe
78

Las otras respuestas son buenas, pero una implementación muy "ligera" que he usado cuando la máquina de estados es muy simple parece:

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 usaría cuando la máquina de estado sea lo suficientemente simple como para que el puntero de función y el enfoque de la tabla de transición de estado sean excesivos. Esto suele ser útil para el análisis de caracteres por caracteres o de palabra por palabra.

coste y flete
fuente
37

Discúlpeme por romper todas las reglas en informática, pero una máquina de estados es uno de los pocos lugares (puedo contar solo dos), donde una gotodeclaración no solo es más eficiente, sino que también hace que su código sea más limpio y fácil de leer. Debido a que las gotodeclaraciones se basan en etiquetas, puede nombrar sus estados en lugar de tener que hacer un seguimiento de un desorden de números o usar una enumeración. También proporciona un código mucho más limpio, ya que no necesita todos los punteros extra crudos de funciones o grandes declaraciones de cambio y bucles while. ¿Mencioné que también es más eficiente?

Así es como se vería una máquina de estados:

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

Tienes la idea general. El punto es que puede implementar la máquina de estado de una manera eficiente y que sea relativamente fácil de leer y le grita al lector que está mirando una máquina de estado. Tenga en cuenta que si está usando gotodeclaraciones, debe tener cuidado ya que es muy fácil dispararse en el pie mientras lo hace.

Jason E
fuente
44
Esto solo funciona si la máquina de estado está en el objeto de nivel superior. En el momento en que algún otro objeto que ocasionalmente se sondea / envía mensajes, necesita tener un estado, estás atrapado con este enfoque (eso, o tienes que hacerlo mucho más complicado)
skrebbel
1
Esto realmente te obliga a usar la multitarea preventiva en todos los casos, excepto en el más simple.
Craig McQueen
1
Esos gotos podrían reemplazarse con llamadas a funciones. Y si un generador de perfiles le dice que su programa se está ahogando debido a la sobrecarga de llamadas de función, entonces puede reemplazar las llamadas con gotos según sea necesario.
Abtin Forouzandeh
77
@AbtinForouzandeh simplemente reemplazando los gotos con llamadas a funciones causaría un desbordamiento de la pila ya que la pila de llamadas solo se borra en caso de un error.
JustMaximumPower
Estoy de acuerdo con el método goto. Aquí hay un conjunto de macros que ilustran eso. Y las macros hacen que su código esté estructurado como si lo hubiera codificado como lo haría normalmente. También funciona a nivel de interrupción, que generalmente es donde se necesitan máquinas de estado codeproject.com/Articles/37037/…
eddyq
30

Puede considerar el compilador de máquinas de estado http://smc.sourceforge.net/

Esta espléndida utilidad de código abierto acepta una descripción de una máquina de estado en un lenguaje simple y la compila en cualquiera de una docena de lenguajes, incluidos C y C ++. La utilidad en sí está escrita en Java y se puede incluir como parte de una compilación.

La razón para hacer esto, en lugar de la codificación manual utilizando el patrón de estado GoF o cualquier otro enfoque, es que una vez que su máquina de estados se expresa como código, la estructura subyacente tiende a desaparecer bajo el peso de repetitivo que debe generarse para soportarlo. El uso de este enfoque le brinda una excelente separación de preocupaciones y mantiene la estructura de su máquina de estado 'visible'. El código generado automáticamente entra en módulos que no necesita tocar, para que pueda retroceder y manipular la estructura de la máquina de estado sin afectar el código de soporte que ha escrito.

Lo siento, estoy demasiado entusiasmado y, sin duda, estoy posponiendo a todos. Pero es una utilidad de primer nivel, y también está bien documentada.

willw
fuente
20

Asegúrese de verificar el trabajo de Miro Samek (blog State Space , sitio web State Machines & Tools ), cuyos artículos en el C / C ++ Users Journal fueron geniales.

El sitio web contiene una implementación completa (C / C ++) en licencia de código abierto y comercial de un marco de máquina de estado (QP Framework) , un controlador de eventos (QEP) , una herramienta de modelado básica (QM) y una herramienta de rastreo (QSpy) que Permitir dibujar máquinas de estado, crear código y depurarlas.

El libro contiene una amplia explicación sobre qué / por qué de la implementación y cómo usarlo, y también es un excelente material para comprender los fundamentos de las máquinas de estados jerárquicos y finitos.

El sitio web también contiene enlaces a varios paquetes de soporte de la placa para el uso del software con plataformas integradas.

Daniel Daranas
fuente
Modifiqué el título de la pregunta según tu juego de palabras.
jldupont
@jldupont: Solo quería decir que era mejor aclarar. He eliminado las partes irrelevantes de mi respuesta ahora.
Daniel Daranas
1
He agregado qué esperar en el sitio web / libro, después de haber utilizado el software con éxito yo mismo; Es el mejor libro en mi estantería.
Adriaan
@Adriann, ¡gran explicación! Acabo de modificar la página de inicio del sitio web, el enlace anterior había dejado de funcionar.
Daniel Daranas
2
Los enlaces están muertos o apuntan a la página de inicio del sitio que parece haber cambiado su dirección hacia el software incorporado. Todavía puede ver parte del contenido en state-machine.com/resources/articles.php , pero incluso allí la mayoría de los enlaces relacionados con la máquina de estado están muertos. Este es uno de los únicos buenos enlaces allí: state-machine.com/resources/…
Tatiana Racheva
11

Hice algo similar a lo que describe paxdiablo, solo que en lugar de una matriz de transiciones de estado / evento, configuré una matriz bidimensional de punteros de función, con el valor del evento como el índice de un eje y el valor del estado actual como el otro. Entonces solo llamo state = state_table[event][state](params)y sucede lo correcto. Las celdas que representan combinaciones de estado / evento no válidas obtienen un puntero a una función que lo dice, por supuesto.

Obviamente, esto solo funciona si los valores de estado y evento son rangos contiguos y comienzan en 0 o lo suficientemente cerca.

CEO
fuente
1
Siente que esta solución no escala bien: demasiado relleno de la mesa, ¿no?
jldupont
2
+1. El problema de escalado aquí es la memoria: mi propia solución tiene un problema de escalado en el tiempo, es decir, el tiempo necesario para escanear la tabla de transiciones (aunque puede optimizar manualmente para las transiciones más comunes). Este sacrifica la memoria por la velocidad, es solo una compensación. Probablemente necesitará verificaciones de límites, pero no es una mala solución.
paxdiablo
Chicos: mi comentario no salió como estaba previsto: quise decir que es mucho más laborioso y propenso a errores. Si agrega un estado / evento, es necesario realizar muchas modificaciones.
jldupont el
3
Nadie dijo que la matriz 2D se inicializara a mano. Tal vez hay algo que lee un archivo de configuración y lo crea (o al menos podría haberlo).
John Zwinck el
Una forma de inicializar matrices como esa es hacer uso del preprocesador como un aglutinante tardío (en oposición a la unión temprana). Defina una lista de todos los estados #define STATE_LIST() \STATE_LIST_ENTRY(state1)\STATE_LIST_ENTRY(state2)\...(una nueva línea implícita después de cada uno \ ) donde (re) defina la macro de entrada cuando use la macro STATE_LIST. Ejemplo - hacer una variedad de nombres de estado: #define STATE_LIST_ENTRY(s) #s , \n const char *state_names[] = { STATE_LIST() };\n #undef STATE_LIST_ENTRY. Algunos trabajan para configurar primero, pero esto es extremadamente poderoso. Añadir nuevo estado -> garantizado sin fallos.
hlovdal
9

Stefan Heinzmann da un muy buen "marco" de máquina de estado C ++ basado en plantillas en su artículo .

Como no hay un enlace a una descarga completa de código en el artículo, me tomé la libertad de pegar el código en un proyecto y comprobarlo. Las cosas a continuación se prueban e incluyen las pocas piezas faltantes menores pero bastante obvias.

La principal innovación aquí es que el compilador está generando código muy eficiente. Las acciones de entrada / salida vacías no tienen costo. Las acciones de entrada / salida no vacías están en línea. El compilador también está verificando la integridad del diagrama de estado. Las acciones faltantes generan errores de enlace. Lo único que no se atrapa son los desaparecidos Top::init.

Esta es una muy buena alternativa a la implementación de Miro Samek, si puede vivir sin lo que falta: está lejos de ser una implementación completa de UML Statechart, aunque implementa correctamente la semántica de UML, mientras que el código de Samek por diseño no maneja la salida / transición / acciones de entrada en el orden correcto.

Si este código funciona para lo que necesita hacer, y tiene un compilador de C ++ decente para su sistema, probablemente funcionará mejor que la implementación de C / C ++ de Miro. El compilador genera una implementación aplanada de máquina de estado de transición O (1) para usted. Si la auditoría de la salida del ensamblaje confirma que las optimizaciones funcionan según lo deseado, se acerca al rendimiento teórico. La mejor parte: es un código relativamente pequeño y fácil de entender.

#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 D, class B>
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<D*>(0))) == sizeof(Yes) ? 1 : 0 };
};

template<bool> class Bool {};

// Top State, Composite State and Leaf State

template <typename H>
struct TopState {
    typedef H Host;
    typedef void Base;
    virtual void handler(Host&) const = 0;
    virtual unsigned getId() const = 0;
};

template <typename H, unsigned id, typename B>
struct CompState;

template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct CompState : B {
    typedef B Base;
    typedef CompState<H, id, Base> This;
    template <typename X> 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 <typename H>
struct CompState<H, 0, TopState<H> > : TopState<H> {
    typedef TopState<H> Base;
    typedef CompState<H, 0, Base> This;
    template <typename X> void handle(H&, const X&) const {}
    static void init(H&); // no implementation
    static void entry(H&) {}
    static void exit(H&) {}
};

template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct LeafState : B {
    typedef H Host;
    typedef B Base;
    typedef LeafState<H, id, Base> This;
    template <typename X> 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 <typename H, unsigned id, typename B>
const LeafState<H, id, B> LeafState<H, id, B>::obj;

// Transition Object

template <typename C, typename S, typename T>
// 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<TargetBase, CurrentBase>::Res,
        eS_CB = IsDerivedFrom<S, CurrentBase>::Res,
        eS_C = IsDerivedFrom<S, C>::Res,
        eC_S = IsDerivedFrom<C, S>::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<true>) {}
    static void exitActions(Host&h, Bool<false>) {
        C::exit(h);
        Tran<CurrentBase, S, T>::exitActions(h, Bool<exitStop>());
    }
    static void entryActions(Host&, Bool<true>) {}
    static void entryActions(Host& h, Bool<false>) {
        Tran<CurrentBase, S, T>::entryActions(h, Bool<entryStop>());
        C::entry(h);
    }
    Tran(Host & h) : host_(h) {
        exitActions(host_, Bool<false>());
    }
    ~Tran() {
        Tran<T, S, T>::entryActions(host_, Bool<false>());
        T::init(host_);
    }
    Host& host_;
};

// Initializer for Compound States

template <typename T>
struct Init {
    typedef typename T::Host Host;
    Init(Host& h) : host_(h) {}
    ~Init() {
        T::entry(host_);
        T::init(host_);
    }
    Host& host_;
};

#endif // HSM_HPP

El código de prueba sigue.

#include <cstdio>
#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<TestHSM,0>     Top;
typedef CompState<TestHSM,1,Top>   S0;
typedef CompState<TestHSM,2,S0>      S1;
typedef LeafState<TestHSM,3,S1>        S11;
typedef CompState<TestHSM,4,S0>      S2;
typedef CompState<TestHSM,5,S2>        S21;
typedef LeafState<TestHSM,6,S21>         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<TestHSM>& 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<TestHSM>* state_;
    Signal sig_;
    int foo_;
};

bool testDispatch(char c) {
    static TestHSM test;
    if (c<'a' || 'h'<c) {
        return false;
    }
    printf("Signal<-%c", c);
    test.dispatch((Signal)(c-'a'));
    printf("\n");
    return true;
}

int main(int, char**) {
    testDispatch('a');
    testDispatch('e');
    testDispatch('e');
    testDispatch('a');
    testDispatch('h');
    testDispatch('h');
    return 0;
}

#define HSMHANDLER(State) \
    template<> template<typename X> inline void State::handle(TestHSM& h, const X& x) const

HSMHANDLER(S0) {
    switch (h.getSig()) {
    case E_SIG: { Tran<X, This, S211> t(h);
        printf("s0-E;");
        return; }
    default:
        break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S1) {
    switch (h.getSig()) {
    case A_SIG: { Tran<X, This, S1> t(h);
        printf("s1-A;"); return; }
    case B_SIG: { Tran<X, This, S11> t(h);
        printf("s1-B;"); return; }
    case C_SIG: { Tran<X, This, S2> t(h);
        printf("s1-C;"); return; }
    case D_SIG: { Tran<X, This, S0> t(h);
        printf("s1-D;"); return; }
    case F_SIG: { Tran<X, This, S211> t(h);
        printf("s1-F;"); return; }
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S11) {
    switch (h.getSig()) {
    case G_SIG: { Tran<X, This, S211> 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<X, This, S1> t(h);
        printf("s2-C"); return; }
    case F_SIG: { Tran<X, This, S11> t(h);
        printf("s2-F"); return; }
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S21) {
    switch (h.getSig()) {
    case B_SIG: { Tran<X, This, S211> t(h);
        printf("s21-B;"); return; }
    case H_SIG: if (!h.foo()) {
            Tran<X, This, S21> 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<X, This, S21> t(h);
        printf("s211-D;"); return; }
    case G_SIG: { Tran<X, This, S0> 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<InitState> i(h); \
       printf(#State "-INIT;"); \
    }

HSMINIT(Top, S0)
HSMINIT(S0, S1)
HSMINIT(S1, S11)
HSMINIT(S2, S21)
HSMINIT(S21, S211)
Kuba Ober
fuente
Hmm ... falta algo en tu código. En primer lugar, incluye dos encabezados, pero proporciona solo el primero. Cuando acabo de comentar la declaración "include", aparece este error al compilar: d: \ 1 \ hsm> g ++ test.cpp test.cpp: 195: 1: error: especialización de 'static void CompState <H, id, B> :: init (H &) [con H = TestHSM; unsigned int id = 0u; B = CompState <TestHSM, 0u, TopState <TestHSM>>] 'después de la instanciación
Freddie Chopin
Tuve que mover las definiciones de todo HSMINIT () para estar por encima de la clase TestHSM y se compila y funciona bien (; Lo único que está mal es el hecho de que todas las transiciones son "externas", mientras que deberían ser "internas" - hubo Un debate al respecto en el artículo y el autor decidió que "extrenal" tenía razón, pero las flechas utilizadas sugieren "interno".
Freddie Chopin
5

La técnica que me gusta para las máquinas de estado (al menos las de control de programas) es utilizar punteros de función. Cada estado está representado por una función diferente. La función toma un símbolo de entrada y devuelve el puntero de función para el siguiente estado. Los monitores de bucle de despacho central toman la siguiente entrada, la alimentan al estado actual y procesan el resultado.

El escribir en él se vuelve un poco extraño, ya que C no tiene una manera de indicar los tipos de punteros de función que se devuelven, por lo que las funciones de estado regresan void*. Pero puedes hacer algo como esto:

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

Luego, sus funciones de estado individuales pueden activar su entrada para procesar y devolver el valor apropiado.

Michael Ekstrand
fuente
+1 que es realmente agradable, y proporciona lugares agradables para la funcionalidad de manos dentro de las funciones de transición
Fire Crow
5

Caso más simple

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

Puntos: El estado es privado, no solo para la unidad de compilación sino también para el controlador de eventos. Los casos especiales se pueden manejar por separado del interruptor principal utilizando cualquier construcción que se considere necesaria.

Caso más complejo

Cuando el interruptor se hace más grande que un par de pantallas llenas, divídalo en funciones que manejan cada estado, usando una tabla de estado para buscar la función directamente. El estado aún es privado para el controlador de eventos. Las funciones del controlador de estado devuelven el siguiente estado. Si es necesario, algunos eventos aún pueden recibir un tratamiento especial en el controlador de eventos principal. Me gusta agregar pseudoeventos para la entrada y salida de estados y quizás el inicio de la máquina de estados:

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

No estoy seguro si clavé la sintaxis, especialmente con respecto a la matriz de punteros de función. No he ejecutado nada de esto a través de un compilador. Tras la revisión, noté que olvidé descartar explícitamente el siguiente estado al manejar los pseudoeventos (el paréntesis (nulo) antes de la llamada a state_handler ()). Esto es algo que me gusta hacer incluso si los compiladores aceptan la omisión en silencio. Le dice a los lectores del código que "sí, realmente quise llamar a la función sin usar el valor de retorno", y puede evitar que las herramientas de análisis estático avisen al respecto. Puede ser idiosincrásico porque no recuerdo haber visto a nadie más haciendo esto.

Puntos: agregar un poco de complejidad (verificar si el siguiente estado es diferente del actual), puede evitar el código duplicado en otro lugar, porque las funciones del controlador de estado pueden disfrutar de los pseudo eventos que ocurren cuando se ingresa y se deja un estado. Recuerde que el estado no puede cambiar cuando se manejan los pseudoeventos, porque el resultado del controlador de estado se descarta después de estos eventos. Por supuesto, puede optar por modificar el comportamiento.

Un controlador de estado se vería así:

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

Más complejidad

Cuando la unidad de compilación se vuelve demasiado grande (lo que sea que sientas, debería decir alrededor de 1000 líneas), coloca cada controlador de estado en un archivo separado. Cuando cada controlador de estado se alargue más que un par de pantallas, divida cada evento en una función separada, similar a la forma en que se dividió el interruptor de estado. Puede hacerlo de varias maneras, por separado del estado o mediante el uso de una tabla común o combinando varios esquemas. Algunos de ellos han sido cubiertos aquí por otros. Ordene sus tablas y use la búsqueda binaria si la velocidad es un requisito.

Programación genérica

Me gustaría que el preprocesador se ocupe de problemas como ordenar tablas o incluso generar máquinas de estado a partir de descripciones, lo que le permite "escribir programas sobre programas". Creo que esto es para lo que las personas de Boost están explotando las plantillas de C ++, pero encuentro que la sintaxis es críptica.

Tablas bidimensionales

He usado tablas de estado / evento en el pasado, pero tengo que decir que para los casos más simples no las considero necesarias y prefiero la claridad y la legibilidad de la declaración de cambio, incluso si se extiende más allá de una pantalla completa. Para casos más complejos, las tablas se descontrolan rápidamente como otros han señalado. Los modismos que presento aquí le permiten agregar una serie de eventos y estados cuando lo desee, sin tener que mantener una tabla que consuma memoria (incluso si puede ser memoria de programa).

Descargo de responsabilidad

Las necesidades especiales pueden hacer que estos modismos sean menos útiles, pero he descubierto que son muy claros y fáciles de mantener.

Joe el hámster
fuente
Evitaría 'esto' como un nombre o símbolo de variable solo para la asociación, incluso si en realidad no es una palabra reservada.
XTL
4

Extremadamente no probado, pero divertido de codificar, ahora en una versión más refinada que mi respuesta original; Las versiones actualizadas se pueden encontrar en 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

ejemplo.c

#include <stdio.h>

#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;
}
Christoph
fuente
14
Me encanta el comentario "extremadamente no probado". Parece indicar que hay grados de untestedness y que se pone un poco de esfuerzo en no probarlo :-)
paxdiablo
@ Christoph el enlace en esta respuesta está roto. Además, ¿has probado este código o no? Si ha sido probado y funciona, debe eliminarlo de la respuesta. También puede mostrar un ejemplo de en qué código se traduce esto una vez que se han expandido las macros. Me gusta la idea general.
Joakim
4

Realmente me gustó la respuesta de paxdiable y decidí implementar todas las características faltantes para mi aplicación, como las variables de protección y los datos específicos de la máquina de estado.

Subí mi implementación a este sitio para compartir con la comunidad. Se ha probado con IAR Embedded Workbench para ARM.

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

usuario108570
fuente
Encontrar esto en 2018 y que todavía es aplicable. Estaba leyendo la respuesta @paxdiablo, y he usado con éxito ese tipo de implementación en sistemas embebidos anteriormente. Esta solución agrega las cosas que faltan de la respuesta de paxdiablos :)
Kristoffer
4

Otra herramienta interesante de código abierto es Yakindu Statechart Tools en statecharts.org . Utiliza los gráficos de estado de Harel y, por lo tanto, proporciona estados jerárquicos y paralelos y genera código C y C ++ (así como Java). No utiliza bibliotecas, pero sigue un enfoque de "código simple". El código básicamente aplica estructuras de mayúsculas y minúsculas. Los generadores de código también se pueden personalizar. Además, la herramienta ofrece muchas otras características.

Axel T.
fuente
3

Llegando a esta hora (como siempre) pero escaneando las respuestas hasta la fecha, creo que falta algo importante;

He descubierto en mis propios proyectos que puede ser muy útil no tener una función para cada combinación válida de estado / evento. Me gusta la idea de tener efectivamente una tabla 2D de estados / eventos. Pero me gusta que los elementos de la tabla sean más que un simple puntero de función. En cambio, trato de organizar mi diseño para que, en esencia, comprenda un conjunto de elementos atómicos o acciones simples. De esa manera puedo enumerar esos elementos atómicos simples en cada intersección de mi tabla de estado / evento. La idea es que no tiene que definir una masa de N funciones cuadradas (generalmente muy simples). ¿Por qué tener algo tan propenso a errores, lento, difícil de escribir, difícil de leer, lo que sea?

También incluyo un nuevo estado opcional y un puntero de función opcional para cada celda de la tabla. El puntero de función está ahí para esos casos excepcionales en los que no desea simplemente disparar una lista de acciones atómicas.

Sabes que lo estás haciendo bien cuando puedes expresar muchas funciones diferentes, simplemente editando tu tabla, sin ningún código nuevo para escribir.

Bill Forster
fuente
2
Quizás un ejemplo sería bueno, ¿no?
jldupont el
1
Un ejemplo realista que se puede presentar de forma aislada es una tarea desafiante que requeriría más tiempo del que estoy dispuesto a dar en este momento. ¿Hay algo en mi publicación que sea particularmente difícil de entender? Tal vez pueda expresarlo más claramente. La idea es muy simple; No defina un mecanismo de estado que requiera una función separada para cada combinación de evento / estado, de ese modo obtendrá demasiadas funciones. En su lugar, busque otra forma de describir la funcionalidad que desea para esa combinación de evento / estado, al menos en la mayoría de los casos.
Bill Forster el
2
Entendido: un ejemplo de pseudocódigo habría sido bueno, pero su punto es claro.
jldupont el
3

Sin embargo, creo que el mío es un poco diferente al de los demás. Un poco más de separación de código y datos de lo que veo en las otras respuestas. Realmente leí sobre la teoría para escribir esto, que implementa un lenguaje regular completo (sin expresiones regulares, por desgracia). Ullman, Minsky, Chomsky. No puedo decir que lo entendí todo, pero he sacado de los viejos maestros lo más directamente posible: a través de sus palabras.

Utilizo un puntero de función a un predicado que determina la transición a un estado 'sí' o un estado 'no'. Esto facilita la creación de un aceptador de estado finito para un lenguaje regular que usted programa de una manera más similar al lenguaje ensamblador. No se desanime por mis tontas opciones de nombre. 'czek' == 'verificar'. 'grok' == [ve a buscarlo en el Diccionario Hacker].

Entonces, para cada iteración, czek llama a una función de predicado con el carácter actual como argumento. Si el predicado devuelve verdadero, se consume el carácter (el puntero avanzado) y seguimos la transición 'y' para seleccionar el siguiente estado. Si el predicado devuelve falso, el carácter NO se consume y seguimos la transición 'n'. ¡Entonces cada instrucción es una rama bidireccional! Debo haber estado leyendo La historia de Mel en ese momento.

Este código viene directamente de mi intérprete PostScript y evolucionó a su forma actual con mucha guía de los compañeros en comp.lang.c. Dado que PostScript básicamente no tiene sintaxis (solo requiere corchetes equilibrados), un aceptador de lenguaje regular como este también funciona como analizador.

/* 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<i; j++) {
                    a_put(st, proc, j, a[j]);
                }
            }
            free(a);
            return proc;
        }

        case '/': {
            s[1] = (char)next(st,src);
            puff(st, s+2, ns-2, src, next, back);
            if (s[1] == '/') {
                push(consname(st,s+2));
                opexec(st, op_cuts.load);
                return pop();
            }
            return cvlit(consname(st,s+1));
        }

        default: return consname(st,s);
    }
    return null; /* should be unreachable */
}

/*
   Helper function for toke.
   Read into buffer any regular characters.
   If we read one too many characters, put it back
   unless it's whitespace.
 */
int puff (state *st, char *buf, int nbuf,
    object *src,
    int (*next)(state *,object *),
    void (*back)(state *,int, object *)) {
    int c;
    char *s = buf;
    while (isreg(c=next(st,src))) {
        if (s-buf >= 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;
    }
}
luser droog
fuente
2
Esto es lo que cualquier generador de analizador o lexer emitirá con gusto para usted. Asombrosamente así. Si desea codificarlo a mano es cuestionable. Tiene mérito pedagógico, por supuesto.
Vuelva a instalar Mónica
3

boost.org viene con 2 implementaciones diferentes de gráficos de estado:

Como siempre, el impulso te llevará al infierno de las plantillas.

La primera biblioteca es para máquinas de estado más críticas para el rendimiento. La segunda biblioteca le ofrece una ruta de transición directa de un diagrama de estado UML al código.

Aquí está la pregunta SO pidiendo una comparación entre los dos donde ambos autores responden.

Roland Wolf
fuente
2

Vi esto en alguna parte

#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);
  }
}
pixelbeat
fuente
1
Es interesante, pero no vota a favor hasta que des un ejemplo o dos (y tal vez un resultado descifrado) o alguna discusión sobre por qué esto puede ser más práctico que otro. Uso interesante de corchetes y macros huérfanos. Me imagino que se podría hacer algo similar en un lenguaje que hace algún tipo de optimización de recursión de cola; podría usar llamadas de función directas y no preocuparse por sobrecargar el espacio de la pila con basura de llamada de función (que creo que es lo que las macros esencialmente están superando aquí)
Ape-inago
2
Las ventajas de este método son ...? Veo varias desventajas, como ofuscar macros, y el uso de gotoeso crea una dependencia en un sistema operativo multitarea preventivo.
Craig McQueen
2

Dado que usted implica que puede usar C ++ y, por lo tanto, el código OO, sugeriría evaluar el patrón de estado 'GoF' (GoF = Gang of Four, los chicos que escribieron el libro de patrones de diseño que trajo los patrones de diseño a la fama).

No es particularmente complejo y se usa y discute ampliamente, por lo que es fácil ver ejemplos y explicaciones en línea.

También es muy probable que sea reconocido por cualquier otra persona que mantenga su código en una fecha posterior.

Si la preocupación es la eficiencia, valdría realmente la evaluación comparativa para asegurarse de que un enfoque sin OO sea más eficiente, ya que muchos factores afectan el rendimiento y no siempre es simplemente un código funcional OO malo. Del mismo modo, si el uso de la memoria es una restricción para usted, nuevamente vale la pena hacer algunas pruebas o cálculos para ver si esto realmente será un problema para su aplicación en particular si usa el patrón de estado.

Los siguientes son algunos enlaces al patrón de estado 'Gof', como sugiere Craig:

Mick
fuente
se parece más a un comentario: ¿podría sugerirle que lo trate como tal? es decir, no lo coloque en la sección de "respuesta".
jldupont
Sería bueno si pudiera proporcionar un buen enlace URL para el "patrón de estado GoF", para aquellos que no están familiarizados con él.
Craig McQueen
1
@jldupont - comentario justo. Cambié el texto para que sea una respuesta adecuada, ya que me siento basado en la experiencia personal de que, a menos que haya problemas de rendimiento específicos, el enfoque GoF funciona bien y tendrá una 'base de usuarios' relativamente grande
Mick
@Craig: se agregaron algunos enlaces. Ambos parecían precisos y claros en el momento en que los agregué.
Mick
2

Aquí hay un ejemplo de una máquina de estados finitos para Linux que usa colas de mensajes como eventos. Los eventos se ponen en la cola y se manejan en orden. El estado cambia según lo que ocurra para cada evento.

Este es un ejemplo para una conexión de datos con estados como:

  • Sin inicializar
  • Inicializado
  • Conectado
  • MTU negociado
  • Autenticado

Una pequeña característica adicional que agregué fue una marca de tiempo para cada mensaje / evento. El controlador de eventos ignorará los eventos que son demasiado antiguos (han caducado). Esto puede suceder mucho en el mundo real, donde podría quedar atrapado en un estado inesperado.

Este ejemplo se ejecuta en Linux, use el Makefile a continuación para compilarlo y jugar con él.

state_machine.c

#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <unistd.h>   // sysconf()
#include <errno.h>    // errno
#include <string.h>   // strerror()
#include <sys/time.h> // gettimeofday()
#include <fcntl.h>    // For O_* constants
#include <sys/stat.h> // For mode constants

#include <mqueue.h>
#include <poll.h>

//------------------------------------------------
// States
//------------------------------------------------
typedef enum
{
    ST_UNKNOWN = 0,
    ST_UNINIT,
    ST_INIT,
    ST_CONNECTED,
    ST_MTU_NEGOTIATED,
    ST_AUTHENTICATED,
    ST_ERROR,
    ST_DONT_CHANGE,
    ST_TERM,
} fsmState_t;

//------------------------------------------------
// Events
//------------------------------------------------
typedef enum
{
    EV_UNKNOWN = 0,
    EV_INIT_SUCCESS,
    EV_INIT_FAIL,
    EV_MASTER_CMD_MSG,
    EV_CONNECT_SUCCESS,
    EV_CONNECT_FAIL,
    EV_MTU_SUCCESS,
    EV_MTU_FAIL,
    EV_AUTH_SUCCESS,
    EV_AUTH_FAIL,
    EV_TX_SUCCESS,
    EV_TX_FAIL,
    EV_DISCONNECTED,
    EV_DISCON_FAILED,
    EV_LAST_ENTRY,
} fsmEvName_t;

typedef struct fsmEvent_type
{
    fsmEvName_t name;
    struct timeval genTime; // Time the event was generated.
                            // This allows us to see how old the event is.
} fsmEvent_t;

// Finite State Machine Data Members
typedef struct fsmData_type
{
    int  connectTries;
    int  MTUtries;
    int  authTries;
    int  txTries;
} fsmData_t;

// Each row of the state table
typedef struct stateTable_type {
    fsmState_t  st;             // Current state
    fsmEvName_t evName;         // Got this event
    int (*conditionfn)(void *);  // If this condition func returns TRUE
    fsmState_t nextState;       // Change to this state and
    void (*fn)(void *);          // Run this function
} stateTable_t;

// Finite State Machine state structure
typedef struct fsm_type
{
    const stateTable_t *pStateTable; // Pointer to state table
    int        numStates;            // Number of entries in the table
    fsmState_t currentState;         // Current state
    fsmEvent_t currentEvent;         // Current event
    fsmData_t *fsmData;              // Pointer to the data attributes
    mqd_t      mqdes;                // Message Queue descriptor
    mqd_t      master_cmd_mqdes;     // Master command message queue
} fsm_t;

// Wildcard events and wildcard state
#define   EV_ANY    -1
#define   ST_ANY    -1
#define   TRUE     (1)
#define   FALSE    (0)

// Maximum priority for message queues (see "man mq_overview")
#define FSM_PRIO  (sysconf(_SC_MQ_PRIO_MAX) - 1)

static void addev                              (fsm_t *fsm, fsmEvName_t ev);
static void doNothing                          (void *fsm) {addev(fsm, EV_MASTER_CMD_MSG);}
static void doInit                             (void *fsm) {addev(fsm, EV_INIT_SUCCESS);}
static void doConnect                          (void *fsm) {addev(fsm, EV_CONNECT_SUCCESS);}
static void doMTU                              (void *fsm) {addev(fsm, EV_MTU_SUCCESS);}
static void reportFailConnect                  (void *fsm) {addev(fsm, EV_ANY);}
static void doAuth                             (void *fsm) {addev(fsm, EV_AUTH_SUCCESS);}
static void reportDisConnect                   (void *fsm) {addev(fsm, EV_ANY);}
static void doDisconnect                       (void *fsm) {addev(fsm, EV_ANY);}
static void doTransaction                      (void *fsm) {addev(fsm, EV_TX_FAIL);}
static void fsmError                           (void *fsm) {addev(fsm, EV_ANY);}

static int currentlyLessThanMaxConnectTries    (void *fsm) {
    fsm_t *l = (fsm_t *)fsm;
    return (l->fsmData->connectTries < 5 ? TRUE : FALSE);
}
static int        isMoreThanMaxConnectTries    (void *fsm) {return TRUE;}
static int currentlyLessThanMaxMTUtries        (void *fsm) {return TRUE;}
static int        isMoreThanMaxMTUtries        (void *fsm) {return TRUE;}
static int currentyLessThanMaxAuthTries        (void *fsm) {return TRUE;}
static int       isMoreThanMaxAuthTries        (void *fsm) {return TRUE;}
static int currentlyLessThanMaxTXtries         (void *fsm) {return FALSE;}
static int        isMoreThanMaxTXtries         (void *fsm) {return TRUE;}
static int didNotSelfDisconnect                (void *fsm) {return TRUE;}

static int  waitForEvent                       (fsm_t *fsm);
static void runEvent                           (fsm_t *fsm);
static void runStateMachine(fsm_t *fsm);
static int newEventIsValid(fsmEvent_t *event);
static void getTime(struct timeval *time);
void printState(fsmState_t st);
void printEvent(fsmEvName_t ev);

// Global State Table
const stateTable_t GST[] = {
    // Current state         Got this event          If this condition func returns TRUE     Change to this state and    Run this function
    { ST_UNINIT,             EV_INIT_SUCCESS,        NULL,                                   ST_INIT,                    &doNothing              },
    { ST_UNINIT,             EV_INIT_FAIL,           NULL,                                   ST_UNINIT,                  &doInit                 },
    { ST_INIT,               EV_MASTER_CMD_MSG,      NULL,                                   ST_INIT,                    &doConnect              },
    { ST_INIT,               EV_CONNECT_SUCCESS,     NULL,                                   ST_CONNECTED,               &doMTU                  },
    { ST_INIT,               EV_CONNECT_FAIL,        &currentlyLessThanMaxConnectTries,      ST_INIT,                    &doConnect              },
    { ST_INIT,               EV_CONNECT_FAIL,        &isMoreThanMaxConnectTries,             ST_INIT,                    &reportFailConnect      },
    { ST_CONNECTED,          EV_MTU_SUCCESS,         NULL,                                   ST_MTU_NEGOTIATED,          &doAuth                 },
    { ST_CONNECTED,          EV_MTU_FAIL,            &currentlyLessThanMaxMTUtries,          ST_CONNECTED,               &doMTU                  },
    { ST_CONNECTED,          EV_MTU_FAIL,            &isMoreThanMaxMTUtries,                 ST_CONNECTED,               &doDisconnect           },
    { ST_CONNECTED,          EV_DISCONNECTED,        &didNotSelfDisconnect,                  ST_INIT,                    &reportDisConnect       },
    { ST_MTU_NEGOTIATED,     EV_AUTH_SUCCESS,        NULL,                                   ST_AUTHENTICATED,           &doTransaction          },
    { ST_MTU_NEGOTIATED,     EV_AUTH_FAIL,           &currentyLessThanMaxAuthTries,          ST_MTU_NEGOTIATED,          &doAuth                 },
    { ST_MTU_NEGOTIATED,     EV_AUTH_FAIL,           &isMoreThanMaxAuthTries,                ST_MTU_NEGOTIATED,          &doDisconnect           },
    { ST_MTU_NEGOTIATED,     EV_DISCONNECTED,        &didNotSelfDisconnect,                  ST_INIT,                    &reportDisConnect       },
    { ST_AUTHENTICATED,      EV_TX_SUCCESS,          NULL,                                   ST_AUTHENTICATED,           &doDisconnect           },
    { ST_AUTHENTICATED,      EV_TX_FAIL,             &currentlyLessThanMaxTXtries,           ST_AUTHENTICATED,           &doTransaction          },
    { ST_AUTHENTICATED,      EV_TX_FAIL,             &isMoreThanMaxTXtries,                  ST_AUTHENTICATED,           &doDisconnect           },
    { ST_AUTHENTICATED,      EV_DISCONNECTED,        &didNotSelfDisconnect,                  ST_INIT,                    &reportDisConnect       },
    { ST_ANY,                EV_DISCON_FAILED,       NULL,                                   ST_DONT_CHANGE,             &doDisconnect           },
    { ST_ANY,                EV_ANY,                 NULL,                                   ST_UNINIT,                  &fsmError               }    // Wildcard state for errors
};

#define GST_COUNT (sizeof(GST)/sizeof(stateTable_t))

int main()
{
    int ret = 0;
    fsmData_t dataAttr;
    dataAttr.connectTries = 0;
    dataAttr.MTUtries     = 0;
    dataAttr.authTries    = 0;
    dataAttr.txTries      = 0;

    fsm_t lfsm;
    memset(&lfsm, 0, sizeof(fsm_t));
    lfsm.pStateTable       = GST;
    lfsm.numStates         = GST_COUNT;
    lfsm.currentState      = ST_UNINIT;
    lfsm.currentEvent.name = EV_ANY;
    lfsm.fsmData           = &dataAttr;

    struct mq_attr attr;
    attr.mq_maxmsg = 30;
    attr.mq_msgsize = sizeof(fsmEvent_t);

    // Dev info
    //printf("Size of fsmEvent_t [%ld]\n", sizeof(fsmEvent_t));

    ret = mq_unlink("/abcmq");
    if (ret == -1) {
        fprintf(stderr, "Error on mq_unlink(), errno[%d] strerror[%s]\n",
                errno, strerror(errno));
    }

    lfsm.mqdes = mq_open("/abcmq", O_CREAT | O_RDWR, S_IWUSR | S_IRUSR, &attr);
    if (lfsm.mqdes == (mqd_t)-1) {
        fprintf(stderr, "Error on mq_open(), errno[%d] strerror[%s]\n",
                errno, strerror(errno));
        return -1;
    }

    doInit(&lfsm);  // This will generate the first event
    runStateMachine(&lfsm);

    return 0;
}


static void runStateMachine(fsm_t *fsm)
{
    int ret = 0;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    // Cycle through the state machine
    while (fsm->currentState != ST_TERM) {
        printf("current state [");
        printState(fsm->currentState);
        printf("]\n");

        ret = waitForEvent(fsm);
        if (ret == 0) {
            printf("got event [");
            printEvent(fsm->currentEvent.name);
            printf("]\n");

            runEvent(fsm);
        }
        sleep(2);
    }
}


static int waitForEvent(fsm_t *fsm)
{
    //const int numFds = 2;
    const int numFds = 1;
    struct pollfd fds[numFds];
    int timeout_msecs = -1; // -1 is forever
    int ret = 0;
    int i = 0;
    ssize_t num = 0;
    fsmEvent_t newEv;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return -1;
    }

    fsm->currentEvent.name = EV_ANY;

    fds[0].fd     = fsm->mqdes;
    fds[0].events = POLLIN;
    //fds[1].fd     = fsm->master_cmd_mqdes;
    //fds[1].events = POLLIN;
    ret = poll(fds, numFds, timeout_msecs);

    if (ret > 0) {
        // An event on one of the fds has occurred
        for (i = 0; i < numFds; i++) {
            if (fds[i].revents & POLLIN) {
                // Data may be read on device number i
                num = mq_receive(fds[i].fd, (void *)(&newEv),
                                 sizeof(fsmEvent_t), NULL);
                if (num == -1) {
                    fprintf(stderr, "Error on mq_receive(), errno[%d] "
                            "strerror[%s]\n", errno, strerror(errno));
                    return -1;
                }

                if (newEventIsValid(&newEv)) {
                    fsm->currentEvent = newEv;
                } else {
                    return -1;
                }
            }
        }
    } else {
        fprintf(stderr, "Error on poll(), ret[%d] errno[%d] strerror[%s]\n",
                ret, errno, strerror(errno));
        return -1;
    }

    return 0;
}


static int newEventIsValid(fsmEvent_t *event)
{
    if (event == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return FALSE;
    }

    printf("[%s]\n", __func__);

    struct timeval now;
    getTime(&now);

    if ( (event->name < EV_LAST_ENTRY) &&
         ((now.tv_sec - event->genTime.tv_sec) < (60*5))
       )
    {
        return TRUE;
    } else {
        return FALSE;
    }
}


//------------------------------------------------
// Performs event handling on the FSM (finite state machine).
// Make sure there is a wildcard state at the end of
// your table, otherwise; the event will be ignored.
//------------------------------------------------
static void runEvent(fsm_t *fsm)
{
    int i;
    int condRet = 0;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    printf("[%s]\n", __func__);

    // Find a relevant entry for this state and event
    for (i = 0; i < fsm->numStates; i++) {
        // Look in the table for our current state or ST_ANY
        if (  (fsm->pStateTable[i].st == fsm->currentState) ||
              (fsm->pStateTable[i].st == ST_ANY)
           )
        {
            // Is this the event we are looking for?
            if ( (fsm->pStateTable[i].evName == fsm->currentEvent.name) ||
                 (fsm->pStateTable[i].evName == EV_ANY)
               )
            {
                if (fsm->pStateTable[i].conditionfn != NULL) {
                    condRet = fsm->pStateTable[i].conditionfn(fsm->fsmData);
                }

                // See if there is a condition associated
                // or we are not looking for any condition
                //
                if ( (condRet != 0) || (fsm->pStateTable[i].conditionfn == NULL))
                {
                    // Set the next state (if applicable)
                    if (fsm->pStateTable[i].nextState != ST_DONT_CHANGE) {
                        fsm->currentState = fsm->pStateTable[i].nextState;
                        printf("new state [");
                        printState(fsm->currentState);
                        printf("]\n");
                    }

                    // Call the state callback function
                    fsm->pStateTable[i].fn(fsm);
                    break;
                }
            }
        }
    }
}


//------------------------------------------------
//               EVENT HANDLERS
//------------------------------------------------
static void getTime(struct timeval *time)
{
    if (time == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    printf("[%s]\n", __func__);

    int ret = gettimeofday(time, NULL);
    if (ret != 0) {
        fprintf(stderr, "gettimeofday() failed: errno [%d], strerror [%s]\n",
                errno, strerror(errno));
        memset(time, 0, sizeof(struct timeval));
    }
}


static void addev (fsm_t *fsm, fsmEvName_t ev)
{
    int ret = 0;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    printf("[%s] ev[%d]\n", __func__, ev);

    if (ev == EV_ANY) {
        // Don't generate a new event, just return...
        return;
    }

    fsmEvent_t newev;
    getTime(&(newev.genTime));
    newev.name = ev;

    ret = mq_send(fsm->mqdes, (void *)(&newev), sizeof(fsmEvent_t), FSM_PRIO);
    if (ret == -1) {
        fprintf(stderr, "[%s] mq_send() failed: errno [%d], strerror [%s]\n",
                __func__, errno, strerror(errno));
    }
}
//------------------------------------------------
//           end EVENT HANDLERS
//------------------------------------------------

void printState(fsmState_t st)
{
    switch(st) {
        case    ST_UNKNOWN:
        printf("ST_UNKNOWN");
            break;
        case    ST_UNINIT:
        printf("ST_UNINIT");
            break;
        case    ST_INIT:
        printf("ST_INIT");
            break;
        case    ST_CONNECTED:
        printf("ST_CONNECTED");
            break;
        case    ST_MTU_NEGOTIATED:
        printf("ST_MTU_NEGOTIATED");
            break;
        case    ST_AUTHENTICATED:
        printf("ST_AUTHENTICATED");
            break;
        case    ST_ERROR:
        printf("ST_ERROR");
            break;
        case    ST_TERM:
        printf("ST_TERM");
            break;
        default:
        printf("unknown state");
            break;
    }
}

void printEvent(fsmEvName_t ev)
{
    switch (ev) {
        case    EV_UNKNOWN:
        printf("EV_UNKNOWN");
            break;
        case    EV_INIT_SUCCESS:
        printf("EV_INIT_SUCCESS");
            break;
        case    EV_INIT_FAIL:
        printf("EV_INIT_FAIL");
            break;
        case    EV_MASTER_CMD_MSG:
        printf("EV_MASTER_CMD_MSG");
            break;
        case    EV_CONNECT_SUCCESS:
        printf("EV_CONNECT_SUCCESS");
            break;
        case    EV_CONNECT_FAIL:
        printf("EV_CONNECT_FAIL");
            break;
        case    EV_MTU_SUCCESS:
        printf("EV_MTU_SUCCESS");
            break;
        case    EV_MTU_FAIL:
        printf("EV_MTU_FAIL");
            break;
        case    EV_AUTH_SUCCESS:
        printf("EV_AUTH_SUCCESS");
            break;
        case    EV_AUTH_FAIL:
        printf("EV_AUTH_FAIL");
            break;
        case    EV_TX_SUCCESS:
        printf("EV_TX_SUCCESS");
            break;
        case    EV_TX_FAIL:
        printf("EV_TX_FAIL");
            break;
        case    EV_DISCONNECTED:
        printf("EV_DISCONNECTED");
            break;
        case    EV_LAST_ENTRY:
        printf("EV_LAST_ENTRY");
            break;
        default:
        printf("unknown event");
            break;
    }
}

Makefile

CXX = gcc
COMPFLAGS = -c -Wall -g

state_machine: state_machine.o
    $(CXX) -lrt state_machine.o -o state_machine

state_machine.o: state_machine.c
    $(CXX) $(COMPFLAGS) state_machine.c

clean:
    rm state_machine state_machine.o
Brad Grissom
fuente
1

Su pregunta es bastante genérica.
Aquí hay dos artículos de referencia que pueden ser útiles,

  1. Implementación de máquina de estado incorporada

    Este artículo describe un enfoque simple para implementar una máquina de estado para un sistema integrado. Para los propósitos de este artículo, una máquina de estados se define como un algoritmo que puede estar en uno de los pocos estados. Un estado es una condición que causa una relación prescrita de entradas a salidas, y de entradas a los siguientes estados.
    Un lector inteligente notará rápidamente que las máquinas de estado descritas en este artículo son máquinas Mealy. Una máquina Mealy es una máquina de estados donde las salidas son una función tanto del estado actual como de la entrada, a diferencia de una máquina Moore, en la que las salidas son solo una función del estado.

    • Codificación de máquinas de estado en C y C ++

      Mi preocupación en este artículo es con los fundamentos de la máquina de estado y algunas pautas de programación directas para codificar máquinas de estado en C o C ++. Espero que estas técnicas simples se vuelvan más comunes, para que usted (y otros) puedan ver fácilmente la estructura de la máquina de estado directamente desde el código fuente.

nik
fuente
1

Esta es una publicación antigua con muchas respuestas, pero pensé que agregaría mi propio enfoque a la máquina de estados finitos en C. Hice un script de Python para producir el código C esqueleto para cualquier número de estados. Ese script está documentado en GituHub en FsmTemplateC

Este ejemplo se basa en otros enfoques sobre los que he leído. No usa las instrucciones goto o switch, sino que tiene funciones de transición en una matriz de puntero (tabla de consulta). El código se basa en una gran macro inicializadora multilínea y características C99 (inicializadores designados y literales compuestos), por lo que si no le gustan estas cosas, es posible que no le guste este enfoque.

Aquí hay un script de Python de un ejemplo de torniquete que genera código C esqueleto usando 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)

El encabezado de salida generado contiene los 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 eFsmTurnstileCheckse usa para determinar si una transición se bloqueó EFSM_TURNSTILE_TR_RETREAT, si se permitió el progreso EFSM_TURNSTILE_TR_ADVANCEo si la llamada a la función no fue precedida por una transición con EFSM_TURNSTILE_TR_CONTINUE.
  • enum eFsmTurnstileStatees simplemente la lista de estados.
  • enum eFsmTurnstileInputes simplemente la lista de entradas.
  • La FsmTurnstileestructura es el corazón de la máquina de estados con la verificación de transición, la tabla de búsqueda de funciones, el estado actual, el estado ordenado y un alias a la función principal que ejecuta la máquina.
  • Cada puntero de función (alias) FsmTurnstilesolo debe llamarse desde la estructura y debe tener su primera entrada como un puntero en sí mismo para mantener un estado persistente, estilo orientado a objetos.

Ahora para las declaraciones de funciones en el encabezado:

/* 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);

Los nombres de las funciones están en el formato {prefix}_{from}_{to}, donde {from}es el estado anterior (actual) y {to}el siguiente. Tenga en cuenta que si la tabla de transición no permite ciertas transiciones, se establecerá un puntero NULO en lugar de un puntero de función. Finalmente, la magia ocurre con una macro. Aquí construimos la tabla de transición (matriz de enumeraciones de estado) y la tabla de búsqueda de funciones de transición de estado (una matriz de punteros de función):

/* 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 \
}

Al crear el FSM, la macro FSM_EXAMPLE_CREATE() se debe usar .

Ahora, en el código fuente, todas las funciones de transición de estado declaradas anteriormente deben rellenarse. La FsmTurnstileFoptsestructura se puede utilizar para pasar datos a / desde la máquina de estado. Cada transición debe establecerse fsm->checkpara que sea igual a EFSM_EXAMPLE_TR_RETREATbloquearla de la transición o EFSM_EXAMPLE_TR_ADVANCEpara permitirle hacer la transición al estado ordenado. Puede encontrar un ejemplo de trabajo en (FsmTemplateC) [ https://github.com/ChisholmKyle/FsmTemplateC] .

Aquí está el uso real muy simple en su código:

/* 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);
}

Todo ese negocio de encabezado y todas esas funciones solo para tener una interfaz simple y rápida lo vale en mi mente.

ChisholmKyle
fuente
0

Puede usar la biblioteca de código abierto OpenFST .

OpenFst es una biblioteca para construir, combinar, optimizar y buscar transductores de estado finito (FST) ponderados. Los transductores ponderados de estado finito son autómatas donde cada transición tiene una etiqueta de entrada, una etiqueta de salida y un peso. El aceptor de estado finito más familiar se representa como un transductor con la etiqueta de entrada y salida de cada transición igual. Los aceptadores de estado finito se utilizan para representar conjuntos de cadenas (específicamente, conjuntos regulares o racionales); Los transductores de estado finito se utilizan para representar relaciones binarias entre pares de cadenas (específicamente, transducciones racionales). Los pesos se pueden usar para representar el costo de realizar una transición particular.

Vicky Chijwani
fuente
0
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;
}
AlphaGoku
fuente
Puede optimizarlo aún más para la seguridad mediante el uso de una matriz de punteros de función constantes para funciones
AlphaGoku
0

Yo personalmente uso estructuras de referencia automática en combinación con matrices de punteros. Subí un tutorial en github hace un tiempo, enlace:

https://github.com/mmelchger/polling_state_machine_c

Nota: Me doy cuenta de que este hilo es bastante antiguo, pero espero obtener opiniones y reflexiones sobre el diseño de la máquina de estado, así como poder proporcionar un ejemplo para un posible diseño de máquina de estado en C.

mmoment
fuente
0

Se puede considerar UML-Estado-máquina-en-c , un marco máquina de estados "ligera" en C. He escrito este marco para apoyar tanto a máquina de estados finitos y máquina de estados jerárquicos . En comparación con las tablas de estado o casos de cambio simples, un enfoque de marco es más escalable. Se puede usar para máquinas de estado finito simples a máquinas de estado jerárquicas complejas.

La máquina de estados está representada por la state_machine_testructura. Contiene solo dos miembros "Evento" y un puntero al "estado_t".

struct state_machine_t
{
   uint32_t Event;          //!< Pending Event for state machine
   const state_t* State;    //!< State of state machine.
};

state_machine_tdebe ser el primer miembro de su estructura de máquina de estado. p.ej

struct user_state_machine
{
  state_machine_t Machine;    // Base state machine. Must be the first member of user derived state machine.

  // User specific state machine members
  uint32_t param1;
  uint32_t param2;
  ...
};

state_t contiene un controlador para el estado y también controladores opcionales para la acción de entrada y salida.

//! finite state structure
struct finite_state{
  state_handler Handler;      //!< State handler to handle event of the state
  state_handler Entry;        //!< Entry action for state
  state_handler Exit;          //!< Exit action for state.
};

Si el marco está configurado para una máquina de estados jerárquica, entonces el state_t contiene un puntero al estado primario y secundario.

Framework proporciona una API dispatch_eventpara enviar el evento a la máquina de estado y switch_stateactivar la transición de estado.

Para obtener más detalles sobre cómo implementar una máquina de estados jerárquica, consulte el repositorio de GitHub .

ejemplos de código,

https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine/readme.md https://github.com/kiishor/UML-State-Machine-in-C /blob/master/demo/simple_state_machine_enhanced/readme.md

Nandkishor Biradar
fuente
-1

Aquí hay un método para una máquina de estados que usa macros de modo que cada función pueda tener su propio conjunto de estados: https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code -a

Se titula "simular multitarea", pero ese no es el único uso.

Este método utiliza devoluciones de llamada para recoger en cada función donde se dejó. Cada función contiene una lista de estados únicos para cada función. Se usa un "bucle inactivo" central para ejecutar las máquinas de estado. El "bucle inactivo" no tiene idea de cómo funcionan las máquinas de estado, son las funciones individuales las que "saben qué hacer". Para escribir código para las funciones, uno simplemente crea una lista de estados y usa las macros para "suspender" y "reanudar". Usé estas macros en Cisco cuando escribí la Biblioteca Transceptor para el conmutador Nexus 7000.

eddyq
fuente