@Corviniol30 окт 2014 в 07:49

Конечный автомат (он же машина состояний) на чистом С

5 мин

138K

Алгоритмы * C *

Из песочницы

+44

Комментарии 50

@lemelisk 30 окт 2014 в 08:12

С точки зрения регулярных выражений задача проста — ищем во входной строке подстроку «ACDA».

Если ваша задача звучит именно таким образом, то не очень понятно, зачем вам здесь регулярные выражения или собственная реализация конечного автомата. Задача поиска подстроки в строке является классической, известно множество алгоритмов её решения, в вашем случае, если строка-образец действительно такая короткая, подойдет тривиальный алгоритм, работающий за O(nm), где n — длина строки, в которой ищем, а m — длина образца.

@Corviniol 30 окт 2014 в 10:33

Вообще-то — да. Регулярные выражения здесь вообще overkill.
А вот с поиском подстроки в строке есть несколько нюансов:
Так как нельзя дождаться окончания строки, а надо реагировать на каждый символ, то приходится хранить где-то уже пришедшую строку.
Если образцов несколько — то надо при приходе каждого символа сравнивать получившуюся строку с каждым из образцов.
Если экономить память — то нужно хранить последние m символов в кольцевом буфере и писать собственную реализацию алгоритма поиска подстроки в строке работающую не на подряд идущей строке, а на буфере. Если не писать свою реализацию — надо при приходе каждого символа накопленную строку из кольцевого буфера копировать в линейный.
В принципе всё это решаемо, но по итогам я подумал что собственный ДКА будет компактнее.

@lemelisk 30 окт 2014 в 11:38

Если экономить память — то нужно хранить последние m символов в кольцевом буфере

Не обязательно, можно банально каждый раз сдвигать символы на 1 элемент влево. Вообще, если дело обстоит так, как вы описали выше, и у вас всего 4 возможных символа, то любую строку длины 4 можно представить просто числом от 0 до 15 и сравнение строк свести к сравнению двух чисел.

В принципе всё это решаемо, но по итогам я подумал что собственный ДКА будет компактнее.

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

В чем минус вашего решения на мой взгляд? Представим себе, что мы захотели поменять шаблонную строку или добавить новую. В этом случае мы не можем просто где-то заменить константу, а вынуждены будем руками реализовывать конечный автомат для нашей новой строки. Дело это не такое уж и тривиальное, как кажется, представим, что у нас строка вида "ABAC" и мы находимся в состоянии «встречено первые 3 символа». Тогда для символа A мы должны перейти в состояние «встречен 1 символ», для B — «встречено 2 символа», для С — «найдена вся строка», для D — «ни один символ не встречен». Если хотите, можно, увеличив длину строки, построить ещё более сложный пример.

@Corviniol 30 окт 2014 в 11:57

Не обязательно, можно банально каждый раз сдвигать символы на 1 элемент влево. Вообще, если дело обстоит так, как вы описали выше, и у вас всего 4 возможных символа, то любую строку длины 4 можно представить просто числом от 0 до 15 и сравнение строк свести к сравнению двух чисел.

Это уже посоветовали в комментариях ниже.

Про сложность потенциальную сложность автомата — да, наверное вы правы. Надо совершенствоваться в умении не строить Hammer, когда достаточно телеги.

@lemelisk 30 окт 2014 в 12:32

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

@Propheta13 30 окт 2014 в 14:56

Нет ничего такого что регулярные выражения не могли бы сделать хуже.

@Corviniol 30 окт 2014 в 18:46

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

@MrYuran 30 окт 2014 в 08:23

Как раз думал над унификацией разбросанных по проектам частных решений с автоматами, и ваша статья как нельзя кстати. И да, как раз размышлял, как бы универсально обрабатывать переходы по эвентам. Двумерный массив переходов — оригинально :)
К сожалению, не могу пока голосовать, но плюсик в уме
Ещё, я бы таблицу размещал как const, в флеш-памяти. Экономия ОЗУ и надежность.

@MrYuran 30 окт 2014 в 08:48

И ещё кое-что.
Мне больше нравится оформление в виде

BEGIN_STATE_MASHINE(SM_Name)
    ADD_BRANCH(OldState, Event, NewState, CallBack)
END_STATE_MASHINE(SM_Name)

@hardex 30 окт 2014 в 09:57

*MACHINE *Callback

@sim2q 9 фев 2020 в 16:44

Это авторский define

@hardex 9 фев 2020 в 17:13

вау

@Corviniol 30 окт 2014 в 10:52

Дальнейшее оформление — дело вкуса.
В принципе лучше в функцию doFSM выделять отдельный шаг автомата, а не весь цикл. Тогда можно делать «вложенные» машины состояний, когда шаг одной вызывает событие в другой и т.д.
А ещё можно к таблице переходов прикрутить имя автомата и текущее состояние и передавать эту структуру в doFSM. Тогда можно обойтись вообще одной функцией на все автоматы и несколькими структурами с таблицами переходов. Но я решил не перегружать статью, а то можно бесконечно писать.

@Corviniol 30 окт 2014 в 10:35

Можно объявлять как const. Тогда уж сразу же надо заставить компилятор выделать под enum не int, а минимально необходимое число байт.
Но тогда нельзя (сложно) будет переконфигурировать «на лету», т.е. в моём случае, менять кодовые последовательности. Это не всегда нужно, но иногда приятно — например при создании перепрограммируемого кодового замка.

@MacIn 30 окт 2014 в 20:30

Двумерный массив переходов — оригинально :)

Извините, без подкола, — а как еще можно представить-то?

@Corviniol 31 окт 2014 в 06:59

Можно (но не нужно) представить линейным массивом структур из {old_state, signal, new_state, callback}. Если его правильно отсортировать он окажется двумерным. Если не сортировать — поиск нужного перехода из O(1) станет O(n) и будет вызывать боль (кроме случая когда мы экономим память, а таблица разреженная).
~~здесь должен был быть монолог в пользу map<pair<state,event>, pair<state, callback>>, но я не люблю С++ в микроконтроллерах~~

@MacIn 31 окт 2014 в 14:34

А, понятно, спасибо.
Насколько ж по-разному головы работают… Мне бы в голову ничего, кроме двухмерного массива не пришло бы.

@lemelisk 31 окт 2014 в 16:06

Другой, гораздо более типичный способ — представлять в виде функции, вычисляющей новое состояние (это может быть как единая функция для всех состояний, так и по одной штуке для каждого состояния). Пример есть в статье под катом «Наиболее интуитивный, но громоздкий код для подобной задачи». В случае, когда у вас алфавит достаточно велик (а не 4 символа, как у автора), способы, честно хранящие новое состояние для каждой пары <исходное состояние, символ>, дают слишком большой memory overhead.

@sashagil 31 окт 2014 в 23:27

Если вы думаете над унификацией по проектам с коллективной разработкой, имеет смысл рассмотреть устоявшийся хорошо документированный фреймворк — про один из таких есть, на мой взгляд, толковая книга автора по имени Miro Samek «Practical UML Statecharts in C/C++, Second Editiion. Event-Driven Programming for Embedded Systems». Собственно, очевидное преимущество описываемого там фреймворка (автор назвал его QP, Quantum leaPs) — сам факт существования книги :) (я первое издание читал в бумажной копии, теперь имею pdf второго издания, прочту, когда реально понадобится).

(заглянул на сайт автора — у него, оказывается, графический инструмент ещё появился для моделирования, ещё один плюс...)

@VioletGiraffe 30 окт 2014 в 09:19

По-русски — не «машина состояний», а «конечный автомат». Заголовок глаза режет.

@Corviniol 30 окт 2014 в 10:36

Поправил заголовок.

@Nehc 30 окт 2014 в 09:23

«Устройство с четырьмя кнопками» да на чистом С — это не Pebble случайно? ) Очень похоже!

@vassav 30 окт 2014 в 10:41

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

current_signal = getSignal();
current_state = (current_state&0xffffffff << 8) + current_signal;
	if (current_signal==valid_state)
		// установлено нужное состояние

@Corviniol 30 окт 2014 в 10:58

Можно, но (при моём руководстве) боязно делать настолько узкозаточенные алгоритмы — а вдруг попросят сделать последовательность из 7 кнопок? И не говорите мне что если кнопок всего 4, то нужно 2 бита на сигнал и в Uint32 влезет последовательность из 16 кнопок.
Хотя идея тоже красивая в своей оптимизированности.

@dimoclus 30 окт 2014 в 11:33

Хотелось бы порекомендовать автору ragel: en.wikipedia.org/wiki/Ragel — генератор конечных автоматов на чистом C. Там, где борьба идет за каждый лишний байт кода, возможно, и не подойдет, но в общем его вывод весьма хорош (-G2).

@Corviniol 30 окт 2014 в 11:49

Спасибо, покурю. Раньше пользовался только flex — но мне кажется что он слишком заточен на работу именно с текстом.

@mejedi 30 окт 2014 в 12:06

Присоединяюсь к рекомендации Ragel. Хочу особо выделить некоторые фичи

генерация быстрого Си кода (можно сгенерировать fsm целиком на goto)
можно писать как в стиле регулярных выражений, так и писать явный fsm. Можно мешать то и другое.
на состояния и переходы можно повесить произвольные действия, код подставляется inline.

@xaizek 30 окт 2014 в 12:32

Для тех, кто испытывал чувство дежавю во время прочтения: описанное очень близко к алгоритму Кнута — Морриса — Пратта (жалко на Википедии нет примера ДКА, для полноты аналогии).

@QtRoS 30 окт 2014 в 14:33

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

@xaizek 30 окт 2014 в 15:01

Если расстатривать алгоритм отдельно, то да. А если рассматривать решаемую задачу и алгоритм, то он прямо «просится» сюда. Во-первых, обработка данных при их поступлении без использования буфера. Во-вторых, заранее известный шаблон, идеальный случай для данного алгоритма.

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

@imwode 30 окт 2014 в 15:40

Я вот так всегда делаю:
github.com/Traumflug/Teacup_Firmware/blob/master/gcode_parse.c
Т.е. если нужна последовательность «ACDA», то алгоритм такой: читаем символ, если он А и стейт «начало», идем в стейт «ждем С». Читаем символ, если он С — идем в стейт «ждем D», иначе откатываемся в начало. В случае приведенного примера не очень-то большой код получается, а вот с ростом количества сигналов и состояний можно немаленький огород вырастить.

Вроде чувствую, что в топике что-то интересное описано, а понять код не могу :-(

@Corviniol 30 окт 2014 в 19:36

Так топик как раз об этом — как удобнее расположить грядки в огороде, чтобы в нём не запутаться.
С описанного вами подхода я как раз начинал — смотрите первый приведённый мною кусок кода «Наиболее интуитивный, но громоздкий код для подобной задачи».
А дальше я рассказываю как его сделать компактнее.
ОФФТОП: читая gcode_parse.c, на который вы ссылаетесь, задался вопросом: мне кажется или

if (DEBUG_ECHO && (debug_flags & DEBUG_ECHO))

полностью эквивалентна более компактной

if (debug_flags & DEBUG_ECHO)

?
Казалось бы что если (debug_flags & DEBUG_ECHO), т.е. (debug_flags & DEBUG_ECHO) != 0, то и DEBUG_ECHO != 0.

@imwode 31 окт 2014 в 19:21

Да, что-то странное с этим. Если бы это был питон, то можно было бы сказать, что это для ускорения :-)

@MacIn 30 окт 2014 в 20:28

читаем символ, если он А и стейт «начало», идем в стейт «ждем С». Читаем символ, если он С — идем в стейт «ждем D», иначе откатываемся в начало

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

@IlyaSkriblovsky 30 окт 2014 в 20:49

иначе откатываемся в начало

Тут нюанс: если искомая строка имеет префикс, входящий в строку не только в её начале (например, букву А в ABADC или AB в строке ABABC), то в некоторых ситуациях нужно откатываться не в начало. Например, если искомая строка ABABC, и на входе имеем ABABD, то получив букву D нужно из стейта «ждём букву №5» откатываться не в начало, а в стейт «ждём бувку №3».

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

@IlyaSkriblovsky 30 окт 2014 в 20:41

В последнем примере автомата для последовательности ABADC забыли переход:
[sABA][dB] = sAB

Без него он не среагирует на входную строку ABABADC

@Corviniol 31 окт 2014 в 06:42

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

@KurilkaRymin 30 окт 2014 в 22:49

Очень полезная статья. Помню, как я замучился с этим FSM, когда проходил курс «Embedded Systems — Shape the World» на edX. И скажу, что в плане синтеза, составления графа переходов и составление самой таблицы — тема не раскрыта (но это и не было целью статьи, как я понял).
Кстати, курс стартует вновь — www.edx.org/course/utaustinx/utaustinx-ut-6-02x-embedded-systems-4806

@saterenko 31 окт 2014 в 06:21

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

@Corviniol 31 окт 2014 в 06:54

Это очень зависит от компилятора. Если компилятор развернёт switch в таблицу переходов по адресам — будет примерно так же по времени.
Если switch будет развёрнут как последовательность if-else — то мой вариант будет быстрее, т.к. любой переход будет выполняться за фиксированное время, независимо зависимости от расположения в таблице. А у switch-case придётся выверять последовательность case, так чтобы наиболее частые шли первыми.
Помню как у меня замена

