C State-Design [закрыт]

193

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

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

ПРИМЕЧАНИЕ: я в первую очередь после проверенных и проверенных методов реализации.

ОБНОВЛЕНО: Основываясь на всех замечательных материалах, собранных на SO, я остановился на этой архитектуре:

Насос событий указывает на интегратор событий, который указывает на диспетчера.  Диспетчер указывает на действия от 1 до n, которые указывают на интегратор событий.  Таблица перехода с подстановочными знаками указывает на диспетчера.

jldupont
источник
4
Ответы здесь очень хорошие. Также взгляните на этот дублирующий вопрос, на который также есть несколько хороших ответов: stackoverflow.com/questions/1371460/state-machines-tutorials
Майкл Берр
2
Это также интересно: stackoverflow.com/questions/133214/…
Даниэль Даранас
Смотрите также этот вопрос .
Даниэль Даранас

Ответы:

170

Конечные автоматы, которые я разработал ранее (C, а не C ++), все сводятся к structмассиву и циклу. Структура в основном состоит из состояния и события (для просмотра) и функции, которая возвращает новое состояние, что-то вроде:

typedef struct {
    int st;
    int ev;
    int (*fn)(void);
} tTransition;

Затем вы определяете свои состояния и события с помощью простых определений ( ANYэто специальные маркеры, см. Ниже):

#define ST_ANY              -1
#define ST_INIT              0
#define ST_ERROR             1
#define ST_TERM              2
: :
#define EV_ANY              -1
#define EV_KEYPRESS       5000
#define EV_MOUSEMOVE      5001

Затем вы определяете все функции, которые вызываются переходами:

static int GotKey (void) { ... };
static int FsmError (void) { ... };

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

Использование глобальных переменных не так плохо, как кажется, поскольку FSM обычно блокируется внутри одного модуля компиляции, и все переменные являются статическими по отношению к этому модулю (именно поэтому я использовал кавычки вокруг «global» выше - они более распространены внутри ФСМ, чем истинно глобальный). Как и во всех глобальных, он требует осторожности.

Затем массив переходов определяет все возможные переходы и функции, которые вызываются для этих переходов (включая последний из них для всех):

tTransition trans[] = {
    { ST_INIT, EV_KEYPRESS, &GotKey},
    : :
    { ST_ANY, EV_ANY, &FsmError}
};
#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))

Это означает следующее: если вы находитесь в ST_INITштате и получаете EV_KEYPRESSсобытие, позвоните GotKey.

Работа FSM становится относительно простым циклом:

state = ST_INIT;
while (state != ST_TERM) {
    event = GetNextEvent();
    for (i = 0; i < TRANS_COUNT; i++) {
        if ((state == trans[i].st) || (ST_ANY == trans[i].st)) {
            if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) {
                state = (trans[i].fn)();
                break;
            }
        }
    }
}

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

Это также может гарантировать, что, если вы дойдете до конца массива переходов, вы получите сообщение о том, что ваш FSM не был построен правильно (с помощью ST_ANY/EV_ANYкомбинации.

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

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


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

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

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

paxdiablo
источник
24
Гигантский переключатель смешивает код с FSM. Даже если для каждого перехода есть только вызов функции, есть некоторый код, и кому-то легко злоупотребить этим, просто добавив небольшой 4-строчный переход внутри строки. курица из десяти строк. Тогда это выходит из-под контроля. С массивом struct FSM остается чистым - вы можете видеть каждый переход и эффект (функцию). И я начал, когда перечисления были в мгновение ока в глазах ISO, написание кода для встраиваемых платформ 6809 с компиляторами, которые, скажем так, были не идеальны :-)
paxdiablo
5
Вы правы, перечисления были бы лучше, но я все же предпочитаю использовать FSM в качестве массива структуры. Тогда все это выполняется с помощью данных, а не кода (ну, есть некоторый код, но вероятность запутать тот цикл FSM, который я дал, невелика).
paxdiablo
2
Это хорошо, для конечных автоматов управления процессом, которые я использовал, чтобы всегда добавлять три (возможно, пустые) подсостояния для каждого состояния, чтобы вызов функции состояния стал GotKey (подсостояние), где подсостояние будет: - SS_ENTRY - SS_RUN - SS_EXIT По сути, функция состояния вызывается с подсостоянием SS_ENTRY при входе, чтобы состояние могло восстановить состояние (например, положения исполнительных механизмов). Пока перехода нет, передается значение подсостояния SS_RUN. При переходе функция состояния вызывается из подсостояния SS_EXIT, так что она может выполнять любые очистки (например, освобождать ресурсы).
Метиу
13
Вы упомянули, что вы обмениваетесь данными, используя глобальные переменные, но, вероятно, будет лучше, если вы определите функции состояния, int (*fn)(void*);где void*будет указатель на данные, которые каждая функция состояния принимает в качестве параметра. Тогда функции состояния могут либо использовать данные, либо игнорировать их.
ldog
13
Я использую то же разделение данных и кода для написания автоматов, за исключением того, что мне никогда не приходило в голову вводить «подстановочные» состояния. Интересная идея! Тем не менее, итерация массива переходов может стать дорогой, если у вас много состояний (что было для меня, так как код C был сгенерирован автоматически). В таких ситуациях было бы более эффективно иметь один массив переходов на состояние. Таким образом, состояние больше не является значением перечисления, а является таблицей переходов. Таким образом, вам не придется перебирать все переходы в машине, а только те, которые соответствуют текущему состоянию.
Фрерих Раабе
78

Другие ответы хороши, но очень «легкая» реализация, которую я использовал, когда конечный автомат очень прост, выглядит так:

enum state { ST_NEW, ST_OPEN, ST_SHIFT, ST_END };

enum state current_state = ST_NEW;

while (current_state != ST_END)
{
    input = get_input();

    switch (current_state)
    {
        case ST_NEW:
        /* Do something with input and set current_state */
        break;

        case ST_OPEN:
        /* Do something different and set current_state */
        break;

        /* ... etc ... */
    }
}

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

кафе
источник
37

Извините, что нарушил все правила в информатике, но конечный автомат - одно из немногих (я могу считать только два) мест, где gotoутверждение не только более эффективно, но и делает ваш код чище и легче для чтения. Поскольку gotoоператоры основаны на метках, вы можете называть свои состояния вместо того, чтобы отслеживать беспорядок чисел или использовать перечисление. Это также делает код намного чище, так как вам не нужны все лишние указатели на функции или огромные операторы switch и while. Я уже говорил, что это более эффективно?

Вот как может выглядеть конечный автомат:

void state_machine() {
first_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }

second_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }
}

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

Джейсон Э
источник
4
Это работает только в том случае, если конечный автомат находится в объекте верхнего уровня. В тот момент, когда какой-то другой объект, который время от времени опрашивается / отправляется сообщение, должен иметь состояние, вы застряли на этом подходе (или вы должны сделать его намного более сложным)
skrebbel
1
Это действительно заставляет вас использовать упреждающую многозадачность во всех случаях, кроме самых простых.
Крейг МакКуин
1
Эти gotos могут быть заменены вызовами функций. И если профилировщик скажет вам, что ваша программа тонет из-за накладных расходов на вызов функции, тогда вы можете при необходимости заменить вызовы gotos.
Abtin Forouzandeh
7
@AbtinForouzandeh простая замена gotos вызовами функций вызовет переполнение стека, поскольку стек вызовов очищается только в случае ошибки.
JustMaximumPower
Я согласен с методом Гото. Вот набор макросов, которые иллюстрируют это. А макросы структурируют ваш код так, как если бы вы его кодировали, как обычно. Он также работает на уровне прерываний, где обычно требуются
конечные
30

Вы можете рассмотреть State Machine Compiler http://smc.sourceforge.net/

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

Причина, по которой это делается, а не ручное кодирование с использованием шаблона состояния GoF или любого другого подхода, заключается в том, что после того, как ваш конечный автомат выражается в виде кода, базовая структура имеет тенденцию исчезать под весом стандартного шаблона, который необходимо сгенерировать для его поддержки. Использование этого подхода дает вам отличное разделение задач, и вы сохраняете структуру своего конечного автомата «видимой». Автоматически сгенерированный код входит в модули, к которым вам не нужно прикасаться, чтобы вы могли вернуться и поиграть со структурой конечного автомата, не влияя на написанный вами вспомогательный код.

Извините, я преувеличиваю и, несомненно, откладываю всех. Но это первоклассная утилита, и хорошо документированная тоже.

willw
источник
20

Обязательно проверьте работу Миро Самека (блог State Space , сайт State Machines & Tools ), чьи статьи в C / C ++ Users Journal были замечательными.

Веб-сайт содержит полную (C / C ++) реализацию как с открытым исходным кодом, так и с коммерческой лицензией платформы конечного автомата (QP Framework) , обработчик событий (QEP) , базовый инструмент моделирования (QM) и инструмент трассировки (QSpy), который позволяют рисовать конечные автоматы, создавать код и отлаживать их.

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

Веб-сайт также содержит ссылки на несколько пакетов поддержки плат для использования программного обеспечения со встроенными платформами.

Даниэль Даранас
источник
Я изменил название вопроса в соответствии с вашим каламбуром.
jldupont
@jldupont: Я просто имел в виду, что лучше уточнить. Я удалил ненужные части моего ответа сейчас.
Даниэль Даранас
1
Я добавил, что ожидать на веб-сайте / книге, успешно использовав программное обеспечение самостоятельно; это лучшая книга на моей книжной полке.
Adriaan
@Adriann, отличное объяснение! Я только что изменил домашний сайт, предыдущая ссылка перестала работать.
Даниэль Даранас
2
Ссылки либо устарели, либо указывают на домашнюю страницу сайта, которая, похоже, изменила свое направление на встроенное программное обеспечение. Вы все еще можете увидеть некоторые материалы на сайте state-machine.com/resources/articles.php , но даже там большинство ссылок, связанных с конечным автоматом , не работает. Это одна из единственных хороших ссылок: state-machine.com/resources/…
Татьяна Рачева,
11

Я сделал нечто похожее на то, что описывает paxdiablo, только вместо массива переходов между состояниями и событиями я установил двумерный массив указателей функций со значением события в качестве индекса одной оси и значением текущего состояния в виде другой. Тогда я просто звоню, state = state_table[event][state](params)и происходит правильная вещь. Ячейки, представляющие недопустимые комбинации состояния / события, получают указатель на функцию, которая так говорит, конечно.

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

Генеральный директор
источник
1
Похоже, что это решение не очень хорошо масштабируется: слишком много заполнения стола, нет?
jldupont
2
+1. Проблема масштабирования в данном случае связана с памятью. У моего собственного решения есть проблема масштабирования, т. Е. Время, затрачиваемое на сканирование таблицы переходов (хотя вы можете оптимизировать вручную для наиболее распространенных переходов). Этот жертвует памятью ради скорости - это просто компромисс. Вам, вероятно, понадобятся проверки на наличие границ, но это не плохое решение.
paxdiablo
Ребята. Мой комментарий вышел не так, как задумано: я имел в виду, что он гораздо более трудоемкий и подвержен ошибкам. Если вы добавляете состояние / событие, нужно много редактировать.
Jldupont
3
Никто не сказал, что 2D массив был инициализирован вручную. Может быть, есть что-то, что читает конфигурационный файл и создает его (или, по крайней мере, может быть).
Джон Цвинк
Один из способов инициализации таких массивов состоит в том, чтобы использовать препроцессор, являющийся поздним связывателем (в отличие от раннего связывания). Вы определяете список всех состояний #define STATE_LIST() \STATE_LIST_ENTRY(state1)\STATE_LIST_ENTRY(state2)\...(подразумеваемый символ новой строки после каждого \ ), в которых вы (пере) определяете макрос ввода при использовании макроса STATE_LIST. Пример - создание массива названий состояний: #define STATE_LIST_ENTRY(s) #s , \n const char *state_names[] = { STATE_LIST() };\n #undef STATE_LIST_ENTRY. Некоторая работа сначала настраивается, но это очень мощно. Добавить новое состояние -> гарантированно без промахов.
Хловдал
9

Стефан Хайнцманн (Stefan Heinzmann) в своей статье дал замечательную «основу» конечного автомата C ++ на основе шаблонов. .

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

Основным нововведением здесь является то, что компилятор генерирует очень эффективный код. Пустые действия входа / выхода бесплатны. Непустые действия входа / выхода встроены. Компилятор также проверяет полноту диаграммы состояний. Пропущенные действия приводят к ошибкам компоновки. Единственное, что не пойман, это пропавшийTop::init .

Это очень хорошая альтернатива реализации Miro Samek, если вы можете жить без того, чего не хватает - это далеко от полной реализации UML Statechart, хотя она правильно реализует семантику UML, тогда как код Samek по своему дизайну не обрабатывает выход / переход / вход действия в правильном порядке.

Если этот код работает для того, что вам нужно, и у вас есть приличный компилятор C ++ для вашей системы, он, вероятно, будет работать лучше, чем реализация Miro C / C ++. Компилятор сгенерирует для вас плоскую реализацию конечного автомата O (1). Если аудит результатов сборки подтверждает, что оптимизации работают так, как вам нужно, вы приближаетесь к теоретической производительности. Лучшая часть: это относительно крошечный, легкий для понимания код.

#ifndef HSM_HPP
#define HSM_HPP

// This code is from:
// Yet Another Hierarchical State Machine
// by Stefan Heinzmann
// Overload issue 64 december 2004
// http://accu.org/index.php/journals/252

/* This is a basic implementation of UML Statecharts.
 * The key observation is that the machine can only
 * be in a leaf state at any given time. The composite
 * states are only traversed, never final.
 * Only the leaf states are ever instantiated. The composite
 * states are only mechanisms used to generate code. They are
 * never instantiated.
 */

// Helpers

// A gadget from Herb Sutter's GotW #71 -- depends on SFINAE
template<class D, class B>
class IsDerivedFrom {
    class Yes { char a[1]; };
    class No  { char a[10]; };
    static Yes Test(B*); // undefined
    static No Test(...); // undefined
public:
    enum { Res = sizeof(Test(static_cast<D*>(0))) == sizeof(Yes) ? 1 : 0 };
};

template<bool> class Bool {};

// Top State, Composite State and Leaf State

template <typename H>
struct TopState {
    typedef H Host;
    typedef void Base;
    virtual void handler(Host&) const = 0;
    virtual unsigned getId() const = 0;
};

template <typename H, unsigned id, typename B>
struct CompState;

template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct CompState : B {
    typedef B Base;
    typedef CompState<H, id, Base> This;
    template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
    static void init(H&); // no implementation
    static void entry(H&) {}
    static void exit(H&) {}
};

template <typename H>
struct CompState<H, 0, TopState<H> > : TopState<H> {
    typedef TopState<H> Base;
    typedef CompState<H, 0, Base> This;
    template <typename X> void handle(H&, const X&) const {}
    static void init(H&); // no implementation
    static void entry(H&) {}
    static void exit(H&) {}
};

template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct LeafState : B {
    typedef H Host;
    typedef B Base;
    typedef LeafState<H, id, Base> This;
    template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
    virtual void handler(H& h) const { handle(h, *this); }
    virtual unsigned getId() const { return id; }
    static void init(H& h) { h.next(obj); } // don't specialize this
    static void entry(H&) {}
    static void exit(H&) {}
    static const LeafState obj; // only the leaf states have instances
};

template <typename H, unsigned id, typename B>
const LeafState<H, id, B> LeafState<H, id, B>::obj;

// Transition Object

template <typename C, typename S, typename T>
// Current, Source, Target
struct Tran {
    typedef typename C::Host Host;
    typedef typename C::Base CurrentBase;
    typedef typename S::Base SourceBase;
    typedef typename T::Base TargetBase;
    enum { // work out when to terminate template recursion
        eTB_CB = IsDerivedFrom<TargetBase, CurrentBase>::Res,
        eS_CB = IsDerivedFrom<S, CurrentBase>::Res,
        eS_C = IsDerivedFrom<S, C>::Res,
        eC_S = IsDerivedFrom<C, S>::Res,
        exitStop = eTB_CB && eS_C,
        entryStop = eS_C || eS_CB && !eC_S
    };
    // We use overloading to stop recursion.
    // The more natural template specialization
    // method would require to specialize the inner
    // template without specializing the outer one,
    // which is forbidden.
    static void exitActions(Host&, Bool<true>) {}
    static void exitActions(Host&h, Bool<false>) {
        C::exit(h);
        Tran<CurrentBase, S, T>::exitActions(h, Bool<exitStop>());
    }
    static void entryActions(Host&, Bool<true>) {}
    static void entryActions(Host& h, Bool<false>) {
        Tran<CurrentBase, S, T>::entryActions(h, Bool<entryStop>());
        C::entry(h);
    }
    Tran(Host & h) : host_(h) {
        exitActions(host_, Bool<false>());
    }
    ~Tran() {
        Tran<T, S, T>::entryActions(host_, Bool<false>());
        T::init(host_);
    }
    Host& host_;
};

// Initializer for Compound States

template <typename T>
struct Init {
    typedef typename T::Host Host;
    Init(Host& h) : host_(h) {}
    ~Init() {
        T::entry(host_);
        T::init(host_);
    }
    Host& host_;
};

#endif // HSM_HPP

Тестовый код следует.

#include <cstdio>
#include "hsm.hpp"
#include "hsmtest.hpp"

/* Implements the following state machine from Miro Samek's
 * Practical Statecharts in C/C++
 *
 * |-init-----------------------------------------------------|
 * |                           s0                             |
 * |----------------------------------------------------------|
 * |                                                          |
 * |    |-init-----------|        |-------------------------| |
 * |    |       s1       |---c--->|            s2           | |
 * |    |----------------|<--c----|-------------------------| |
 * |    |                |        |                         | |
 * |<-d-| |-init-------| |        | |-init----------------| | |
 * |    | |     s11    |<----f----| |          s21        | | |
 * | /--| |------------| |        | |---------------------| | |
 * | a  | |            | |        | |                     | | |
 * | \->| |            |------g--------->|-init------|    | | |
 * |    | |____________| |        | |-b->|    s211   |---g--->|
 * |    |----b---^       |------f------->|           |    | | |
 * |    |________________|        | |<-d-|___________|<--e----|
 * |                              | |_____________________| | |
 * |                              |_________________________| |
 * |__________________________________________________________|
 */

class TestHSM;

typedef CompState<TestHSM,0>     Top;
typedef CompState<TestHSM,1,Top>   S0;
typedef CompState<TestHSM,2,S0>      S1;
typedef LeafState<TestHSM,3,S1>        S11;
typedef CompState<TestHSM,4,S0>      S2;
typedef CompState<TestHSM,5,S2>        S21;
typedef LeafState<TestHSM,6,S21>         S211;

enum Signal { A_SIG, B_SIG, C_SIG, D_SIG, E_SIG, F_SIG, G_SIG, H_SIG };

class TestHSM {
public:
    TestHSM() { Top::init(*this); }
    ~TestHSM() {}
    void next(const TopState<TestHSM>& state) {
        state_ = &state;
    }
    Signal getSig() const { return sig_; }
    void dispatch(Signal sig) {
        sig_ = sig;
        state_->handler(*this);
    }
    void foo(int i) {
        foo_ = i;
    }
    int foo() const {
        return foo_;
    }
private:
    const TopState<TestHSM>* state_;
    Signal sig_;
    int foo_;
};

bool testDispatch(char c) {
    static TestHSM test;
    if (c<'a' || 'h'<c) {
        return false;
    }
    printf("Signal<-%c", c);
    test.dispatch((Signal)(c-'a'));
    printf("\n");
    return true;
}

int main(int, char**) {
    testDispatch('a');
    testDispatch('e');
    testDispatch('e');
    testDispatch('a');
    testDispatch('h');
    testDispatch('h');
    return 0;
}

#define HSMHANDLER(State) \
    template<> template<typename X> inline void State::handle(TestHSM& h, const X& x) const

HSMHANDLER(S0) {
    switch (h.getSig()) {
    case E_SIG: { Tran<X, This, S211> t(h);
        printf("s0-E;");
        return; }
    default:
        break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S1) {
    switch (h.getSig()) {
    case A_SIG: { Tran<X, This, S1> t(h);
        printf("s1-A;"); return; }
    case B_SIG: { Tran<X, This, S11> t(h);
        printf("s1-B;"); return; }
    case C_SIG: { Tran<X, This, S2> t(h);
        printf("s1-C;"); return; }
    case D_SIG: { Tran<X, This, S0> t(h);
        printf("s1-D;"); return; }
    case F_SIG: { Tran<X, This, S211> t(h);
        printf("s1-F;"); return; }
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S11) {
    switch (h.getSig()) {
    case G_SIG: { Tran<X, This, S211> t(h);
        printf("s11-G;"); return; }
    case H_SIG: if (h.foo()) {
            printf("s11-H");
            h.foo(0); return;
        } break;
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S2) {
    switch (h.getSig()) {
    case C_SIG: { Tran<X, This, S1> t(h);
        printf("s2-C"); return; }
    case F_SIG: { Tran<X, This, S11> t(h);
        printf("s2-F"); return; }
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S21) {
    switch (h.getSig()) {
    case B_SIG: { Tran<X, This, S211> t(h);
        printf("s21-B;"); return; }
    case H_SIG: if (!h.foo()) {
            Tran<X, This, S21> t(h);
            printf("s21-H;"); h.foo(1);
            return;
        } break;
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S211) {
    switch (h.getSig()) {
    case D_SIG: { Tran<X, This, S21> t(h);
        printf("s211-D;"); return; }
    case G_SIG: { Tran<X, This, S0> t(h);
        printf("s211-G;"); return; }
    }
    return Base::handle(h, x);
}

#define HSMENTRY(State) \
    template<> inline void State::entry(TestHSM&) { \
        printf(#State "-ENTRY;"); \
    }

HSMENTRY(S0)
HSMENTRY(S1)
HSMENTRY(S11)
HSMENTRY(S2)
HSMENTRY(S21)
HSMENTRY(S211)

#define HSMEXIT(State) \
    template<> inline void State::exit(TestHSM&) { \
        printf(#State "-EXIT;"); \
    }

HSMEXIT(S0)
HSMEXIT(S1)
HSMEXIT(S11)
HSMEXIT(S2)
HSMEXIT(S21)
HSMEXIT(S211)

#define HSMINIT(State, InitState) \
    template<> inline void State::init(TestHSM& h) { \
       Init<InitState> i(h); \
       printf(#State "-INIT;"); \
    }

HSMINIT(Top, S0)
HSMINIT(S0, S1)
HSMINIT(S1, S11)
HSMINIT(S2, S21)
HSMINIT(S21, S211)
Куба Обер
источник
Хм ... в вашем коде нет ничего. Прежде всего, вы включаете два заголовка, но предоставляете только первый. Когда я просто комментирую оператор include, я получаю эту ошибку при компиляции: d: \ 1 \ hsm> g ++ test.cpp test.cpp: 195: 1: error: специализация 'static void CompState <H, id, B> :: init (H &) [с H = TestHSM; без знака int id = 0u; B = CompState <TestHSM, 0u, TopState <TestHSM>>] 'после создания экземпляра
Фредди Шопен,
Мне пришлось переместить определения всех HSMINIT () выше класса TestHSM, и он компилируется и работает нормально (; Единственное, что неправильно, это то, что все переходы являются «внешними», в то время как они должны быть «внутренними» - там было некоторые споры об этом в статье , и автор решили , что «extrenal» был прав, но стрелы использовали предложить «внутренние».
Фредди Шопен
5

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

Печатание на нем становится немного странным, так как C не может указать типы указателей на функции, возвращающие себя, поэтому функции состояния возвращают void*. Но вы можете сделать что-то вроде этого:

typedef void* (*state_handler)(input_symbol_t);
void dispatch_fsm()
{
    state_handler current = initial_handler;
    /* Let's assume returning null indicates end-of-machine */
    while (current) {
        current = current(get_input);
    }
 }

Тогда ваши индивидуальные функции состояния могут включить их ввод для обработки и вернуть соответствующее значение.

Майкл Экстранд
источник
+1 это действительно хорошо, и предоставляет хорошие места для передачи функциональности внутри функций перехода
Fire Crow
5

Самый простой случай

enum event_type { ET_THIS, ET_THAT };
union event_parm { uint8_t this; uint16_t that; }
static void handle_event(enum event_type event, union event_parm parm)
{
  static enum { THIS, THAT } state;
  switch (state)
  {
    case THIS:
    switch (event)
    {
      case ET_THIS:
      // Handle event.
      break;

      default:
      // Unhandled events in this state.
      break;
    }
    break;

    case THAT:
    // Handle state.
    break;
  }
}

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

Более сложный случай

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

enum state_type { THIS, THAT, FOO, NA };
enum event_type { ET_START, ET_ENTER, ET_EXIT, ET_THIS, ET_THAT, ET_WHATEVER, ET_TIMEOUT };
union event_parm { uint8_t this; uint16_t that; };
static void handle_event(enum event_type event, union event_parm parm)
{
  static enum state_type state;
  static void (* const state_handler[])(enum event_type event, union event_parm parm) = { handle_this, handle_that };
  enum state_type next_state = state_handler[state](event, parm);
  if (NA != next_state && state != next_state)
  {
    (void)state_handler[state](ET_EXIT, 0);
    state = next_state;
    (void)state_handler[state](ET_ENTER, 0);
  }
}

Я не уверен, прибил ли я синтаксис, особенно относительно массива указателей на функции. Я не запускал ничего из этого через компилятор. После проверки я заметил, что забыл явно отбрасывать следующее состояние при обработке псевдо-событий (скобка (void) перед вызовом state_handler ()). Это то, что мне нравится делать, даже если компиляторы молча принимают это упущение. Он сообщает читателям кода, что «да, я действительно имел в виду вызов функции без использования возвращаемого значения», и это может помешать инструментам статического анализа предупреждать об этом. Это может быть своеобразным, потому что я не помню, чтобы кто-нибудь еще делал это.

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

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

static enum state_type handle_this(enum event_type event, union event_parm parm)
{
  enum state_type next_state = NA;
  switch (event)
  {
    case ET_ENTER:
    // Start a timer to do whatever.
    // Do other stuff necessary when entering this state.
    break;

    case ET_WHATEVER:
    // Switch state.
    next_state = THAT;
    break;

    case ET_TIMEOUT:
    // Switch state.
    next_state = FOO;
    break;

    case ET_EXIT:
    // Stop the timer.
    // Generally clean up this state.
    break;
  }
  return next_state;
}

Больше сложности

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

Общее программирование

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

Двумерные таблицы

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

отказ

Особые потребности могут сделать эти идиомы менее полезными, но я обнаружил, что они очень ясны и понятны.

Джо Хомяк
источник
Я бы избегал «this» как имени переменной или символа только для ассоциации, даже если это на самом деле не зарезервированное слово.
XTL
4

Крайне непроверенный, но забавный код, теперь в более изысканной версии, чем мой первоначальный ответ; Актуальные версии можно найти на mercurial.intuxication.org :

sm.h

#ifndef SM_ARGS
#error "SM_ARGS undefined: " \
    "use '#define SM_ARGS (void)' to get an empty argument list"
#endif

#ifndef SM_STATES
#error "SM_STATES undefined: " \
    "you must provide a list of comma-separated states"
#endif

typedef void (*sm_state) SM_ARGS;
static const sm_state SM_STATES;

#define sm_transit(STATE) ((sm_state (*) SM_ARGS)STATE)

#define sm_def(NAME) \
    static sm_state NAME ## _fn SM_ARGS; \
    static const sm_state NAME = (sm_state)NAME ## _fn; \
    static sm_state NAME ## _fn SM_ARGS

example.c

#include <stdio.h>

#define SM_ARGS (int i)
#define SM_STATES EVEN, ODD
#include "sm.h"

sm_def(EVEN)
{
    printf("even %i\n", i);
    return ODD;
}

sm_def(ODD)
{
    printf("odd  %i\n", i);
    return EVEN;
}

int main(void)
{
    int i = 0;
    sm_state state = EVEN;

    for(; i < 10; ++i)
        state = sm_transit(state)(i);

    return 0;
}
Christoph
источник
14
Мне нравится "крайне непроверенный" комментарий. Кажется, указывает на то, что существуют степени непроверенности и что вы приложили немало усилий, чтобы не протестировать его :-)
paxdiablo
@ Кристоф, ссылка в этом ответе не работает. Кроме того, вы проверяли этот код или нет? Если это было проверено и работает, вы должны удалить это из ответа. Также, возможно, покажите пример того, к какому коду это приводит после развертывания макросов. Мне нравится общая идея.
Иоаким
4

Мне очень понравился ответ paxdiable, и я решил реализовать все недостающие функции для моего приложения, такие как защитные переменные и данные, относящиеся к конечному автомату.

Я загрузил свою реализацию на этот сайт, чтобы поделиться с сообществом. Он был протестирован с использованием IAR Embedded Workbench для ARM.

https://sourceforge.net/projects/compactfsm/

user108570
источник
Нахождение этого в 2018 году и что это все еще применимо. Я читал ответ @paxdiablo и раньше успешно использовал этот тип реализации во встроенных системах. Это решение добавляет недостающие вещи из ответа paxdiablos :)
Кристоффер
4

Еще один интересный инструмент с открытым исходным кодом - Yakindu Statechart Tools на statecharts.org . Он использует диаграммы состояний Harel и, таким образом, обеспечивает иерархические и параллельные состояния и генерирует код C и C ++ (а также Java). Он не использует библиотеки, но следует подходу «простого кода». Код в основном применяет структуры switch-case. Генераторы кода также могут быть настроены. Кроме того, инструмент предоставляет множество других функций.

Аксель Т.
источник
3

Приходя к этому поздно (как обычно), но просматривая ответы на сегодняшний день, я думаю, что чего-то важного не хватает;

Я обнаружил в своих собственных проектах, что это может быть очень полезно для не иметь функции для каждой действительной комбинации состояния / события. Мне нравится идея эффективно иметь 2D таблицу состояний / событий. Но мне нравится, что элементы таблицы больше, чем простой указатель на функцию. Вместо этого я пытаюсь организовать свой дизайн так, чтобы в его основе было множество простых атомарных элементов или действий. Таким образом, я могу перечислить эти простые атомарные элементы на каждом пересечении моей таблицы состояний / событий. Идея состоит в том, что вам не нужно определять массу из N квадратов (обычно очень простых) функций. Почему есть что-то такое подверженное ошибкам, трудоемкое, трудное для написания, трудное для чтения, назовите это?

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

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

Билл Форстер
источник
2
Может быть, пример был бы хорош, нет?
jldupont
1
Реалистичный пример, который может быть представлен отдельно, - это сложная задача, которая потребует больше времени, чем я готов дать прямо сейчас. Есть ли в моем посте что-то особенно сложное для понимания? Может быть, я могу выразить это более четко. Идея очень проста; Не определяйте механизм состояний, который требует отдельной функции для каждой комбинации события / состояния, вы получаете слишком много функций таким образом. Вместо этого найдите другой способ описать функциональность, которую вы хотите для этой комбинации события / состояния, по крайней мере, в большинстве случаев.
Билл Форстер
2
Понял: пример с псевдокодом был бы хорош, но ваша точка зрения ясна.
jldupont
3

В общем, я думаю, что мой немного отличается от всех остальных. Чуть больше разделения кода и данных, чем я вижу в других ответах. Я действительно прочитал теорию, чтобы написать это, которая реализует полный Regular-язык (без регулярных выражений, к сожалению). Ульман, Минский, Хомский. Не могу сказать, что все понял, но я обратился к старым мастерам как можно более прямо: через их слова.

Я использую указатель функции на предикат, который определяет переход в состояние «да» или «нет». Это облегчает создание конечного акцептора состояний для обычного языка, который вы программируете более похожим на ассемблер. Пожалуйста, не откладывай на мой глупый выбор имени. 'czek' == 'проверить'. 'grok' == [посмотрите в словаре хакеров].

Поэтому для каждой итерации czek вызывает функцию предиката с текущим символом в качестве аргумента. Если предикат возвращает true, символ потребляется (указатель продвинут), и мы следуем переходу «y», чтобы выбрать следующее состояние. Если предикат возвращает false, символ НЕ используется, и мы следуем переходу 'n'. Так что каждая инструкция - это двусторонняя ветвь! Должно быть, я читал «Историю Мела» в то время.

Этот код взят прямо из моего постскриптумного интерпретатора и развился в его нынешнюю форму под большим руководством коллег по comp.lang.c. Так как postscript в основном не имеет синтаксиса (требующего только сбалансированных скобок), Regular Language Accepter, подобный этому, также работает как синтаксический анализатор.

/* currentstr is set to the start of string by czek
   and used by setrad (called by israd) to set currentrad
   which is used by israddig to determine if the character
   in question is valid for the specified radix
   --
   a little semantic checking in the syntax!
 */
char *currentstr;
int currentrad;
void setrad(void) {
    char *end;
    currentrad = strtol(currentstr, &end, 10);
    if (*end != '#' /* just a sanity check,
                       the automaton should already have determined this */
    ||  currentrad > 36
    ||  currentrad < 2)
        fatal("bad radix"); /* should probably be a simple syntaxerror */
}

/*
   character classes
   used as tests by automatons under control of czek
 */
char *alpha = "0123456789" "ABCDE" "FGHIJ" "KLMNO" "PQRST" "UVWXYZ";
#define EQ(a,b) a==b
#define WITHIN(a,b) strchr(a,b)!=NULL
int israd  (int c) {
    if (EQ('#',c)) { setrad(); return true; }
    return false;
}
int israddig(int c) {
    return strchrnul(alpha,toupper(c))-alpha <= currentrad;
}
int isdot  (int c) {return EQ('.',c);}
int ise    (int c) {return WITHIN("eE",c);}
int issign (int c) {return WITHIN("+-",c);}
int isdel  (int c) {return WITHIN("()<>[]{}/%",c);}
int isreg  (int c) {return c!=EOF && !isspace(c) && !isdel(c);}
#undef WITHIN
#undef EQ

/*
   the automaton type
 */
typedef struct { int (*pred)(int); int y, n; } test;

/*
   automaton to match a simple decimal number
 */
/* /^[+-]?[0-9]+$/ */
test fsm_dec[] = {
/* 0*/ { issign,  1,  1 },
/* 1*/ { isdigit, 2, -1 },
/* 2*/ { isdigit, 2, -1 },
};
int acc_dec(int i) { return i==2; }

/*
   automaton to match a radix number
 */
/* /^[0-9]+[#][a-Z0-9]+$/ */
test fsm_rad[] = {
/* 0*/ { isdigit,  1, -1 },
/* 1*/ { isdigit,  1,  2 },
/* 2*/ { israd,    3, -1 },
/* 3*/ { israddig, 4, -1 },
/* 4*/ { israddig, 4, -1 },
};
int acc_rad(int i) { return i==4; }

/*
   automaton to match a real number
 */
/* /^[+-]?(d+(.d*)?)|(d*.d+)([eE][+-]?d+)?$/ */
/* represents the merge of these (simpler) expressions
   [+-]?[0-9]+\.[0-9]*([eE][+-]?[0-9]+)?
   [+-]?[0-9]*\.[0-9]+([eE][+-]?[0-9]+)?
   The complexity comes from ensuring at least one
   digit in the integer or the fraction with optional
   sign and optional optionally-signed exponent.
   So passing isdot in state 3 means at least one integer digit has been found
   but passing isdot in state 4 means we must find at least one fraction digit
   via state 5 or the whole thing is a bust.
 */
test fsm_real[] = {
/* 0*/ { issign,  1,   1 },
/* 1*/ { isdigit, 2,   4 },
/* 2*/ { isdigit, 2,   3 },
/* 3*/ { isdot,   6,   7 },
/* 4*/ { isdot,   5,  -1 },
/* 5*/ { isdigit, 6,  -1 },
/* 6*/ { isdigit, 6,   7 },
/* 7*/ { ise,     8,  -1 },
/* 8*/ { issign,  9,   9 },
/* 9*/ { isdigit, 10, -1 },
/*10*/ { isdigit, 10, -1 },
};
int acc_real(int i) {
    switch(i) {
        case 2: /* integer */
        case 6: /* real */
        case 10: /* real with exponent */
            return true;
    }
    return false;
}

/*
   Helper function for grok.
   Execute automaton against the buffer,
   applying test to each character:
       on success, consume character and follow 'y' transition.
       on failure, do not consume but follow 'n' transition.
   Call yes function to determine if the ending state
   is considered an acceptable final state.
   A transition to -1 represents rejection by the automaton
 */
int czek (char *s, test *fsm, int (*yes)(int)) {
    int sta = 0;
    currentstr = s;
    while (sta!=-1 && *s) {
        if (fsm[sta].pred((int)*s)) {
            sta=fsm[sta].y;
            s++;
        } else {
            sta=fsm[sta].n;
        }
    }
    return yes(sta);
}

/*
   Helper function for toke.
   Interpret the contents of the buffer,
   trying automatons to match number formats;
   and falling through to a switch for special characters.
   Any token consisting of all regular characters
   that cannot be interpreted as a number is an executable name
 */
object grok (state *st, char *s, int ns,
    object *src,
    int (*next)(state *,object *),
    void (*back)(state *,int, object *)) {

    if (czek(s, fsm_dec, acc_dec)) {
        long num;
        num = strtol(s,NULL,10);
        if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) {
            error(st,limitcheck);
/*       } else if (num > INT_MAX || num < INT_MIN) { */
/*           error(limitcheck, OP_token); */
        } else {
            return consint(num);
        }
    }

    else if (czek(s, fsm_rad, acc_rad)) {
        long ra,num;
        ra = (int)strtol(s,NULL,10);
        if (ra > 36 || ra < 2) {
            error(st,limitcheck);
        }
        num = strtol(strchr(s,'#')+1, NULL, (int)ra);
        if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) {
            error(st,limitcheck);
/*       } else if (num > INT_MAX || num < INT_MAX) { */
/*           error(limitcheck, OP_token); */
        } else {
            return consint(num);
        }
    }

    else if (czek(s, fsm_real, acc_real)) {
        double num;
        num = strtod(s,NULL);
        if ((num==HUGE_VAL || num==-HUGE_VAL) && errno==ERANGE) {
            error(st,limitcheck);
        } else {
            return consreal(num);
        }
    }

    else switch(*s) {
        case '(': {
            int c, defer=1;
            char *sp = s;

            while (defer && (c=next(st,src)) != EOF ) {
                switch(c) {
                    case '(': defer++; break;
                    case ')': defer--;
                        if (!defer) goto endstring;
                        break;
                    case '\\': c=next(st,src);
                        switch(c) {
                            case '\n': continue;
                            case 'a': c = '\a'; break;
                            case 'b': c = '\b'; break;
                            case 'f': c = '\f'; break;
                            case 'n': c = '\n'; break;
                            case 'r': c = '\r'; break;
                            case 't': c = '\t'; break;
                            case 'v': c = '\v'; break;
                            case '\'': case '\"':
                            case '(': case ')':
                            default: break;
                        }
                }
                if (sp-s>ns) error(st,limitcheck);
                else *sp++ = c;
            }
endstring:  *sp=0;
            return cvlit(consstring(st,s,sp-s));
        }

        case '<': {
            int c;
            char d, *x = "0123456789abcdef", *sp = s;
            while (c=next(st,src), c!='>' && c!=EOF) {
                if (isspace(c)) continue;
                if (isxdigit(c)) c = strchr(x,tolower(c)) - x;
                else error(st,syntaxerror);
                d = (char)c << 4;
                while (isspace(c=next(st,src))) /*loop*/;
                if (isxdigit(c)) c = strchr(x,tolower(c)) - x;
                else error(st,syntaxerror);
                d |= (char)c;
                if (sp-s>ns) error(st,limitcheck);
                *sp++ = d;
            }
            *sp = 0;
            return cvlit(consstring(st,s,sp-s));
        }

        case '{': {
            object *a;
            size_t na = 100;
            size_t i;
            object proc;
            object fin;

            fin = consname(st,"}");
            (a = malloc(na * sizeof(object))) || (fatal("failure to malloc"),0);
            for (i=0 ; objcmp(st,a[i]=toke(st,src,next,back),fin) != 0; i++) {
                if (i == na-1)
                (a = realloc(a, (na+=100) * sizeof(object))) || (fatal("failure to malloc"),0);
            }
            proc = consarray(st,i);
            { size_t j;
                for (j=0; j<i; j++) {
                    a_put(st, proc, j, a[j]);
                }
            }
            free(a);
            return proc;
        }

        case '/': {
            s[1] = (char)next(st,src);
            puff(st, s+2, ns-2, src, next, back);
            if (s[1] == '/') {
                push(consname(st,s+2));
                opexec(st, op_cuts.load);
                return pop();
            }
            return cvlit(consname(st,s+1));
        }

        default: return consname(st,s);
    }
    return null; /* should be unreachable */
}

/*
   Helper function for toke.
   Read into buffer any regular characters.
   If we read one too many characters, put it back
   unless it's whitespace.
 */
int puff (state *st, char *buf, int nbuf,
    object *src,
    int (*next)(state *,object *),
    void (*back)(state *,int, object *)) {
    int c;
    char *s = buf;
    while (isreg(c=next(st,src))) {
        if (s-buf >= nbuf-1) return false;
        *s++ = c;
    }
    *s = 0;
    if (!isspace(c) && c != EOF) back(st,c,src); /* eat interstice */
    return true;
}

/*
   Helper function for Stoken Ftoken.
   Read a token from src using next and back.
   Loop until having read a bona-fide non-whitespace non-comment character.
   Call puff to read into buffer up to next delimiter or space.
   Call grok to figure out what it is.
 */
#define NBUF MAXLINE
object toke (state *st, object *src,
        int (*next)(state *, object *),
        void (*back)(state *, int, object *)) {
    char buf[NBUF] = "", *s=buf;
    int c,sta = 1;
    object o;

    do {
        c=next(st,src);
        //if (c==EOF) return null;
        if (c=='%') {
            if (DUMPCOMMENTS) fputc(c, stdout);
            do {
                c=next(st,src);
                if (DUMPCOMMENTS) fputc(c, stdout);
            } while (c!='\n' && c!='\f' && c!=EOF);
        }
    } while (c!=EOF && isspace(c));
    if (c==EOF) return null;
    *s++ = c;
    *s = 0;
    if (!isdel(c)) sta=puff(st, s,NBUF-1,src,next,back);

    if (sta) {
        o=grok(st,buf,NBUF-1,src,next,back);
        return o;
    } else {
        return null;
    }
}
Люзер Дрог
источник
2
Это то, что любой парсер или генератор лексеров с радостью выпустит для вас. Странно так. Хотите ли вы написать код вручную, сомнительно. Это имеет педагогическую ценность, конечно.
Восстановите Монику
3

boost.org поставляется с 2 различными реализациями диаграмм состояний:

Как всегда, boost перенесет вас в адский шаблон.

Первая библиотека предназначена для более критичных к производительности машин состояния. Вторая библиотека дает вам прямой путь перехода от UML Statechart к коду.

Вот SO вопрос, требующий сравнения между двумя, где оба автора отвечают.

Роланд Вольф
источник
2

Видел это где-то

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

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

  STATE(y) {
    ...
    if (x == 0)
      NEXTSTATE(y);
    else
      NEXTSTATE(x);
  }
}
pixelbeat
источник
1
Это интересно, но не возражайте, пока вы не приведете пример или два (и, возможно, результат de-macro'ed) или некоторое обсуждение того, почему это может быть более практичным, чем другой. Интересное использование сиротских скобок и макросов. Я полагаю, что нечто подобное можно было бы сделать на языке, который выполняет некоторую оптимизацию хвостовой рекурсии; Вы могли бы использовать прямые вызовы функций и не беспокоиться о перегрузке стекового пространства мусором при вызове функций (что, я думаю, является тем, что макросы здесь по существу преодолевают)
Ape-inago
2
Преимущества этого метода ...? Я вижу несколько недостатков, таких как запутывание макросов, использование gotoкоторых создает зависимость от более ранней многозадачной ОС.
Крейг МакКуин
2

Учитывая, что вы подразумеваете, что вы можете использовать C ++ и, следовательно, OO-код, я бы посоветовал оценить шаблон GoF'state (GoF = Gang of Four, ребята, которые написали книгу шаблонов проектирования, которая вывела шаблоны проектирования в центр внимания).

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

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

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

Ниже приводятся некоторые ссылки на шаблон состояния «Gof», как предлагает Крейг:

Мик
источник
выглядит больше как комментарий: могу ли я предложить вам относиться к нему как таковой? т.е. не помещайте его в раздел «ответ».
jldupont
Было бы хорошо, если бы вы могли предоставить хорошую URL-ссылку для «шаблона состояния GoF» для тех, кто не знаком с ним.
Крейг МакКуин
1
@jldupont - честный комментарий. Я изменил текст, чтобы сделать его правильным ответом, так как чувствую, основываясь на личном опыте, что, если нет особых проблем с производительностью, подход GoF работает нормально и будет иметь относительно большую «базу пользователей»
Мик
@Craig - добавил несколько ссылок. Оба выглядели точными и ясными в то время, когда я их добавил.
Мик
2

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

Это пример подключения к данным с такими состояниями, как:

  • Uninitialized
  • Initialized
  • Связано
  • MTU Договорная
  • Проверенный

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

Этот пример работает на Linux, используйте Makefile ниже, чтобы скомпилировать его и поэкспериментировать с ним.

state_machine.c

#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <unistd.h>   // sysconf()
#include <errno.h>    // errno
#include <string.h>   // strerror()
#include <sys/time.h> // gettimeofday()
#include <fcntl.h>    // For O_* constants
#include <sys/stat.h> // For mode constants

#include <mqueue.h>
#include <poll.h>

//------------------------------------------------
// States
//------------------------------------------------
typedef enum
{
    ST_UNKNOWN = 0,
    ST_UNINIT,
    ST_INIT,
    ST_CONNECTED,
    ST_MTU_NEGOTIATED,
    ST_AUTHENTICATED,
    ST_ERROR,
    ST_DONT_CHANGE,
    ST_TERM,
} fsmState_t;

//------------------------------------------------
// Events
//------------------------------------------------
typedef enum
{
    EV_UNKNOWN = 0,
    EV_INIT_SUCCESS,
    EV_INIT_FAIL,
    EV_MASTER_CMD_MSG,
    EV_CONNECT_SUCCESS,
    EV_CONNECT_FAIL,
    EV_MTU_SUCCESS,
    EV_MTU_FAIL,
    EV_AUTH_SUCCESS,
    EV_AUTH_FAIL,
    EV_TX_SUCCESS,
    EV_TX_FAIL,
    EV_DISCONNECTED,
    EV_DISCON_FAILED,
    EV_LAST_ENTRY,
} fsmEvName_t;

typedef struct fsmEvent_type
{
    fsmEvName_t name;
    struct timeval genTime; // Time the event was generated.
                            // This allows us to see how old the event is.
} fsmEvent_t;

// Finite State Machine Data Members
typedef struct fsmData_type
{
    int  connectTries;
    int  MTUtries;
    int  authTries;
    int  txTries;
} fsmData_t;

// Each row of the state table
typedef struct stateTable_type {
    fsmState_t  st;             // Current state
    fsmEvName_t evName;         // Got this event
    int (*conditionfn)(void *);  // If this condition func returns TRUE
    fsmState_t nextState;       // Change to this state and
    void (*fn)(void *);          // Run this function
} stateTable_t;

// Finite State Machine state structure
typedef struct fsm_type
{
    const stateTable_t *pStateTable; // Pointer to state table
    int        numStates;            // Number of entries in the table
    fsmState_t currentState;         // Current state
    fsmEvent_t currentEvent;         // Current event
    fsmData_t *fsmData;              // Pointer to the data attributes
    mqd_t      mqdes;                // Message Queue descriptor
    mqd_t      master_cmd_mqdes;     // Master command message queue
} fsm_t;

// Wildcard events and wildcard state
#define   EV_ANY    -1
#define   ST_ANY    -1
#define   TRUE     (1)
#define   FALSE    (0)

// Maximum priority for message queues (see "man mq_overview")
#define FSM_PRIO  (sysconf(_SC_MQ_PRIO_MAX) - 1)

static void addev                              (fsm_t *fsm, fsmEvName_t ev);
static void doNothing                          (void *fsm) {addev(fsm, EV_MASTER_CMD_MSG);}
static void doInit                             (void *fsm) {addev(fsm, EV_INIT_SUCCESS);}
static void doConnect                          (void *fsm) {addev(fsm, EV_CONNECT_SUCCESS);}
static void doMTU                              (void *fsm) {addev(fsm, EV_MTU_SUCCESS);}
static void reportFailConnect                  (void *fsm) {addev(fsm, EV_ANY);}
static void doAuth                             (void *fsm) {addev(fsm, EV_AUTH_SUCCESS);}
static void reportDisConnect                   (void *fsm) {addev(fsm, EV_ANY);}
static void doDisconnect                       (void *fsm) {addev(fsm, EV_ANY);}
static void doTransaction                      (void *fsm) {addev(fsm, EV_TX_FAIL);}
static void fsmError                           (void *fsm) {addev(fsm, EV_ANY);}

static int currentlyLessThanMaxConnectTries    (void *fsm) {
    fsm_t *l = (fsm_t *)fsm;
    return (l->fsmData->connectTries < 5 ? TRUE : FALSE);
}
static int        isMoreThanMaxConnectTries    (void *fsm) {return TRUE;}
static int currentlyLessThanMaxMTUtries        (void *fsm) {return TRUE;}
static int        isMoreThanMaxMTUtries        (void *fsm) {return TRUE;}
static int currentyLessThanMaxAuthTries        (void *fsm) {return TRUE;}
static int       isMoreThanMaxAuthTries        (void *fsm) {return TRUE;}
static int currentlyLessThanMaxTXtries         (void *fsm) {return FALSE;}
static int        isMoreThanMaxTXtries         (void *fsm) {return TRUE;}
static int didNotSelfDisconnect                (void *fsm) {return TRUE;}

static int  waitForEvent                       (fsm_t *fsm);
static void runEvent                           (fsm_t *fsm);
static void runStateMachine(fsm_t *fsm);
static int newEventIsValid(fsmEvent_t *event);
static void getTime(struct timeval *time);
void printState(fsmState_t st);
void printEvent(fsmEvName_t ev);

// Global State Table
const stateTable_t GST[] = {
    // Current state         Got this event          If this condition func returns TRUE     Change to this state and    Run this function
    { ST_UNINIT,             EV_INIT_SUCCESS,        NULL,                                   ST_INIT,                    &doNothing              },
    { ST_UNINIT,             EV_INIT_FAIL,           NULL,                                   ST_UNINIT,                  &doInit                 },
    { ST_INIT,               EV_MASTER_CMD_MSG,      NULL,                                   ST_INIT,                    &doConnect              },
    { ST_INIT,               EV_CONNECT_SUCCESS,     NULL,                                   ST_CONNECTED,               &doMTU                  },
    { ST_INIT,               EV_CONNECT_FAIL,        &currentlyLessThanMaxConnectTries,      ST_INIT,                    &doConnect              },
    { ST_INIT,               EV_CONNECT_FAIL,        &isMoreThanMaxConnectTries,             ST_INIT,                    &reportFailConnect      },
    { ST_CONNECTED,          EV_MTU_SUCCESS,         NULL,                                   ST_MTU_NEGOTIATED,          &doAuth                 },
    { ST_CONNECTED,          EV_MTU_FAIL,            &currentlyLessThanMaxMTUtries,          ST_CONNECTED,               &doMTU                  },
    { ST_CONNECTED,          EV_MTU_FAIL,            &isMoreThanMaxMTUtries,                 ST_CONNECTED,               &doDisconnect           },
    { ST_CONNECTED,          EV_DISCONNECTED,        &didNotSelfDisconnect,                  ST_INIT,                    &reportDisConnect       },
    { ST_MTU_NEGOTIATED,     EV_AUTH_SUCCESS,        NULL,                                   ST_AUTHENTICATED,           &doTransaction          },
    { ST_MTU_NEGOTIATED,     EV_AUTH_FAIL,           &currentyLessThanMaxAuthTries,          ST_MTU_NEGOTIATED,          &doAuth                 },
    { ST_MTU_NEGOTIATED,     EV_AUTH_FAIL,           &isMoreThanMaxAuthTries,                ST_MTU_NEGOTIATED,          &doDisconnect           },
    { ST_MTU_NEGOTIATED,     EV_DISCONNECTED,        &didNotSelfDisconnect,                  ST_INIT,                    &reportDisConnect       },
    { ST_AUTHENTICATED,      EV_TX_SUCCESS,          NULL,                                   ST_AUTHENTICATED,           &doDisconnect           },
    { ST_AUTHENTICATED,      EV_TX_FAIL,             &currentlyLessThanMaxTXtries,           ST_AUTHENTICATED,           &doTransaction          },
    { ST_AUTHENTICATED,      EV_TX_FAIL,             &isMoreThanMaxTXtries,                  ST_AUTHENTICATED,           &doDisconnect           },
    { ST_AUTHENTICATED,      EV_DISCONNECTED,        &didNotSelfDisconnect,                  ST_INIT,                    &reportDisConnect       },
    { ST_ANY,                EV_DISCON_FAILED,       NULL,                                   ST_DONT_CHANGE,             &doDisconnect           },
    { ST_ANY,                EV_ANY,                 NULL,                                   ST_UNINIT,                  &fsmError               }    // Wildcard state for errors
};

#define GST_COUNT (sizeof(GST)/sizeof(stateTable_t))

int main()
{
    int ret = 0;
    fsmData_t dataAttr;
    dataAttr.connectTries = 0;
    dataAttr.MTUtries     = 0;
    dataAttr.authTries    = 0;
    dataAttr.txTries      = 0;

    fsm_t lfsm;
    memset(&lfsm, 0, sizeof(fsm_t));
    lfsm.pStateTable       = GST;
    lfsm.numStates         = GST_COUNT;
    lfsm.currentState      = ST_UNINIT;
    lfsm.currentEvent.name = EV_ANY;
    lfsm.fsmData           = &dataAttr;

    struct mq_attr attr;
    attr.mq_maxmsg = 30;
    attr.mq_msgsize = sizeof(fsmEvent_t);

    // Dev info
    //printf("Size of fsmEvent_t [%ld]\n", sizeof(fsmEvent_t));

    ret = mq_unlink("/abcmq");
    if (ret == -1) {
        fprintf(stderr, "Error on mq_unlink(), errno[%d] strerror[%s]\n",
                errno, strerror(errno));
    }

    lfsm.mqdes = mq_open("/abcmq", O_CREAT | O_RDWR, S_IWUSR | S_IRUSR, &attr);
    if (lfsm.mqdes == (mqd_t)-1) {
        fprintf(stderr, "Error on mq_open(), errno[%d] strerror[%s]\n",
                errno, strerror(errno));
        return -1;
    }

    doInit(&lfsm);  // This will generate the first event
    runStateMachine(&lfsm);

    return 0;
}


static void runStateMachine(fsm_t *fsm)
{
    int ret = 0;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    // Cycle through the state machine
    while (fsm->currentState != ST_TERM) {
        printf("current state [");
        printState(fsm->currentState);
        printf("]\n");

        ret = waitForEvent(fsm);
        if (ret == 0) {
            printf("got event [");
            printEvent(fsm->currentEvent.name);
            printf("]\n");

            runEvent(fsm);
        }
        sleep(2);
    }
}


static int waitForEvent(fsm_t *fsm)
{
    //const int numFds = 2;
    const int numFds = 1;
    struct pollfd fds[numFds];
    int timeout_msecs = -1; // -1 is forever
    int ret = 0;
    int i = 0;
    ssize_t num = 0;
    fsmEvent_t newEv;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return -1;
    }

    fsm->currentEvent.name = EV_ANY;

    fds[0].fd     = fsm->mqdes;
    fds[0].events = POLLIN;
    //fds[1].fd     = fsm->master_cmd_mqdes;
    //fds[1].events = POLLIN;
    ret = poll(fds, numFds, timeout_msecs);

    if (ret > 0) {
        // An event on one of the fds has occurred
        for (i = 0; i < numFds; i++) {
            if (fds[i].revents & POLLIN) {
                // Data may be read on device number i
                num = mq_receive(fds[i].fd, (void *)(&newEv),
                                 sizeof(fsmEvent_t), NULL);
                if (num == -1) {
                    fprintf(stderr, "Error on mq_receive(), errno[%d] "
                            "strerror[%s]\n", errno, strerror(errno));
                    return -1;
                }

                if (newEventIsValid(&newEv)) {
                    fsm->currentEvent = newEv;
                } else {
                    return -1;
                }
            }
        }
    } else {
        fprintf(stderr, "Error on poll(), ret[%d] errno[%d] strerror[%s]\n",
                ret, errno, strerror(errno));
        return -1;
    }

    return 0;
}


static int newEventIsValid(fsmEvent_t *event)
{
    if (event == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return FALSE;
    }

    printf("[%s]\n", __func__);

    struct timeval now;
    getTime(&now);

    if ( (event->name < EV_LAST_ENTRY) &&
         ((now.tv_sec - event->genTime.tv_sec) < (60*5))
       )
    {
        return TRUE;
    } else {
        return FALSE;
    }
}


//------------------------------------------------
// Performs event handling on the FSM (finite state machine).
// Make sure there is a wildcard state at the end of
// your table, otherwise; the event will be ignored.
//------------------------------------------------
static void runEvent(fsm_t *fsm)
{
    int i;
    int condRet = 0;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    printf("[%s]\n", __func__);

    // Find a relevant entry for this state and event
    for (i = 0; i < fsm->numStates; i++) {
        // Look in the table for our current state or ST_ANY
        if (  (fsm->pStateTable[i].st == fsm->currentState) ||
              (fsm->pStateTable[i].st == ST_ANY)
           )
        {
            // Is this the event we are looking for?
            if ( (fsm->pStateTable[i].evName == fsm->currentEvent.name) ||
                 (fsm->pStateTable[i].evName == EV_ANY)
               )
            {
                if (fsm->pStateTable[i].conditionfn != NULL) {
                    condRet = fsm->pStateTable[i].conditionfn(fsm->fsmData);
                }

                // See if there is a condition associated
                // or we are not looking for any condition
                //
                if ( (condRet != 0) || (fsm->pStateTable[i].conditionfn == NULL))
                {
                    // Set the next state (if applicable)
                    if (fsm->pStateTable[i].nextState != ST_DONT_CHANGE) {
                        fsm->currentState = fsm->pStateTable[i].nextState;
                        printf("new state [");
                        printState(fsm->currentState);
                        printf("]\n");
                    }

                    // Call the state callback function
                    fsm->pStateTable[i].fn(fsm);
                    break;
                }
            }
        }
    }
}


//------------------------------------------------
//               EVENT HANDLERS
//------------------------------------------------
static void getTime(struct timeval *time)
{
    if (time == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    printf("[%s]\n", __func__);

    int ret = gettimeofday(time, NULL);
    if (ret != 0) {
        fprintf(stderr, "gettimeofday() failed: errno [%d], strerror [%s]\n",
                errno, strerror(errno));
        memset(time, 0, sizeof(struct timeval));
    }
}


static void addev (fsm_t *fsm, fsmEvName_t ev)
{
    int ret = 0;

    if (fsm == NULL) {
        fprintf(stderr, "[%s] NULL argument\n", __func__);
        return;
    }

    printf("[%s] ev[%d]\n", __func__, ev);

    if (ev == EV_ANY) {
        // Don't generate a new event, just return...
        return;
    }

    fsmEvent_t newev;
    getTime(&(newev.genTime));
    newev.name = ev;

    ret = mq_send(fsm->mqdes, (void *)(&newev), sizeof(fsmEvent_t), FSM_PRIO);
    if (ret == -1) {
        fprintf(stderr, "[%s] mq_send() failed: errno [%d], strerror [%s]\n",
                __func__, errno, strerror(errno));
    }
}
//------------------------------------------------
//           end EVENT HANDLERS
//------------------------------------------------

void printState(fsmState_t st)
{
    switch(st) {
        case    ST_UNKNOWN:
        printf("ST_UNKNOWN");
            break;
        case    ST_UNINIT:
        printf("ST_UNINIT");
            break;
        case    ST_INIT:
        printf("ST_INIT");
            break;
        case    ST_CONNECTED:
        printf("ST_CONNECTED");
            break;
        case    ST_MTU_NEGOTIATED:
        printf("ST_MTU_NEGOTIATED");
            break;
        case    ST_AUTHENTICATED:
        printf("ST_AUTHENTICATED");
            break;
        case    ST_ERROR:
        printf("ST_ERROR");
            break;
        case    ST_TERM:
        printf("ST_TERM");
            break;
        default:
        printf("unknown state");
            break;
    }
}

void printEvent(fsmEvName_t ev)
{
    switch (ev) {
        case    EV_UNKNOWN:
        printf("EV_UNKNOWN");
            break;
        case    EV_INIT_SUCCESS:
        printf("EV_INIT_SUCCESS");
            break;
        case    EV_INIT_FAIL:
        printf("EV_INIT_FAIL");
            break;
        case    EV_MASTER_CMD_MSG:
        printf("EV_MASTER_CMD_MSG");
            break;
        case    EV_CONNECT_SUCCESS:
        printf("EV_CONNECT_SUCCESS");
            break;
        case    EV_CONNECT_FAIL:
        printf("EV_CONNECT_FAIL");
            break;
        case    EV_MTU_SUCCESS:
        printf("EV_MTU_SUCCESS");
            break;
        case    EV_MTU_FAIL:
        printf("EV_MTU_FAIL");
            break;
        case    EV_AUTH_SUCCESS:
        printf("EV_AUTH_SUCCESS");
            break;
        case    EV_AUTH_FAIL:
        printf("EV_AUTH_FAIL");
            break;
        case    EV_TX_SUCCESS:
        printf("EV_TX_SUCCESS");
            break;
        case    EV_TX_FAIL:
        printf("EV_TX_FAIL");
            break;
        case    EV_DISCONNECTED:
        printf("EV_DISCONNECTED");
            break;
        case    EV_LAST_ENTRY:
        printf("EV_LAST_ENTRY");
            break;
        default:
        printf("unknown event");
            break;
    }
}

Makefile

CXX = gcc
COMPFLAGS = -c -Wall -g

state_machine: state_machine.o
    $(CXX) -lrt state_machine.o -o state_machine

state_machine.o: state_machine.c
    $(CXX) $(COMPFLAGS) state_machine.c

clean:
    rm state_machine state_machine.o
Брэд Гриссом
источник
1

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

  1. Реализация встроенного конечного автомата

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

    • Машины кодирования состояний в C и C ++

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

Nik
источник
1

Это старый пост с множеством ответов, но я подумал, что добавлю свой собственный подход к конечному автомату в C. Я создал скрипт Python, чтобы создать скелетный C-код для любого количества состояний. Этот скрипт задокументирован на GituHub в FsmTemplateC

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

Вот скрипт Python примера турникета, который генерирует C-код скелета, используя FsmTemplateC :

# dict parameter for generating FSM
fsm_param = {
    # main FSM struct type string
    'type': 'FsmTurnstile',
    # struct type and name for passing data to state machine functions
    # by pointer (these custom names are optional)
    'fopts': {
        'type': 'FsmTurnstileFopts',
        'name': 'fopts'
    },
    # list of states
    'states': ['locked', 'unlocked'],
    # list of inputs (can be any length > 0)
    'inputs': ['coin', 'push'],
    # map inputs to commands (next desired state) using a transition table
    # index of array corresponds to 'inputs' array
    # for this example, index 0 is 'coin', index 1 is 'push'
    'transitiontable': {
        # current state |  'coin'  |  'push'  |
        'locked':       ['unlocked',        ''],
        'unlocked':     [        '',  'locked']
    }
}

# folder to contain generated code
folder = 'turnstile_example'
# function prefix
prefix = 'fsm_turnstile'

# generate FSM code
code = fsm.Fsm(fsm_param).genccode(folder, prefix)

Сгенерированный выходной заголовок содержит typedefs:

/* function options (EDIT) */
typedef struct FsmTurnstileFopts {
    /* define your options struct here */
} FsmTurnstileFopts;

/* transition check */
typedef enum eFsmTurnstileCheck {
    EFSM_TURNSTILE_TR_RETREAT,
    EFSM_TURNSTILE_TR_ADVANCE,
    EFSM_TURNSTILE_TR_CONTINUE,
    EFSM_TURNSTILE_TR_BADINPUT
} eFsmTurnstileCheck;

/* states (enum) */
typedef enum eFsmTurnstileState {
    EFSM_TURNSTILE_ST_LOCKED,
    EFSM_TURNSTILE_ST_UNLOCKED,
    EFSM_TURNSTILE_NUM_STATES
} eFsmTurnstileState;

/* inputs (enum) */
typedef enum eFsmTurnstileInput {
    EFSM_TURNSTILE_IN_COIN,
    EFSM_TURNSTILE_IN_PUSH,
    EFSM_TURNSTILE_NUM_INPUTS,
    EFSM_TURNSTILE_NOINPUT
} eFsmTurnstileInput;

/* finite state machine struct */
typedef struct FsmTurnstile {
    eFsmTurnstileInput input;
    eFsmTurnstileCheck check;
    eFsmTurnstileState cur;
    eFsmTurnstileState cmd;
    eFsmTurnstileState **transition_table;
    void (***state_transitions)(struct FsmTurnstile *, FsmTurnstileFopts *);
    void (*run)(struct FsmTurnstile *, FsmTurnstileFopts *, const eFsmTurnstileInput);
} FsmTurnstile;

/* transition functions */
typedef void (*pFsmTurnstileStateTransitions)(struct FsmTurnstile *, FsmTurnstileFopts *);
  • enum eFsmTurnstileCheckиспользуется, чтобы определить, был ли переход заблокирован EFSM_TURNSTILE_TR_RETREAT, разрешен ли переход EFSM_TURNSTILE_TR_ADVANCE, или вызову функции не предшествовал переход сEFSM_TURNSTILE_TR_CONTINUE .
  • перечисление eFsmTurnstileState - это просто список состояний.
  • перечисление eFsmTurnstileInput - это просто список входных данных.
  • FsmTurnstile является сердцем конечного автомата с проверкой перехода, таблицей поиска функций, текущим состоянием, заданным состоянием и псевдонимом основной функции, которая запускает машину.
  • Каждый указатель на функцию (псевдоним) FsmTurnstileдолжен вызываться только из структуры и должен иметь свой первый вход в качестве указателя на себя, чтобы поддерживать постоянное состояние, объектно-ориентированный стиль.

Теперь для объявлений функций в заголовке:

/* fsm declarations */
void fsm_turnstile_locked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_locked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_unlocked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_unlocked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_run (FsmTurnstile *fsm, FsmTurnstileFopts *fopts, const eFsmTurnstileInput input);

Имена функций имеют формат {prefix}_{from}_{to}, в котором {from}находится предыдущее (текущее) состояние и {to}следующее состояние. Обратите внимание, что если таблица переходов не допускает определенные переходы, вместо указателя функции будет установлен указатель NULL. Наконец, магия случается с макросом. Здесь мы строим таблицу переходов (матрицу перечислений состояний) и таблицу поиска функций перехода состояний (матрицу указателей функций):

/* creation macro */
#define FSM_TURNSTILE_CREATE() \
{ \
    .input = EFSM_TURNSTILE_NOINPUT, \
    .check = EFSM_TURNSTILE_TR_CONTINUE, \
    .cur = EFSM_TURNSTILE_ST_LOCKED, \
    .cmd = EFSM_TURNSTILE_ST_LOCKED, \
    .transition_table = (eFsmTurnstileState * [EFSM_TURNSTILE_NUM_STATES]) { \
        (eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \
            EFSM_TURNSTILE_ST_UNLOCKED, \
            EFSM_TURNSTILE_ST_LOCKED \
        }, \
        (eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \
            EFSM_TURNSTILE_ST_UNLOCKED, \
            EFSM_TURNSTILE_ST_LOCKED \
        } \
    }, \
    .state_transitions = (pFsmTurnstileStateTransitions * [EFSM_TURNSTILE_NUM_STATES]) { \
        (pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \
            fsm_turnstile_locked_locked, \
            fsm_turnstile_locked_unlocked \
        }, \
        (pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \
            fsm_turnstile_unlocked_locked, \
            fsm_turnstile_unlocked_unlocked \
        } \
    }, \
    .run = fsm_turnstile_run \
}

При создании автомата необходимо использовать макрос FSM_EXAMPLE_CREATE().

Теперь в исходном коде должны быть указаны все функции перехода состояний, объявленные выше. Структура FsmTurnstileFoptsможет использоваться для передачи данных в / из конечного автомата. Каждый переход должен fsm->checkбыть равен либо EFSM_EXAMPLE_TR_RETREATблокированию перехода, либо EFSM_EXAMPLE_TR_ADVANCEразрешению перехода в заданное состояние. Рабочий пример можно найти по адресу (FsmTemplateC) [ https://github.com/ChisholmKyle/FsmTemplateC] .

Вот очень простое фактическое использование в вашем коде:

/* create fsm */
FsmTurnstile fsm = FSM_TURNSTILE_CREATE();
/* create fopts */
FsmTurnstileFopts fopts = {
    .msg = ""
};
/* initialize input */
eFsmTurnstileInput input = EFSM_TURNSTILE_NOINPUT;

/* main loop */
for (;;) {
    /* wait for timer signal, inputs, interrupts, whatever */
    /* optionally set the input (my_input = EFSM_TURNSTILE_IN_PUSH for example) */
    /* run state machine */
    my_fsm.run(&my_fsm, &my_fopts, my_input);
}

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

ChisholmKyle
источник
0

Вы можете использовать библиотеку с открытым исходным кодом OpenFST .

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

Вики Чижвани
источник
0
void (* StateController)(void); 
void state1(void);
void state2(void);

void main()
{
 StateController=&state1;
 while(1)
 {
  (* StateController)();
 }
}

void state1(void)
{
 //do something in state1
 StateController=&state2;
}

void state2(void)
{
 //do something in state2
 //Keep changing function direction based on state transition
 StateController=&state1;
}
AlphaGoku
источник
Вы можете дополнительно оптимизировать его для безопасности, используя массив постоянных указателей на функции
AlphaGoku
0

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

https://github.com/mmelchger/polling_state_machine_c

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

mmoment
источник
0

Вы можете рассмотреть UML-state-machine-in-c , «облегченную» структуру конечного автомата в C. Я написал эту среду для поддержки как конечного автомата, так и иерархического конечного автомата. . По сравнению с таблицами состояний или простыми случаями переключения, каркасный подход более масштабируем. Его можно использовать для простых конечных автоматов и сложных иерархических конечных автоматов.

Конечный автомат представлен state_machine_tструктурой. Он содержит только два члена «Event» и указатель на «state_t».

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

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

struct user_state_machine
{
  state_machine_t Machine;    // Base state machine. Must be the first member of user derived state machine.

  // User specific state machine members
  uint32_t param1;
  uint32_t param2;
  ...
};

state_t содержит обработчик состояния, а также необязательные обработчики для действий входа и выхода.

//! finite state structure
struct finite_state{
  state_handler Handler;      //!< State handler to handle event of the state
  state_handler Entry;        //!< Entry action for state
  state_handler Exit;          //!< Exit action for state.
};

Если структура настроена для иерархического конечного автомата, то state_t содержит указатель на родительское и дочернее состояние.

Framework предоставляет API dispatch_eventдля отправки события на конечный автомат и switch_stateдля запуска перехода состояния.

Для получения дополнительной информации о том, как реализовать иерархический конечный автомат, обратитесь к репозиторию 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

Нандкишор Бирадар
источник
-1

Вот метод для конечного автомата, который использует макросы так, что каждая функция может иметь свой собственный набор состояний: https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code -в

Он называется «имитировать многозадачность», но это не единственное использование.

Этот метод использует обратные вызовы для захвата в каждой функции, где он остановился. Каждая функция содержит список состояний, уникальных для каждой функции. Центральный «холостой цикл» используется для запуска конечных автоматов. «Цикл простоя» не имеет представления о том, как работают конечные автоматы, это отдельные функции, которые «знают, что делать». Чтобы написать код для функций, нужно просто создать список состояний и использовать макросы для «приостановки» и «возобновления». Я использовал эти макросы в Cisco, когда писал библиотеку Transceiver для коммутатора Nexus 7000.

eddyq
источник