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

Наверное, каждый, кто интересуется регулярными выражениями и читает Хабр, видел этот кроссворд из регулярных выражений:

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

Здравствуйте, уважаемые дамы и господа.

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

I. Возможности

Когда я прочитал на MDN: «The static String.raw() method is a tag function of template literals, similar to the r prefix in Python or the @ prefix in C# for string literals» — я здорово обрадовался, потому что мне часто не хватало в JavaScript чего-то вроде одиночных кавычек в Perl.

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

1. Определение путей к файлам Windows без двойного экранирования.

const r = String.raw;

const test_module = require(r`e:\DOC\prg\js\node\-lib\test.js`);

2. Определение путей к ключам реестра Windows.

const r = String.raw;

const Winreg = require('winreg');

const regKey = new Winreg({
  hive: Winreg.HKCU,
  key: r`\Software\MPC-HC\MPC-HC\Settings`
});

3. Создание сложных регулярных выражений из составных литералов.

См. пример кода в одной из недавних статей.

II. Ограничения

Однако со временем я стал натыкаться на неожиданные ограничения. Написав об одном из них в багтрекер V8, я получил отрезвляющее объяснение. Оказывается, хоть String.raw и выдаёт строку без интерпретации экранированных литералов, на стадии парсинга кода анализатор всё равно требует, чтобы литералы соответствовали правилам. Из этого следуют неочевидные ограничения для упомянутых случаев применения.

1. C чего всё началось

Недавно у меня возникла необходимость написать очередную утилиту, обрабатывающую текстовый файл в формате, похожем на упрощённый BBCode, а именно в формате исходников для словарей ABBYY Lingvo — DSL (Dictionary Specification Language). (Не путать с другим DSL (Domain-specific language) — интересный случай, когда гипоним является омонимом к гиперониму).

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

Одной из задач утилиты было как раз нахождение этих тегов с исключением экранированных сочетаний.

Поскольку в регулярных выражениях JavaScript с недавнего времени можно пользоваться lookbehind assertions (в личных целях), я подумал, нельзя ли реализовать поиск при помощи этого средства, — тем более что в данной разновидности lookbehind можно использовать выражения переменной длины.

Регулярные выражения в JavaScript понемногу догоняют PCRE.

Недавно упомянутая возможность lookbehind перешла на стадию флага --es_staging.

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

В продвижении lookbehind и character properties, на мой взгляд, есть две разницы: первая возможность вводит совсем немного нового синтаксиса по сравнению со второй, зато вторая меньше изменяет поведение всего процесса (сравните количество затрагиваемых изменениями файлов в исходниках V8 по двум упомянутым ссылкам). По сути, свойства Юникода — всего лишь удобные сокращения, синонимы для разных групп codepoint-ов, поэтому от них можно ожидать минимум подвохов при интеграции в систему.

Конечно, обе возможности не советуют применять в продукции (кроме Google Chrome, они нигде в браузерах не реализованы, а Node.js только-только переходит на соответствующую им версию V8, в которой они всё равно пока под флагами).

Но для личных нужд (утилиты по обработке текста и т.д.), мне кажется, они вполне применимы. Возможно, коду разработчиков V8, даже экспериментальному, можно порой доверять с ничуть не большим риском, чем разнообразным библиотекам на npmjs или GitHub.

Приветствую уважаемые.

«Ехали регулярные выражения, через регулярные выражения, видят регулярные выражения, в регулярных выражениях, регулярные выражения — регулярные выражения, регулярные выражения, регулярные выражения...»

Нет. Это не бред сумасшедшего. Именно так я хотел назвать мой небольшой обзор на тему поиска регулярных выражений с помощью регулярных выражений. Что по сути тоже не меньший бред. Даже не знаю может ли вам такое в жизни пригодиться. Лучше конечно избегать таких ситуаций когда надо искать непонятно что, непонятно где. Ведь что такое регулярное выражение? Да почти всё что угодно!

Вам может показаться странным, но:

.это, например, вполне себе регулярное выражение:.
(Или это тоже может быть (можете даже проверить))
~это~
<script src="И это - регулярка, вполне рабочая и может быть даже кому нибудь очень необходимая.js">

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

Кажется, прошла незамеченной хорошая новость.

Разработчики V8 активно взялись за добавление lookbehind assertions в регулярные выражения JavaScript.

В Google Chrome Canary уже можно потестировать при помощи флага:

chrome.exe --js-flags="--harmony-regexp-lookbehind"

В этом месяце выходит шестая версия Node.js, основанная на V8 5.0, и в ней тоже можно включить поддержку lookbehind:

node --harmony_regexp_lookbehind

Если совсем не терпится, можно потестировать на уже появляющихся RC:

nodejs.org/download/rc

Что, если бы я попросил вас написать регулярку для проверки e-mail адреса? Вы бы, наверное, подумали минутку, и потом бы нагуглили запрос. И получили бы нечто вроде:

^([a-zA-Z0-9_-.]+)@([a-zA-Z0-9_-.]+).([a-zA-Z]{2,5})$

Регулярок на эту тему существуют тысячи. Но почему? Наверняка же кто-нибудь, да прочёл стандарт RFC822 и выдал надёжную регулярку?



И даже этот монстр не в силах проверить емейл-адрес. Почему? Оказывается, в скромном адресе может скрываться очень многое. Некоторые части стандарта RFC822 достаточно полезны, а некоторые – просто безумны. Но в любом случае это интересно – давайте разбираться.

В дополнение к большим и подробным материалам, разработчики библиотеки MSLibrary for iOS решили начать серию очень компактных статей, посвященных тому как ПРОСТО реализовать ту или иную функцию. Никакой теории, только практика…

Итак, удаляем из строки ненужные символы, используя регулярные выражения, с помощью простой функции:

NSString *yourFuncionName(NSString *string) {
    NSString *regExString = @"yourRegularExpression";
    NSRegularExpression *_regEx = [NSRegularExpression regularExpressionWithPattern:regExString options:NSRegularExpressionCaseInsensitive error:nil];
    return [_regEx stringByReplacingMatchesInString:string options:0 range:NSMakeRange(0, [string length]) withTemplate:@""];
}

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

Несколько полезных регулярных выражений:

    \\s - удаляет все пробелы
    [-:_\\.] - удаляет все символы, находящиеся в квадратных скобках
    [:^digit:] - оставляет только цифры
    [:^alpha:] - оставляет только буквы
    [:^alnum:] - оставляет только буквы и цифры
    [:^word:] - оставляет только буквы, цифры и подчеркивания

Мы продолжаем публикацию материалов, от разработчиков библиотеки MSLibrary for iOS. Тема этой статьи не случайна, проблема выбора нескольких условий из заданного множества, не редко встречается в нашей работе. Простейший пример — выбор партнера для игры (свидания, путешествия и тд). Выбор надо осуществлять из нескольких групп, сформированных по уровню подготовленности (здесь могут быть и возрастные группы и все что угодно). Условие — дать пользователю возможность выбрать партнера из одной или нескольких групп одновременно. Другим примером могут служить константы NSRegularExpressionOptions проверки типа данных для класса NSRegularExpression. При подстановке этих констант в методы класса, мы можем записать:

	NSRegularExpressionCaseInsensitive | NSRegularExpressionDotMatchesLineSeparators 

Объединив константы знаком логического «ИЛИ» мы будем уверены, что проверим анализируемую строку на соответствие обоим из заданных условий.

Один из способов реализации подобной задачи — использование списка констант в виде перечисления enum, в котором элементы перечисления представляют собой двоичные числа с одним установленным битом. Сделать это не очень сложно, но сначала немного теории. Вспомним такие битовые операции, как «СДВИГ», «И», «ИЛИ».

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



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

Кто-то парсирует текстовый файл программой на Питоне, другой пишет скрипт с регулярными выражениями на Перле, Си-программист стыдливо возится с буферами и указателями, иногда применяя Yacc и Lex.

А можно ли парсировать текст голым железом? Вообще без программы?

— А как это?, — спросил меня знакомый, — С помощью Ардуино?

— Внутри Ардуино стоит вполне фон-неймановский процессор и работает программа, — ответил я, — Нет, еще более голое железо.

— А-а-а-а, этот, микрокод?, — догадался мой товарищ и взглянул на меня победно.

— Нет, термин «микрокод» использовался для специфической организации процессоров в 1970-е годы, потом его использование сошло на нет, — ответил я и добавил, — Правда есть еще микрооперации в интеловских процессорах, в которые перекодируется x86, но это тоже другое. Нет, я имею в виду парсинг текста устройством, состоящим из логических элементов И-ИЛИ-НЕ и Д-триггерами, как на картинке ниже.

— Невозможно! — воскликнул мой приятель, — в таком устройстве где-то сбоку должен сидеть процессор и хитро подмигивать!

— Почему это невозможно?, — парировал я, — Вот машину Тьюринга знаешь? Парсирует текст на ленте, а сбоку никакие интелы и ардуино не подмигивают.

— Нуу, машина Тьюринга, — протянул приятель, — это абстракция, типа Демона Максвелла.

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

В первой части статьи разработчики библиотеки MSLibrary for iOS рассказали об особенностях структуры телефонных номеров с точки зрения международных стандартов, опубликованных в документе RFC 3966 , рассмотрели Международную структуру телефонных номеров, корпоративные WEB стандарты набора телефонного номера, их взаимодействие между собой и то, как ведут себя пользователи.
Как уже было сказано, захват и верификация это — разные задачи, но решаются они схожими методами, различающимися в основном применяемыми в них регулярными выражениями. Во второй части статьи речь пойдет собственно о регулярных выражениях.

Верификация телефонных номеров

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

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

Рассмотрим оба варианта, но сначала общие соображения.

Валидация строки телефонного номера, чтобы он был адекватно обработан iOS, сводится к нескольким условиям:
1. общая структура номера должна соответствовать документу RFC 3966

telephone-uri = global-number-digits [extension]

_{рис. 1}

Поводом для появления серии статей, первая из которых представлена вашему вниманию, послужил большой аналитический и практический материал, накопившийся в процессе работы над библиотекой MSLibrary for iOS. Библиотека MSLibrary включает множество классов, и еще больше функций и макросов, призванных упростить рутинный труд разработчиков, существенно сократить сроки разработки и размер кода. Но, всему свое время, о библиотеке мы расскажем чуть позже.

Итак, захват и верификация телефонных номеров с помощью регулярных выражений. Казалось бы, о чем здесь говорить? Кто умеет, напишет сам, а кто не умеет скопирует одно из множества готовых решений, разбросанных на просторах Всемирной паутины. Вопрос только в том, что он напишет и что скопирует и насколько этот код будет соответствовать поставленным задачам, а также действующим международным, отраслевым и корпоративным стандартам? Любое решение, даже самое простое, хорошо лишь в том случае, если разработчик полностью осознает его работу и абсолютно в нем уверен.

От переводчика: прочитав статью, начал было отвечать в комментариях, но решил, что текст, на которую я собирался ссылаться, достоин отдельной публикации. Встречайте!

Если вы знаете, как валидировать email-адрес, поднимите руку. Те из вас, кто поднял руку — опустите её немедленно, пока вас кто-нибудь не увидел: это достаточно глупо — сидеть в одиночестве за клавиатурой с поднятой рукой; я говорил в переносном смысле.

До вчерашнего дня я бы тоже поднял руку (в переносном смысле). Мне нужно было проверить валидность email-адреса на сервере. Я это уже делал несколько сот тысяч раз (не шучу — я считал) при помощи классного регулярного выражения из моей личной библиотеки.

В этот раз меня почему-то потянуло ещё раз осмыслить мои предположения. Я никогда не читал (и даже не пролистывал) RFC по email-адресам. Я попросту основывал мою реализацию на основе того, что я подразумевал под корректным email-адресом. Ну, вы в курсе, что обычно говорят о том, кто подразумевает. [прим. перев. Автор имеет в виду игру слов: «when you assume, you make an ass out of you and me» — «когда вы (что-то) подразумеваете, вы делаете /./удака из себя и из меня»]

И обнаружил кое-что занимательное: почти все регулярные выражения, представлены в интернете как «проверяющие корректность email-адреса», излишне строги.

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

Python — один из немногих динамических языков, в которых отсутствует встроенная поддержка регулярных выражений, но это компенсируется проработанной базовой системой (с точки зрения API). В то же время он весьма причудлив. К примеру, поведение написанного на Python парсера может вас удивить. Если вы попытаетесь в ходе импорта профилировать Python, то, скорее всего, 90% времени вы проведёте в работе с модулем re.

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



В первом случае поиск занимает A?ⁿAⁿ времени, во втором — Aⁿ.

Степени обозначают повторяемость строк, то есть A?³A³ — это то же самое, что и A?A?A?AAA. Графики отражают время, требуемое для поиска через регулярные выражения.

Обратите внимание, что в Perl для поиска строки из 29 символов требуется более 60 секунд. А при втором методе — 20 микросекунд. Это не ошибка. При поиске 29-символьной строки Thompson NFA работает примерно в миллион раз быстрее. Если нужно найти 100-символьную строку, то Thompson NFA справится менее чем за 200 микросекунд, а Perl понадобится более 10¹⁵ лет. Причём он взят лишь для примера, во многих других языках наблюдается та же картина — в Python, PHP, Ruby и т. д. Ниже мы рассмотрим этот вопрос более детально.

Наверняка вам трудно поверить приведённым данным. Если вы работали с Perl, то вряд ли подмечали за ним низкую производительность при работе с регулярными выражениями. Дело в том, что в большинстве случаев Perl обращается с ними достаточно быстро. Однако, как следует из графика, можно столкнуться с так называемыми патологическими регулярными выражениями, на которых Perl начинает буксовать. В то же время у Thompson NFA такой проблемы нет.

Возникает логичный вопрос: а почему бы в Perl не использовать метод Thompson NFA? Это возможно и следует делать, и об этом пойдёт далее речь.

Привет, Хабр!

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

• Мы открыли публичный чат сообщества Хекслет в Слаке! Там можно общаться с другими юзерами и с преподавателями. Есть специальные каналы по отдельным курсам и темам, есть даже канал для изучения английского языка.
• Оповещения о выходе новых уроков в ваших курсах теперь приходят на почту и появляются в уведомлениях на сайте.
• На сайте теперь появляются запланированные курсы, которые находятся сейчас в разработке (подробнее о них ниже). На эти курсы можно подписаться заранее.
• В разделе «Песочница» находятся бесплатные курсы в свободном формате от других пользователей Хекслета. Вы тоже можете создать свой практический курс!
• За прохождения уроков начисляются баллы, а на главной странице можно видеть свою позицию в топе пользователей.

А теперь — новые курсы:

Основы Ansible

Системы управления конфигурацией и оркестрации – важные инструменты в арсенале современного разработчика и системного администратора. Цель этого курса – научиться работать с Ansible, популярным инструментом управления конфигурацией. Как мы писали ранее, Ansible активно используется при разработке и деплое Хекслета.

Мы часто видим ошибки и опечатки в интернете. Как правило, принято или с достоинством пройти мимо, в глубине души презирая неграмотного (или невнимательного) писателя, или, наоборот, с увлечением развернуть просветительскую деятельность (не всегда, к сожалению, уважительную). В лучшем случае, если на сайте установлен Orphus — нажать Ctrl+Enter.

Так поступал и я, пока однажды с ужасом не заметил, что написал «вООбщем» или нечто подобное. Разрушительное влияние чтения форумов, да и, что уж там, самого Хабра, на читательскую грамотность — налицо. А между тем — сейчас есть многое, что могло бы облегчить участь наших бедных глаз!

Не все JSON нельзя комментировать (например, Хром[иум] вполне переносит комментарии в manifest.json), но в стандарте не предусмотрены комментарии к нему. Поэтому ряд функций в NodeJS не обрабатывают комментарии в формате JS и считают их ошибкой. Точно так же, AJAX с форматом JSON принимает их за ошибку. Поэтому для конфигурационных файлов в формате JSON имеется масса неудобств при попытках их использовать как человеко-читаемые файлы. Может быть, это иногда хорошо. Если хотим прокомментировать, то будем вынуждены оформить комментарий под или над строкой как «ключ-значение».

...{...
    "some-key_comment":"my comment for key and value",
    "some-key":"some-value",
...}...

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

...{...
    "some-key":"some-value", //какой-какой key?? Ай, комментарии - нельзя!
...}...

Придумаем JSON-подобный формат с комментариями в стиле JS, чтобы их можно было выполнять как JS, а, очистив от комментариев — читать как JSON. ("TL:DR: покажите мне код.")