Projeto de máquina de estado C [fechado]

193

Estou criando um pequeno projeto em C e C ++ misto. Estou construindo uma pequena máquina de estado no coração de um dos meus segmentos de trabalho.

Fiquei me perguntando se vocês, gurus do SO, compartilhariam suas técnicas de design de máquinas de estado.

OBSERVAÇÃO: Estou principalmente depois das técnicas de implementação testadas e experimentadas.

ATUALIZADO: Com base em todas as ótimas contribuições reunidas no SO, decidi sobre essa arquitetura:

Uma bomba de eventos aponta para um integrador de eventos que aponta para um expedidor.  O despachante aponta para 1 a n ações que apontam para o integrador de eventos.  Uma tabela de transição com caracteres curinga aponta para o expedidor.

jldupont
fonte
4
As respostas aqui são muito boas. Também olhar para esta questão duplicado que tem várias respostas boas, também: stackoverflow.com/questions/1371460/state-machines-tutorials
Michael Burr
2
Isso também é interessante: stackoverflow.com/questions/133214/…
Daniel Daranas 30/10/2009
Veja também esta questão .
Daniel Daranas

Respostas:

170

Máquinas de estado que eu projetei antes (C, não C ++) se resumem a uma structmatriz e um loop. A estrutura consiste basicamente em um estado e evento (para consulta) e uma função que retorna o novo estado, algo como:

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

Em seguida, você define seus estados e eventos com definições simples (esses ANYsão marcadores especiais, veja abaixo):

#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

Então você define todas as funções chamadas pelas transições:

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

Todas essas funções são escritas para não pegar variáveis ​​e retornar o novo estado para a máquina de estados. Neste exemplo, variáveis ​​globais são usadas para transmitir qualquer informação para as funções de estado, quando necessário.

O uso de globais não é tão ruim quanto parece, pois o FSM geralmente está trancado dentro de uma única unidade de compilação e todas as variáveis ​​são estáticas nessa unidade (e é por isso que usei aspas em "global" acima - elas são mais compartilhadas no FSM, do que verdadeiramente global). Como em todos os globais, requer cuidados.

A matriz de transições define todas as transições possíveis e as funções que são chamadas para essas transições (incluindo a última catch-all):

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

O que isso significa é: se você estiver no ST_INITestado e receber o EV_KEYPRESSevento, ligue para GotKey.

O funcionamento do FSM se torna um loop relativamente simples:

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 mencionado acima, observe o uso de ST_ANYcuringas, permitindo que um evento chame uma função, independentemente do estado atual.EV_ANYtambém funciona de maneira semelhante, permitindo que qualquer evento em um estado específico chame uma função.

Também pode garantir que, se você chegar ao final da matriz de transições, receberá um erro informando que o FSM não foi construído corretamente (usando a ST_ANY/EV_ANYcombinação.

Eu usei código semelhante para isso em muitos projetos de comunicação, como uma implementação antecipada de pilhas e protocolos de comunicação para sistemas embarcados. A grande vantagem foi sua simplicidade e relativa facilidade na alteração da matriz de transições.

Não tenho dúvida de que haverá abstrações de nível superior que podem ser mais adequadas hoje em dia, mas suspeito que todas se resumem a esse mesmo tipo de estrutura.


E como ldog afirma um comentário, você pode evitar completamente os globais, passando um ponteiro de estrutura para todas as funções (e usando isso no loop de eventos). Isso permitirá que várias máquinas de estado funcionem lado a lado sem interferência.

Basta criar um tipo de estrutura que mantenha os dados específicos da máquina (estado no mínimo) e use-os em vez dos globais.

A razão pela qual raramente fiz isso é simplesmente porque a maioria das máquinas de estado que escrevi são do tipo singleton (leitura única, durante o processo de inicialização do arquivo de configuração, por exemplo), não precisando executar mais de uma instância . Mas tem valor se você precisar executar mais de um.

paxdiablo
fonte
24
Um switch gigante mistura código com o FSM. Mesmo se houver apenas uma chamada de função por transição, ainda há algum código, e é fácil alguém abusar disso adicionando apenas uma pequena linha de transição de 4 linhas. então um de dez linhas. Então fica fora de controle. Com a matriz struct, o FSM permanece limpo - você pode ver todas as transições e o efeito (função). E eu comecei quando as enums estavam brilhando nos olhos da ISO, escrevendo código para plataformas embarcadas 6809 com compiladores que eram, digamos, menos do que perfeitos :-) #
315
5
Você está certo, enums seria melhor, mas eu ainda prefiro ter o FSM como uma matriz struct. Então tudo é executado por dados, e não por código (bem, há algum código, mas a chance de preencher o loop FSM que eu dei é pequena).
paxdiablo
2
Isso é bom, para máquinas de estado de controle de processo que eu costumava adicionar sempre três subestados (possivelmente vazios) para cada estado, para que a chamada para uma função de estado se tornasse GotKey (subestado), onde seria subestado: - SS_ENTRY - SS_RUN - SS_EXIT Basicamente, a função state é chamada com um subestado SS_ENTRY na entrada, para que o estado possa reconstruir um status (por exemplo, posições dos atuadores). Enquanto não há transição, o valor subestado SS_RUN é passado. Após a transição, a função state é chamada com o subestado SS_EXIT, para que ele possa fazer qualquer limpeza (por exemplo, desalocar recursos).
Metiu 30/10/2009
13
Você mencionou que compartilha dados usando globals, mas provavelmente seria mais limpo se você definir as funções de estado int (*fn)(void*);onde void*está o ponteiro para os dados que cada função de estado recebe como parâmetro. Em seguida, as funções de estado podem usar os dados ou ignorá-los.
Ldog
13
Eu uso a mesma separação de dados / código para escrever FSMs, exceto que nunca me ocorreu introduzir estados 'curinga'. Idéia interessante! No entanto, a iteração da matriz de transições pode se tornar cara se você tiver muitos estados (o que foi o meu caso, pois o código C foi gerado automaticamente). Em tais situações, seria mais eficiente ter uma matriz de transições por estado. Portanto, um estado não é mais um valor enum, mas uma tabela de transição. Dessa forma, você não precisa repetir todas as transições na máquina, mas apenas aquelas que são relevantes para o estado atual.
Frerich Raabe
78

