Строковый автомат. Реализация для микроконтроллера PIC18

В статье описан способ обработки символьных массивов автоматом с конечным числом состояний. Приведена реализация на языке Си для микроконтроллеров PIC 18 серии. (среда разработки - MPLab + HiTech C)

автор: Астраханцев Дмитрий
информация: www.robosoft.info
опубликовано: 25.05.2007

Введение

Часто и повсеместно возникает необходимость обработки строк различными контрольно-управляющими устройствами. Нельзя утверждать, что бинарные форматы данных ушли в прошлое, однако человеку куда более понятными являются именно строковые форматы представления информации. Персональные компьютеры уже давно оперируют получающими все большее распространение и более «понятными» строковыми форматами: XML, HTML и пр.

Не исключением являются и микроконтроллеры, которые все чаще должны обеспечивать обмен и обработку информации строкового формата. Прогресс не стоит на месте, и если в 16 серии микроконтроллеров фирмы Microchip обработка строк была довольно трудоемка, то в 18 серии несложную обработку строк можно сделать как на ассемблере, так и используя различные строковые функции Си компиляторов.

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

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

Алгоритм

Алгоритм функционирования автомата можно условно разделить на 3и части:

Инициализация автомата
Анализ поступающих строк и изменение состояния автомата
Чтение внутреннего состояния автомата

Рассмотрим перечисленные пункты подробней:

Инициализация

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

После выполнения инициализации автомат будет настроен на прием/передачу строковых выражений. Теоретически, шаблоны можно устанавливать и в течение работы программы, т.е. инициализировать внутреннее состояние при приходе новой (неизвестной) строки, но данный алгоритм здесь не будет рассматриваться, т.к. его довольно трудно реализовать стандартными средствами разработки для PIC18.

Анализ поступающих строк и изменение состояния автомата

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

Чтение внутреннего состояния автомата

Чтение состояния можно предусмотреть тремя различными способами:

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

Реализация

Приведенный код написан для среды MPLab и компилятора Си HiTech.

Секция описания переменных и констант:

#include <pic18.h>;
#include <string.h>;

//недействительный индекс
#define NOT_MATCH_INDEX 255

//количество используемых шаблонов
#define PATTERNS_COUNT 2

//количество используемых переменных
#define VALUES_COUNT 19

//максимальное количество переменных в шаблоне
#define MAX_VALUES_IN_PATTERN 14

//максимальная длина имени строки
#define STRING_NAME_LENGTH 5

//максимальная длина значения строки
#define STRING_VALUE_LENGTH 10

//шаблоны
const char * const patterns[] =
{          
           "$GPGGA,time,lon,lonSN,lat,latWE,fact,sat,HDOP,alt,units,xz1,xz2,xz3,chsum",
           "$GPRMC,time,wrn,lon,lonSN,lat,latWE,spd,dirct,date,mvar,mvard,chsum"
};

Функции инициализации автомата:

//добавление переменной, описывающей внутреннее состояние автомата
void AddNewValue(far char * name, far unsigned char * nameNum, char patternNum)
{
   char indexValue; //индекс добавляемой переменной
   char k;
   char count;
   char * str0;
   char * str1;

   indexValue = NOT_MATCH_INDEX;
   count = *nameNum;
   if(count>=VALUES_COUNT)
   count = VALUES_COUNT-1;
  
   //анализ присутствия в списке имен только что добавленной строки
   //если такая строка уже существует в списке - уменьшаем счетчик имен на 1
   //т.е. по сути перезаписываем (игнорируем) дубль
   for(k=0; k<count; k++)
   {
       str0 = (char *) names[k];
       str1 = (char *) name;
       if(strcmp(str0, str1)==0)
       {

          //переменная встречалась ранее - нас интересует старый индекс
          indexValue = k; 
          break;
       }
   }
    
   if(indexValue==NOT_MATCH_INDEX)
   {
       if(*nameNum<VALUES_COUNT)
       {
          indexValue = *nameNum;
          str0 = (char *) names[*nameNum]; //от
          str1 = (char *) name;            //до
          strcpy(str0, str1);
          *nameNum = (*nameNum) + 1;
       }
   }
   
    memset(name, 0, STRING_NAME_LENGTH);
  
    //добавляем индекс шаблона, в котором встречается переменная
    for(k=0; k<MAX_VALUES_IN_PATTERN; k++)
    {
        if(values_num[patternNum][k]==NOT_MATCH_INDEX)
        {
            values_num[patternNum][k] = indexValue;
            return;
        }
    }
}


//Инициализация автомата
void InitializeAutomate()
{
    unsigned char nameNum=0;  //указатель на найденное имя
    unsigned char i; //индексная переменная - индексатор номера шаблона
    unsigned char tokenNum;
    unsigned char j; //индексная переменная - индексатор номера символа в шаблоне
    const char * pattern; //указатель на текущий шаблон
    int patternLength; //длина текущего шаблона
    char charIndex; //индекс символа в строке - имени переменной
    char name[STRING_NAME_LENGTH]; //переменная для хранения временного имени (добавляемой переменной)

 

    //Инициализация массива:
    //номера переменных по номерам шаблонов (для быстрого поиска)
    for(i=0; i<PATTERNS_COUNT; i++)
    {
        for(j=0; j<MAX_VALUES_IN_PATTERN; j++)
        {
            values_num[i][j] = NOT_MATCH_INDEX; //недействительное значение
        }
    }

    //ищем все переменные и инициализирем массив их имен:
    charIndex = 0;
    for(i=0; i|<PATTERNS_COUNT; i++)
    {
        tokenNum = 0; // номер текущего разделителя (все, что до первого разделителя - имя шаблона)
        if(i>0)
        {
            //добавляем новую переменную при переходе на след шаблон
            AddNewValue(name, &nameNum, i-1);
            charIndex = 0;
        }
 
       //перебираем все символы в шаблоне:
       pattern = (const char *) patterns[i];
       patternLength = strlen(pattern);
       for(j=0; j<patternLength; j++)
       {
           if(*pattern==token)
           {
               if(tokenNum>0)
               {
                   //добавляем новую переменную
                   //при переходе на новый разделитель
                   AddNewValue(name, &nameNum, i);
                   charIndex = 0;
               }
               tokenNum++;
               pattern++;
               continue;
           }

           if(tokenNum>0)
           {
               //добавляем новый символ в имя переменной
               name[charIndex] = *pattern;
               charIndex++;
           }
       }

       pattern++;
   }
   AddNewValue(name, &nameNum, PATTERNS_COUNT-1);
}

Function of condition state setting (strings analyze function):

//поступление новой строки, к-рая изменяет внутреннее состояние автомата
//если она соответствует какому-либо известному шаблону
unsigned char NewSentence(far char * sentence)
{
   char i; //индексатор индекса шаблона
   char j; //индексатор индекса символа в шаблоне
   const char * pattern; //указатель на текущий шаблон
   int patternLength; //длина текущего шаблона
   far char * sentenceTemp; //указатель на принятую строку
   int sentenceLength; //указатель на принятую строку
   char indexToken;
   char valueNumNum; //индекс значения индекса переменной в массиве ссылок values_num[]
   far char * value; //ссылка на значение переменной

   sentenceTemp = (far char *) sentence;
  
   for(i=0; i<PATTERNS_COUNT; i++)
   {
       //проверка имени шаблона:
       //перебор всех символов в шаблоне, до первого разделителя
       indexToken = NOT_MATCH_INDEX;

       pattern = (const char *) patterns[i];
       patternLength = strlen(pattern);
       for(j=0; j<patternLength; j++)
       {
           if(*pattern==token)
           {
               //встретился разделитель - выходим из анализатора
               indexToken = j;
               break;
           }
           if(*pattern!=*sentenceTemp)
           {
               //equal=false;
               break;
           }
           pattern++;
           sentenceTemp++;
       }
       if(indexToken>0)
       {
           //анализируем искомый шаблон:
           sentenceTemp = (far char *) sentence;
           sentenceLength = strlen(sentenceTemp);
           sentenceTemp = sentenceTemp + indexToken + 1;

           valueNumNum = 0; //индекс значения индекса переменной в массиве ссылок values_num[]
           value = (far char *) values[values_num[i][valueNumNum]];
           memset(value, 0, STRING_VALUE_LENGTH); //обнуление значения переменной
    
           for(j=indexToken+1; j<sentenceLength; j++)
           {
               if(*sentenceTemp==token)
               {
                   valueNumNum++;
                   value = (far char *) values[values_num[i][valueNumNum]];
                   memset(value, 0, STRING_VALUE_LENGTH); //обнуление значения переменной
               }
               else
               {
                   *value = *sentenceTemp;
                   value++;
               }
               sentenceTemp++;
           }
           return 1; //изменили значения переменных в соответствии с шаблоном
       }
   }
   return 0; //ни одна переменная не была изменена
}

Function of reading of internal states of the parser:

//возвращает ссылку на значение переменной по ее номеру
far char * GetValueByNum(char num)
{
    return (far char *) values[num];
}

 

//возвращает ссылку на значение переменной по ее имени
far char * GetValueByName(far char * nameRequested)
{
    char i;
    far char * name;

    for(i=0; i<VALUES_COUNT; i++)
    {
        name = (far char *) names[i];
        if(strcmp(nameRequested, name)==0)
        {
            return (far char *) values[i];
        }
    }
    return 0; //переменная не найдена
}

Пример использования:

char buffer[] = "$GPGGA,092204.999,4250.5589,S,14718.5084,E,1,04,24.4,19.7,M,,,,0000*1F";
far char * value = "N/A";
InitializeAutomate();
NewSentence(buffer);
value = GetValueByNum(0);
value = GetValueByName("lon");

Резюме

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

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

Литература:

Майкл Предко. Справочник по PIC-микроконтроллерам. - Мск. ДМК, 2006.
Техническая документация ANSI C.
Техническая документация Microchip PIC18