Я думаю все слышали про регулярные выражения и знают зачем они нужны — по сути они позволяют узнать соответствует ли строка регулярному выражению, и если да — то какие именно участки строки соответствуют каким участкам выражения.
А что если написать свой движок регулярных выражений?
Итак, вспомним, что регулярные выражения — это по сути конечный автомат. Когда мы встречаем какой-то символ — автомат переходит в новое состояние (если это возможно). Например, для выражения ab(cd|ef)g получится такой автомат:
Я не буду вдаваться в подробности о детерминированных и недетерминированных автоматах. Просто будем помнить, что само выражение описывает всевозможные состояния и связи между ними, а входная строка буква за буквой переключает состояния автомата. Здесь, например, в состоянии 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 🙂