As outras respostas são boas, mas uma implementação muito "leve" que usei quando a máquina de estado é muito simples se parece com:

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

Eu usaria isso quando a máquina de estados for simples o suficiente para que a abordagem de ponteiro de função e tabela de transição de estado seja um exagero. Isso geralmente é útil para análise caractere por caractere ou palavra por palavra.

caf
fonte
37

Perdoe-me por violar todas as regras da ciência da computação, mas uma máquina de estado é um dos poucos (posso contar apenas duas vezes) onde uma gotodeclaração não é apenas mais eficiente, mas também torna seu código mais limpo e fácil de ler. Porquegoto instruções são baseadas em rótulos, é possível nomear seus estados em vez de controlar uma confusão de números ou usar uma enumeração. Ele também cria um código muito mais limpo, já que você não precisa de toda a quantidade extra de ponteiros de função ou enormes instruções de chave e loops while. Eu mencionei que é mais eficiente também?

Aqui está a aparência de uma máquina de estado:

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

Você entendeu a ideia geral. O ponto é que você pode implementar a máquina de estado de maneira eficiente e relativamente fácil de ler e gritar para o leitor que ele está olhando para uma máquina de estado. Observe que, se você estiver usando gotoinstruções, você ainda deve ter cuidado, pois é muito fácil dar um tiro no pé enquanto o faz.

Jason E
fonte
4
Isso funciona apenas se a máquina de estado estiver no objeto de nível superior. O momento algum outro objeto que é ocasionalmente entrevistados / enviou mensagens para, precisa de ter estado, você está preso com esta abordagem (que, ou você tem que torná-lo muito mais complicado)
skrebbel
1
Isso realmente obriga a usar multitarefa preventiva em todos os casos, exceto nos mais simples.
Craig McQueen
1
Esses gotos podem ser substituídos por chamadas de função. E se um criador de perfil diz que seu programa está se afogando devido à sobrecarga de chamada de função, você pode substituir as chamadas por gotos, conforme necessário.
Abtin Forouzandeh 08/09/12
7
A simples substituição do gotos por chamadas de função @AbtinForouzandeh causaria um excesso de pilha, uma vez que a pilha de chamadas é limpa apenas em caso de erro.
JustMaximumPower
Eu concordo com o método goto. Aqui está um conjunto de macros que ilustram isso. E as macros tornam seu código estruturado como se você o tivesse codificado como faria normalmente. Ele também funciona no nível de interrupção que é geralmente onde máquinas de estado são necessários codeproject.com/Articles/37037/...
eddyq
30

Você pode considerar o State Machine Compiler http://smc.sourceforge.net/

Este esplêndido utilitário de código-fonte aberto aceita uma descrição de uma máquina de estado em uma linguagem simples e a compila em qualquer uma das dezenas de outras línguas - incluindo C e C ++. O próprio utilitário é escrito em Java e pode ser incluído como parte de uma construção.

O motivo para fazer isso, em vez de codificar manualmente usando o padrão GoF State ou qualquer outra abordagem, é que, uma vez que sua máquina de estado é expressa como código, a estrutura subjacente tende a desaparecer sob o peso do clichê que precisa ser gerado para suportá-lo. O uso dessa abordagem oferece uma excelente separação de preocupações e você mantém a estrutura da sua máquina de estado 'visível'. O código gerado automaticamente entra nos módulos que você não precisa tocar, para que você possa voltar e mexer com a estrutura da máquina de estado sem afetar o código de suporte que você escreveu.

Desculpe, estou sendo muito entusiasmado e, sem dúvida, deixando todo mundo de lado. Mas é um utilitário de primeira linha e bem documentado também.

willw
fonte
20

Verifique o trabalho de Miro Samek (blog State Space , site State Machines & Tools ), cujos artigos no C / C ++ Users Journal foram ótimos.

O site contém uma implementação completa (C / C ++) na licença de código aberto e comercial de uma estrutura de máquina de estado (QP Framework) , um manipulador de eventos (QEP) , uma ferramenta de modelagem básica (QM) e uma ferramenta de rastreamento (QSpy) que permite desenhar máquinas de estado, criar código e depurá-las.

O livro contém uma extensa explicação sobre o que / por que a implementação e como usá-lo e também é um ótimo material para entender os fundamentos das máquinas de estado hierárquico e finito.

O site também contém links para vários pacotes de suporte da placa para uso do software em plataformas embarcadas.

Daniel Daranas
fonte
Modifiquei o título da pergunta de acordo com o seu trocadilho.
jldupont
@ jldupont: Eu apenas quis dizer que era melhor esclarecer. Eu apaguei as partes irrelevantes da minha resposta agora.
30511 Daniel Daranas
1
Eu adicionei o que esperar no site / livro, tendo usado o software com sucesso; é o melhor livro da minha estante.
Adriaan
@ Adriann, ótima explicação! Acabei de modificar a página inicial do site, o link anterior havia parado de funcionar.
Daniel Daranas
2
Os links estão inoperantes ou apontam para a página inicial do site que parece ter mudado sua direção para software incorporado. Você ainda pode ver parte do conteúdo em state-machine.com/resources/articles.php , mas até mesmo a maioria dos links relacionados a máquinas de estado estão inoperantes. Este é um dos únicos links bons lá: state-machine.com/resources/…
Tatiana Racheva
11

Fiz algo semelhante ao que o paxdiablo descreve. Somente em vez de uma matriz de transições de estado / evento, configurei uma matriz bidimensional de ponteiros de função, com o valor do evento como o índice de um eixo e o valor do estado atual como o outro. Então eu ligo state = state_table[event][state](params)e a coisa certa acontece. Células que representam combinações inválidas de estado / evento recebem um ponteiro para uma função que diz isso, é claro.

Obviamente, isso só funciona se os valores de estado e evento forem intervalos contíguos e iniciarem em 0 ou fechar o suficiente.

CEO
fonte
1
Parece que esta solução não se adapta bem: muito preenchimento de mesa, não?
jldupont
2
+1. O problema de dimensionamento aqui é a memória - minha própria solução tem um problema de dimensionamento, ou seja, o tempo necessário para varrer a tabela de transições (embora você possa otimizar manualmente as transições mais comuns). Este sacrifica a memória por velocidade - é apenas uma troca. Você provavelmente precisaria verificar os limites, mas não é uma solução ruim.
22430
Gente - Meu comentário não saiu como o esperado: quis dizer que é muito mais trabalhoso e propenso a erros. Se você adicionar um estado / evento, muita edição precisará ser feita.
jldupont
3
Ninguém disse que o array 2D foi inicializado manualmente. Talvez haja algo que leia um arquivo de configuração e o crie (ou pelo menos certamente poderia haver).
John Zwinck
Uma maneira de inicializar matrizes como essa é fazer com que o pré-processador seja um fichário atrasado (em oposição à ligação antecipada). Você define uma lista de todos os estados #define STATE_LIST() \STATE_LIST_ENTRY(state1)\STATE_LIST_ENTRY(state2)\...(uma nova linha implícita após cada \ ) em que (re) define a macro de entrada quando usa a macro STATE_LIST. Exemplo - fazendo uma matriz de nomes de estado: #define STATE_LIST_ENTRY(s) #s , \n const char *state_names[] = { STATE_LIST() };\n #undef STATE_LIST_ENTRY. Alguns trabalham para configurar primeiro, mas isso é extremamente poderoso. Adicionar novo estado -> garantido sem perdas.
precisa saber é o seguinte
9

Um "framework" de máquina de estado C ++ baseado em modelo muito bom é dado por Stefan Heinzmann em seu artigo .

Como não há link para um download completo do código no artigo, tomei a liberdade de colar o código em um projeto e verificá-lo. O material abaixo é testado e inclui as poucas peças menores, mas bastante óbvias.

A principal inovação aqui é que o compilador está gerando código muito eficiente. As ações vazias de entrada / saída não têm custo. Ações de entrada / saída não vazias são incorporadas. O compilador também está verificando a integridade do gráfico de estados. Ações ausentes geram erros de vinculação. A única coisa que não é capturada é a falta Top::init.

Essa é uma alternativa muito boa à implementação do Miro Samek, se você pode viver sem o que está faltando - isso está longe de ser uma implementação completa do UML Statechart, embora implemente corretamente a semântica da UML, enquanto o código do projeto de Samek não lida com saída / transição / ações de entrada na ordem correta.

Se esse código funcionar para o que você precisa fazer e você tiver um compilador C ++ decente para o seu sistema, provavelmente terá um desempenho melhor que a implementação C / C ++ do Miro. O compilador gera uma implementação de máquina de estado de transição O (1) achatada para você. Se a auditoria da saída da montagem confirmar que as otimizações funcionam como desejado, você se aproxima do desempenho teórico. Melhor parte: é um código relativamente pequeno e 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

Código de teste a seguir.

#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
fonte
Hmm ... sth está faltando no seu código. Antes de tudo, inclua dois cabeçalhos, mas forneça apenas o primeiro. Quando eu apenas comento a instrução "include", recebo esse erro ao compilar: d: \ 1 \ hsm> g ++ test.cpp test.cpp: 195: 1: error: especialização de 'static void CompState <H, id, B> :: init (H &) [com H = TestHSM; ID int não assinado = 0u; B = CompState <TestHSM, 0u, TopState <TestHSM>>] 'após instanciação
Freddie Chopin
Eu tive que mover as definições de todos os HSMINIT () para ficar acima da classe TestHSM e ele compila e funciona bem (; A única coisa errada é o fato de que todas as transições são "externas", enquanto deveriam ser "internas" - havia algum debate sobre isso no artigo e o autor decidiu que "extrenal" estava certo, mas as flechas usadas sugerem "interno".
Freddie Chopin
5

A técnica que eu gosto para máquinas de estado (pelo menos para controle de programa) é usar ponteiros de função. Cada estado é representado por uma função diferente. A função pega um símbolo de entrada e retorna o ponteiro da função para o próximo estado. O monitor central de loop de despacho pega a próxima entrada, a alimenta no estado atual e processa o resultado.

A digitação fica um pouco estranha, já que C não tem como indicar os tipos de ponteiros de função retornando, então as funções de estado retornam void*. Mas você pode fazer algo assim:

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

Então, suas funções de estado individuais podem ativar suas entradas para processar e retornar o valor apropriado.

Michael Ekstrand
fonte
+1 isso é muito bom, e oferece lugares agradáveis para funcionalidade mão dentro das funções de transição
Fogo Corvo
5

Caso mais simples

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

Pontos: o estado é privado, não apenas para a unidade de compilação, mas também para o event_handler. Casos especiais podem ser tratados separadamente do comutador principal usando qualquer construção que seja necessária.

Caso mais complexo

Quando o comutador ficar maior que duas telas cheias, divida-o em funções que tratam de cada estado, usando uma tabela de estados para procurar diretamente a função. O estado ainda é privado para o manipulador de eventos. As funções do manipulador de estado retornam o próximo estado. Se necessário, alguns eventos ainda podem receber tratamento especial no manipulador de eventos principais. Eu gosto de lançar pseudo-eventos para entrada e saída de estado e talvez início de máquina de estado:

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

Não tenho certeza se preguei a sintaxe, especialmente em relação à matriz de ponteiros de função. Eu não executei nada disso através de um compilador. Ao revisar, notei que esqueci de descartar explicitamente o próximo estado ao manipular os pseudo-eventos (o parêntese (nulo) antes da chamada para state_handler ()). Isso é algo que eu gosto de fazer, mesmo que os compiladores aceitem a omissão silenciosamente. Diz aos leitores do código que "sim, eu realmente pretendi chamar a função sem usar o valor de retorno", e isso pode impedir as ferramentas de análise estática de alertá-lo. Pode ser idiossincrático, porque não me lembro de ter visto mais alguém fazendo isso.

Pontos: adicionar um pouquinho de complexidade (verificar se o próximo estado é diferente do atual), pode evitar códigos duplicados em outros lugares, porque as funções do manipulador de estados podem aproveitar os pseudo eventos que ocorrem quando um estado é inserido e deixado. Lembre-se de que o estado não pode mudar ao manipular os pseudo eventos, porque o resultado do manipulador de estados é descartado após esses eventos. Obviamente, você pode optar por modificar o comportamento.

Um manipulador de estado ficaria assim:

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

Mais complexidade

Quando a unidade de compilação se tornar muito grande (o que você acha que é, devo dizer em torno de 1000 linhas), coloque cada manipulador de estado em um arquivo separado. Quando cada manipulador de estados se tornar maior que duas telas, divida cada evento em uma função separada, semelhante à maneira como a troca de estado foi dividida. Você pode fazer isso de várias maneiras, separadamente do estado ou usando uma tabela comum ou combinando vários esquemas. Alguns deles foram abordados aqui por outros. Classifique suas tabelas e use a pesquisa binária se a velocidade for um requisito.

Programação genérica

Gostaria que o pré-processador lide com questões como classificar tabelas ou até gerar máquinas de estado a partir de descrições, permitindo que você "escreva programas sobre programas". Acredito que é para isso que as pessoas do Boost estão explorando modelos C ++, mas acho a sintaxe enigmática.

Mesas bidimensionais

Eu usei tabelas de estado / evento no passado, mas devo dizer que, nos casos mais simples, não as acho necessárias e prefiro a clareza e legibilidade da instrução switch, mesmo que ela ultrapasse uma tela inteira. Para casos mais complexos, as tabelas ficam fora de controle rapidamente, como outros observaram. Os idiomas que apresento aqui permitem que você adicione vários eventos e estados quando desejar, sem precisar manter uma tabela que consome memória (mesmo que seja memória de programa).

aviso Legal

Necessidades especiais podem tornar esses idiomas menos úteis, mas eu os achei muito claros e sustentáveis.

Joe, o hamster
fonte
Eu evitaria 'this' como um nome ou símbolo de variável apenas para a associação, mesmo que não seja realmente uma palavra reservada.
XTL
4

Extremamente não testado, mas divertido de codificar, agora em uma versão mais refinada do que minha resposta original; Versões atualizadas podem ser encontradas em mercurial.intuxication.org :

sm.h

#ifndef SM_ARGS
#error "SM_ARGS undefined: " \
    "use '#define SM_ARGS (void)' to get an empty argument list"
#endif

#ifndef SM_STATES
#error "SM_STATES undefined: " \
    "you must provide a list of comma-separated states"
#endif

typedef void (*sm_state) SM_ARGS;
static const sm_state SM_STATES;

#define sm_transit(STATE) ((sm_state (*) SM_ARGS)STATE)

#define sm_def(NAME) \
    static sm_state NAME ## _fn SM_ARGS; \
    static const sm_state NAME = (sm_state)NAME ## _fn; \
    static sm_state NAME ## _fn SM_ARGS

example.c

#include <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
fonte
14
Adoro o comentário "extremamente não testado". Parece indicar que há graus de falta de testamento e que você se esforça bastante para não testá-lo :-) #
395
@ Christoph o link nesta resposta está quebrado. Além disso, você testou esse código ou não? Se foi testado e funciona, remova-o da resposta. Talvez também mostre um exemplo de qual código isso resulta depois que as macros foram expandidas. Eu gosto da ideia geral.
Joakim
4

Gostei muito da resposta do paxdiable e decidi implementar todos os recursos ausentes para o meu aplicativo, como variáveis ​​de guarda e dados específicos da máquina de estado.

Carreguei minha implementação neste site para compartilhar com a comunidade. Foi testado usando o IAR Embedded Workbench for ARM.

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

user108570
fonte
Encontrar isso em 2018 e que ainda é aplicável. Eu estava lendo a resposta @paxdiablo e já usei esse tipo de implementação com sucesso em sistemas embarcados. Esta solução adiciona as coisas que faltam de resposta paxdiablos :)
Kristoffer
4

Outra ferramenta interessante de código aberto é o Yakindu Statechart Tools em statecharts.org . Ele utiliza os gráficos de estados Harel e, portanto, fornece estados hierárquicos e paralelos e gera código C e C ++ (além de Java). Ele não faz uso de bibliotecas, mas segue uma abordagem de 'código simples'. O código basicamente aplica estruturas de casos de comutação. Os geradores de código também podem ser personalizados. Além disso, a ferramenta fornece muitos outros recursos.

Axel T.
fonte
3

Chegando tarde demais (como sempre), mas examinando as respostas até o momento, acho que falta algo importante;

Descobri em meus próprios projetos que pode ser muito útil não ter uma função para todas as combinações válidas de estado / evento. Eu gosto da idéia de efetivamente ter uma tabela 2D de estados / eventos. Mas eu gosto que os elementos da tabela sejam mais do que um simples ponteiro de função. Em vez disso, tento organizar meu design para que, no fundo, ele compreenda um monte de elementos ou ações atômicos simples. Dessa forma, posso listar esses elementos atômicos simples em cada interseção da minha tabela de estado / evento. A idéia é que você não precisa definir uma massa de N ao quadrado (normalmente muito simples) funções. Por que algo tão propenso a erros, demorado, difícil de escrever e de ler, o nome dele?

Eu também incluo um novo estado opcional e um ponteiro de função opcional para cada célula na tabela. O ponteiro de função existe para aqueles casos excepcionais em que você não deseja apenas disparar uma lista de ações atômicas.

Você sabe que está fazendo certo quando pode expressar muitas funcionalidades diferentes, apenas editando sua tabela, sem nenhum novo código para escrever.

Bill Forster
fonte
2
Talvez um exemplo seria legal, não?
jldupont
1
Um exemplo realista que pode ser apresentado isoladamente é uma tarefa desafiadora que exigiria mais tempo do que estou preparado para dar no momento. Existe algo no meu post que seja particularmente difícil de entender? Talvez eu possa expressar mais claramente. A ideia é muito simples; Não defina um mecanismo de estado que exija uma função separada para cada combinação de evento / estado; você terá muitas funções dessa maneira. Em vez disso, encontre outra maneira de descrever a funcionalidade desejada para essa combinação de evento / estado, pelo menos na maioria dos casos.
Bill Forster
2
Entendido: um exemplo de pseudo-código teria sido bom, mas seu argumento é claro.
jldupont
3

Acho que o meu é um pouco diferente do de todos os outros. Um pouco mais de separação de código e dados do que vejo nas outras respostas. Eu realmente li a teoria para escrever isso, que implementa uma linguagem regular completa (sem expressões regulares, infelizmente). Ullman, Minsky, Chomsky. Não posso dizer que entendi tudo, mas me baseiei nos antigos mestres o mais diretamente possível: através de suas palavras.

Eu uso um ponteiro de função para um predicado que determina a transição para um estado 'yes' ou 'no'. Isso facilita a criação de um aceitador de estado finito para um idioma regular que você programa de maneira mais semelhante à linguagem assembly. Por favor, não se deixe levar por minhas escolhas de nome bobo. 'czek' == 'cheque'. 'grok' == [vá procurar no Dicionário Hacker].

Portanto, para cada iteração, o czek chama uma função predicada com o caractere atual como argumento. Se o predicado retornar verdadeiro, o caractere será consumido (o ponteiro avançado) e seguiremos a transição 'y' para selecionar o próximo estado. Se o predicado retornar falso, o caractere NÃO será consumido e seguiremos a transição 'n'. Portanto, toda instrução é um ramo de mão dupla! Eu devia estar lendo A história de Mel na época.

Esse código vem direto do meu intérprete postscript e evoluiu para sua forma atual com muita orientação dos colegas no comp.lang.c. Como o postscript basicamente não possui sintaxe (requer apenas colchetes balanceados), um Aceitador de linguagem regular como esse também funciona como analisador.

/* 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
fonte
2
É isso que qualquer gerador de analisador ou lexer emitirá com prazer para você. Estranhamente. Se você deseja codificá-lo manualmente é questionável. Tem mérito pedagógico, é claro.
Restabeleça Monica
3

O boost.org vem com 2 implementações diferentes de gráfico de estado:

Como sempre, o impulso levará você ao inferno dos modelos.

A primeira biblioteca é para máquinas de estado mais críticas para o desempenho. A segunda biblioteca fornece um caminho de transição direto de um Statechart UML para o código.

Aqui está a pergunta SO solicitando uma comparação entre os dois, onde ambos os autores respondem.

Roland Wolf
fonte
2

Esta série de postagens do Ars OpenForum sobre um pouco complicado de lógica de controle inclui uma implementação muito fácil de seguir como uma máquina de estado em C.

Steven Huwig
fonte
2

Vi isso em algum lugar

#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
fonte
1
É interessante, mas não há voto positivo até você dar um ou dois exemplos (e talvez resultado sem macro) ou alguma discussão sobre por que isso pode ser mais prático do que outro. Uso interessante de colchetes e macros órfãos. Eu imagino que algo semelhante possa ser feito em uma linguagem que faça algum tipo de otimização da recursão da cauda; você poderia usar chamadas de função-se em linha reta e não se preocupar com a sobrecarga do espaço de pilha de lixo chamada de função (que eu acho que é o que as macros são essencialmente superando aqui)
Ape-Inago
2
As vantagens deste método são ...? Vejo várias desvantagens, como ofuscar macros, e o uso gotodisso cria uma dependência de um sistema operacional multitarefa preventivo.
Craig McQueen
2

Como você sugere que pode usar C ++ e, portanto, código OO, sugiro avaliar o padrão 'GoF'state (GoF = Gang of Four, os caras que escreveram o livro de padrões de design que trouxeram padrões de design para os holofotes).

Não é particularmente complexo e é amplamente utilizado e discutido, por isso é fácil ver exemplos e explicações on-line.

Também provavelmente será reconhecível por qualquer outra pessoa que mantenha seu código posteriormente.

Se a eficiência é a preocupação, vale a pena comparar o desempenho para garantir que uma abordagem não OO seja mais eficiente, pois muitos fatores afetam o desempenho e nem sempre é simplesmente OO ruim, código funcional bom. Da mesma forma, se o uso de memória é uma restrição para você, vale a pena fazer alguns testes ou cálculos para verificar se isso realmente será um problema para seu aplicativo em particular se você usar o padrão de estado.

A seguir, estão alguns links para o padrão de estado 'Gof', como Craig sugere:

Mick
fonte
parece mais um comentário: posso sugerir que você o trate como tal? ou seja, não o coloque na seção "resposta".
jldupont
Seria bom se você pudesse fornecer um bom link de URL para o "padrão de estado GoF", para aqueles que não estão familiarizados com ele.
Craig McQueen
1
@jldupont - comentário justo. Alterei o texto para torná-lo uma resposta adequada, pois me sinto baseado na experiência pessoal de que, a menos que haja problemas específicos de desempenho, a abordagem GoF funcione bem e terá uma 'base de usuários' relativamente grande
Mick
@ Craig - adicionou alguns links. Ambos pareciam precisos e claros no momento em que os adicionei.
Mick
2

Aqui está um exemplo de uma máquina de estado finito para Linux que usa filas de mensagens como os eventos. Os eventos são colocados na fila e tratados em ordem. O estado muda dependendo do que acontece para cada evento.

Este é um exemplo para uma conexão de dados com estados como:

  • Não inicializado
  • Inicializado
  • Conectado
  • MTU negociado
  • Autenticado

Um pequeno recurso extra que adicionei foi um carimbo de data / hora para cada mensagem / evento. O manipulador de eventos ignorará os eventos que são muito antigos (eles expiraram). Isso pode acontecer muito no mundo real, onde você pode ficar preso em um estado inesperadamente.

Este exemplo é executado no Linux, use o Makefile abaixo para compilá-lo e brincar com ele.

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
fonte
1

Sua pergunta é bastante genérica.
Aqui estão dois artigos de referência que podem ser úteis,

  1. Implementação de máquina de estado incorporado

    Este artigo descreve uma abordagem simples para implementar uma máquina de estado para um sistema incorporado. Para os fins deste artigo, uma máquina de estados é definida como um algoritmo que pode estar em um de um pequeno número de estados. Um estado é uma condição que causa um relacionamento prescrito de entradas para saídas e de entradas para os próximos estados.
    Um leitor experiente notará rapidamente que as máquinas de estado descritas neste artigo são máquinas Mealy. Uma máquina Mealy é uma máquina de estado em que as saídas são uma função do estado atual e da entrada, em oposição a uma máquina de Moore, na qual as saídas são uma função apenas do estado.

    • Codificando máquinas de estado em C e C ++

      Minha preocupação neste artigo é com os fundamentos de máquina de estado e algumas diretrizes diretas de programação para codificar máquinas de estado em C ou C ++. Espero que essas técnicas simples possam se tornar mais comuns, para que você (e outros) possam ver facilmente a estrutura da máquina de estado diretamente no código-fonte.

nik
fonte
1

Este é um post antigo com muitas respostas, mas pensei em adicionar minha própria abordagem à máquina de estados finitos em C. Fiz um script Python para produzir o código C do esqueleto para qualquer número de estados. Esse script está documentado no GituHub em FsmTemplateC

Este exemplo é baseado em outras abordagens sobre as quais eu li. Ele não usa instruções goto ou switch, mas possui funções de transição em uma matriz de ponteiro (tabela de consulta). O código baseia-se em uma grande macro inicializadora de várias linhas e recursos C99 (inicializadores designados e literais compostos). Portanto, se você não gosta dessas coisas, talvez não goste dessa abordagem.

Aqui está um script Python de um exemplo de catraca que gera código C de 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)

O cabeçalho de saída gerado contém os typedefs:

/* function options (EDIT) */
typedef struct FsmTurnstileFopts {
    /* define your options struct here */
} FsmTurnstileFopts;

