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

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

Разработчики 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 of you and me» — «когда вы (что-то) подразумеваете, вы делаете /./удака из себя и из меня»]

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

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

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

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

Предположим, у нас есть база данных SQLite с довольно большим количеством записей, и эта база используется в нашем .NET приложении через System.Data.SQLite и Entity Framework 6.0. И вот приходит заказчик и сообщает, что ему нужна новая функция поиска записей в базе, да такая, чтобы можно было искать с использованием стандартных регулярных выражений.

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

В этой статье мы рассмотрим два способа поиска с помощью регулярных выражений. Один широко распространён и используется в стандартных интерпретаторах многих языков. Второй мало где применяется, в основном в реализациях 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: покажите мне код.")

Известные ParserCombinator'ы и Parboiled предназначены исключительно для разбора формальных языков. Мы же решаем задачу разбора естественного языка и при этом хотим, чтобы с помощью той же грамматики можно было осуществлять синтез фраз на естественном языке, отражающих требуемую нам семантику. Было бы удобно иметь возможность описывать языковые конструкции вместе с правилами абстрагирования/конкретизации.

Например,

1. Преобразование числительных в число («десять» -> 10:Int)
2. и обратно (10:Int -> «десять» («десятый», «десяток» ...))
3. Преобразование числительных вместе с единицей измерения («десять рублей» <-> NumberWithMeasurement(10, RUB))
4. Неполный адрес («ул. Яблочная» <-> Address(street=«Яблочная»))
5. Адрес в пределах города («улица Яблочная дом сто двадцать три квартира сорок пять» <-> Address(street=«Яблочная», building=123, flat=45))
6. Телефон (256-00-21 («двести пятьдесят шесть ноль ноль двадцать один») <-> NumericalSequence(256,0,0,21))

Причём хотелось бы иметь следующие системные свойства:

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

Под катом — описание подхода, реализованного в библиотеке synapse-typed-expressions. Рассмотрены только числительные, но подход естественным образом распространяется на другие вышеупомянутые формальные языковые конструкции.

Пролог, просто пролог!

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

Криптонит для чайника.

Знакомьтесь, я чайник! Вообще-то я и правда не особо силен в программировании, но особенно не комфортно себя чувствую пытаясь «что-то» создать на незнакомом мне языке. В моем рассказе «Visual Basic for Applications» и есть тот непривычный для меня язык. На самом деле, все это лирическое отступление, не более чем попытка занизить ваши ожидания.

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

Утро понедельника как всегда было отвратительным. Рассеивающаяся дымка и еле заметно срывающийся дождь — малоприятное зрелище. Желание работать отпало еще в воскресенье. Работы как всегда много, ничего не клеится, а тут еще и экселевская база на 300к строк свалилась мне в руки. Ну не то что-бы свалилась, закончила парсится. И как вы понимаете, что структурированной, форматированной и однородной базой там и не пахло, а иначе откуда статье взяться. Так что на выходе я получил громадное множество неоднородной информации, из которой необходимо было выделить то нужное, что требовалось мне для работы, отсекая все остальное.

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

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

Согласно Википедии, Oniguruma означает «колесница дьявола» в переводе с японского.

Мы все знакомы с регулярными выражениями. Они являются «швейцарским армейским ножом разработчика». Что бы вы ни искали, какой бы текст ни разбирали, вы всегда можете сделать это используя регулярные выражения. На самом деле, вероятно, вы начали использовать их гораздо раньше, чем стали использовать Ruby — они уже давно включены в большинство популярных языков программирования: Perl, JavaScript, PHP, Java и прочие. Ruby появился в середине 1990-х годов, тогда как регулярные выражения еще в 1960-х, то есть почти на 30 лет раньше!

Но как на самом деле работают регулярные выражения?

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