Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Найти текстовые блоки разного типа в С.  [new]
jenya7
Member

Откуда:
Сообщений: 679
Мне нужно выделить из текста блоки разного типа. У каждого типа есть начальный маркер и конечный маркер. Сейчас есть два типа текстовых блоков - инструкция и тест. Соответственно маркеры выглядят так:
автор
SOI – start of instruction
EOI – end of instruction
SOT – start of test
EOT – end of test

И текст выглядит так:
автор
SOI
Line1
Line2
Line3
EOI
SOT
Line4
Line5
Line6
EOT

Мой топорный вариант выглядит так.
uint32_t Parse(char *text, char *buf, uint32_t *text_type, uint32_t *idx)
{
    uint32_t loc_idx = *idx;
    uint32_t txt_len = strlen(text);
    uint32_t start_pos = 0;
    uint32_t end_pos = 0;
    uint32_t start_found = 0;
    char *pchr;
    
    if (loc_idx >= txt_len) return PARSE_FAIL;
    
    //find SOI - start of instraction
    pchr = strstr(&text[loc_idx], START_OF_INSTRACTION);
    //if(pchr == NULL) return PARSE_FAIL;
    if (pchr != NULL)
    {
        start_pos = pchr - text + strlen(START_OF_INSTRACTION);
        start_found = 1;
    }
        
    //find EOI - end of instraction
    pchr = strstr(text, END_OF_INSTRACTION);
    //if(pchr == NULL) return PARSE_FAIL;  
    if (start_found && pchr != NULL)
    {
        end_pos = pchr - text;
        //copy the found block
        memcpy(buf, &text[start_pos], (end_pos - start_pos));
        buf[(end_pos - start_pos)] = '\0';
        *text_type = TXT_TYPE_INSTRACTION;
        *idx = end_pos + strlen(END_OF_INSTRACTION);
        return PARSE_SUCCESS;
    }
    
    //find SOT - start of test
    pchr = strstr(&text[loc_idx], START_OF_TEST);
    if (pchr != NULL)
    {
        start_pos = pchr - text + strlen(START_OF_TEST);
        start_found = 1;
    }
    
    //find EOT - end of test
    pchr = strstr(text, END_OF_TEST);
    if (start_found && pchr != NULL)
    {
        end_pos = pchr - text;
        //copy the found block
        memcpy(buf, &text[start_pos], (end_pos - start_pos)); 
        buf[(end_pos - start_pos)] = '\0';
        *text_type = TXT_TYPE_TEST;
        *idx = end_pos + strlen(END_OF_TEST);
        return PARSE_SUCCESS;
    }
       
    return PARSE_FAIL; 

И он работает если в тексте есть два блока.
Но если текст выглядит скажем так
автор
SOI
line1
line2
line3
EOI
SOT
line4
line5
line6
EOT
SOT
line7
line8
line9
EOT
SOI
line10
line11
line12
EOI


То весь мой парсер ломается. Как можно улучшить алгоритм?
11 янв 17, 09:35    [20092329]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 14386
Сформулируйте все условия, а не основные.

1) Что значит "выделить"? что хотите получить в итоге и в каком виде?
2) Есть ли гарантия, что любой текст, не являющийся маркером, находится в блоке? или бывает текст вне блоков (в т.ч. "пустые" строки)?
3) Есть ли гарантия согласованности разметки? или возможны пересечения блоков, незакрытые блоки и пр?
11 янв 17, 10:12    [20092415]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
Изопропил
Member

Откуда: @
Сообщений: 26726
jenya7
То весь мой парсер ломается. Как можно улучшить алгоритм?

1)расписать синтаксис в форме Бэкуса — Наура (BNF)
2)запрограммировать автомат (если неограниченной вложенности нет - то конечный)

нужно последовательно обрабатывать каждый символ(максимум заглядывая на один вперёд, но в этой задаче не придётся) и изменять состояние , а не пытаться сканировать строку вперёд
11 янв 17, 10:34    [20092473]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
jenya7
Member

Откуда:
Сообщений: 679
Akina
Сформулируйте все условия, а не основные.

