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

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


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

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

Править: Для C++ я думаю, что библиотека Boost Statechart могла бы быть способом пойти. Однако это не помогает с C. Позволяет концентрату на варианте использования C.

114
задан Machavity 2 November 2018 в 18:48
поделиться

13 ответов

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

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

табличный подход легче поддержать и расшириться и более простой отобразиться на диаграммы состояний.

127
ответ дан Ricket 24 November 2019 в 02:34
поделиться

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

я не могу говорить с использованием его, все же. Не используемый это самостоятельно (все же)

-1
ответ дан jdt141 24 November 2019 в 02:34
поделиться

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

0
ответ дан Bruno De Fraine 24 November 2019 в 02:34
поделиться

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

1
ответ дан Benoit 24 November 2019 в 02:34
поделиться

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

1
ответ дан Phil Wright 24 November 2019 в 02:34
поделиться

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

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

2
ответ дан Peter K. 24 November 2019 в 02:34
поделиться

переключатель () является мощным и стандартным способом реализовать конечные автоматы в 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;
}
4
ответ дан Commodore Jaeger 24 November 2019 в 02:34
поделиться

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

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
}

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

4
ответ дан Mark 24 November 2019 в 02:34
поделиться

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

9
ответ дан geocoin 24 November 2019 в 02:34
поделиться

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

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;
    }
    ...
}
10
ответ дан jsl4980 24 November 2019 в 02:34
поделиться

Вы, возможно, видели мой ответ на другой вопрос 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:

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

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

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

25
ответ дан Remo.D 24 November 2019 в 02:34
поделиться

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

2
ответ дан pklausner 24 November 2019 в 02:34
поделиться

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

0
ответ дан 24 November 2019 в 02:34
поделиться
Другие вопросы по тегам:

Похожие вопросы: