И много кто, начиная писать реализацию какого-либо протокола, задумывался как написать её красиво, изящно, так чтобы через месяц было понятно что ты имел в виду, чтобы она не отжирала всю память и вообще какала бабочками.
И вот тут на помощь приходят машины состояний, они же конечные автоматы (те самые которые используются в регулярных выражениях).
Собственно через регулярные выражения я к ним и пришёл.
Недавно мне потребовалось реализовать несложную функциональность устройства с 4-мя кнопками — выделение в потенциально хаотичных нажатиях кнопок двух кодовых последовательностей и выполнение определённых действий, когда последовательность найдена.
Поясню на примере: есть 4 кнопки — A, B, C, D и кодовая последовательность ACDA. Тогда при последовательном нажатии B, C, A, D, A, C, D, A, B, устройство должно зажечь лампочку после 8-го (предпоследнего) нажатия. С точки зрения регулярных выражений задача проста — ищем во входной строке подстроку «ACDA». Как только нашли — зажигаем лампочку. Но тащить в микроконтроллер какую-нибудь библиотеку по работе с regexp не хотелось. Я чувствовал что всё можно сделать самому и проще. Тогда я решил попробовать самостоятельно реализовать конечный автомат соответствующий поиску данной подпоследовательности.
А теперь — немного теории и практики:
Основная черта конечных автоматов — они описываются набором возможных состояний, набором сигналов (событий) и таблицей переходов. Таблица переходов — это сопоставление паре из текущего состояния и пришедшего сигнала нового состояния.
Представим, что у нас есть автомат с 3 состояниями и 3 сигналами, которые нужно обрабатывать. По приходу каждого сигнала автомат совершает переходит в новое состояние.
enum states
{
initial = 0,
state_1,
state_final
};
enum signals
{
sign0,
sign1,
sign_N
};
enum signals getSignal();
void doFSM()
{
enum states current_state = initial;
while (1)
{
enum signals current_signal = getSignal();
switch (current_state)
{
case initial:
switch (current_signal)
{
case sign0:
current_state = state_1;
break;
case sign1:
current_state = initial;
break;
case signN:
current_state = state_1;
break;
}
break;
case state_1:
switch (current_signal)
{
case sign0:
current_state = initial;
break;
case sign1:
current_state = state_1;
break;
case signN:
current_state = state_final;
break;
}
break;
case state_final:
switch (current_signal)
{
case sign0:
current_state = initial;
break;
case sign1:
current_state = initial;
break;
case signN:
current_state = initial;
break;
}
break;
}
}
}
Очевидно что данный код не очень удобочитаем и будет катастрофически разрастаться с увеличением количества состояний и сигналов.
Кроме того, если мы захотим в каждый переход добавить какое-либо однотипное действие (например логирование — что-то вроде
printf("Current = %d, signal = %d\n", current_state, current_signal);
), то это породит кучу изменений в коде. При редактировании таких изменений почти наверняка будет допущена какая-нибудь ошибка и отладка превратится в ад.
Заметим, что суть двух вложенных switch — это выбор из таблицы (по колонке и по столбцу) и вспомним что формально конечные автоматы удобно записывать в виде таблицы переходов где каждая строка соответствует сигналу, каждый столбец — состоянию, а на пересечении записано состояние в которое переходит автомат.
Попробуем упростить имеющийся код, задав таблицу переходов, извините за тафтологию, таблицей.
enum states FSM_table[3][3] = {
[initial][sign0] = state_1,
[initial][sign1] = initial,
[initial][sign_N] = state_1,
[state_1][sign0] = initial,
[state_1][sign1] = state_1,
[state_1][sign_N] = state_final,
[state_final][sign0] = initial,
[state_final][sign1] = initial,
[state_final][sign_N] = initial
};
Продемонстрированый вид инициализации даннных известен как designated inits и был введён в С99.
теперь надо полученную структуру данных обработать — пишем функцию doFSM_table:
void doFSM_table()
{
enum states current_state = initial;
while (1)
{
enum signals current_signal = getSignal();
current_state = FSM_table[current_state][current_signal];
}
}
Код получился проще и понятнее, правда?
Теперь ещё несколько бонусов подобной записи:
- нет ничего проще, чем добавить отладочный вывод к каждому шагу автомата:doFSM_table с отладочным выводом
void doFSM_table()
{
enum states current_state = initial;
while (1)
{
enum signals current_signal = getSignal();
enum states new_state = FSM_table[current_state][current_signal];
printf("Current = %d, signal = %d, new = %d\n", current_state, current_signal, new_state);
current_state = new_state;
}
}
- собранный бинарный код существенно уменьшится, что бывает очень полезно в микроконтроллерах
- при необходимости таблицу переходов можно изменить прямо во время выполнения, например при загрузке новой конфигурации
Чтобы сделать получившийся автомат ещё более универсальным и придать ему возможность совершать какие-то действия кроме перехода по состояниям добавим в таблицу указатели на функции-обработчики, соответствующие переходам:
typedef void (*transition_callback)(enum states state, enum signals signal);
struct transition
{
enum states new_state;
transition_callback worker;
};
void initial_1_fxn(enum states state, enum signals signal);
void initial_1N_fxn(enum states state, enum signals signal);
void fxn2(enum states state, enum signals signal);
void fxn3(enum states state, enum signals signal);
void to_initial_fxn(enum states state, enum signals signal);
struct transition FSM_table[3][3] = {
[initial][sign0] = {state_1, initial_1_fxn},
[initial][sign1] = {initial, NULL},
[initial][sign_N] = {state_1, initial_1N_fxn},
[state_1][sign0] = {initial, fxn2},
[state_1][sign1] = {state_1, fxn3},
[state_1][sign_N] = {state_final, NULL},
[state_final][sign0] = {initial, to_initial_fxn},
[state_final][sign1] = {initial, to_initial_fxn},
[state_final][sign_N] = {initial, to_initial_fxn}
};
void doFSM_table()
{
enum states current_state = initial;
while (1)
{
enum signals current_signal = getSignal();
enum states new_state = FSM_table[current_state][current_signal].new_state;
transition_callback worker = FSM_table[current_state][current_signal].worker;
if (worker != NULL)
{
worker(current_state, current_signal);
}
current_state = new_state;
}
}
Вообще улучшать данный механизм можно долго, но данная статья ставит своей целью не разработать универсальную библиотеку для реализации конечных автоматов, а продемонстрировать как некоторые задачи могут быть решены значительно проще и компактнее чем «в лоб», при этом не прибегая ни к каким замысловатым библиотекам или языкам.
В заключение приведу таблицу, получившуюся для задача поиска подпоследовательности, с которой я начинал:
enum states FSM_table[9][4] = {
[initial ... sACDA][bA ... bD] = initial, //для всех сигналов кроме описанных ниже возвращаемся в исходное состояние.
[initial][bA] = sA, //распознали начало последовательности
//ветка для последовательности ABADC
[sA][bB] = sAB,
[sAB][bA] = sABA,
[sABA][bD] = sABAD,
[sABAD][bC] = sABADC,
//ветка для последовательности ACDA
[sA][bC] = sAC,
[sAC][bD] = sACD,
[sACD][bA] = sACDA
};
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Комментариев нет:
Отправить комментарий