Comments 50
С точки зрения регулярных выражений задача проста — ищем во входной строке подстроку «ACDA».Если ваша задача звучит именно таким образом, то не очень понятно, зачем вам здесь регулярные выражения или собственная реализация конечного автомата. Задача поиска подстроки в строке является классической, известно множество алгоритмов её решения, в вашем случае, если строка-образец действительно такая короткая, подойдет тривиальный алгоритм, работающий за O(nm), где n — длина строки, в которой ищем, а m — длина образца.
Вообще-то — да. Регулярные выражения здесь вообще overkill.
А вот с поиском подстроки в строке есть несколько нюансов:
Так как нельзя дождаться окончания строки, а надо реагировать на каждый символ, то приходится хранить где-то уже пришедшую строку.
Если образцов несколько — то надо при приходе каждого символа сравнивать получившуюся строку с каждым из образцов.
Если экономить память — то нужно хранить последние m символов в кольцевом буфере и писать собственную реализацию алгоритма поиска подстроки в строке работающую не на подряд идущей строке, а на буфере. Если не писать свою реализацию — надо при приходе каждого символа накопленную строку из кольцевого буфера копировать в линейный.
В принципе всё это решаемо, но по итогам я подумал что собственный ДКА будет компактнее.
А вот с поиском подстроки в строке есть несколько нюансов:
Так как нельзя дождаться окончания строки, а надо реагировать на каждый символ, то приходится хранить где-то уже пришедшую строку.
Если образцов несколько — то надо при приходе каждого символа сравнивать получившуюся строку с каждым из образцов.
Если экономить память — то нужно хранить последние m символов в кольцевом буфере и писать собственную реализацию алгоритма поиска подстроки в строке работающую не на подряд идущей строке, а на буфере. Если не писать свою реализацию — надо при приходе каждого символа накопленную строку из кольцевого буфера копировать в линейный.
В принципе всё это решаемо, но по итогам я подумал что собственный ДКА будет компактнее.
Если экономить память — то нужно хранить последние m символов в кольцевом буфереНе обязательно, можно банально каждый раз сдвигать символы на 1 элемент влево. Вообще, если дело обстоит так, как вы описали выше, и у вас всего 4 возможных символа, то любую строку длины 4 можно представить просто числом от 0 до 15 и сравнение строк свести к сравнению двух чисел.
В принципе всё это решаемо, но по итогам я подумал что собственный ДКА будет компактнее.Мне кажется, тут вы ошиблись, тривиальный алгоритм займет меньше строк, чем одно лишь описание автомата для вашей строки.
В чем минус вашего решения на мой взгляд? Представим себе, что мы захотели поменять шаблонную строку или добавить новую. В этом случае мы не можем просто где-то заменить константу, а вынуждены будем руками реализовывать конечный автомат для нашей новой строки. Дело это не такое уж и тривиальное, как кажется, представим, что у нас строка вида "ABAC" и мы находимся в состоянии «встречено первые 3 символа». Тогда для символа A мы должны перейти в состояние «встречен 1 символ», для B — «встречено 2 символа», для С — «найдена вся строка», для D — «ни один символ не встречен». Если хотите, можно, увеличив длину строки, построить ещё более сложный пример.
Не обязательно, можно банально каждый раз сдвигать символы на 1 элемент влево. Вообще, если дело обстоит так, как вы описали выше, и у вас всего 4 возможных символа, то любую строку длины 4 можно представить просто числом от 0 до 15 и сравнение строк свести к сравнению двух чисел.Это уже посоветовали в комментариях ниже.
Про сложность потенциальную сложность автомата — да, наверное вы правы. Надо совершенствоваться в умении не строить Hammer, когда достаточно телеги.
Регулярки и автоматы хороши, когда вам требуется найти все подстроки, принадлежащие к некоторому классу (например, выделить из текста все даты в каком-то формате). Для вашей же задачи и в более общем случае (когда длина шаблона может быть большой) существуют более простые и при этом не менее эффективные алгоритмы, например алгоритм Кнута-Морриса-Пратта
Нет ничего такого что регулярные выражения не могли бы сделать хуже.
Как раз думал над унификацией разбросанных по проектам частных решений с автоматами, и ваша статья как нельзя кстати. И да, как раз размышлял, как бы универсально обрабатывать переходы по эвентам. Двумерный массив переходов — оригинально :)
К сожалению, не могу пока голосовать, но плюсик в уме
Ещё, я бы таблицу размещал как const, в флеш-памяти. Экономия ОЗУ и надежность.
К сожалению, не могу пока голосовать, но плюсик в уме
Ещё, я бы таблицу размещал как const, в флеш-памяти. Экономия ОЗУ и надежность.
И ещё кое-что.
Мне больше нравится оформление в виде
Мне больше нравится оформление в виде
BEGIN_STATE_MASHINE(SM_Name)
ADD_BRANCH(OldState, Event, NewState, CallBack)
END_STATE_MASHINE(SM_Name)
*MACHINE *Callback
Дальнейшее оформление — дело вкуса.
В принципе лучше в функцию doFSM выделять отдельный шаг автомата, а не весь цикл. Тогда можно делать «вложенные» машины состояний, когда шаг одной вызывает событие в другой и т.д.
А ещё можно к таблице переходов прикрутить имя автомата и текущее состояние и передавать эту структуру в doFSM. Тогда можно обойтись вообще одной функцией на все автоматы и несколькими структурами с таблицами переходов. Но я решил не перегружать статью, а то можно бесконечно писать.
В принципе лучше в функцию doFSM выделять отдельный шаг автомата, а не весь цикл. Тогда можно делать «вложенные» машины состояний, когда шаг одной вызывает событие в другой и т.д.
А ещё можно к таблице переходов прикрутить имя автомата и текущее состояние и передавать эту структуру в doFSM. Тогда можно обойтись вообще одной функцией на все автоматы и несколькими структурами с таблицами переходов. Но я решил не перегружать статью, а то можно бесконечно писать.
Можно объявлять как const. Тогда уж сразу же надо заставить компилятор выделать под enum не int, а минимально необходимое число байт.
Но тогда нельзя (сложно) будет переконфигурировать «на лету», т.е. в моём случае, менять кодовые последовательности. Это не всегда нужно, но иногда приятно — например при создании перепрограммируемого кодового замка.
Но тогда нельзя (сложно) будет переконфигурировать «на лету», т.е. в моём случае, менять кодовые последовательности. Это не всегда нужно, но иногда приятно — например при создании перепрограммируемого кодового замка.
Двумерный массив переходов — оригинально :)
Извините, без подкола, — а как еще можно представить-то?
Можно (но не нужно) представить линейным массивом структур из {old_state, signal, new_state, callback}. Если его правильно отсортировать он окажется двумерным. Если не сортировать — поиск нужного перехода из O(1) станет O(n) и будет вызывать боль (кроме случая когда мы экономим память, а таблица разреженная).
здесь должен был быть монолог в пользу map<pair<state,event>, pair<state, callback>>, но я не люблю С++ в микроконтроллерах
А, понятно, спасибо.
Насколько ж по-разному головы работают… Мне бы в голову ничего, кроме двухмерного массива не пришло бы.
Насколько ж по-разному головы работают… Мне бы в голову ничего, кроме двухмерного массива не пришло бы.
Другой, гораздо более типичный способ — представлять в виде функции, вычисляющей новое состояние (это может быть как единая функция для всех состояний, так и по одной штуке для каждого состояния). Пример есть в статье под катом «Наиболее интуитивный, но громоздкий код для подобной задачи». В случае, когда у вас алфавит достаточно велик (а не 4 символа, как у автора), способы, честно хранящие новое состояние для каждой пары <исходное состояние, символ>, дают слишком большой memory overhead.
Если вы думаете над унификацией по проектам с коллективной разработкой, имеет смысл рассмотреть устоявшийся хорошо документированный фреймворк — про один из таких есть, на мой взгляд, толковая книга автора по имени Miro Samek «Practical UML Statecharts in C/C++, Second Editiion. Event-Driven Programming for Embedded Systems». Собственно, очевидное преимущество описываемого там фреймворка (автор назвал его QP, Quantum leaPs) — сам факт существования книги :) (я первое издание читал в бумажной копии, теперь имею pdf второго издания, прочту, когда реально понадобится).
(заглянул на сайт автора — у него, оказывается, графический инструмент ещё появился для моделирования, ещё один плюс...)
(заглянул на сайт автора — у него, оказывается, графический инструмент ещё появился для моделирования, ещё один плюс...)
По-русски — не «машина состояний», а «конечный автомат». Заголовок глаза режет.
«Устройство с четырьмя кнопками» да на чистом С — это не Pebble случайно? ) Очень похоже!
Полезная статейка, возьму на заметку.
Если у в вашем случае нужно проверять строку из четырех символов (байт) то реализацию можно сильно упростить:
Если у в вашем случае нужно проверять строку из четырех символов (байт) то реализацию можно сильно упростить:
current_signal = getSignal();
current_state = (current_state&0xffffffff << 8) + current_signal;
if (current_signal==valid_state)
// установлено нужное состояние
Можно, но (при моём руководстве) боязно делать настолько узкозаточенные алгоритмы — а вдруг попросят сделать последовательность из 7 кнопок? И не говорите мне что если кнопок всего 4, то нужно 2 бита на сигнал и в Uint32 влезет последовательность из 16 кнопок.
Хотя идея тоже красивая в своей оптимизированности.
Хотя идея тоже красивая в своей оптимизированности.
Хотелось бы порекомендовать автору ragel: en.wikipedia.org/wiki/Ragel — генератор конечных автоматов на чистом C. Там, где борьба идет за каждый лишний байт кода, возможно, и не подойдет, но в общем его вывод весьма хорош (-G2).
Спасибо, покурю. Раньше пользовался только flex — но мне кажется что он слишком заточен на работу именно с текстом.
Присоединяюсь к рекомендации Ragel. Хочу особо выделить некоторые фичи
- генерация быстрого Си кода (можно сгенерировать fsm целиком на goto)
- можно писать как в стиле регулярных выражений, так и писать явный fsm. Можно мешать то и другое.
- на состояния и переходы можно повесить произвольные действия, код подставляется inline.
Для тех, кто испытывал чувство дежавю во время прочтения: описанное очень близко к алгоритму Кнута — Морриса — Пратта (жалко на Википедии нет примера ДКА, для полноты аналогии).
В указанном Вами алгоритме самая интересная часть, по моему мнению, это именно построение таблицы переходов, а не описание общих принципов работы.
Если расстатривать алгоритм отдельно, то да. А если рассматривать решаемую задачу и алгоритм, то он прямо «просится» сюда. Во-первых, обработка данных при их поступлении без использования буфера. Во-вторых, заранее известный шаблон, идеальный случай для данного алгоритма.
После фразы про строки мысли идут в сторону соответствующих алгоритмов, дальше требования отсекают остальные, а потом в тексте описывается автомат в таком виде, какой был бы построен КМП. Если бы это было целью автора, то вышел бы отличный пример использования алгоритма.
После фразы про строки мысли идут в сторону соответствующих алгоритмов, дальше требования отсекают остальные, а потом в тексте описывается автомат в таком виде, какой был бы построен КМП. Если бы это было целью автора, то вышел бы отличный пример использования алгоритма.
Я вот так всегда делаю:
github.com/Traumflug/Teacup_Firmware/blob/master/gcode_parse.c
Т.е. если нужна последовательность «ACDA», то алгоритм такой: читаем символ, если он А и стейт «начало», идем в стейт «ждем С». Читаем символ, если он С — идем в стейт «ждем D», иначе откатываемся в начало. В случае приведенного примера не очень-то большой код получается, а вот с ростом количества сигналов и состояний можно немаленький огород вырастить.
Вроде чувствую, что в топике что-то интересное описано, а понять код не могу :-(
github.com/Traumflug/Teacup_Firmware/blob/master/gcode_parse.c
Т.е. если нужна последовательность «ACDA», то алгоритм такой: читаем символ, если он А и стейт «начало», идем в стейт «ждем С». Читаем символ, если он С — идем в стейт «ждем D», иначе откатываемся в начало. В случае приведенного примера не очень-то большой код получается, а вот с ростом количества сигналов и состояний можно немаленький огород вырастить.
Вроде чувствую, что в топике что-то интересное описано, а понять код не могу :-(
Так топик как раз об этом — как удобнее расположить грядки в огороде, чтобы в нём не запутаться.
С описанного вами подхода я как раз начинал — смотрите первый приведённый мною кусок кода «Наиболее интуитивный, но громоздкий код для подобной задачи».
А дальше я рассказываю как его сделать компактнее.
ОФФТОП: читая gcode_parse.c, на который вы ссылаетесь, задался вопросом: мне кажется или
Казалось бы что если (debug_flags & DEBUG_ECHO), т.е. (debug_flags & DEBUG_ECHO) != 0, то и DEBUG_ECHO != 0.
С описанного вами подхода я как раз начинал — смотрите первый приведённый мною кусок кода «Наиболее интуитивный, но громоздкий код для подобной задачи».
А дальше я рассказываю как его сделать компактнее.
ОФФТОП: читая 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.
читаем символ, если он А и стейт «начало», идем в стейт «ждем С». Читаем символ, если он С — идем в стейт «ждем D», иначе откатываемся в начало
Ну так, блин, это и есть конечный автомат. Автор описал универсальное, короткое решение.
Таблица легко строится по графу, методы минимизации автомата известны. Соответственно, решение топикстартера лекго поменять. А вот править стену кода…
иначе откатываемся в начало
Тут нюанс: если искомая строка имеет префикс, входящий в строку не только в её начале (например, букву А в ABADC или AB в строке ABABC), то в некоторых ситуациях нужно откатываться не в начало. Например, если искомая строка ABABC, и на входе имеем ABABD, то получив букву D нужно из стейта «ждём букву №5» откатываться не в начало, а в стейт «ждём бувку №3».
И в общем виде, для произвольной искомой строки эта задача не решается таким простым алгоритмом, как вы предлагаете. Нужно построить префикс-функцию, как это делает алгоритм Кнута-Морриса-Пратта, и проще всего она выражается как раз таблицей переходов конечного автомата.
В последнем примере автомата для последовательности ABADC забыли переход:
[sABA][dB] = sAB
Без него он не среагирует на входную строку ABABADC
[sABA][dB] = sAB
Без него он не среагирует на входную строку ABABADC
Очень полезная статья. Помню, как я замучился с этим FSM, когда проходил курс «Embedded Systems — Shape the World» на edX. И скажу, что в плане синтеза, составления графа переходов и составление самой таблицы — тема не раскрыта (но это и не было целью статьи, как я понял).
Кстати, курс стартует вновь — www.edx.org/course/utaustinx/utaustinx-ut-6-02x-embedded-systems-4806
Кстати, курс стартует вновь — www.edx.org/course/utaustinx/utaustinx-ut-6-02x-embedded-systems-4806
А что у него с производительностью по сравнению с первым, громоздким вариантом. У меня парсинг HTTP-запросов делается через свич на несколько сотен строк. Предполагаю, что использование таблицы переходов плюс вызов отдельной функции на каждый переход должно сказаться на производительности, вопрос в том на сколько скажется.
Это очень зависит от компилятора. Если компилятор развернёт switch в таблицу переходов по адресам — будет примерно так же по времени.
Если switch будет развёрнут как последовательность if-else — то мой вариант будет быстрее, т.к. любой переход будет выполняться за фиксированное время, независимо зависимости от расположения в таблице. А у switch-case придётся выверять последовательность case, так чтобы наиболее частые шли первыми.
Помню как у меня замена
на
дало очень существенный прирост.
Про вызов функции — надо смотреть на соотношение трудоёмкости пролога/эпилога с обработкой switch-case. А ещё принимать во внимание как всё это будет кэшироваться. Вообщем без прямых тестов сказать невозможно.
Вообще для оптиматльной производительности, с шансами, подойдёт как раз упомянутый выше Ragel с генерацией кода на goto.
Если 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.
Когда я писал КА на C++ я использовал немного другой подход. Я делал примерно так:
Для Си будет тоже самое, только вместо методов — функции
Каждая из функций уже меняла состояние. Интересно сравнить такой подход с таблицей состояний по скорости.
...
int start();
int state1();
int stateN();
...
parse = &TParser::start;
...
while( getByte() != END){
if((this->*parse)() < 0)
break;
}
Для Си будет тоже самое, только вместо методов — функции
Каждая из функций уже меняла состояние. Интересно сравнить такой подход с таблицей состояний по скорости.
Подход тоже имеет право на жизнь, но:
- В случае если требуется только поменять состояние получается куцая функция перехода
- Непрозрачно (по крайней мере в вашем примере) соответствие графического представления КА с исходным текстом. Я ведь правильно понимаю, что под функцией state1() скрывается парсер входных данных и все переходы из состояния 1? Тогда сложно эти переходы наглядно увидеть в одном месте кода
- в случае добавления ещё одного состояния придётся менять очень много кода разбросанного по файлу — неудобно будет читать diff в системе контроля версий
- Если в рамках отладки захотелось добавить текстовый лог вида «Начальное состояние -> сигнал -> конечное состояние» то его придётся добавлять в каждую функцию, потому что нет момента выполнения где доступны все три значения одновременно.
Про скорость ничего сказать не могу.
Я вот никака не могу понять код :-( Объясни, плз:
enum signals current_signal = getSignal();
Я правильно понимаю, что enum signals — это тип? Т.е. можно сделать typedef enum signals signal_t;
А где функция getSignal? Или это просто некая не относящаяся к посту функция, которая ловит сигнал… АААААААА
ок
enum states new_state = FSM_table[current_state][current_signal];
Блин, понял. В цикле ловим сигнал и меняем стейт по таблице
А чо, класс! Два дня всего отняло понимание :-) Супер пост!
enum signals current_signal = getSignal();
Я правильно понимаю, что enum signals — это тип? Т.е. можно сделать typedef enum signals signal_t;
А где функция getSignal? Или это просто некая не относящаяся к посту функция, которая ловит сигнал… АААААААА
ок
enum states new_state = FSM_table[current_state][current_signal];
Блин, понял. В цикле ловим сигнал и меняем стейт по таблице
А чо, класс! Два дня всего отняло понимание :-) Супер пост!
Нет, для пяти состояний и четырех сигналов табличка получается достаточно компактная, не спорю. Но…
Через какое-то время апологеты табличного задания КА сталкиваются с ситуацией сложных сигналов. Типа такого — если нажата кнопка 1 и температура меньше T1 и двигатель включен, то выключить двигатель. А если двигатель выключен, то зажечь лампу. И начинают выбирать — или плодить сигналы по комбинации условий, или добавлять три-пять промежуточных состояний. Опа, а табличка раздулась, состояний увеличилось и разбираться с ними не менее сложно, чем с ветвистым switch.
И в этом плане мне гораздо удобнее читать
Через какое-то время апологеты табличного задания КА сталкиваются с ситуацией сложных сигналов. Типа такого — если нажата кнопка 1 и температура меньше T1 и двигатель включен, то выключить двигатель. А если двигатель выключен, то зажечь лампу. И начинают выбирать — или плодить сигналы по комбинации условий, или добавлять три-пять промежуточных состояний. Опа, а табличка раздулась, состояний увеличилось и разбираться с ними не менее сложно, чем с ветвистым switch.
И в этом плане мне гораздо удобнее читать
if (blah-blah-blah) {// коммент
GOTO_STATE(POWER_OFF);
} else if (nah-nah-nah) {// коммент
GOTO_STATE(POWER_ON);
}
Это смотря что в качестве входного алфавита выбирать. Раздутая таблица — не проблема, есть способы поиска совместных состояний.
ну так и возвращаемся к теме — добавить левых символов, которые используются только в одном состоянии (а такой комбинации условий может больше и не быть) или наплодить состояний, оптимизировать автомат и потом пытаться понять, что же там не взлетело. И это только для того, чтобы сократить главный цикл до двух строк?
И вдогонку — вывод отладки во всех состояниях конечно делается легко, красиво и одной строкой, а если надо вывод сделать в половине состояний? А в другой половине состояний писать в UART?
И вдогонку — вывод отладки во всех состояниях конечно делается легко, красиво и одной строкой, а если надо вывод сделать в половине состояний? А в другой половине состояний писать в UART?
или наплодить состояний, оптимизировать автомат и потом пытаться понять, что же там не взлетело
Зачем? Вполне по силам написать утилиту, которая поправит таблицу и проведет, если надо оптимизацию.
В конце концов, системы типа parser builder'а как раз по БНФ строят таблицы. Тут — аналогично.
а если надо вывод сделать в половине состояний? А в другой половине состояний писать в UART?
Вполне реализуемо.
и вот так по шагам придем к SFC и успокоимся ))
Sign up to leave a comment.
Конечный автомат (он же машина состояний) на чистом С