LINUX.ORG.RU
Форум — Development  

Конечный автомат

 


0

2

Здравствуйте.

Есть задача - распарсить строку «s x1 y1\nm x2 y2\n» разложив x1, y1, x2, y2 по отдельным массивам...

  #define VARBUF 8
  char mystr[] = "s x1 y1\nm x2 y2\n";
  char *str = mystr;
  char var1[VARBUF] = {0,};
  char var2[VARBUF] = {0,};
  char var3[VARBUF] = {0,};
  char var4[VARBUF] = {0,};
  int flag = 1, i = 0, i2 = 0;
  int str_len = (int)strlen(mystr);
  
  for(; i < str_len; i++)
  {
	  if(flag == 1 && *str == ' ')
	  {                               
		  flag = 2;
		  str++;
		  i++;
		  i2 = 0;
		  for(; i < str_len && i2 < VARBUF - 1; i++, i2++, str++)
		  {
			  var1[i2] = *str;
			  if(*str == ' ') 
			  {
				  var1[i2] = 0;
				  break;
			  }
		  }
	  }
	  
	  if(flag == 2 && *str == ' ')
	  {                               
		  flag = 3;
		  str++;
		  i++;
		  i2 = 0;
		  for(; i < str_len && i2 < VARBUF - 1; i++, i2++, str++)
		  {
			  var2[i2] = *str;
			  if(*str == '\n') 
			  {
				  var2[i2] = 0;
				  break;
			  }
		  }
	  }	  
 
	  if(flag == 3 && *str == ' ')
	  {                              
		  flag = 4;
		  str++;
		  i++;
		  i2 = 0;
		  for(; i < str_len && i2 < VARBUF - 1; i++, i2++, str++)
		  {
			  var3[i2] = *str;
			  if(*str == ' ') 
			  {
				  var3[i2] = 0;
				  break;
			  }
		  }
	  }		  
	  
	  if(flag == 4 && *str == ' ')
	  {                              
		  flag = 0;
		  str++;
		  i++;
		  i2 = 0;
		  for(; i < str_len && i2 < VARBUF - 1; i++, i2++, str++)
		  {
			  var4[i2] = *str;
			  if(*str == '\n') 
			  {
				  var4[i2] = 0;
				  break;
			  }
		  }
	  }	
	  
	  str++;  
}

Можно ли назвать представленный выше код конечным автоматом?

★
← bash Передача переменной в curl
Восклицательный знак после автокоманд →
  1 2 →
Ответ на: комментарий от stD

Если не затруднит, поясните подробнее в чем ошибка с «чтение будет за str_end» ?

Вместо кода: 

