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