учебные пособия по конечным автоматам

Конечные автоматы в C очень просты, если вы используете указатели на функции.

В основном вам нужно 2 массива - один для указателей функций состояния и один для правил перехода состояний. Каждая функция состояния возвращает код, вы просматриваете таблицу переходов состояний по состоянию и возвращаете код, чтобы найти следующее состояние, а затем просто выполняете его.

int entry_state(void);
int foo_state(void);
int bar_state(void);
int exit_state(void);

/* array and enum below must be in sync! */
int (* state[])(void) = { entry_state, foo_state, bar_state, exit_state};
enum state_codes { entry, foo, bar, end};

enum ret_codes { ok, fail, repeat};
struct transition {
    enum state_codes src_state;
    enum ret_codes   ret_code;
    enum state_codes dst_state;
};
/* transitions from end state aren't needed */
struct transition state_transitions[] = {
    {entry, ok,     foo},
    {entry, fail,   end},
    {foo,   ok,     bar},
    {foo,   fail,   end},
    {foo,   repeat, foo},
    {bar,   ok,     end},
    {bar,   fail,   end},
    {bar,   repeat, foo}};

#define EXIT_STATE end
#define ENTRY_STATE entry

int main(int argc, char *argv[]) {
    enum state_codes cur_state = ENTRY_STATE;
    enum ret_codes rc;
    int (* state_fun)(void);

    for (;;) {
        state_fun = state[cur_state];
        rc = state_fun();
        if (EXIT_STATE == cur_state)
            break;
        cur_state = lookup_transitions(cur_state, rc);
    }

    return EXIT_SUCCESS;
}

Я не ставлю lookup_transitions() функцию, это банально.

Так я годами занимаюсь государственными автоматами.

Я предпочитаю использовать указатели на функции, а не гигантские операторы switch, но, в отличие от ответа qrdl, я обычно не используйте явные коды возврата или таблицы переходов.

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

#include <stdio.h>

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

struct state
{
    state_fn * next;
    int i; // data
};

state_fn foo, bar;

void foo(struct state * state)
{
    printf("%s %i\n", __func__, ++state->i);
    state->next = bar;
}

void bar(struct state * state)
{
    printf("%s %i\n", __func__, ++state->i);
    state->next = state->i < 10 ? foo : 0;
}

int main(void)
{
    struct state state = { foo, 0 };
    while(state.next) state.next(&state);
}

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

Тем не менее, довольно легко реализовать конечные автоматы на C, используя либо операторы switch для отправки событий состояниям (для простых автоматов они в значительной степени кодируют прямо), либо использование таблиц для сопоставления событий с переходами состояний.

Здесь есть пара простых, но достойных статей по базовой структуре для конечных автоматов на C:

• http://www.gedan.net/2008/09/08/finite-state-machine-matrix-style-c-implementation/
• http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/

Изменить: сайт «на обслуживании», ссылки на веб-архив:

• http://web.archive.org/web/20160517005245/http://www.gedan.net/2008/09/08/finite-state-machine-matrix-style-c-implementation < / а>
• http://web.archive.org/web/20160808120758/http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/

switch конечные автоматы на основе операторов часто используют набор макросов, чтобы «скрыть» механизм оператора switch (или использовать набор операторов _3 _ / _ 4 _ / _ 5_ вместо switch) и сделать то, что составляет «язык конечных автоматов» для описание конечного автомата в исходном коде C. Я лично предпочитаю табличный подход, но он определенно имеет свои достоинства, широко используется и может быть эффективным, особенно для более простых автоматов.

Одна такая структура описана Стивом Рабином в " Жемчужины игрового программирования "Глава 3.0 (Разработка общего надежного движка ИИ).

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

• https://contrarymotion.net/2008/02/12/some-code-snippets-for-a-simple-c-state-machine/

Если вас также интересуют реализации конечного автомата C ++, можно найти гораздо больше. Я отправлю указатели, если вам интересно.

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

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

Код написан с использованием C ++ и доступен как ParseFCU. Как видите, сначала он определяет, какую версию мы анализируем, и оттуда он входит в два разных конечных автомата.

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

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

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

Это все, что вам нужно знать.

int state = 0;
while (state < 3)
{
    switch (state)
    {
        case 0:
            // Do State 0 Stuff
            if (should_go_to_next_state)
            {
                state++;
            }
            break;
        case 1:
            // Do State 1 Stuff    
            if (should_go_back) 
            {
                state--;
            }    
            else if (should_go_to_next_state) 
            {
                state++;
            }
            break;
        case 2:
            // Do State 2 Stuff    
            if (should_go_back_two) 
            {
                state -= 2;
            }    
            else if (should_go_to_next_state) 
            {
                state++;
            }
            break;
        default:
            break;
    }
}

Объектно-ориентированное моделирование в реальном времени было фантастическим ( опубликовано в 1994 году и сейчас продается всего за 81 цент плюс 3,99 доллара за доставку).

Есть много уроков для изучения ручного создания конечных автоматов на C, но позвольте мне также предложить компилятор конечных автоматов Ragel:

http://www.complang.org/ragel/

Он имеет довольно простой способ определения конечных автоматов, а затем вы можете генерировать графики, генерировать код в разных стилях (на основе таблиц, на основе goto), анализировать этот код, если хотите, и т. Д. И он мощный, может использоваться в производстве код для различных протоколов.

Конечные автоматы могут быть очень сложными для сложной задачи. Они также подвержены неожиданным ошибкам. Они могут превратиться в кошмар, если кто-то столкнется с ошибкой или потребуется изменить логику в будущем. Их также трудно отслеживать и отлаживать без диаграммы состояний. Структурированное программирование намного лучше (например, вы, вероятно, не будете использовать конечный автомат на уровне основной линии). Вы можете использовать структурированное программирование даже в контексте прерывания (где обычно используются конечные автоматы). См. Эту статью «Макросы для моделирования нескольких код задания / блокировки на уровне прерывания " на codeproject.com.