учебные пособия по конечным машинам [закрыты]

https://stackoverflow.com/questions/1371460

21-09-2019
|

Вопрос

Мне просто интересно, знает ли кто-нибудь о каких-нибудь хороших руководствах в Интернете по разработке конечных автоматов.Или электронные книги?

Я начинаю работать над конечными машинами, и мне просто нужно что-то общее, чтобы начать.

Решение

Конечные автоматы очень просты в 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);
}

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

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

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

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

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

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

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

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

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

Редактировать:Сайт "на обслуживании", ссылки на веб-архив:

switch конечные автоматы, основанные на операторах, часто используют набор макросов, чтобы "скрыть" механику switch оператор (или используйте набор if/then/else утверждения вместо switch) и создайте то, что равносильно "языку FSM" для описания конечного автомата в исходном коде C.Лично я предпочитаю подход, основанный на таблицах, но они, безусловно, имеют свои достоинства, широко используются и могут быть эффективными, особенно для более простых FSMS.

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow