Такая задача. Контроллер принимает по UART некоторые данные в виде строк разной длины и содержания. Т.е. обычные текстовые строки. В этих строках может содержаться команда для контроллера, например: Switсh on out 7, input 1 disable, Led 11 on.
Строки хранятся до разбора в массиве. Размер массива ограничен, а частота поступления новых строк не нормируется. Поэтому нужно быстро разобрать строку, вычленить из нее ключевые слова и передать соответствующие команды основной программе. Задача усложняется тем, что таких слов будет около 100, кроме того, в будущем их кол-во предполагается увеличить.
Как реализуется обычно такая задача? Ничего умнее, как последовательный поиск каждого слова в строке придумать не могу. Но это очень долго получается. Например, сначала придется пролистать весь массив в поисках "Led", потом опять весь массив в поисках "input" и т.д. А хочется читать строку 1 раз, по пути находя все ключевые слова.

Если есть возможность повлиять на формирование самих команд, то можно перед "значимой" частью передавать преамбулу (уникальный символ или группа символов). Найдя преамбулу в строке можно взвести флаг о том, что дальше идет/идут команды. Окончание поля команд тоже можно обособить для того, чтобы декодировку и поиск.

Да в общем-то все данные получаются значимыми. Просто не известно, какая команда будет первой, какая последней, сколько команд будет в строке и каких именно. Т.е. строка может выглядеть так:

Switch on out 1, led 7 off.

А может так:

led 8 on, timer1 stop, Switch on out6, led 9 off

Как пример.
Есть GSM-модуль, управляемый через терминал. Допустим, я ввожу команду AT+CGSN\r\n
Что происходит дальше? Как контроллер обрабатывает эту строку и находит соответствие этой записи конкретной команде? Вот мне нужно реализовать примерно то же самое.

Ну, для начала надо взять большой листок бумаги и разрисовать машину состояний, которая будет обрабатывать ваши ключевые слова.
Например, команда "Switch on out 1" правильная, а "Switch 1 on out" неправильная, я надеюсь. То есть при приеме токена "switch" следующим токеном должен быть "on" или "off" итп.
Если вы начнете кодить не имея полного формального описания автомата разбора, ничего не получится.

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

А вот потом начнется самое интересное Тестирование А то в ваш парзер придет строка "led -1 fuck off" и он зависнет в бесконечном цикле

Сообщение отредактировал CrimsonPig - Dec 3 2015, 20:58

Ну примитивный разбор работает. Т.е. я просматриваю строку в поисках "Switch". Далее смотрю уже "off" или "on", далее объект "out", потом номер.
Далее приходится снова просматривать всю строку в поисках "timer" -> номер таймера -> команда.

Необходимо оптимизировать именно начальный поиск (а оп аналогии и разветвления так же). Ну например, просматриваю строку. Первая буква "S" - таких команд 10. Вторая "w" - таких команд 5. Третья "i" - таких команд 1. Проверяю, действительно ли это она ну и смотрю ее параметры.
Далее нахожу разделитель, например ",". После нее 1-я буква "L" - 20 команд, 2-я "e" - 2 команды, ну и т.п. Т.е. обработка всей строки за 1 проход.

Можно составить статический связный список соответствия вида 'символ' -> 'команда1', 'команда2', ... 'командаN', в который внести команды, в которых этот символ встречается, и упорядочить его по частоте употребления символа в командах, начиная с наиболее популярного. Например, в вашем случае словарь команд состоит из 3 команд - switch,timer,led. Видим, что самые популярные символы в командах - это t, i и e (встречаются по 2 раза). Начнём с любого из них, например, t:

Позиция команды в списке "по горизонтали" соответствует позиции искомого символа внутри команды. NULL заканчивает связный список.

Тогда, чтобы вычленить и выполнить команду в пришедшей строке, в которой команд может быть несколько в любом порядке, необходимо организовать последовательный поиск символов, начиная с наиболее популярного и далее вниз по списку. Бежим по разбираемой строке с каждым символом из списка - если символ находится, то в этом месте начинаем уже перебирать команды, связанные с этим символом и сравнивать на совпадение. Совпало? Выполняем команду со всеми аргументами и идем дальше.
Почему список начинается с наиболее популярных символов? Чтобы увеличить вероятность разбора всей строки без перебора всего списка. Для этого надо после распознания и выполнения каждой команды вычитать из длины строки количество распознанных символов, пока не останется ноль.
Прошли весь список, а ноль не остался? Синтаксическая ошибка в строке.

Сообщение отредактировал gerber - Dec 3 2015, 22:21

У Вас как я понял строка-команда представляет из себя смесь команд (которые являются группой из латинских букв+цифр) разделённых знаками препинания и пробелами?
Тогда разбиваете строку на лексемы (группы алфавитно-цифровых символов разделённых знаками препинания) за один проход по строке.
Потом просто для каждой лексемы ищете её в массиве - есть-ли такая.
Массив - это набор хешей (ну или просто CRC32) для всех возможных команд. Тогда для каждой лексемы достаточно одного прохода поиска по массиву 32-битных слов.
Да и поиск лучше делать по ходу выделения лексем. Так проще контролировать правильность синтаксиса всей строки.

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

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

вот проект. решает аналогичную задачу. может пригодится.

Ввод может быть как человеком, так и внешним устр-вом. Как пример я привел GSM-модуль: можно ручками через терминал писать ему команды, а можно выстреливать их из контроллера. При этом последовательность команд будет разной, кол-во в общем-то тоже (0xOD выступает в качестве разделителя и флага одновременно).
C CRC32 интересно, тоже думал в этом направлении. Наверно, это наиболее быстрый вариант (считать CRC32 для первого слова, искать в массиве команд. Потом CRC второго слова - искать в массиве, и так, пока не наткнулся на подходящее. Разобрал команду - пошел дальше).

Может упростить задачу?
Писать примерно так : "~ включить_канал:1;"
где "~" - стартовый байт
"включить_канал" - команда
":" признак что потом идёт число
";" признак конца пачки
команду собирать побайтно в массив и сравнивать через strcmp .
IO("~ включить_канал:1;",19);

Спасибо, пойду разбираться.

Вам подойдет поиск по Регулярным Выражениям. Из всех ваших команд делается 1 регулярное выражение, из которого строится конечный автомат. Он (автомат) запускается на входной поток символов и выдает все совпадения за 1 проход над входной строкой (на лету)

Если вас устроит готовый парсер можете посмотреть в сторону flex - он генерирует готовый автомат

Ну сейчас примерно так и делается. Сначала я ищу команду "включить" потом номер канала, потом разделитель. Просто самих команд достаточно много, приходится по много раз заниматься поиском возможной команды по всей строке. Сама команда состоит из 1 слова, номера канала, уровень сигнала и т.п. - это параметры, разбираемые после обнаружения команды.

За пример спасибо.