Минимализм, текстовый парсинг и классификатор на оперативных шаблонах

в 20:49, , рубрики: C, c; c++; обработка текстов;, c++, высокая производительность, поисковые технологии, Семантика, метки:

Как часто нам приходится сталкиваться с обработкой текстовых потоков в реальном времени? Как минимум при каждой загрузке файлов инициализации или конфигурации и тому подобных параметрических данных. Хорошо, когда его содержимое сводится к формату «param = value» и можно воспользоваться стандартными инструментами нарезки. Но что если по ходу разработки программы возникла необходимость усложнить тексты до работы со ссылками? Или обрабатывать условия на этапе чтения? Более того реализовать ветвления? В такой ситуации обычно на скорую руку пишется парсер, занимающий первоначально некоторое количество строчек кода. Который однако со временем разрастается, начинает ветвиться и в конечном итоге приводит к самоповторению, либо заходит в самоисключающий тупик. Именно в этот момент и появляется в голове мысль, что вся суть смысловой разбивки текста сводится к определенному количеству шаблонных операций, зависимых от контекста. И все что требуется для обработки текстов любой сложности — это абстрактный обработчик шаблонов, а не сложносочиненный парсер с детальным описанием всех возникающих условий.

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

Шаблоны представляют собой группы данных, подразумевающих ассоциированный контекст и делятся на подгруппы, описывающие все принадлежащие элементы. Каждый элемент представляет собой конкретный символ и содержит до 5 модификаторов, влияющих на обработку: 1-код символа, 2-тип данных текущего символа, 3-модификатор изменения предыдущего типа данных, 4-изменение профиля, 5-условие изменения текущего типа данных, в зависимости от предыдущего.

Настройка шаблонов и исходных данных
//глобальные структуры и параметры
INT64 splCutType = 0;	//тип данных выделенного отрезка
INT64 splGlyphType = 0;	//тип разрабатываемого знака
INT64 splLastType = 0;	//тип предыдущего знака
INT64 splProfile = 0;	//текущий загруженный шаблон
INT64 splitProfiles[7][256][6];

//типы данных
INT64 splTrash = 1;
INT64 splString = 2;
INT64 splDigits = 3;
INT64 splWords = 4;
INT64 splKey = 5;

//структура контекстных шаблонов
INT64 spCode = 1;	//связанный char-code
INT64 spPrefix = 2;	//изменение текущего типа данных
INT64 spPostfix = 3;	//изменение предыдущего типа данных
INT64 spSwitch = 4;	//переключение шаблона
INT64 spCntxCond = 5;	//контекстные условия переключения шаблона


void splitSet(void)	//настройка контекстных шаблонов
{
	// 1.общий
	//заполнение значений по умолчанию. остальные ячейки заполняются под номерами, соответствующими char-кодам символов.
	for (int i = 1; i < 256; i++)
		splitProfiles[1][i][2] = splWords;
	splitProfiles[1][(unsigned char)('0')][spCode]		= (unsigned char)('0');
	splitProfiles[1][(unsigned char)('0')][spPrefix]	= splDigits;
	splitProfiles[1][(unsigned char)('0')][spCntxCond]	= splTrash;
	splitProfiles[1][(unsigned char)('1')][spCode]		= (unsigned char)('1');
	splitProfiles[1][(unsigned char)('1')][spPrefix]	= splDigits;
	splitProfiles[1][(unsigned char)('1')][spCntxCond]	= splTrash;
	splitProfiles[1][(unsigned char)('2')][spCode]		= (unsigned char)('2');
	splitProfiles[1][(unsigned char)('2')][spPrefix]	= splDigits;
	splitProfiles[1][(unsigned char)('2')][spCntxCond]	= splTrash;
	splitProfiles[1][(unsigned char)('3')][spCode]		= (unsigned char)('3');
	splitProfiles[1][(unsigned char)('3')][spPrefix]	= splDigits;
	splitProfiles[1][(unsigned char)('3')][spCntxCond]	= splTrash;
	splitProfiles[1][(unsigned char)('4')][spCode]		= (unsigned char)('4');
	splitProfiles[1][(unsigned char)('4')][spPrefix]	= splDigits;
	splitProfiles[1][(unsigned char)('4')][spCntxCond]	= splTrash;
	splitProfiles[1][(unsigned char)('5')][spCode]		= (unsigned char)('5');
	splitProfiles[1][(unsigned char)('5')][spPrefix]	= splDigits;
	splitProfiles[1][(unsigned char)('5')][spCntxCond]	= splTrash;
	splitProfiles[1][(unsigned char)('6')][spCode]		= (unsigned char)('6');
	splitProfiles[1][(unsigned char)('6')][spPrefix]	= splDigits;
	splitProfiles[1][(unsigned char)('6')][spCntxCond]	= splTrash;
	splitProfiles[1][(unsigned char)('7')][spCode]		= (unsigned char)('7');
	splitProfiles[1][(unsigned char)('7')][spPrefix]	= splDigits;
	splitProfiles[1][(unsigned char)('7')][spCntxCond]	= splTrash;
	splitProfiles[1][(unsigned char)('8')][spCode]		= (unsigned char)('8');
	splitProfiles[1][(unsigned char)('8')][spPrefix]	= splDigits;
	splitProfiles[1][(unsigned char)('8')][spCntxCond]	= splTrash;
	splitProfiles[1][(unsigned char)('9')][spCode]		= (unsigned char)('9');
	splitProfiles[1][(unsigned char)('9')][spPrefix]	= splDigits;
	splitProfiles[1][(unsigned char)('9')][spCntxCond]	= splTrash;
	splitProfiles[1][(unsigned char)('n')][spCode]		= (unsigned char)('n');
	splitProfiles[1][(unsigned char)('n')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)('	')][spCode]	= (unsigned char)('	');	//TAB
	splitProfiles[1][(unsigned char)('	')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)('/')][spCode]		= (unsigned char)('/');
	splitProfiles[1][(unsigned char)('/')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)('/')][spSwitch]	= 2;
	splitProfiles[1][(unsigned char)('[')][spCode]		= (unsigned char)('[');
	splitProfiles[1][(unsigned char)('[')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)('[')][spSwitch]	= 3;
	splitProfiles[1][(unsigned char)('"')][spCode]		= (unsigned char)('"');
	splitProfiles[1][(unsigned char)('"')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)('"')][spSwitch]	= 4;
	splitProfiles[1][(unsigned char)('$')][spCode]		= (unsigned char)('$');
	splitProfiles[1][(unsigned char)('$')][spPrefix]	= splKey;
	splitProfiles[1][(unsigned char)('$')][spSwitch]	= 6;
	splitProfiles[1][(unsigned char)(':')][spCode]		= (unsigned char)(':');
	splitProfiles[1][(unsigned char)(':')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)(',')][spCode]		= (unsigned char)(',');
	splitProfiles[1][(unsigned char)(',')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)('.')][spCode]		= (unsigned char)('.');
	splitProfiles[1][(unsigned char)('.')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)('=')][spCode]		= (unsigned char)('=');
	splitProfiles[1][(unsigned char)('=')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)(';')][spCode]		= (unsigned char)(';');
	splitProfiles[1][(unsigned char)(';')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)('+')][spCode]		= (unsigned char)('+');
	splitProfiles[1][(unsigned char)('+')][spPrefix]	= splKey;
	splitProfiles[1][(unsigned char)('&')][spCode]		= (unsigned char)('&');
	splitProfiles[1][(unsigned char)('&')][spPrefix]	= splKey;
	splitProfiles[1][(unsigned char)('(')][spCode]		= (unsigned char)('(');
	splitProfiles[1][(unsigned char)('(')][spPrefix]	= splTrash;
	splitProfiles[1][(unsigned char)('(')][spSwitch]	= 5;
	splitProfiles[1][(unsigned char)(' ')][spCode]		= (unsigned char)(' ');	//SPACE
	splitProfiles[1][(unsigned char)(' ')][spPrefix]	= splTrash;

	// 2.комментарий
	for (int i = 1; i < 256; i++)
		splitProfiles[2][i][2] = splTrash;
	splitProfiles[2][(unsigned char)('n')][spCode]		= (unsigned char)('n');
	splitProfiles[2][(unsigned char)('n')][spPrefix]	= splTrash;
	splitProfiles[2][(unsigned char)('n')][spSwitch]	= 1;
	splitProfiles[2][(unsigned char)('/')][spCode]		= (unsigned char)('/');
	splitProfiles[2][(unsigned char)('/')][spPrefix]	= splTrash;
	splitProfiles[2][(unsigned char)('/')][spSwitch]	= 1;

	// 3.массивный текст
	for (int i = 1; i < 256; i++)
		splitProfiles[3][i][2] = splString;
	splitProfiles[3][(unsigned char)(']')][spCode]		= (unsigned char)(']');
	splitProfiles[3][(unsigned char)(']')][spPrefix]	= splTrash;
	splitProfiles[3][(unsigned char)(']')][spSwitch]	= 1;

	// 4.цитата
	for (int i = 1; i < 256; i++)
		splitProfiles[4][i][2] = splString;
	splitProfiles[4][(unsigned char)('"')][spCode]		= (unsigned char)('"');
	splitProfiles[4][(unsigned char)('"')][spPrefix]	= splTrash;
	splitProfiles[4][(unsigned char)('"')][spSwitch]	= 1;

	// 5.функция
	for (int i = 1; i < 256; i++)
		splitProfiles[5][i][2] = splString;
	splitProfiles[5][(unsigned char)(')')][spCode]		= (unsigned char)(')');
	splitProfiles[5][(unsigned char)(')')][spPrefix]	= splTrash;
	splitProfiles[5][(unsigned char)(')')][spSwitch]	= 1;

	// 6.ключ
	for (int i = 1; i < 256; i++)
		splitProfiles[6][i][2] = splKey;
	splitProfiles[6][(unsigned char)(' ')][spCode]		= (unsigned char)(' '); //SPACE
	splitProfiles[6][(unsigned char)(' ')][spPrefix]	= splTrash;
	splitProfiles[6][(unsigned char)(' ')][spSwitch]	= 1;
}

Код обработчика
INT64 split(INT64 *strPtr)
{
	INT64 ret = 0;
	//разбор длится до окончания строки, пока не встретится нулевой символ
	while (*(char*)(*strPtr)) {
		//при отсутствии дополнительных условий в пункте spCntxCond, тип данных меняется на новый
		if (splitProfiles[splProfile][*(unsigned char*)(*strPtr)][spCntxCond] == 0 || splitProfiles[splProfile][*(unsigned char*)(*strPtr)][spCntxCond] == splGlyphType)
			splGlyphType = splitProfiles[splProfile][*(unsigned char*)(*strPtr)][spPrefix];	
		//изменение предыдущего типа данных при возникновении ключевых символов в строке
		if (splitProfiles[splProfile][*(unsigned char*)(*strPtr)][spPostfix] > 0)
			splLastType = splitProfiles[splProfile][*(unsigned char*)(*strPtr)][spPostfix];
		//изменение профиля
		if (splitProfiles[splProfile][*(unsigned char*)(*strPtr)][spSwitch] > 0)
			splProfile = splitProfiles[splProfile][*(unsigned char*)(*strPtr)][spSwitch];
		//при смене типа данных происходит выход из функции для последующей нарезки
		if (splGlyphType != splLastType) {
			//тип данных сохраняется для доступа к нему вызывающей функции
			splCutType = splLastType;
			//предыдущий тип данных перестраивается на новый отрезок
			splLastType = splGlyphType;
			ret = 1;
			goto finish;
		}
		//указатель увеличивается на единицу для движения по строке
		*strPtr += 1;
	}
	//в конце строки последний отрезок сохраняет свой тип данных, действий для следующего отрезка не производится
	splCutType = splGlyphType;
finish:
	//при выходе из функции указатель переводится либо на начало следующего отрезка, либо на нулевой символ конца строки
	*strPtr += 1;
	return ret;
}

Пример использования функционала

char *text = "тест "цитата" 123 /комментарий/ [большой текст] $команда";
INT64 textPtr = (INT64)text;
INT64 lastPos = textPtr;
INT64 length = 0;
//тип данных устанавливается по первому символу
splGlyphType = splLastType = splitProfiles[1][*(unsigned char*)textPtr][spPrefix];
//номер профиля данных по умолчанию
splProfile = 1;


while (split(&textPtr) != 0) {		//обработка завершится по окончанию строки
	length = textPtr - lastPos - 1;	//длина выделенного отрезка без крайнего символа (null-terminated, либо следующего отрезка)
	lastPos = textPtr - 1;		//счетчик последнего прочитанного символа модифицируется
	if (splCutType != splTrash) {	//если отрезок не содержит мусор, имеет смысл извлечь из него данные.
		//далее копирование отрезка из строки в отдельную строку, либо запуск собственных интерпретаторов.
	}
	else {
		//впрочем мусор также можно просмотреть или обработать
	}
}

Что выдаст нам процедура на каждом шаге цикла while?
1. 'тест' — 4 символа — splWords
2. ' "' — 2 символа — splTrash
3. 'цитата' — 6 символов — splString
4. '" ' — 2 символа — splTrash
5. '123' — 3 символа — splDigit
6. ' /комментарий/ [' — 16 символов — splTrash
7. 'большой текст' — 13 символов — splString
8. '] ' — 2 символа — splTrash
9. '$команда' — 8 символов — splKey

Автор: Tatuin

Источник

Поделиться новостью

* - обязательные к заполнению поля