Поиск команды в массиве данных Опции

[interrupt]

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

[Александр77]

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

[interrupt]

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

Switch on out 1, led 7 off.

А может так:

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

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

[CrimsonPig]

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

Switch on out 1, led 7 off.

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

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

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

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

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

[interrupt]

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

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

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

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

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

[gerber]

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

Код

't' -> "timer", "", "", "switch", NULL
'e' -> "", "led", NULL

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

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

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

[jcxz]

Такая задача. Контроллер принимает по UART некоторые данные в виде строк разной длины и содержания. Т.е. обычные текстовые строки. В этих строках может содержаться команда для контроллера, например: Switсh on out 7, input 1 disable, Led 11 on.

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

[Dog Pawlowa]

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

[jcxz]

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

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

[psL]

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

Прикрепленные файлы

 lwshell.zip ( 6.23 килобайт ) Кол-во скачиваний: 30

 

[interrupt]

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

[Lmx2315]

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

Прикрепленные файлы

 io.txt ( 7.5 килобайт ) Кол-во скачиваний: 21

 

[interrupt]

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

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

[XVR]

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

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

[interrupt]

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

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

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

[MrYuran]

AT команды

[CrimsonPig]

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

Да ладно... шаз мы будем рассказывать, что надо использовать Lexx, YACC, perfect hash, поиск по boyes moore, лексический анализ и прочие страшные вещи.. а потом выяснится, что у ТС команды сыпятся по 1200 8N1, обработка идет на двухядерном арме, и вся эта оптимизация с экономией тактов нафиг не нужна

Сообщение отредактировал CrimsonPig - Dec 4 2015, 10:27

[XVR]

а потом выяснится, что у ТС команды сыпятся по 1200 8N1, обработка идет на двухядерном арме, и вся эта оптимизация с экономией тактов нафиг не нужна

Видимо нужна, иначе бы ТС с этот вопрос не задавал

Да ладно... шаз мы будем рассказывать, что надо использовать Lexx, ... лексический анализ и прочие страшные вещи..

Они не такие страшные. Что бы воспользоваться flex'ом совсем не обязательно писать его (flex) самому - можно взять готовый А уж команды для flex'а написать в виде regexp'ов и вовсе простое дело

[CrimsonPig]

Видимо нужна, иначе бы ТС с этот вопрос не задавал

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

[interrupt]

За советы спасибо.

По поводу скорости. Обмен идет на 115200, обработка на STM32F100. Кроме этого контроллер загружен другими интерфейсами, обработкой прерываний, АЦП ну и т.п. Поэтому оптимизация времени обработки строки вроде бы актуальна.

Насчет AT команд. Ну примерно к этому и иду, но не понимаю, как их быстро разбирать. Ну вот есть у GSM-модуля огромный список этих команд. Контроллер выплевывает в него одну из них. Как он находит соответствие из всего перечня команд? Была у меня и такая мысль, делать группы команд, просто через обычный "if". Но получается очень громоздко и сложно при добавлении новых команд.

[Tarbal]

AT команды

Хороший подход. Все техзадания написаны и все стандартное.

[XVR]

Как он находит соответствие из всего перечня команд?

Trie дерево

[interrupt]

Trie дерево

Похоже, в точку. Только пока не нашел, как это реализовать. Буду копать.

[ДЕЙЛ]

Такая задача. Контроллер принимает по UART некоторые данные в виде строк разной длины и содержания. Т.е. обычные текстовые строки. В этих строках может содержаться команда для контроллера, например: Switсh on out 7, input 1 disable, Led 11 on.
............

Если известна максимальная длина команды, то в обработчике прерыввания можно сделать буфер FIFO той же длины и с каждым входящим байтом анализировать именно это окно, а не весь массив. В GSM-модеме в конце каждой команды следует байт 0x0D, по которому обработчик прерывания устанавливает флаг, что принята команда и FIFO буфер нужно скопировать для последующего неспешного анализа, чтобы следующие приходящие байты не помешали. Если крутится операционка, то прерывание по определённому символу выдаёт семафор соответствующей задаче. Как-то так мне это представляется.

[Harvester]

Похоже, в точку. Только пока не нашел, как это реализовать. Буду копать.

Там все гораздо проще - простой перебор
По первому символу после сочетания "AT" определяется класс команды, а потом в соответствующей таблице ищется требуемая запись

Сообщение отредактировал Harvester - Dec 19 2015, 13:32

Прикрепленные файлы

 80_VF696_1_B_AT_Command_Set_AMSS.pdf ( 1.02 мегабайт ) Кол-во скачиваний: 9

 

[SlavaV]

привет,

особо не вдавался в советы форумчан (прочитал только первый пост)

вот кусок кода с ATMega (обработка прерывания)
int Flag_Sign_1 = NO;
int Flag_Sgn_OK = NO;
int Flag_Addr_Comm = NO;
char AddrCommand;
char Data;

ISR(USART_RXC_vect)
{
unsigned char RX_Data;
RX_Data = UDR;
if (RX_Data == 0xAA && Flag_Sign_1 == NO) // первая фаза получения сигнатуры
{
Flag_Sign_1 = YES;
return;
}
if (RX_Data == 0x55 && Flag_Sign_1 == YES) // вторая(конечная) фаза получения сигнатуры
{
Flag_Sgn_OK = YES;
return;
}
if (Flag_Sgn_OK = YES) // сигнатура принята переходим к декодированию адреса - команд - данных
{
if (Flag_Addr_Comm == NO) // получаем адрес - команду
{
Flag_Addr_Comm = YES;
AddrCommand = RX_Data;
return;
}
else // получаем данные и отправляем на декодирование
{
Data = RX_Data;
Decoder(AddrCommand, Data);
Flag_Addr_Comm = NO;
}
}
Flag_Sign_1 = NO;
Flag_Sgn_OK = NO;
}

YES и NO определены через define

в принципе из кода всё ясно, но если есть какие вопросы отвечу.