Задача выделения из потока символов определенных лексем является весьма распространенной. Часто ее решают с помощью лексических анализаторов, конфигурируемых регулярными выражениями. Многие анализаторы построены по принципу генерации программного кода, который в свою очередь реализует логику регулярных выражений. Фактически, это компиляция языка регулярных выражений в код языка программирования.

Например, flex — это один из таких анализаторов. Старый, но проверенный годами.

Я много пользовался flex'ом, он имеет и плохие и хорошие стороны, но по большому счету, жаловаться не приходилось.

Но вчера наткнулся на интересный проект — re2c. По сути, на этой штуке можно писать лексические анализаторы прямо на коленке за несколько минут.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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