Конечные автоматы в C
Что лучший способ состоит в том, чтобы записать конечному автомату в C?
Я обычно пишу большого оператора case оператора switch в для (;;), с обратными вызовами, чтобы повторно ввести конечный автомат, когда внешняя операция закончена.
Вы знаете более эффективный путь?
6 ответов
Мне нравится подход Quantum Leaps.
Текущее состояние - это указатель на функцию, которая принимает в качестве аргумента объект события. Когда происходит событие, просто вызываем функцию состояния с этим событием; функция может затем сделать свою работу и перейти в другое состояние, просто установив состояние другой функции.
Например:
// 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 предоставляют помощников для дополнительных вещей, таких как действия входа/выхода/входа, иерархические машины состояний и т.д. Я настоятельно рекомендую книгу для более глубокого объяснения и хорошей реализации этого.
Команды Switch - хороший способ начать работу, но они становятся громоздкими, когда FSM становится больше.
Пара связанных (или повторяющихся) вопросов SO с большой информацией и идеями:
Я использовал этот шаблон. Существует ли типичный шаблон реализации конечного автомата? (выберите лучший ответ).
Но я также добавляю некоторые функции
1. Информация о предыдущем состоянии.
2. Передача параметров
3. Добавление внешних событий, таких как глобальный тайм-аут и "изменение SM"
, я обнаружил, что конечные автоматы менее загадочны и удобны в обслуживании.
В любом случае, я все еще считаю конечные автоматы самой сложной и утомительной задачей программирования. (Я так далеко)
Альтернативный подход - двумерный массив, описывающий для каждого состояния/события комбинацию действий, которые нужно выполнить, и следующее состояние, в которое нужно перейти. Это может быть сложнее в управлении, когда вам нужно переходить в разные состояния в зависимости от "обстоятельств", но это можно сделать хорошо. У вас есть функция распознавания событий, которая возвращает следующее событие; у вас есть таблица, где каждая запись в таблице определяет функцию, которую нужно вызвать при получении события, и следующее состояние, в которое нужно перейти - если только вызываемая функция не переопределит это состояние.
На самом деле генерировать такой код сложнее - это зависит от того, как FSM описана изначально. Часто важно обнаружить дублирующие действия. Часто можно полагаться на технику "разреженной матрицы", которая не записывает обработку ошибок в явном виде: если запись логически существует в разреженной матрице, вы действуете на основе информации о событии/состоянии, но если запись не существует, вы возвращаетесь к соответствующему коду сообщения об ошибках и ресинхронизации.
Двумерный массив указателей на структуры может быть передан в общую функцию FSM; того факта, что вы пишете тройной указатель, достаточно, чтобы заставить вас насторожиться по поводу происходящего. (Я написал одну из таких функций еще в марте 1986 года - у меня больше нет исходного текста на диске, но у меня все еще есть распечатка документа, в котором она описана)
.Лучший способ в значительной степени субъективен, но наиболее распространенным способом является использование подхода "на основе таблиц" где вы сопоставляете коды состояний (перечисления или какой-либо другой интегральный тип) с указателями функций. Функция возвращает ваше следующее состояние и другие связанные данные, и вы выполняете цикл до тех пор, пока не будет достигнуто конечное состояние. На самом деле это может быть то, что вы описываете как свой подход выше.
Это практически стандартный подход. Если вам интересно изучить хорошо продуманную библиотеку и сравнить специфику, посмотрите на Ragel:
Ragel компилирует исполняемые конечные автоматы состояний из обычных языков. Ragel ориентирован на C, C++, Objective-C, D, Java и Ruby. Автоматы состояний Ragel могут не только распознавать последовательности байтов, как это делают автоматы регулярных выражений, но и выполнять код в произвольных точках распознавания регулярного языка. Встраивание кода осуществляется с помощью встроенных операторов, которые не нарушают синтаксис регулярного языка.