/* transition check */
typedef enum eFsmTurnstileCheck {
    EFSM_TURNSTILE_TR_RETREAT,
    EFSM_TURNSTILE_TR_ADVANCE,
    EFSM_TURNSTILE_TR_CONTINUE,
    EFSM_TURNSTILE_TR_BADINPUT
} eFsmTurnstileCheck;

/* states (enum) */
typedef enum eFsmTurnstileState {
    EFSM_TURNSTILE_ST_LOCKED,
    EFSM_TURNSTILE_ST_UNLOCKED,
    EFSM_TURNSTILE_NUM_STATES
} eFsmTurnstileState;

/* inputs (enum) */
typedef enum eFsmTurnstileInput {
    EFSM_TURNSTILE_IN_COIN,
    EFSM_TURNSTILE_IN_PUSH,
    EFSM_TURNSTILE_NUM_INPUTS,
    EFSM_TURNSTILE_NOINPUT
} eFsmTurnstileInput;

/* finite state machine struct */
typedef struct FsmTurnstile {
    eFsmTurnstileInput input;
    eFsmTurnstileCheck check;
    eFsmTurnstileState cur;
    eFsmTurnstileState cmd;
    eFsmTurnstileState **transition_table;
    void (***state_transitions)(struct FsmTurnstile *, FsmTurnstileFopts *);
    void (*run)(struct FsmTurnstile *, FsmTurnstileFopts *, const eFsmTurnstileInput);
} FsmTurnstile;

/* transition functions */
typedef void (*pFsmTurnstileStateTransitions)(struct FsmTurnstile *, FsmTurnstileFopts *);
  • enum eFsmTurnstileChecké usado para determinar se uma transição foi bloqueada EFSM_TURNSTILE_TR_RETREAT, permitida a progressão EFSM_TURNSTILE_TR_ADVANCEou a chamada de função não foi precedida por uma transição com EFSM_TURNSTILE_TR_CONTINUE.
  • enum eFsmTurnstileStateé simplesmente a lista de estados.
  • enum eFsmTurnstileInputé simplesmente a lista de entradas.
  • A FsmTurnstileestrutura é o coração da máquina de estados com a verificação de transição, a tabela de pesquisa de funções, o estado atual, o estado comandado e um alias para a função principal que executa a máquina.
  • Todo ponteiro de função (alias) FsmTurnstilesó deve ser chamado a partir da estrutura e deve ter sua primeira entrada como ponteiro para si mesmo, a fim de manter um estado persistente, estilo orientado a objeto.