1) Что значит "выделить"? что хотите получить в итоге и в каком виде?
2) Есть ли гарантия, что любой текст, не являющийся маркером, находится в блоке? или бывает текст вне блоков (в т.ч. "пустые" строки)?
3) Есть ли гарантия согласованности разметки? или возможны пересечения блоков, незакрытые блоки и пр?


Нужно скопировать текст в буфер между маркерами SOI-EOI , SOT-EOT.
скажем в HTML документе тоже есть блоки – header, paragraph, div.
11 янв 17, 10:50    [20092526]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
OoCc
Member

Откуда: с Кавказа
Сообщений: 1199
или использовать готовый регэкс автомат типа такого
11 янв 17, 10:53    [20092538]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
jenya7
Member

Откуда:
Сообщений: 679
OoCc
или использовать готовый регэкс автомат типа такого

у меня голый С.
11 янв 17, 11:14    [20092641]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 14386
jenya7, пожалуйста, отвечайте на те вопросы, которые Вам задают, а не на вопросы, которые Вы себе сами придумали.

jenya7
Нужно скопировать текст в буфер между маркерами SOI-EOI , SOT-EOT.

И что же должно быть помещено в буфер для показанного Вами текста?

jenya7
скажем в HTML документе тоже есть блоки – header, paragraph, div

Да ладно... а мужики-то не знают...
11 янв 17, 11:17    [20092664]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
Изопропил
Member

Откуда: @
Сообщений: 26726
jenya7
OoCc
или использовать готовый регэкс автомат типа такого

у меня голый С.

не в С или С++ проблема, а влезет ли в твой контроллер библиотека регулярок
11 янв 17, 11:17    [20092667]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 1406
jenya7
OoCc
или использовать готовый регэкс автомат типа такого

у меня голый С.

в этом нет проблем, большинство парсер-генераторов поддерживают С да и нагенерированный автомат выполняется элементарно
11 янв 17, 11:26    [20092721]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
Изопропил
Member

Откуда: @
Сообщений: 26726
kealon(Ruslan),

для этой задачи с конечным автоматом из трёх состояний и генерить ничего не надо
11 янв 17, 11:41    [20092835]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 1406
Изопропил,

не скажи, как раз таки эту задачу можно решить за один побайтный проход если иметь свой лексер-генератор и знать как он работает
11 янв 17, 11:56    [20092917]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
jenya7
Member

Откуда:
Сообщений: 679
ничего не понимаю. что происходит.
есть строка "SOI Happy EOI SOT New EOT SOT Year EOT SOI Folks EOI ".
блоки приходят в любом порядке. могут быть только SOI-EOI, SOI-EOI…. Или SOT-EOT, SOT-EOT….. или вперемежку SOI-EOI, SOT-EOT, SOI-EOI, SOT-EOT .
в результате нужно получить buf1 = Happy, buf2 = New, buf3 = Year, buf4 = Folks.
можно даже не одновременно а по очереди.
какие регексы, какие библиотеки. задача на несколько строк кода.
11 янв 17, 11:58    [20092933]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
Изопропил
Member

Откуда: @
Сообщений: 26726
kealon(Ruslan)
Изопропил,

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

можно решить естественно за один проход и без генератора )
11 янв 17, 12:04    [20092969]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
Изопропил
Member

Откуда: @
Сообщений: 26726
jenya7
задача на несколько строк кода.

правильно. нехрен искать какие то символы впереди

один цикл по исходной строке
11 янв 17, 12:05    [20092971]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 1406
jenya7
ничего не понимаю. что происходит.
есть строка "SOI Happy EOI SOT New EOT SOT Year EOT SOI Folks EOI ".
блоки приходят в любом порядке. могут быть только SOI-EOI, SOI-EOI…. Или SOT-EOT, SOT-EOT….. или вперемежку SOI-EOI, SOT-EOT, SOI-EOI, SOT-EOT .
в результате нужно получить buf1 = Happy, buf2 = New, buf3 = Year, buf4 = Folks.
можно даже не одновременно а по очереди.
какие регексы, какие библиотеки. задача на несколько строк кода.

