Регулярные выражения *

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

В общем, наверное, как и другой любой начинающий JavaScript прогрммист (2 года назад), мне хотелось все реализовать своими руками. Так возникло ужасающее очень быстрое регулярное выражение из 280 символов.

Немного истории

Приблизительно полтора года назад, я узнал о библиотеке yass, которая была самым быстрым инструментом для поиска DOM элементов в JavaScript по CSS селекторам (ссылка на тесты).
И тут у меня возник ужасный интерес. Я захотел придумать способ, который будет еще быстрее. В то время я как раз читал книгу «Регулярные выражения Библиотека программиста» второе издание от Дж. Фридла. И вот… Это было лето, я еще был студентом и у меня была масса времени. Работа закипела…

Часть 1: метасимволы внутри и вне символьных классов.

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

Вместо вступления

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

Что бывает, когда начинающий программист в первый раз узнает про регулярные выражения? Чаще всего первое знакомство с ними происходит методом «научного тыка», поскольку ни знаний в соотвествующей области, ни понимания «как это работает» обычно на данном этапе у человека нет. Почему так происходит?

Регулярное выражение для валидации номера телефона:

^((8|\+7)[\- ]?)?(\(?\d{3}\)?[\- ]?)?[\d\- ]{7,10}$

Ориентировано на российские мобильные + городские с кодом из 3 цифр (например, Москва).

Я видел множество проблем, связанных с регулярными выражениями, но в прошлую пятницу, спасибо Крису и Шону я нашел одну регулярку, которая позволяет проверить, является ли данное целое число простым. Оригинальные статьи предлагали следующее регулярное выражение для определения простоты числа:

Регулярные выражения — это арифметика для алгоритмов. Они доступны во многих языках программирования, редакторах и настройках приложений. Как и сложение с умножением они просты в использовании.
Но для правильного и эффективного использования regexp-ов нужно понимание того, как они работают. Я постараюсь описать принцип работы регулярных выражений, покажу в каких случаях бывают проблемы и как их решать.

В продолжение общих советов.

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

По мотивам переведенной статьи

Впервые я увидел регэкспы еще в школе в перле, и в общем полюбил их с первого взгляда, конечно после того как разобрался что это такое :). И с превеликим энтузиазмом принялся все регэкспить. Конечно, при этом, понабивал себе шишек на мозг, но любить их не перестал. Со временем любая искренняя любовь взрослеет и перерастает в глубокую привязанность, с понимаем того, что объект твоего чувства может быть несовершенным, но от этого не менее любимым.

Итак, несколько способов предохраниться от разочарования в этом мощном и прекрасном инструменте…

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

1. Часть ЧПУ (человекопонятный URL)

По сути, слово с дефисами.

Паттерн: /^[a-z0-9-]+$/

После прочтения книги про регулярные выражения (далее просто РВ) у меня появились кое-какие мысли по поводу их читаемости. Когда РВ только появлялись, и в них было довольно мало условных обозначений вроде \d, \w и тому подобных, то, наверное, все было не так страшно, хотя уже тогда стоило задуматься о наглядности. Сейчас чтение кода с РВ — это тихий ужас. Нет, если РВ короткое, то особых проблем нет, но по мере их усложнения и появления различных скобок все становится просто кошмарно. Ситуация усугубляется тем, что в некоторых языках (не будем указывать пальцем) постоянно приходится удваивать слеши.

Кроме того в той нотации РВ, которая сейчас используется в большинстве языках программирования, в некоторых, казалось бы простых ситуациях, приходится выкручиваться с помощью различных финтов. Первый пример, что пришел в голову — составить регулярное выражение если «abc», то затем НЕ «xyz».

0. Присказка

В некотором царстве, в некотором государстве жил-был программист. Звали его, как полагается, Иван. Был он настоящим спецом, обладал всеми Тремя Великими Добродетелями Программиста, то есть был ленив, спесив и нетерпелив. Случилась в том царстве печаль великая: кризис. И выгнали Ваню с работы без выходного пособия. Горевал Ваня долго, а потом собрался с духом и разослал резюме по всему белу свету. Долго ли, коротко ли, вызвали Ваню на собеседование. Требований к соискателю было много, но главное — требовалось хорошо владеть регулярными выражениями. До собеседования — почти месяц, готовься — не хочу. Будучи человеком серьёзным, готовиться Иван решил обстоятельно. 3 недели и 3 дня он лежал на печи, почитывал Хабр и думал, как же неслыханно обстоятельно он будет готовиться. До собеседования остался 1 день. Ванюша мысленно обругал работодателей, которые назначают собеседование так скоро, что совсем подготовиться не успеваешь, слез с печи, сдал пивные бутылки и на вырученные деньги купил книжку по регексам. Читал он её до полного изнеможения, пока не отключился. Утром мы найдём сонную физиономию Ванюши лежащей, как на подушке, на этой самой книжке под Хабракатом.

В статье Regexp — это «язык программирования». Основы была поставлена задача: написать регулярное выражение, находящее в цепочке символов текст в двойных кавычках, причем внутри кавычек "..." могут быть и сами символы ", если они экранированы обратным слэшем, например:
one two "foo:=\"quux\"; print" three "four"
Здесь наш регекс должен найти соответствие цепочке
"foo:=\"quux\"; print"
Автором (той статьи) было предложено такое решение:
/ " ( \\" | [^"] )* " /x
(здесь и далее синтаксис Perl; ключ /x означает, что пробелы в регексе не учитываются, мы добавили их лишь для наглядности, чтобы части регекса не слились в единый «модемный шум»).
Этот регекс работает в том случае, когда есть совпадение (текст в кавычках). Проблема же в том, что он находит текст в кавычках даже тогда, когда текста в кавычках (согласно нашим правилам экранирования обратным слэшем) просто нет. Например, в цепочке "\" регекс находит соответствие (равное всей строке "\" ), хотя его быть не должно: кавычка открыта, экранированная кавычка… а вот закрывающей-то кавычки нет.
Ситуацию легко исправить, исходную задачу решить несложно, внеся несколько простых изменений в регекс… но речь не об этом, а о том, что если у вас в руках современный инструмент, т. е. движок регексов (свежая версия Perl, Java или PHP с PCRE), то вы можете «исправить» описанный регекс, добавив в него всего лишь 1 символ. Какой? Куда? Почему? Если знаете ответы, то читать дальше вам не стОит ;-)

В книге Дж. Фридла «Регулярные выражения» есть прекрасная табличка, которую хочу тут привести.
Регулярные выражения открывают широкие возможности для поиска и замены в любом тексте. Используя регулярные выражения можно гибко и просто обрабатывать текстовые документы. Одним из простейших применений регулярных выражений является поиск текста — во многих текстовых редакторах предусмотрена возможность поиска по шаблонам регулярных выражений В regexp существует несколько типов метасимволов выполняющих разные функции, давайте кратко их рассмотрим:

В этой статье рассмотривается валидация email изпользуя регулярные выражения. Все регэкспы выполняются с модификатором i, т.е. делают регистронезависимую проверку.

Несколько лет назад я думал, что regexp осуществляет линейный поиск по тексту, но какое моё удивление было, когда я понял, что это не так. Тогда я убедился на собственном опыте, что от простой смены местами а и b в схеме (...a...)|(...b...) поменялся полностью результат.

Поэтому сейчас я расскажу, как на самом деле работает regexp.
Поняв эти простые принципы и как оно работает, вы сможете писать любые запросы.
Для примера, я разберу сложную при первом приближении, но на самом деле простейшую задачу – выявление всех строк в кавычках.

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

Для начала, поговорим о том, что такое регулярные выражения, и каково их практическое применение.

Данная заметка не предназначена для начинающих изучать регулярные выражения, для начинающих я бы посоветовал книгу Ben Forta "Teach Yourself Regular Expressions in 10 Minutes" (ISBN: 0-672-32566-7).

Для тестирования и отладки регулярных выражений идеально подходит программа RegexBuddy (http://www.regexbuddy.com). Чтобы отлаживать следующие примеры нужно во вкладку Test скопировать HTML какой-либо страницы или вбить несколько тегов самим.

Задача — найти в HTML все теги IMG и вытащить из тегов значения атрибутов SRC и ALT.