Регулярные выражения и выражения благодарности Робу Пайку.

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

А что если написать свой движок регулярных выражений?

Итак, вспомним, что регулярные выражения — это по сути конечный автомат. Когда мы встречаем какой-то символ — автомат переходит в новое состояние (если это возможно). Например, для выражения ab(cd|ef)g получится такой автомат:

RegEx State Automata

Я не буду вдаваться в подробности о детерминированных и недетерминированных автоматах. Просто будем помнить, что само выражение описывает всевозможные состояния и связи между ними, а входная строка буква за буквой переключает состояния автомата. Здесь, например, в состоянии 2 если на вход поступит буква ‘d’ — перейдем в состояние 3, если буква ‘c’ — в состояние 4. Иногда нельзя будет сказать в какое состояние переходить не заглядывая наперёд строки.

Самый простой движок регулярных выражений

Существует великолепная книжка Роба Пайка и (кажется) Брайна Кернигана — The Practice Of Programming (TPOP). Там приводится код простейшего движка для регулярных выражений. Кому лень читать всю книгу — тут описан основной подход и приводятся те самые легендарные 30 строк кода.

Движок способен распознавать начало/конец строки и задавать wildcard — маску для множества одинаковых символов.
Гениальность этой реализации в рекурсивном подходе. Код получается очень лаконичный, а разница в скорости почти не заметна.

Извлекаем больше пользы

Я решил использовать этот код за основу, но получить чуть больше, а именно:

  • Узнавать где начинается соответствие и сколько символов строки попадает под выражение
  • Добавить специальные группы символом — ну хотя бы \d для цифр и \s для пробелов
  • Добавить квантификаторы (ну или как это назвать?) для нахождения 0 и больше вхождений («*»), 1 и больше («+»), 0 или 1 («?») и жадного оператора для 0 и больше («-» — как в Lua)

Попробуем вложиться строчек эдак в 100.

Начинать будем так же — нам нужная единственная главная функция и функция, определяющая соответствие начала строки выражению — regex_match и regex_match_here соответственно:

int regex_match(const char *regex, char *s, int *len) {
	char *p = s;

	/* force match from the beginning of the string */
	if (regex[0] == '^') {
		return (regex_match_here(regex + 1, s, len) ? 0 : -1);
	}

	/* iterate the string to find matching position */
	do {
		*len = 0;
		if (regex_match_here(regex, p, len)) {
			return p - s;
		}
	} while (*p++ != '\0');

	return -1;
}

int regex_match_here(const char *regex, char *s, int *len) {
	// TODO
}

С regex_match все ясно, если «^» — проверяем начало строки, иначе — пляшем слева направо пока не найдем соответствие.

Самое главное находится в regex_match_here:

static int regex_match_here(const char *regex, char *s, int *len) {
	int c = regex[0];

	if (regex[0] == '\0') { /* end of regex = full match */
		return 1;
	} else if (regex[0] == '$' && regex[1] == '\0') { /* check end of string */
		return (*s == '\0');
	} else if (regex[0] == '\\' && regex[1] != '\0') { /* check escaped symbol */
		c = regex[1];
		if (c != '^' && c != '$' && c != '\\' && c != '+' && c != '*' && c != '-' && c != '?') {
			c = c | 0x100;
		}
		regex = regex + 1;
	}
	/* check for special operators *,+,?,- */
	if (regex[1] == '*' || regex[1] == '+' || regex[1] == '-' || regex[1] == '?') {
		return regex_match_quantity(regex[1], c, regex+2, s, len);
	} else if (*s != '\0' && regex_match_group(*s, c)) {
		*len = *len + 1;
		return regex_match_here(regex+1, s+1, len);
	}
	return 0;
}

Здесь проверяем состояние нашего неявного автомата:

  • если выражение закончилось (достигнуто конечное состояние) — вернуть 1, соответствие найдено
  • если в регулярном выражении дошли до последнего символа, и это — «$» (т.е. конец строки) — вернуть 1 если строка тоже закончилась.
  • если нашли «\» — экранирующий символ, но мы имеем дело с особой группой символов. Вообще, в обычном синтаксисе «\» играет две роли — для «\.», «\^», «\$», ‘\?’, ‘\*’, ‘\+’, ‘\-‘ он означает использовать просто символы «.», «^» и т.д. вместо из мета-значений («любой символ», «начало строки», «конец строки», …). Для остальных («\d», «\s», …) он означает использовать мета-значение («любая цифра», «любой пробельный символ», …). Договоримся, что значение выше 256 будут означать мета-символ, т.е. (‘d’|0x100) — это «любая цифра», а ‘d’ — буква ‘d’. Ах да, с точной («.») все будет наоборот. Ну и синтаксис.
  • итак, символ или группу мы считали. Теперь проверяем операторы «+», «*», «?» и «-«. Для них — особая функция проверки regex_match_quantity, а в остальных случаях — просто проверяем попадает ли следующий символ строки в группу и идёт дальше (рекурсивно).

Функция проверки попадания символа в группу простая и легко расширяемая:

static int regex_match_group(int c, int group) {
	if ((group & 0xff) == '.') group ^= 0x100;
	if (group < 0x100) { /* a single char */
		return c == group;
	}
	/* a meta char, like \d, ... */
	switch (group & 0xff) {
		case 'd': return isdigit(c);
		case 's': return isspace(c);
		case 'D': return !isdigit(c);
		case 'S': return !isspace(c);
		case '.': return 1;
	}
	return 0;
}

В этой функции мы смотрим — для простых символов кроме точки — просто сравниваем. Для остальных — проверяем группы. С точкой — все наоборот. Я использую функции из ctypes.h, но для простых групп можно и без них обойтись.

Ну и самый кошмарный код в функции regex_match_quantity:

static int regex_match_quantity(int quant, int c, const char *regex, char *s, int *len) {
	if (quant == '?') {
		if (regex_match_group(*s, c)) {
			*len = *len + 1;
			s = s + 1;
		}
		return regex_match_here(regex, s, len);
	}

	if (quant == '+' || quant == '*') { /* match as much as possible */
		char *p;
		for (p = s; *p != '\0' && regex_match_group(*p, c); p++) {
			*len = *len + 1;
		}
		if (quant == '+' && p == s) {
			return 0;
		}
		do {
			if (regex_match_here(regex, p, len)) {
				return 1;
			}
			*len = *len - 1;
		} while (p-- > s);
	} else if (quant == '-') { /* match as little as possible */
		do {
			if (regex_match_here(regex, s, len)) {
				return 1;
			}
			*len = *len + 1;
		} while (*s != '\0' && regex_match_group(*s++, c));
	}
	return 0;
}

Ну для «?» всегда возвращаем 1, но если символ действительно входит в группу — увеличиваем длину совпадающего региона на 1.

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

Для нежадного оператора «-» просто идёт слева направо пока не совпадет остаток строки с остатком выражения.

Вот и все. У меня получилось 98 строк. Ни одной зависимости. Из libc — только ctype.h, т.е. при особом умении соберется даже каким-нибудь ущербным SmallC. Также никаких особых плюшек С я не использовал, код должен быть переносим и на другие языки, на тот же Forth.

Весь код — как всегда на bitbucket.
Там же и горстка тестов чтобы быть уверенным что все работает как надо.

Вместо выводов

Спасибо Робу Пайку за элегантный и полезный код. Я понимаю, что для серьезных задач такие микро-регекспы не годятся, но для чего-нибудь простенького в embedded — вполне. Тем более лично я считаю, что не стоит делать и регулярных выражений тьюирнг-полный мега-язык, уж лучше бы был способ комбинирования простых регулярных выражений с примесью некоторой простой логики типа условний-циклов.

Здесь кстати тоже стоит отметить работу Роба Пайка о структурных регулярных выражениях. И его текстовый редактор Sam красочный пример их простоты и мощности. Спасибо, Роб.

P.S. Отдельно спасибо, Роб, за язык Go 🙂

Реклама

One comment on “Регулярные выражения и выражения благодарности Робу Пайку.

  1. Anonymous:

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

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s