ну если тебе нужно один раз найти, то никаких проблем
    //find SOI - start of instraction
    pchr1 = strstr(&text[loc_idx], START_OF_INSTRACTION);
   //find SOT - start of test
    pchr2 = strstr(&text[loc_idx], START_OF_TEST);

смотришь какой раньше и ищешь его завершение, очень топорно, но работать будет

а вот если требуется какое-то решение, которое обслуживает протокол приближенный к реальному времени, то извольте учить конечные автоматы
11 янв 17, 12:11    [20092994]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 1406
Изопропил
можно решить естественно за один проход и без генератора )

можно, но что-то не хочется
11 янв 17, 12:14    [20093021]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
jenya7
Member

Откуда:
Сообщений: 679
Изопропил,

ну в этом то и загвоздка. мы нашли начало, нашли конец, но стартовый маркер может встретиться где то еще в тексте. впрочем можно выставить флаг что стартовый маркер уже найден.
11 янв 17, 12:15    [20093030]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
jenya7
Member

Откуда:
Сообщений: 679
kealon(Ruslan)
jenya7
ничего не понимаю. что происходит.
есть строка "SOI Happy EOI SOT New EOT SOT Year EOT SOI Folks EOI ".
блоки приходят в любом порядке. могут быть только SOI-EOI, SOI-EOI…. Или SOT-EOT, SOT-EOT….. или вперемежку SOI-EOI, SOT-EOT, SOI-EOI, SOT-EOT .
в результате нужно получить buf1 = Happy, buf2 = New, buf3 = Year, buf4 = Folks.
можно даже не одновременно а по очереди.
какие регексы, какие библиотеки. задача на несколько строк кода.

ну если тебе нужно один раз найти, то никаких проблем
    //find SOI - start of instraction
    pchr1 = strstr(&text[loc_idx], START_OF_INSTRACTION);
   //find SOT - start of test
    pchr2 = strstr(&text[loc_idx], START_OF_TEST);

смотришь какой раньше и ищешь его завершение, очень топорно, но работать будет

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


я думал об этом. как то не очень элегантно.
11 янв 17, 12:17    [20093053]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 1406
jenya7
я думал об этом. как то не очень элегантно.
лесенка из побайтных switch как видимо прелагает Изопропил

ну а если и это не гоже
kealon(Ruslan)
.., то извольте учить конечные автоматы
11 янв 17, 12:22    [20093077]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
Изопропил
Member

Откуда: @
Сообщений: 26726
jenya7
ну в этом то и загвоздка. мы нашли начало, нашли конец

не надо ничего искать - вот в чём дело- достаточно принимать решение на основании текущего символа
11 янв 17, 13:15    [20093426]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
Изопропил
Member

Откуда: @
Сообщений: 26726
недостаточное знакомство разработчиков с конечными автоматами приводит к появлению микроконтроллерных устройств с диким поведением
11 янв 17, 13:18    [20093446]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
jenya7
Member

