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

Нам необходимо реализовать простую государственную машину в C .
Стандартный оператор switch - лучший способ?
У нас есть текущее состояние (состояние) и триггер перехода.

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

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

РЕДАКТИРОВАТЬ: Для С ++ я думаю, что библиотека Boost Statechart может быть подходящим вариантом. Однако это не помогает с 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», который, к сожалению, больше не издается.

Я также использовал табличный подход. Однако есть накладные расходы. Зачем хранить второй список указателей? Функция в 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 и тип enum для своего состояния. Сделайте свои переходы внутри оператора 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;
    }
    ...
}

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

Диаграмма состояний может быть реализована в трех основных направлениях: вложенная выключатель , то Паттерн состояние , и состояние таблицы .

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

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

Фаулер привел пример кода 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:

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

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

Исходное состояние Целевое состояние Действие защиты событий
-------------------------------------------------- ------------------------------------
Экран Выключен Экран Выключен нажмите Мощность кнопки Низкий дисплей Низкая мощность Сообщение  
Экран выключен Экран включен нажатием кнопки! PowerLow
Экран На экране Выключено нажатие Кнопка
Экран Выключен Экран Разъем для зарядки Питание
Экран На экране Разъем для зарядки Питание
Экран Зарядка Экран Выключено Отключено Питание

сравнение

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

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

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

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

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

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

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

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, но этот подход очень прост, не требует каких-либо внешних зависимостей и легко реализуется.

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

Я нашел действительно изящную реализацию автомата Мура на языке 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];  
  }
}

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

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

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

Один из моих любимых паттернов - паттерн государственного проектирования. Реагировать или вести себя по-разному на один и тот же заданный набор входных данных.
Одна из проблем с использованием операторов 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 можно объединить в один файл.

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

Существует книга « Практические диаграммы состояний на C / 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__

Вы можете использовать минималистичную структуру конечного автомата 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 / блоб / ведущий / демо / simple_state_machine_enhanced / readme.md

В C ++ рассмотрите шаблон состояния .

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

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

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