Конечные автоматы в т

Question

Как лучше написать конечный автомат на C?
Я обычно пишу большой оператор switch-case в for (;;) с обратными вызовами для повторного входа в конечный автомат после завершения внешней операции.
Знаете ли вы более эффективный способ?

Answer 1

Мне нравится Квантовый скачок .

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

например:.

// State type and variable, notice that it's a function pointer.
typedef void (*State)(int);
State state;

// A couple of state functions.
void state_xyz(int event) { /*...*/ }
void state_init(int event) {
    if (event == E_GO_TO_xyz) {
        // State transition done simply by changing the state to another function.
        state = state_xyz;
    }
}

// main contains the event loop here:
int main() {
    int e;
    // Initial state.
    state = state_init;
    // Receive event, dispatch it, repeat... No 'switch'!
    while ((e = wait_for_event()) != E_END) {
        state(e);
    }
    return 0;
}

Каркасы QL предоставляют помощников для дополнительных вещей, таких как действия входа / выхода / инициализации, иерархические конечные автоматы и т. Д. Я настоятельно рекомендую книгу для более глубокого объяснения и хорошей реализации этого.

Answer 2

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

Answer 3

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

Ragel компилирует исполняемые конечные автоматы из обычных языков. Ragel предназначается для C, C ++, Objective-C, D, Java и Ruby. Конечные автоматы Ragel могут не только распознавать последовательности байтов, как это делают машины регулярных выражений, но и выполнять код в произвольных точках при распознавании обычного языка. Внедрение кода выполняется с использованием встроенных операторов, которые не нарушают синтаксис обычного языка.

Answer 4

Операторы Switch - хороший способ начать, но они становятся громоздкими, когда FSM становится больше.

Пара связанных (или дублирующих) SO вопросов с отличной информацией и идеями:

• учебники по конечным автоматам
• Конечный автомат C

Answer 5

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

Но я также добавлю некоторые функции
1. Информация о предыдущем состоянии.
2. Передача параметра
3. Добавление внешних событий, таких как глобальное время ожидания и «восстановление SM»

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

Answer 6

Альтернативный подход - это двумерный массив, который описывает для каждой комбинации состояния / события действия, которые необходимо выполнить, и следующее состояние, в которое нужно перейти. Это может быть сложнее в управлении, когда вам нужно перейти в разные состояния в зависимости от «обстоятельств», но это может быть сделано для правильной работы. У вас есть функция распознавания событий, которая возвращает следующее событие; у вас есть таблица, в которой каждая запись в таблице идентифицирует функцию, вызываемую при получении события, и следующее состояние, в которое нужно перейти - если только вызываемая функция не переопределяет это состояние.

На самом деле генерация такого кода более скудна - это зависит от того, как FSM описан в первую очередь. Обнаружение дублирующих действий часто важно. Часто вы можете положиться на методы «разреженной матрицы», которые не записывают обработку ошибок явно: если запись логически существует в разреженной матрице, вы воздействуете на эту информацию о событии / состоянии, но если запись не существует, вы возвращаетесь к соответствующей код сообщения об ошибках и повторной синхронизации.

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

Answer 7

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

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

Когда происходит событие, я ставлю его в очередь, поэтому у меня появляется нечто, похожее на это

int main(void)
{
    StateList currentState = start_up;
    EventList currentEvent;

    uint8_t stateArray[STATE_COUNT][EVENT_COUNT];

    InitializeStateArray(stateArray);
    InitializeEventQue();

    while(1)
    {
        currentEvent = GetPriorityEvent();
        currentState = (StateList)(*(stateArray[currentState][currentEvent]))();
    }
    return 1;  //should never get here
}

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

Answer 8

Посмотрите здесь: http://code.google.com/p/fwprofile/

Это открытая версия (GNU GPLv3) конечного автомата. в C. Концепция и реализация хорошо подходят для использования в критически важные приложения. Есть развертывания в промышленных приложения.