Откуда:
Сообщений: 679
так работает.
uint32_t Parse(char *text, char *buf, uint32_t *text_type, uint32_t *idx)
{
    uint32_t loc_idx = *idx;
    uint32_t txt_len = strlen(text);
    uint32_t start_pos = 0;
    uint32_t end_pos = 0;
    uint32_t start_found = 0;
    char *pchr_i, *pchr_t;
    
    if (loc_idx >= txt_len) return PARSE_FAIL;
    
    
    //find SOI - start of instraction
    pchr_i = strstr(&text[loc_idx], START_OF_INSTRACTION);
    //find SOT - start of test
    pchr_t = strstr(&text[loc_idx], START_OF_TEST);
    
    if ((pchr_i != NULL) && (pchr_t != NULL))
    {
        start_found = 1;
        
        //marker SOI found first
        if (pchr_i < pchr_t)
        {
            start_pos = pchr_i - text + strlen(START_OF_INSTRACTION);
            //find EOI - end of instraction
            pchr_i = strstr(&text[loc_idx], END_OF_INSTRACTION);
            if (start_found && pchr_i != NULL)
            {
                end_pos = pchr_i - text;
                //copy the found block
                memcpy(buf, &text[start_pos], (end_pos - start_pos));
                buf[(end_pos - start_pos)] = '\0';
                *text_type = TXT_TYPE_INSTRACTION;
                *idx = end_pos + strlen(END_OF_INSTRACTION);
                return PARSE_SUCCESS;
            }
        }
        else  //marker SOT found first
        {
            start_pos = pchr_t - text + strlen(START_OF_TEST);
            //find EOT - end of test
            pchr_t = strstr(&text[loc_idx], END_OF_TEST);
            if (start_found && pchr_t != NULL)
            {
                end_pos = pchr_t - text;
                //copy the found block
                memcpy(buf, &text[start_pos], (end_pos - start_pos)); 
                buf[(end_pos - start_pos)] = '\0';
                *text_type = TXT_TYPE_TEST;
                *idx = end_pos + strlen(END_OF_TEST);
                return PARSE_SUCCESS;
            }
        }
    }
    else
    {
        if (pchr_i != NULL)
        {
            start_found = 1;
          
            start_pos = pchr_i - text + strlen(START_OF_INSTRACTION);
            pchr_i = strstr(&text[loc_idx], END_OF_INSTRACTION);
            if (start_found && pchr_i != NULL)
            {
                end_pos = pchr_i - text;
                //copy the found block
                memcpy(buf, &text[start_pos], (end_pos - start_pos));
                buf[(end_pos - start_pos)] = '\0';
                *text_type = TXT_TYPE_INSTRACTION;
                *idx = end_pos + strlen(END_OF_INSTRACTION);
                return PARSE_SUCCESS;
            }
            
        }
        if (pchr_t != NULL)
        {
            start_found = 1;
            
            start_pos = pchr_t - text + strlen(START_OF_TEST);
            pchr_t = strstr(&text[loc_idx], END_OF_TEST);
            if (start_found && pchr_t != NULL)
            {
                end_pos = pchr_t - text;
                //copy the found block
                memcpy(buf, &text[start_pos], (end_pos - start_pos)); 
                buf[(end_pos - start_pos)] = '\0';
                *text_type = TXT_TYPE_TEST;
                *idx = end_pos + strlen(END_OF_TEST);
                return PARSE_SUCCESS;
            }
        }
        
    }
    
    return PARSE_FAIL; 
}

можно заинлайнить повторяющийся код. сейчас попробую сделать на state machine.
11 янв 17, 13:33    [20093513]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
jenya7
Member