switch (argument)
{
case 0x10: ... break;
case 0x20: ... break;
case 0x50: ... break;
default: ...
}

на

switch (argument >> 4)
{
case 0x1: ... break;
case 0x2: ... break;
case 0x5: ... break;
default: ...
}

дало очень существенный прирост.

Про вызов функции — надо смотреть на соотношение трудоёмкости пролога/эпилога с обработкой switch-case. А ещё принимать во внимание как всё это будет кэшироваться. Вообщем без прямых тестов сказать невозможно.
Вообще для оптиматльной производительности, с шансами, подойдёт как раз упомянутый выше Ragel с генерацией кода на goto.

@saterenko 31 окт 2014 в 07:12

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

@xaoc80 31 окт 2014 в 08:00

Когда я писал КА на C++ я использовал немного другой подход. Я делал примерно так:

...
int start();
int state1();
int stateN();
...
parse = &TParser::start;
...
while( getByte() != END){
       if((this->*parse)() < 0)
              break;
}

Для Си будет тоже самое, только вместо методов — функции
Каждая из функций уже меняла состояние. Интересно сравнить такой подход с таблицей состояний по скорости.

@Corviniol 31 окт 2014 в 08:19

Подход тоже имеет право на жизнь, но:

В случае если требуется только поменять состояние получается куцая функция перехода
Непрозрачно (по крайней мере в вашем примере) соответствие графического представления КА с исходным текстом. Я ведь правильно понимаю, что под функцией state1() скрывается парсер входных данных и все переходы из состояния 1? Тогда сложно эти переходы наглядно увидеть в одном месте кода
в случае добавления ещё одного состояния придётся менять очень много кода разбросанного по файлу — неудобно будет читать diff в системе контроля версий
Если в рамках отладки захотелось добавить текстовый лог вида «Начальное состояние -> сигнал -> конечное состояние» то его придётся добавлять в каждую функцию, потому что нет момента выполнения где доступны все три значения одновременно.

@imwode 31 окт 2014 в 13:55

Я вот никака не могу понять код :-( Объясни, плз:

enum signals current_signal = getSignal();
Я правильно понимаю, что enum signals — это тип? Т.е. можно сделать typedef enum signals signal_t;
А где функция getSignal? Или это просто некая не относящаяся к посту функция, которая ловит сигнал… АААААААА
ок

enum states new_state = FSM_table[current_state][current_signal];

Блин, понял. В цикле ловим сигнал и меняем стейт по таблице

А чо, класс! Два дня всего отняло понимание :-) Супер пост!

@steel_ne 6 ноя 2014 в 19:45

Нет, для пяти состояний и четырех сигналов табличка получается достаточно компактная, не спорю. Но…

Через какое-то время апологеты табличного задания КА сталкиваются с ситуацией сложных сигналов. Типа такого — если нажата кнопка 1 и температура меньше T1 и двигатель включен, то выключить двигатель. А если двигатель выключен, то зажечь лампу. И начинают выбирать — или плодить сигналы по комбинации условий, или добавлять три-пять промежуточных состояний. Опа, а табличка раздулась, состояний увеличилось и разбираться с ними не менее сложно, чем с ветвистым switch.

И в этом плане мне гораздо удобнее читать

if (blah-blah-blah) {// коммент
    GOTO_STATE(POWER_OFF);
} else if (nah-nah-nah) {// коммент
    GOTO_STATE(POWER_ON);
}

@MacIn 6 ноя 2014 в 20:04

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

@steel_ne 6 ноя 2014 в 20:14

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

И вдогонку — вывод отладки во всех состояниях конечно делается легко, красиво и одной строкой, а если надо вывод сделать в половине состояний? А в другой половине состояний писать в UART?

@MacIn 6 ноя 2014 в 20:34

или наплодить состояний, оптимизировать автомат и потом пытаться понять, что же там не взлетело

Зачем? Вполне по силам написать утилиту, которая поправит таблицу и проведет, если надо оптимизацию.
В конце концов, системы типа parser builder'а как раз по БНФ строят таблицы. Тут — аналогично.

а если надо вывод сделать в половине состояний? А в другой половине состояний писать в UART?

Вполне реализуемо.

@steel_ne 6 ноя 2014 в 21:28

и вот так по шагам придем к SFC и успокоимся ))

@MacIn 6 ноя 2014 в 22:33

Каждой задаче — свой инструмент.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий