Осторожно! Регекспы!

Часто ли вы используете регулярные выражения? Задумываетесь ли вы о том, на сколько оправдано их использование? Каковы альтернативы, каковы возможности и ограничения? Какова цена применения регекспа?

Я уже давно и часто замечаю, что люди (особенно из мира Perl) склонны мистифицировать регулярные выражения, наделяя их (в своём сознании) универсальными сверх-способностями.

Настоящей статьёй, я призываю одуматься задуматься.


Заблуждений два. И первое из них

«Регулярные выражения одинаково хорошо подходят для всех задач»

Однако в простых задачах регекспы оказываются неэффективны.

Я молчу про решения типа:

if (/./) { print "not empty\n"; }

очевидно оно менее эффективно, чем сравнение с пустой строкой:

if ($_ ne "") { print "not empty\n"; }

(кстати, эти два условия не совсем эквивалентны и это может таить подвохи, которые потом неожиданно вылезут в самый неподходящий момент).

Но бывают вопиюще-нерациональные решения (я не говорю, что они плохи, но они совершенно точно не рациональны).

Предлагаю простенький тест (определить, состоит ли предпоследняя десятка символов из одних «a»)

use Benchmark qw(:all);
my $a='a'x8000;
cmpthese(1_000_000, {
  'regex' => sub { $a=~/a{10}.{10}$/; },
  'noregex' => sub { substr($a, -20, 10) eq "aaaaaaaaaa"; },
});

Результат не требует комментариев:

             Rate    regex  noregex
regex       414/s       --    -100%
noregex 4413793/s 1065100%       --

<Лирическое отступление 1> Строго говоря, я выбрал для теста не случайный пример, но суть от этого не меняется; тем, кто интересуется оптимизацией регекспов рекомендую почитать Фридла «Регулярные выражения». </Лирическое отступление 1>

<Лирическое отступление 2> То, что ужасающе тормозное решение выглядит на перле более изящно, не должно вынуждать программистов использовать именно нерациональный подход к решению задачи. Возможно это обстоятельство должно заставить программиста задуматься: «а не выбрать ли язык на котором оптимальное решение выглядит компактно и красиво». Вот два кусочка кода на Python:

# вариант с регулярным выражением (тормозной)
import re
cre = re.compile(r'a{10}.{10}$')
if (cre.search(string)):
    # do something
# вариант с явным сравнением подстроки
if (string[-20:-10] == 'aaaaaaaaaa'):
    # do something

Но это уже совсем другая история. </Лирическое отступление 2>

А я перейду ко второму заблуждению:

«Регулярные выражения одинаково хорошо подходят для всех задач»

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

Года четыре назад, я был на собеседовании в одной крупной компании. Собеседование было вообще унылым чуть-более,-чем-полностью, но окончательно меня добил вопрос: «Напишите регулярное выражение, проверяющее правильность расстановки скобок.» (То есть отсутствие ситуаций "{<}>".)

Я сразу спросил, какая максимальная глубина вложения скобок допустима. Ответом было недоумение: «Любая!».

Очевидно, спрашивающий был абсолютно уверен, что такое выражение написать можно, что я его сейчас напишу, а он легко проверит.

Какое горькое заблуждение!

Если кто-то не успел сообразить — поясню.

Регулярное выражение описывает конечный автомат. Если вам требуется проконтролировать бесконечное количество скобок, то конечный автомат вам не поможет.

Заданный вопрос сродни вопросу: «Какова сумма углов треугольника, если его стороны равны 1, 2 и 50 сантиметров». Он выдаёт полное незнание предмета.

Хотя, строго говоря,

разработчики Perl ещё в 2004 году (если я не путаю) уверяли, что эта задача решаема. Для таких вещей придумана конструкция "(??{...})". Но работа этой конструкции очень часто приводит к безобразному падению Perl, обычно с вот таким сообщением:

panic: regfree data code 'Ъ' during global destruction.

(буква «Ъ» зависит от вашей кодировки :-))

Не удивительно, что эти дополнения не могут до сих пор избавиться от клейма экспериментальности. В PCRE эта возможность так и не включена.

На этом разработчики не остановились

и недавно был представлен новый механизм и синтаксис "(?1)". Механизм избавлен от массы корявостей, присущих старой версии.

Но на мой взгляд, рекурсивные регулярные выражения следовало сделать отдельно и не назвать их «регулрнями», ибо

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

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

Таким образом Perl, фактически, лишился регулярных выражений. Теперь программист не может быть уверен, что его «регулярное выражение» будет использовать конечный объём памяти. Или не зациклится. (Классические регулярные выражения удовлетворяют этим требованиям: они никогда не циклятся и требуют конечное количество памяти, которое определяются при компиляции выражения.) Я принадлежу к людям, которые считают эту доработку вредной, несущей неисчерпаемый заряд напастей и уязвимостей, и лишающей программиста доступа к простому и надёжному механизму регулярных выражений.

Но это снова совсем другая история. (И, к стати, тема рекурсии в регулярных выражениях уже была освещена на Хабре.)

А я лишь хотел сказать: «Осторожно! Регекспы!»

Всем спасибо и успехов!