Откуда:
Сообщений: 679
так на state machine.
uint32_t TASKER_Parse(char *text, char *buf, uint32_t *text_type, uint32_t *idx)
{
    uint32_t loc_idx = *idx;
    uint32_t txt_len = strlen(text);
    uint32_t start_pos = 0;
    uint32_t end_pos = 0;
    uint32_t start_found = 0;
    //char buf[128];
    char *pchr_i, *pchr_t;
    
    uint32_t state = IDLE;
    
    if (loc_idx >= txt_len) return PARSE_FAIL;
    
    while (state != ST_END)
    {
        switch (state)
        {
            case IDLE:
                //find SOI - start of instraction
                pchr_i = strstr(&text[loc_idx], START_OF_INSTRACTION);
                //find SOT - start of test
                pchr_t = strstr(&text[loc_idx], START_OF_TEST);
            
                if ((pchr_i != NULL) && (pchr_t != NULL))
                {
                    start_found = 1;
                    state = ST_BOUTH_FOUND;
                }
                else
                {
                    if (pchr_i != NULL)
                    {
                        start_found = 1;
                        state = ST_SOI_FOUND;
                    }
                    else if (pchr_t != NULL)
                    {
                        start_found = 1;
                        state = ST_SOT_FOUND;
                    }
                    else
                      state = ST_END;
                }
            break;
            case ST_BOUTH_FOUND:
                //marker SOI found first
                if (pchr_i < pchr_t)
                    state = ST_SOI_FOUND;
                else  //marker SOT found first
                    state = ST_SOT_FOUND;
            break;   
            case ST_SOI_FOUND:
                start_pos = pchr_i - text + strlen(START_OF_INSTRACTION);
                //find EOI - end of instraction
                pchr_i = strstr(&text[loc_idx], END_OF_INSTRACTION);
                if (start_found && pchr_i != NULL)
                {
                    end_pos = pchr_i - text;
                    //copy the found block
                    memcpy(buf, &text[start_pos], (end_pos - start_pos));
                    buf[(end_pos - start_pos)] = '\0';
                    *text_type = TXT_TYPE_INSTRACTION;
                    *idx = end_pos + strlen(END_OF_INSTRACTION);
                    return PARSE_SUCCESS;
                }
            break;
            case ST_SOT_FOUND:
                start_pos = pchr_t - text + strlen(START_OF_TEST);
                //find EOT - end of test
                pchr_t = strstr(&text[loc_idx], END_OF_TEST);
                if (start_found && pchr_t != NULL)
                {
                    end_pos = pchr_t - text;
                    //copy the found block
                    memcpy(buf, &text[start_pos], (end_pos - start_pos)); 
                    buf[(end_pos - start_pos)] = '\0';
                    *text_type = TXT_TYPE_TEST;
                    *idx = end_pos + strlen(END_OF_TEST);
                    return PARSE_SUCCESS;
                }
            break;      
        }
    }
    return PARSE_FAIL; 
}

наверно так все таки есть выигрыш и по speed и по size.
11 янв 17, 13:54    [20093636]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 1406
jenya7
так на state machine.
наверно так все таки есть выигрыш и по speed и по size.

не особо

ты только логику верхнего уровня загнал в автомат (и то вопрос)

самое плохое место на нижнем уровне
  //find SOI - start of instraction
                pchr_i = strstr(&text[loc_idx], START_OF_INSTRACTION);
                //find SOT - start of test
                pchr_t = strstr(&text[loc_idx], START_OF_TEST);
11 янв 17, 14:08    [20093713]     Ответить | Цитировать Сообщить модератору
 Re: Найти текстовые блоки разного типа в С.  [new]
Dima T
Member

Откуда:
Сообщений: 10157
Не понятно что должно происходить при нарушении порядка начал и концов, например
"SOI Happy SOT New EOT SOT Year EOI SOI Folks EOI ";

Сделал игнорирование таких некорректно оформленных блоков.
Еще у тебя никак не задается размер буфера, что чревато выходом за его пределы.
+ Исходник
// Возвращает указатель на конец найденного блока
const char* parse(const char* text, char* buf, size_t buf_size) {
	char type = 0;
	char* b = buf;
	size_t s = buf_size;
	const char* p = text;
	for(;*p != 0; p++) {
		if(p[0] == 'S' && p[1] == 'O' && (p[2] == 'I' || p[2] == 'T')) { // Проверка начала блока
			if (type != 0) { // Начало следующего блока без окончания текущего, начинаем сначала
				b = buf;
				s = buf_size;
			}
			type = p[2];
			p += 2;
		} else if(type) { // Пишем в буфер
			if (p[0] == 'E' && p[1] == 'O' && (p[2] == 'I' || p[2] == 'T')) { // Проверка конца блока
				if(type != p[2]) { // конец блока не того типа
					b = buf;
					s = buf_size;
					type = 0;
				} else {
					*b = 0;
					return p + 3;
				}
			} else if(s > 1) { // есть место в буфере
				*b = *p;
				s--;
				b++;
			}
		}
	}
	*b = 0;
	return NULL;
}

int main (void) {
	//const char* p = "SOI Happy EOISOT New EOT SOT Year EOT SOI Folks EOI ";
	const char* p = "SOI Happy SOT New EOT SOT Year EOI SOI Folks EOI ";
	char buf[4];
	while(p = parse(p, buf, 4)) {
		printf("*%s*\n", buf);
	}
	return 0;
}
11 янв 17, 14:14    [20093759]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Программирование Ответить