Начало
Учебные материалы
Регулярные выражения
Области применения и реализация
Регулярные выражения (RE) могут использоваться для
- описания входных данных – формальное определение формата входных данных в спецификации, проверка корректности, генерация случайных тестовых данных, как соответствующих спецификации, так и содержащих ошибки;
- обработки текста – поиск информации, выделение частей этой информации, преобразование в новую форму;
- лексического анализа – разбиение текста на смысловые единицы (лексемы).
RE были придуманы как одна из форм описания регулярных языков. Распознавание цепочек текста на регулярном языке требует линейное время (для других классов языков требуется полиномиальное или экспоненциальное время) и выполняется с помощью конечного автомата. Работа такого автомата полностью определяется номером состояния и таблицей перехода вида (текущее состояние, текущий символ)->новое состояние.
Например, поиск подстроки `S` в тексте `T` с помощью алгоритма Кнута-Морриса-Пратта работает за время O(|S|+|T|) и его можно описать в терминах конечного автомата, таблицей перехода для которого служит префикс-функция для искомой подстроки. Алгоритм Ахо-Карасик строит автомат в явном виде и допускает одновременный поиск нескольких подстрок.
Построение таблицы переходов для автомата вручную является нетривиальной задачей, но, к счастью, существуют алгоритмы для преобразования регулярных выражений в конечный автомат.
Большинство реализаций RE (в языках Perl, PHP, C++, C#) используют рекурсивный перебор либо непосредственно по строке с RE, либо по эквивалентному ей графу, так как такой подход не требует затрат времени на создание автомата и памяти для его хранения. Но в результате обработка строк с помощью сложных RE с большим количеством альтернатив может выполняться за экспоненциальное время.
Небольшим плюсом от использования рекурсивного перебора является использование обратных ссылок на найденные ранее фрагменты текста (обратные ссылки нарушают регулярность языка и применение автоматов невозможно).
Поиск подстроки `S` в тексте `T` с помощью библиотеки RE2 выполняется за `O(|T|\ log|S|)` (здесь `log|S|` получается за счет поиска в таблице перехода), в то время как string::find и regex_search – за `O(|T|*|S|)`, при этом regex_search выполняется почти в 10 раз медленнее.