Agora, para as declarações de função no cabeçalho:

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

Os nomes das funções estão no formato {prefix}_{from}_{to}, onde {from}é o estado anterior (atual) e {to}o próximo estado. Observe que, se a tabela de transição não permitir determinadas transições, um ponteiro NULL em vez de um ponteiro de função será definido. Finalmente, a mágica acontece com uma macro. Aqui construímos a tabela de transição (matriz de enumerações de estado) e as funções de transição de estado consultam a tabela (uma matriz de ponteiros de função):

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

Ao criar o FSM, a macro FSM_EXAMPLE_CREATE() deve ser usada.

Agora, no código-fonte, todas as funções de transição de estado declaradas acima devem ser preenchidas. A FsmTurnstileFoptsestrutura pode ser usada para transmitir dados de / para a máquina de estado. Toda transição deve fsm->checkser igual a, EFSM_EXAMPLE_TR_RETREATpara impedir a transição ou EFSM_EXAMPLE_TR_ADVANCEpermitir a transição para o estado comandado. Um exemplo de trabalho pode ser encontrado em (FsmTemplateC) [ https://github.com/ChisholmKyle/FsmTemplateC] .

Aqui está o uso real muito simples em seu 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 esse negócio de cabeçalho e todas essas funções apenas para ter uma interface simples e rápida vale a pena em minha mente.

ChisholmKyle
fonte
0

Você pode usar a biblioteca de código aberto OpenFST .

O OpenFst é uma biblioteca para construção, combinação, otimização e pesquisa de transdutores de estado finito ponderado (FSTs). Os transdutores de estado finito ponderado são autômatos, onde cada transição possui um rótulo de entrada, um rótulo de saída e um peso. O aceitador de estado finito mais familiar é representado como um transdutor com a etiqueta de entrada e saída de cada transição igual. Os aceitadores de estado finito são usados ​​para representar conjuntos de cadeias (especificamente, conjuntos regulares ou racionais); transdutores de estado finito são usados ​​para representar relações binárias entre pares de strings (especificamente, transduções racionais). Os pesos podem ser usados ​​para representar o custo de uma determinada transição.

Vicky Chijwani
fonte
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
fonte
Pode ainda optimizá-lo para a segurança usando uma matriz de ponteiros de função constantes para funções
AlphaGoku
0

Eu pessoalmente uso estruturas de auto-referência em combinação com matrizes de ponteiros. Carreguei um tutorial no github há algum tempo, link:

https://github.com/mmelchger/polling_state_machine_c

Nota: Percebo que esse encadeamento é bastante antigo, mas espero receber informações e idéias sobre o design da máquina de estado, além de poder fornecer um exemplo para um possível design de máquina de estado em C.

mmoment
fonte
0

Você pode considerar UML-state-machine-in-c , uma estrutura de máquina de estado "leve" em C. Escrevi essa estrutura para dar suporte à máquina de estado finita e à máquina de estado hierárquica . Compare com tabelas de estado ou casos de comutação simples, uma abordagem de estrutura é mais escalável. Pode ser usado para máquinas de estados finitos simples para máquinas de estados hierárquicos complexos.

Máquina de estado é representada pela state_machine_testrutura. Ele contém apenas dois membros "Evento" e um ponteiro para o "estado_t".

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

state_machine_tdeve ser o primeiro membro da sua estrutura de máquina de estado. por exemplo

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 contém um manipulador para o estado e também manipuladores opcionais para ação de entrada e saída.

//! 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.
};

Se a estrutura estiver configurada para uma máquina de estado hierárquica, o state_t conterá um ponteiro para o estado pai e filho.

O Framework fornece uma API dispatch_eventpara despachar o evento para a máquina de estado e switch_statedisparar a transição de estado.

Para mais detalhes sobre como implementar uma máquina de estado hierárquica, consulte o repositório GitHub .

exemplos 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
fonte
-1

Aqui está um método para uma máquina de estados que usa macros, de modo que cada função possa ter seu próprio conjunto de estados: https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code -at

É intitulado "simular multitarefa", mas esse não é o único uso.

Este método usa retornos de chamada para capturar em cada função de onde parou. Cada função contém uma lista de estados exclusivos para cada função. Um "loop inativo" central é usado para executar as máquinas de estado. O "loop inativo" não tem idéia de como funcionam as máquinas de estado; são as funções individuais que "sabem o que fazer". Para escrever código para as funções, basta criar uma lista de estados e usar as macros para "suspender" e "retomar". Usei essas macros na Cisco quando escrevi a Transceiver Library para o switch Nexus 7000.

eddyq
fonte