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

Кто-то парсирует текстовый файл программой на Питоне, другой пишет скрипт с регулярными выражениями на Перле, Си-программист стыдливо возится с буферами и указателями, иногда применяя 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: покажите мне код.")

Известные 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, где вместо вопросов — набор регулярных выражений.

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

regex.alf.nu

В честь наступающего Нового года я набрал в ней 2014 очков. Кто больше?

Собственно, столкнулся с банальной задачей — есть база, в которой есть масса данных ФИО, написанных латиницей. Зачастую достаточно безграмотно и непредсказуемо транслитерировано. Вроде бы и есть ГОСТ 7.79 (ISO 9), но на практике его далеко не всегда соблюдают.
Задача — есть БД с записями (как правило, ФИО) латиницей. Плохой латиницей. Требуется по русской подстроке поиска в вэб-приложении выбрать из БД (MySQL) записи, похоже транслитерированные на латиницу.

Привет Хабр!

Немного наблюдений.

По предложенному вопросу пергамента исписано непозволительно много. Тем не менее, я бы хотел остановится на трех важных, но игнорируемых аттрибутах, свойственных email-у, с точки web-разработки.
Во первых email уникален, в отличии от никнейма, который, в половине случаев, занят кем-то до нас. Однако все еще встречаются сайты с логином по никнейму, который, для всех таких сайтов, ну никак не упомнить. Предлагаю использовать для логина только email.
Во вторых, часть разработчиков игнорирует type='email', когда JS валидаторы натравлены на это поле, и планшетные устройства переключают раскладку, что удобно.
В третьих, ради чего это статья, каждый год пишутся статьи вида «Почему плохо валидировать регекспом», что больше похоже на фетиш. Надеюсь гугл проиндексирует верно.

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

Хочу просто поделиться недавно найденным сервисом для работы с регулярными выражениями. Да, это еще один сервис. Но у него есть особенность — он позволяет не только составлять регулярные выражения, но и помогает разбирать уже написанные — эдакий regexp-декомпилятор.
Сервис называется Regex101.

После более детального ознакомления с мануалом редактора WinEdt (предназначенного почти исключительно для создания LaTeX-документов) открыл дополнительные возможности инструмента поиска/замены этой программы. Чтобы активировать «умный» поиск, нужно поставить галочку в чекбоксе Regular Expressions в меню Find или Find and Replace, в результате чего строка поиска превратится, по сути, в командную строку, с помощью которой можно творить чудеса. То есть сделать с текстом можно будет практически всё, другой вопрос, что иногда чересчур извращённо (поэтому в случае серьёзных задач создание соответствующих макросов выглядит более уместным).

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

Недавно столкнулся с тем, что в новом проекте надо было сделать подсветку синтаксиса для языка разметки MarkDown. В последнее время он достаточно популярен в разных местах. Долго гуглил, в результате пришлось все писать самому и долго тестировать чтобы все работало правильно.
Под катом набор регулярных выражений, которые ищут основные элементы разметки MarkDown в варианте для Objective-c.