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

Хочу обратить внимание хабрасообщества на возможную «уязвимость» в TCL, PostgreSQL и теоретически в некоторых других системах, использующих модули ругулярных выражений или NFA утилиты, изначально написаные самим Генри Спенсором (Henry Spencer). Измененных исходников можно найти добрую сотню (у того же Sun Microsystems, UUNET и т.д.). И хотя, я не думаю, что баг существует изначально с далеких 90-х, хотя бы потому, что кода где возникает эта ошибка я у Генри, в старых его источниках, не нашел, проверить ваши системы все-таки стоит.

И так ошибка: это busyloop на стадии компиляции регулярного выражения вида (((((x)*)*)*)*)*. Причем именно не исполнения, а компиляции, т.е. если есть проверка валидности регулярки и она базируется на том же коде NFA — имеем тот же безконечный цикл + 100% cpu usage.

Ошибку нашли коллеги по opensource проекту TCL, во всех его актуальных версиях (включая develop). Зная, что Postgres использует похожее API, нетрудно было выяснить, что скармливание этого регулярного выражения Postgres приводит к полному зависанию потока (процесса), отрабатывающего запрос.

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

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

Оригинал в PDF.

Автор — не я! Это часть MIT Mistery Hunt 2013.

Между регулярными выражениями в JavaScript и регулярными выражениями PCRE (употребляющимися в Perl и в PHP) есть ряд различий, главнейшим из которых, вероятно, является отсутствие lookbehind (ретроспективной проверки) в JavaScript.

Естественной задачею программистов, раздражённых этими различиями, является внедрение PCRE в JavaScript.

На движке Node к концу нынешнего января Брайан Уайт (Brian White) решил эту задачу, создав модуль node-pcre, служащий обёрткою вокруг движка PCRE.

Этому можно порадоваться, и порадуемся.

Однако node-pcre, как и всякая обёртка вокруг двоичного кода, требует отдельной компиляции на каждой из платформ, совместимых с Node.

Интересно, придёт ли со временем кому-нибудь на ум использовать Emscripten для перевода движка PCRE непосредственно на язык JavaScript?

Мечты, мечты.

Я хочу предложить вам поломать голову вечерок-другой над интересными задачками, на регулярные выражения, которые Callum Macrae выкладывает на своем сайте на GitHub каждый Вторник.

Каждый вопрос представлен в виде набора тестов. Задача — написать такой регулярное выражение, чтобы все тесты стали зелеными.
Некоторые из задач сами по себе довольно простые, а самая интересная часть — в том, чтобы написать наиболее короткое возможное регулярное выражение.

Тесты используют JavaScript Regex движок вашего браузера, который обладает всеми основными возможностями PCRE.  Подробнее можно посмотреть тут (англ.) , в колонке ECMA в таблице.

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

UPD: В регулярных выражениях ECMAScript нету ретроспективных проверок.

Регулярные выражения (РВ) — это очень удобная форма записи так называемых регулярных или автоматных языков. Поэтому РВ используются в качестве входного языка во многих системах, обрабатывающих цепочки. Рассмотрим примеры таких систем:

• Команда grep операционной системы Unix или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах РВ используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют РВ либо в детерминированный конечный автомат (ДКА), либо недетерминированный конечный автомат (НКА) и применяют этот автомат к файлу, в котором производится поиск.
• Генераторы лексических анализаторов. Лексические анализаторы являются компонентом компилятора, они разбивают исходную программу на логические единицы (лексемы), которые могут состоять из одного или нескольких символов и имеют определенный смысл. Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу РВ, и создает ДКА, который распознает, какая из лексем появляется на его входе.
• РВ в языках программирования.

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

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

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

Задача банальная — заменить переводы строк на <br/>, за исключением случая, если перед этим шел html-тэг (для простоты только символ >). Отходя от темы — такой алгоритм замены нужен чтобы иметь и автоматическое добавление переводов строки внутри блоков текста в стиле хабра, и при этом не ломать обычную HTML верстку.

Регулярные выражения — спасение от всех бед для одних и ночной кошмар для других разработчиков, а если говорить объективно, то это мощнейший инструмент, требующий, однако, большой осторожности при применении. Регулярные выражения (регексы, регекспы, регулярки) в языке Ruby основаны на синтаксисе Perl 5 и потому в основных чертах знакомы всем, кто использовал Perl, Python или PHP. Но Ruby тем и хорош, что каждый компонент языка реализован со своим собственным подходом, упрощающим использование данного инструмента и увеличивающим его мощность. В предлагаемой мной небольшой статье рассматриваются особенности регулярок в Ruby и их применение в различных операторах.

Весьма полезный рецепт, который облегчает общение с коммандной строкой описан здесь, однако попробовать его вживую не удалось, т.к. под мою систему (OpenIndiana) не существует компиляторя языка Go. Так возникла идея переписать указанную программу на более универсальный язык, который точно существует на любой платформе — Perl.

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

Привет!

Я много работаю с VoIP-сетями. С коммерческим оборудованием, конечно тоже, но и очень много с OpenSource (статья пишется в контексте использования Asterisk PBX).

В телефонии часто возникает простая задача, разделить маршруты на определённые направления. Ну например, направить вызовы на городские номера в сторону оператора 1, МГ — в сторону оператора 2, МН — в сторону оператора 3.
Задача, в общем-то тривиальная, и реализуется на Asterisk легко:

;Местная городская связь: 7 знаков (в разных регионах РФ от 3-х до 7-ми знаков), и номера экстренных служб.
exten => _0X,1,dial(SIP/itsp1/${EXTEN})
exten => _0XX,1,dial(SIP/itsp1/${EXTEN})
exten => _XXXXXXX,1,dial(SIP/itsp1/${EXTEN})
;Междугородняя и мобильная связь: код выхода на МГ связь (в РФ - "8") + 10 знаков.
exten => _8[348]XXXXXXXXX,1,dial(SIP/itsp2/${EXTEN})
exten => _89XXXXXXXXX,1,dial(SIP/itsp2/${EXTEN})
;Международная связь: код выхода на МН связь (в РФ - "810") + номер телефона в международном формате.
exten => _810X.,1,dial(SIP/itsp3/${EXTEN})

Однако иногда возникает необходимость предоставить абоненту доступ только к мобильным телефонам его области, и здесь простым "_89XXXXXXXXX" не отделаешься.

От переводчика

Это перевод небольшой заметки, написанной вчера Lea Verou, в ней предлагается интересная, хотя и не новая техника для решения повседневных задач.

Информация в статье касается ECMAScript, но может использоваться и в других RegExp Движках (хотя и есть вероятность, что там есть более подходящее решение).

Если примеры кажутся вам сложными, рекомендую играть с ними в консоли, по мере прочтения. И Заранее прощу прочтение за пугающее название.

Статья

Если вы какое-то время используете регулярные выражения, то наверняка вы сталкивались с разными вариантами следующих задач:

• Пересечение:«Что-то, что совпадает с шаблоном А и шаблоном Б»
  Например: Пароль, минимум 6 символов, в котором хотя бы одна цифра, хотя бы одна буква, и хотя бы один специальный символ
  
  
• Исключение: «Я хочу что-то, что совпадает с шаблоном А, но не совпадает с шаблоном Б»
  Например: Любое целое число, которое не делится на 50
  
  
• Отрицание: Все. Что не совпадает с шаблоном А
  Например: Строка, которая не содержит в себе слово «Foo»

Regular Expressions For All (REFA)

Основная идея

Существует множество систем для поиска подстрок отвечающих определенной маске. К сожалению они теряют свою мощь как только приходится учитывать многие факторы. Конструкции становятся громозкими, непонятными и трудноподдерживающими.
Именно для этого я попытался создать аналог – REFA. Регулярные выражения для всех.
Его идея в следующем. Как только регулярное выражение перестает быть очевидным – разбить его на два. Оптимизатор при возможности все равно сведет его в одно, таким образом в скорости потерь не будет, но зато код станет яснее.

Друзья,
Передо мной стоит задача разобрать несколько тысяч различных печатных форм.
К счастью, различия в них не сильно большие (где-то больше параметров, где-то меньше), где-то добавлен столбец и т.д. В целом, по контексту можно понять, где и что находится. т.е. очень напрашивается для использования механизм регулярных выражений. Но, поскольку это не текст в чистом виде, контекст регулярного выражения необходимо задавать не только в форме «предшествует/следует за», но и в форме направления — «выше», «ниже».

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

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

Кто-нибудь сталкивался с чем-нибудь подобным?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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