Есть ли типичный шаблон реализации конечного автомата?

Boost имеет библиотеку диаграмм состояний. http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html

Однако я не могу говорить о его использовании. Сам не использовал (пока)

По моему опыту, использование оператора switch - это стандартный способ обработки нескольких возможных состояний. Хотя я удивлен, что вы передаете значение перехода для обработки для каждого состояния. Я думал, что весь смысл конечного автомата в том, что каждое состояние выполняет одно действие. Затем следующее действие / ввод определяет, в какое новое состояние перейти. Поэтому я ожидал, что каждая функция обработки состояния немедленно выполнит все, что зафиксировано для входа в состояние, а затем решит, нужен ли переход в другое состояние.

В C++ рассмотрите Государственный образец.

есть также логическая сетка, который более удобен в обслуживании, поскольку конечный автомат становится больше

В простых случаях вы можете использовать свой метод стиля переключения. Раньше я обнаружил, что хорошо работает и с переходами:

static int current_state;    // should always hold current state -- and probably be an enum or something

void state_leave(int new_state) {
    // do processing on what it means to enter the new state
    // which might be dependent on the current state
}

void state_enter(int new_state) {
    // do processing on what is means to leave the current atate
    // might be dependent on the new state

    current_state = new_state;
}

void state_process() {
    // switch statement to handle current state
}

Я ничего не знаю о библиотеке boost, но этот подход очень прост, не требует каких-либо внешних зависимостей и его легко реализовать.

эта статья хорошо подходит для шаблона состояния (хотя это C++, а не конкретно C).

Если вы можете взять книгу «Шаблоны проектирования Head First», объяснение и пример очень ясны.

Есть книга под названием Практические диаграммы состояний на C / C++. Однако путь слишком тяжеловесен для того, что нам нужно.

Я предпочитаю использовать табличный подход для большинства конечных автоматов:

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

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

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

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

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

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

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

Это, конечно, может быть расширено для поддержки нескольких конечных автоматов и т. д. Также могут быть выполнены действия перехода:

typedef void transition_func_t( instance_data_t *data );

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

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

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

    if ( transition ) {
        transition( data );
    }

    return new_state;
};

Подход, основанный на таблицах, легче поддерживать и расширять, а также проще отображать на диаграммах состояний.

Возможно, вы видели мой ответ на другой вопрос C, где я упомянул FSM! Вот как я это делаю:

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

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

Со следующими определенными макросами

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

Его можно изменить в соответствии с конкретным случаем. Например, у вас может быть файл FSMFILE, которым вы хотите управлять своим FSM, поэтому вы можете включить действие чтения следующего символа в сам макрос:

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

теперь у вас есть два типа переходов: один переходит в состояние и читает новый символ, другой переходит в состояние без использования ввода.

Вы также можете автоматизировать обработку EOF с помощью чего-то вроде:

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

#define ENDFSM    sx_endfsm:

Преимущество этого подхода в том, что вы можете напрямую преобразовать нарисованную вами диаграмму состояний в рабочий код и, наоборот, вы можете легко нарисовать диаграмму состояний из кода.

В других методах реализации конечного автомата структура переходов скрыта в управляющих структурах (в то время как, если, переключатель ...) и контролируется значением переменных (обычно это переменная state), и связать красивую диаграмму с ней может оказаться сложной задачей. запутанный код.

Я узнал об этой технике из статьи, опубликованной в большом журнале Computer Language, который, к сожалению, больше не издается.

Для простого конечного автомата просто используйте оператор switch и тип перечисления для своего состояния. Сделайте свои переходы внутри оператора switch на основе вашего ввода. В реальной программе вы, очевидно, измените «if (input)», чтобы проверить точки перехода. Надеюсь это поможет.

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

my_state_t state = STATE_1;

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

switch () - мощный и стандартный способ реализации конечных автоматов на C, но он может снизить ремонтопригодность, если у вас большое количество состояний. Другой распространенный метод - использовать указатели на функции для сохранения следующего состояния. Этот простой пример реализует триггер установки / сброса:

/* Implement each state as a function with the same prototype */
void state_one(int set, int reset);
void state_two(int set, int reset);

/* Store a pointer to the next state */
void (*next_state)(int set, int reset) = state_one;

/* Users should call next_state(set, reset). This could
   also be wrapped by a real function that validated input
   and dealt with output rather than calling the function
   pointer directly. */

/* State one transitions to state one if set is true */
void state_one(int set, int reset) {
    if (set)
        next_state = state_two;
}

/* State two transitions to state one if reset is true */
void state_two(int set, int reset) {
    if (reset)
        next_state = state_one;
}

Возможно, вы захотите изучить программное обеспечение генератора либеро FSM. Из языка описания состояний и / или редактора диаграмм состояний (Windows) вы можете сгенерировать код для C, C++, java и многих других ... плюс красивую документацию и диаграммы. Исходный код и двоичные файлы из iMatix

Ваш вопрос похож на "есть ли типичный шаблон реализации базы данных"? Ответ зависит от того, чего вы хотите достичь? Если вы хотите реализовать более крупный детерминированный конечный автомат, вы можете использовать модель и генератор конечного автомата. Примеры можно посмотреть на сайте www.StateSoft.org - SM Gallery. Януш Добровольски

Я также использовал табличный подход. Однако есть накладные расходы. Зачем хранить второй список указателей? Функция в C без () является константным указателем. Итак, вы можете:

struct state;
typedef void (*state_func_t)( struct state* );

typedef struct state
{
  state_func_t function;

  // other stateful data

} state_t;

void do_state_initial( state_t* );
void do_state_foo( state_t* );
void do_state_bar( state_t* );

void run_state( state_t* i ) {
    i->function(i);
};

int main( void ) {
    state_t state = { do_state_initial };

    while ( 1 ) {
        run_state( state );

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

Конечно, в зависимости от вашего фактора страха (например, безопасности и скорости) вы можете проверить наличие действительных указателей. Для конечных автоматов, имеющих более трех состояний, описанный выше подход должен содержать меньше инструкций, чем эквивалентный подход с переключением или таблицей. Вы даже можете создать макрос как:

#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))

Кроме того, я чувствую из примера OP, что есть упрощение, которое должно быть сделано при размышлении о / проектировании конечного автомата. Я не думаю, что переходное состояние следует использовать для логики. Каждая функция состояния должна иметь возможность выполнять заданную роль без явного знания прошлого состояния (состояний). В основном вы проектируете, как перейти из состояния, в котором вы находитесь, в другое состояние.

Наконец, не начинайте проектирование конечного автомата, основанного на «функциональных» границах, используйте для этого подфункции. Вместо этого разделите состояния в зависимости от того, когда вам придется подождать, пока что-то произойдет, прежде чем вы сможете продолжить. Это поможет свести к минимуму количество запусков конечного автомата, прежде чем вы получите результат. Это может быть важно при написании функций ввода-вывода или обработчиков прерываний.

Также несколько плюсов и минусов классического оператора switch:

Плюсы:

• он на языке, поэтому он задокументирован и понятен
• состояния определены там, где они называются
• может выполнять несколько состояний за один вызов функции
• код, общий для всех состояний, может выполняться до и после оператора switch

Минусы:

• может выполнять несколько состояний за один вызов функции
• код, общий для всех состояний, может выполняться до и после оператора switch
• реализация переключателя может быть медленной

Обратите внимание на два атрибута: за и против. Я думаю, что переключение дает возможность слишком много делиться между состояниями, и взаимозависимость между состояниями может стать неуправляемой. Однако для небольшого числа состояний он может быть наиболее читаемым и удобным в обслуживании.

Один из моих любимых паттернов - паттерн государственного проектирования. По-разному реагировать на один и тот же набор входных данных или вести себя по-разному. Одна из проблем с использованием операторов switch / case для конечных автоматов заключается в том, что по мере того, как вы создаете больше состояний, switch / case становится все труднее / громоздче для чтения / обслуживания, способствует неорганизованному спагетти-коду и все труднее изменить, не сломав что-то. Я считаю, что использование шаблонов проектирования помогает мне лучше организовать мои данные, и в этом весь смысл абстракции. Вместо того, чтобы разрабатывать свой код состояния на основе того, из какого состояния вы пришли, вместо этого структурируйте свой код так, чтобы он записывал состояние, когда вы входите в новое состояние. Таким образом, вы фактически получите запись своего предыдущего состояния. Мне нравится ответ @JoshPetit, и я продвинул его решение еще на один шаг, взятое прямо из книги GoF:

stateCtxt.h:

#define STATE (void *)
typedef enum fsmSignal
{
   eEnter =0,
   eNormal,
   eExit
}FsmSignalT;

typedef struct fsm 
{
   FsmSignalT signal;
   // StateT is an enum that you can define any which way you want
   StateT currentState;
}FsmT;
extern int STATECTXT_Init(void);
/* optionally allow client context to set the target state */
extern STATECTXT_Set(StateT  stateID);
extern void STATECTXT_Handle(void *pvEvent);

stateCtxt.c:

#include "stateCtxt.h"
#include "statehandlers.h"

typedef STATE (*pfnStateT)(FsmSignalT signal, void *pvEvent);

static FsmT      fsm;
static pfnStateT UsbState ;

int STATECTXT_Init(void)
{    
    UsbState = State1;
    fsm.signal = eEnter;
    // use an enum for better maintainability
    fsm.currentState = '1';
    (*UsbState)( &fsm, pvEvent);
    return 0;
}

static void ChangeState( FsmT *pFsm, pfnStateT targetState )
{
    // Check to see if the state has changed
    if (targetState  != NULL)
    {
        // Call current state's exit event
        pFsm->signal = eExit;
        STATE dummyState = (*UsbState)( pFsm, pvEvent);

        // Update the State Machine structure
        UsbState = targetState ;

        // Call the new state's enter event
        pFsm->signal = eEnter;            
        dummyState = (*UsbState)( pFsm, pvEvent);
    }
}

void STATECTXT_Handle(void *pvEvent)
{
    pfnStateT newState;

    if (UsbState != NULL)
    {
         fsm.signal = eNormal;
         newState = (*UsbState)( &fsm, pvEvent );
         ChangeState( &fsm, newState );
    }        
}


void STATECTXT_Set(StateT  stateID)
{
     prevState = UsbState;
     switch (stateID) 
     {
         case '1':               
            ChangeState( State1 );
            break;
          case '2':
            ChangeState( State2);
            break;
          case '3':
            ChangeState( State3);
            break;
     }
}

statehandlers.h:

/* define state handlers */
extern STATE State1(void);
extern STATE State2(void);
extern STATE State3(void);

statehandlers.c:

#include "stateCtxt.h:"

/* Define behaviour to given set of inputs */
STATE State1(FsmT *fsm, void *pvEvent)
{   
    STATE nextState;
    /* do some state specific behaviours 
     * here
     */
    /* fsm->currentState currently contains the previous state
     * just before it gets updated, so you can implement behaviours 
     * which depend on previous state here
     */
    fsm->currentState = '1';
    /* Now, specify the next state
     * to transition to, or return null if you're still waiting for 
     * more stuff to process.  
     */
    switch (fsm->signal)
    {
        case eEnter:
            nextState = State2;
            break;
        case eNormal:
            nextState = null;
            break;
        case eExit:
            nextState = State2;
            break;
    }

    return nextState;
}

STATE  State3(FsmT *fsm, void *pvEvent)
{
    /* do some state specific behaviours 
     * here
     */
    fsm->currentState = '2';
    /* Now, specify the next state
     * to transition to
     */
     return State1;
}

STATE   State2(FsmT *fsm, void *pvEvent)
{   
    /* do some state specific behaviours 
     * here
     */
    fsm->currentState = '3';
    /* Now, specify the next state
     * to transition to
     */
     return State3;
}

Для большинства государственных машин, особенно. Конечные автоматы, каждое состояние будет знать, каким должно быть его следующее состояние, а также критерии перехода к следующему состоянию. Для проектов со свободным состоянием это может быть не так, поэтому есть возможность предоставить API для перехода между состояниями. Если вы хотите большей абстракции, каждый обработчик состояния можно выделить в отдельный файл, который эквивалентен конкретным обработчикам состояния в книге GoF. Если ваш дизайн прост и содержит всего несколько состояний, то для простоты и stateCtxt.c, и statehandlers.c можно объединить в один файл.

Для компилятора, поддерживающего __COUNTER__, вы можете использовать их для простых (но больших) машин состояний.

  #define START 0      
  #define END 1000

  int run = 1;
  state = START;    
  while(run)
  {
    switch (state)
    {
        case __COUNTER__:
            //do something
            state++;
            break;
        case __COUNTER__:
            //do something
            if (input)
               state = END;
            else
               state++;
            break;
            .
            .
            .
        case __COUNTER__:
            //do something
            if (input)
               state = START;
            else
               state++;
            break;
        case __COUNTER__:
            //do something
            state++;
            break;
        case END:
            //do something
            run = 0;
            state = START;
            break;
        default:
            state++;
            break;
     } 
  } 

Преимущество использования __COUNTER__ вместо жестко закодированных номеров заключается в том, что вы может добавлять состояния в середине других состояний, не перенумеровывая каждый раз все. Если компилятор не поддерживает __COUNTER__, ограниченно можно использовать с осторожностью __LINE__.

Я нашел действительно изящную реализацию автомата Мура на языке C на курсе edx.org Embedded Systems - Shape the World UTAustinX - UT.6.02x, глава 10, авторства Джонатана Вальвано и Рамеша Йеррабалли ....

struct State {
  unsigned long Out;  // 6-bit pattern to output
  unsigned long Time; // delay in 10ms units 
  unsigned long Next[4]; // next state for inputs 0,1,2,3
}; 

typedef const struct State STyp;

//this example has 4 states, defining constants/symbols using #define
#define goN   0
#define waitN 1
#define goE   2
#define waitE 3


//this is the full FSM logic coded into one large array of output values, delays, 
//and next states (indexed by values of the inputs)
STyp FSM[4] = {
 {0x21,3000,{goN,waitN,goN,waitN}}, 
 {0x22, 500,{goE,goE,goE,goE}},
 {0x0C,3000,{goE,goE,waitE,waitE}},
 {0x14, 500,{goN,goN,goN,goN}}};
unsigned long currentState;  // index to the current state 

//super simple controller follows
int main(void){ volatile unsigned long delay;
//embedded micro-controller configuration omitteed [...]
  currentState = goN;  
  while(1){
    LIGHTS = FSM[currentState].Out;  // set outputs lines (from FSM table)
    SysTick_Wait10ms(FSM[currentState].Time);
    currentState = FSM[currentState].Next[INPUT_SENSORS];  
  }
}

В UML Distilled Мартина Фаулера он заявляет (без каламбура) в главе 10 Диаграммы конечных автоматов (выделено мной):

A state diagram can be implemented in three main ways: nested switch, the State pattern, and state tables.

Давайте воспользуемся упрощенным примером состояний дисплея мобильного телефона:

Вложенный переключатель

Фаулер привел пример кода C#, но я адаптировал его к своему примеру.

public void HandleEvent(PhoneEvent anEvent) {
    switch (CurrentState) {
    case PhoneState.ScreenOff:
        switch (anEvent) {
        case PhoneEvent.PressButton:
            if (powerLow) { // guard condition
                DisplayLowPowerMessage(); // action
                // CurrentState = PhoneState.ScreenOff;
            } else {
                CurrentState = PhoneState.ScreenOn;
            }
            break;
        case PhoneEvent.PlugPower:
            CurrentState = PhoneState.ScreenCharging;
            break;
        }
        break;
    case PhoneState.ScreenOn:
        switch (anEvent) {
        case PhoneEvent.PressButton:
            CurrentState = PhoneState.ScreenOff;
            break;
        case PhoneEvent.PlugPower:
            CurrentState = PhoneState.ScreenCharging;
            break;
        }
        break;
    case PhoneState.ScreenCharging:
        switch (anEvent) {
        case PhoneEvent.UnplugPower:
            CurrentState = PhoneState.ScreenOff;
            break;
        }
        break;
    }
}

Государственный образец

Вот реализация моего примера с шаблоном состояния GoF:

Таблицы состояний

Вдохновленный Фаулером, вот таблица для моего примера:

Source State    Target State    Event         Guard        Action
--------------------------------------------------------------------------------------
ScreenOff       ScreenOff       pressButton   powerLow     displayLowPowerMessage  
ScreenOff       ScreenOn        pressButton   !powerLow
ScreenOn        ScreenOff       pressButton
ScreenOff       ScreenCharging  plugPower
ScreenOn        ScreenCharging  plugPower
ScreenCharging  ScreenOff       unplugPower

Сравнение

Вложенный переключатель сохраняет всю логику в одном месте, но код может быть трудночитаемым при большом количестве состояний и переходов. Возможно, это более безопасно и легче проверяется, чем другие подходы (без полиморфизма или интерпретации).

Реализация шаблона состояния потенциально распространяет логику на несколько отдельных классов, что может затруднить понимание ее в целом. С другой стороны, небольшие классы легко понять по отдельности. Дизайн становится особенно хрупким, если вы изменяете поведение, добавляя или удаляя переходы, поскольку они являются методами в иерархии, и в коде может быть много изменений. Если вы живете по принципу дизайна небольших интерфейсов, вы увидите, что этот шаблон на самом деле не так хорош. Однако, если конечный автомат стабилен, то такие изменения не понадобятся.

Подход с использованием таблиц состояний требует написания какого-то интерпретатора для контента (это может быть проще, если у вас есть отражение на языке, который вы используете), что может потребовать много работы заранее. Как указывает Фаулер, если ваша таблица отделена от вашего кода, вы можете изменить поведение своего программного обеспечения без перекомпиляции. Однако это имеет некоторые последствия для безопасности; программное обеспечение работает в зависимости от содержимого внешнего файла.

Изменить (не совсем для языка C)

Также существует подход с плавным интерфейсом (также известный как внутренний язык, специфичный для домена), которому, вероятно, способствуют языки с первоклассные функции. Библиотека без сохранения состояния существует, и этот блог показывает простой пример с кодом. Обсуждается Реализация Java (до Java8). Мне также показали Пример Python на GitHub.

Вы можете использовать минималистичную структуру конечного автомата UML в c. https://github.com/kiishor/UML-State-Machine-in-C

Он поддерживает как конечный, так и иерархический конечный автомат. В нем всего 3 API, 2 структуры и 1 перечисление.

Конечный автомат представлен структурой state_machine_t. Это абстрактная структура, которую можно унаследовать для создания конечного автомата.

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

Состояние представлено указателем на структуру state_t в фреймворке.

Если фреймворк настроен для конечного автомата, то state_t содержит,

typedef struct finite_state_t state_t;

// finite state structure
typedef struct finite_state_t{
  state_handler Handler;        //!< State handler function (function pointer)
  state_handler Entry;          //!< Entry action for state (function pointer)
  state_handler Exit;           //!< Exit action for state (function pointer)
}finite_state_t;

Платформа предоставляет API dispatch_event для отправки события в конечный автомат и два API для обхода состояний.

state_machine_result_t dispatch_event(state_machine_t* const pState_Machine[], uint32_t quantity);

state_machine_result_t switch_state(state_machine_t* const, const state_t*);

state_machine_result_t traverse_state(state_machine_t* const, const state_t*);

Для получения дополнительных сведений о том, как реализовать иерархический конечный автомат, обратитесь к репозиторию GitHub.

примеры кода 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