while (*str != '\n' && str < str_end) {
Должно быть: 
while (str < str_end && *str != '\n') {
Затупил когда писал. Сперва проверка на выход за границы, а после проверка на значение.
Кстати вариант variantA_unsafe не проверял сколько тратит циклов?

V1KT0P ★★
()
Ответ на: комментарий от V1KT0P

То есть, имеется в виду, что если выйдет за границы, то там тоже может быть искомый символ? В этом опасность?

stD ★
() автор топика
Последнее исправление: stD (всего исправлений: 1)
Ответ на: комментарий от stD

То есть, имеется в виду, что если выйдет за границы, то там тоже может быть искомый символ?

Смысл в том что нельзя читать из-за границы, нет гарантии что там вообще есть память или можно ее читать. На x86 можно получить «Segmentation fault» и уронить всю программу.

V1KT0P ★★
()
Ответ на: комментарий от V1KT0P

Хм, поменял местами str < str_end && *str != '\n' в variantA и кол-во тактов увеличилось с 244 до 286.

stD ★
() автор топика

Это скорее не конечный автомат, а конченная копипаста. :)

Sorcerer ★★★★★
()

Не надо употреблять термины только потому, что красиво звучат. У конечного автомата есть вполне определенное формальное определение. Этот код никакого отношения к нему не имеет.

anonymous
()
Ответ на: комментарий от stD

Вариант покороче. Однопроходной.

#include <stdio.h>
#include <stdlib.h>
#define VARBUF 8

void scanxy(char * str,char *v1,char *v2,char *v3, char*v4)
{
    enum{xs,ys,xm,ym,s,m,c};
    for (int i=0,pta=c,ptb=c; str[i]!='\0'; i++)
    {
        (str[i]=='s')?pta=s:0;
        (str[i]=='m')?pta=m:0;
        (str[i]=='y')?(pta==s)?ptb=ys:(ptb=ym):0;
        (str[i]=='x')?(pta==s)?ptb=xs:(ptb=xm):0;
        (str[i]==' '||str[i]=='\n')?ptb=c:0;
        (ptb==xs)?v1[0]=str[i],v1++:0;
        (ptb==ys)?v2[0]=str[i],v2++:0;
        (ptb==xm)?v3[0]=str[i],v3++:0;
        (ptb==ym)?v4[0]=str[i],v4++:0;
    }
}
int main(int argc, char *argv[])
{
    char data[] = "s x1 y1\nm x2 y2\n";
    char v1[VARBUF]={0};
    char v2[VARBUF]={0};
    char v3[VARBUF]={0};
    char v4[VARBUF]={0};
    scanxy(data,v1,v2,v3,v4);
    printf("[%s] [%s] [%s] [%s]\n",v1,v2,v3,v4);
    return 0;
}
Deleted
()
Ответ на: комментарий от V1KT0P

Тогда уже: 

void variantA_unsafe()
{
#define VARBUF 8
    const char *inp = "s x1 y1\nm x2 y2\n";
    char var1[VARBUF], var2[VARBUF], var3[VARBUF], var4[VARBUF], *outp;

    while (*inp != ' ') ++inp; // skip "s"
    while (*inp == ' ') ++inp; // skip spaces
    outp = var1;
    while (*inp != ' ') *outp++ = *inp++; // copy variable 1
    *outp = '\0';

    while (*inp == ' ') ++inp; // skip spaces
    outp = var2;
    while (*inp != '\n') *outp++ = *inp++; // copy variable 2
    *outp = '\0';

    while (*inp != ' ') ++inp; // skip "\nm"
    while (*inp == ' ') ++inp; // skip spaces
    outp = var3;
    while (*inp != ' ') *outp++ = *inp++; // copy variable 3
    *outp = '\0';

    while (*inp == ' ') ++inp; // skip spaces
    outp = var4;
    while (*inp != '\n') *outp++ = *inp++; // copy variable 3
    *outp = '\0';

    printf("[%s] [%s] [%s] [%s]\n", var1, var2, var3, var4);
}

Или, если формат строки действительно гарантируется, вплоть до количества пробелов: 

void variantA_realunsafe()
{
#define VARBUF 8
    const char *inp = "s x1 y1\nm x2 y2\n";
    char var1[VARBUF], var2[VARBUF], var3[VARBUF], var4[VARBUF], *outp;
    
#define SKIP_AND_COPY_TO(OFFSET, TOVAR, ENDCHAR) \
      inp += OFFSET; \
      outp = TOVAR; \
      while (*inp != ENDCHAR) *outp++ = *inp++; \
      *outp = '\0';

    SKIP_AND_COPY_TO(2, var1, ' ');  // skip "s " and copy variable 1
    SKIP_AND_COPY_TO(1, var2, '\n'); // skip " " and copy variable 2
    SKIP_AND_COPY_TO(3, var3, ' ');  // skip "\nm " and copy variable 3
    SKIP_AND_COPY_TO(1, var4, '\n'); // skip " " and copy variable 4

#undef SKIP_AND_COPY_TO

    printf("[%s] [%s] [%s] [%s]\n", var1, var2, var3, var4);
}

Думаю, это уже не победить.

anonymous
()
Ответ на: комментарий от stD

Не забудьте включить компилятору оптимизацию по скорости: опция -O3 или что там для ваших контроллеров есть.

anonymous
()
Ответ на: комментарий от anonymous

или что там для ваших контроллеров есть

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

Оптимизация по размеру -Оs.

stD ★
() автор топика
Последнее исправление: stD (всего исправлений: 3)

Еще есть re2c - загугли, генератор лексеров в виде конечного автомата на основе описания в виде regexp'ов, на выходе код на C.

anymouse ★
()
Ответ на: комментарий от stD

Оптимизация по размеру -Оs.

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

V1KT0P ★★
()
Ответ на: комментарий от stD

С каким кодом сгенерить файлик, с Вашим или моим?

Сгенерируй с вариантом «variantA_unsafe», он хоть и не безопасный но зато должен быть максимально приближен к предельной скорости. Кстати сколько тактов на этом варианте?

V1KT0P ★★
()
Ответ на: комментарий от V1KT0P

Чего-то не получается, файл создаётся но в нем не слова про нужный код. Буду ковыряться.

stD ★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
  1 2 →
← bash Передача переменной в curl
Development
Восклицательный знак после автокоманд →