Ещё одним способом задать язык является регулярное выражение. Регулярным выражением обозначают множество цепочек, которое называют регулярное множество. Чтобы задать регулярное выражение для некого алфавита Σ следуют учитывать 6 правил:
Отдельный символ из алфавита Σ есть регулярное выражение. Например символ а ∈ Σ (символ из алфавита Σ) задаёт множество {а}.
Пустая цепочка ε есть регулярное выражение, задаёт множество {ε}
Если R и Q - регулярные выражения, то запись RQ тоже регулярное выражение, которое обозначает сцеплённое множество, где первая цепочка пары образуется выражением R, а вторая выражением Q. Сцепление ещё называют конкатенацией.
Если R и Q - регулярные выражения, то запись R | Q тоже регулярное выражение, которое обозначает объединение множеств цепочек заданных выражениями R и Q. | - знак читается как «или».
Если R регулярное выражение, то запись R* тоже регулярное выражение, которое обозначает множество, которое получается путём повторения цепочек множества заданное R. Повторение ещё называют итерация.
Если R регулярное выражение, то запись (R) тоже регулярное выражение и обозначает тоже самое множество, что и R.
Предполагаем приоритет операции, высший имеет «*» - повторение, затем сцепление и низший «|» («или»). Скобки используются для изменения порядка операций.
Зачастую при записи регулярного выражения запись ε опускают и вводится дополнительный оператор «один раз и более» обозначенный символом «⁺», что значит R⁺=RR*. Вот так это выглядит на примере языка целых чисел со знаком:
Теорема Клини гласит: Автоматные языки являются регулярными множествами. Регулярные множества являются автоматными языками.
Из вышесказанного значит, что мы любую автоматную грамматику можем записать в виде регулярного выражения и наоборот.
И чтобы вам было проще понять правила сделаем таблицу соответствия правил с участками рисунка порядка (синтаксической диаграммы) языка.
Таблица соответствия
На этом урок окончен. В следующем мы обсудим регулярные выражения на практике и подытожим тему автоматных языков. Новоиспечённые подписываемся, с нами интересно. Дайте пятюню.
В оригинале фраза звучит следующим образом: "При слове "культура" я снимаю с предохранителя свой браунинг". И нет, это говорил не Геббельс.
Браунинг образца 1910 года – тот самый, который надо снимать с предохранителя при слове "культура"
Согласно красивому мифу, фраза звучит в пьесе одного немецкого драматурга в следующих обстоятельствах. Высококультурная публика расходится то ли после концерта, то ли после спектакля, предаваясь умным рассуждениям о только что услышанном и увиденном. У подъезда побирается нищая девочка. Публика обходит её, стараясь не замечать... И вот тут-то герой пьесы и произносит эту сакраментальную фразу.
Согласитесь, красиво. Но, к сожалению, тоже неправда.
Хотя это действительно слова из пьесы, которая называется "Шлагетер" (фамилия героя), и написал её драматург Ганс Йост. Он был что назывется "реакционером": не любил буржуазной публики, любил простой германский народ и считал виновником его невзгод евреев. Всё это вместе сделало его сторонником Гитлера.
Фраза звучит в пьесе при следующих обстоятельствах. Её герой, недавний участник Первой мировой войны, молодой лейтенант Альберт Лео Шлагетер (кстати, реальное историческое лицо) готовится к поступлению в университет. Он считает, что должен осваивать азы политэкономии, потому что главная политическая борьба за будущее нации развернётся не на поле брани, а в политических и финансово-промышленых лабиринтах.
С ним не согласен его товарищ, считающий, что бороться нужно здесь и сейчас, с оружием в руках. Именно он в ходе спора с Шлагетером и произносит пресловутую фразу. Всё? Нет.
Ганс Йост (слева) и его герой, лейтенант Шлагетер
Самое интересное – это реальная история Шлагетера, участника германских добровольческих отрядов, о которых мы в силу понятных причин мало что знаем.
После официального окончания Первой Мировой войны, в которой Германия была объявлена потерпевшей поражение, вооружённое сопротивление немцев отнюдь не прекратилось. Вчерашние солдаты и офицеры не все отправились в Берлин искать работу, спорить об искусстве, напиваться и тосковать, как в романах Ремарка. Нет, армия не прекратила существования. На её основе возник так называемый "Добровольческий корпус", Фрайкор, и ему было суждено сыграть весомую роль в истории.
Война окончена, можно разойтись по домам... Не разошлись. Один из отрядов Фрайкора
В частрности, Фрайкор воспрепятствовал "большевизации" Латвии. А главное, не допустил успеха коммунистической революции в Германии в 1919 году и тем самым – положил конец надеждам на Мировую Революцию. Российским большевикам пришлось считаться с тем, что события происходят не в сферическом вакууме революционной теории, а в конкретной стране с конкретными условиями и традициями, что привело к смене курса на "победу революции в отдельной стране" и осознанию необходимости её модернизации.
Но это было потом. Жизнь же бойца Фрайкора Альберта Лео Шлагетера оборвалась следующим образом: он организовывал железнодорожные диверсии в Руре (области, отторгнутой от Германии по итогам войны), был задержан французскими властями и расстрелян.
В финале пьесы Йоста он стоит на коленях перед расстрельной командой спиной к зрительному залу. Солдаты целятся сквозь его тело в зрителей. Шлагетер восклицает: "Германия! Молю! Приказываю! Поднимайся!" Звучит залп, вспышка... Конец.
Финальная сцена постановки пьесы "Шлагетер"
Вот такая история. Она не является пропагандой нацизма. Нацизму ещё только предстоит зародиться в умах немцев; а пока это время Веймарской республики – буржуазной, лицемерной, коррупционно-воровской и чрезвычайно собою довольной – как всякая "демократия не для всех". Это было время тех, кто был готов на многое, чтобы положить ей конец. На слишком многое...
А в общем, жалко, что миф про культурную публику и нищую девочку – неправда.
В предыщущей статье мы ознакомились с базовыми элементами. в этой части мы рассмотрим более сложные примеры. И затем, применим эти знания для реальных задач.
Квантифаеры (Quantifier) + * ?
Предположим, в нашем выражении один из символов может быть опциональным или повторяться несколько раз. Например, мы ищем слово cat, которое может начинаться с "ca", но последующий символ "t" может быть опциональным или повторяющимся. Здесь у нас есть несколько вариантов в зависимости от наших требований:
Символ вопроса ? или {0,1}
Симол tможет отсутсвовать или присутствовать в рамках символа { } это { 0 , 1 }.
Как видно первые три варианта совпали но мы не задели больше одного символа t. Мы бы достигли такого же результата через cat{0,1}
DOS атаки вошли в чат. Catastrophic Backtracking (Катастрофический возврат)
Далее переходим к выражениям, неоптимальность которых может стать уязвимостью для атак типа DOS (Denial of Service - отказ в обслуживании) а точнее RegexDOS или ReDOS. Неоптимальные и сложные регулярные выражения могут потребовать экспоненциальной сложности для их обработки. Злоумышленник, зная об этом, может заспамить нас строками, которые быстро истощат наши процессорные ресурсы. Более подробную информацию по этой теме можно найти здесь. В качестве примера рассмотрим следующий запрос:
Regex101 достаточно умен чтобы даже не пытаться его запустить, он аналитически предотвратил запуска поиска.
Не стоит паниковать, так как регулярные выражения позволяют нам написать защищенные от атак типа DOS выражения.
Символ плюса + или {1, } (от 1 до бесконечности)
Предположим, что символ "t"должен присутствовать, и при этом мы допускаем его повторение. Это эквивалентно записи {1,} (от 1 до бесконечности). Для этого используем символ "+":
t элемент должен обязательно присутствовать.
Символ звездочки * или {0, } (те от 0 до бесконечности)
В последнем варианте предположим, что символ "t" может быть не включен, и при этом может иметь бесконечное количество повторений. То есть это эквивалентно записи {0,} или от 0 до бесконечности:
Сравним каждый из квантифаеров
Пересмотрим еще раз каждый из них и эквивалентное к ним { }:
? эквивалентна { 0 , 1 }
* эквивалентна { 0, }
+ эквивалентна { 1, }
Cимволы \w \d \s и их отрицания \W \D \S
Некоторые из этих символов я уже упомянул в первой статье, но давайте повторим и добавим немного новых:
\w - любый алфавитный символ (a-z,A-Z) и цифры 0-9 и подчеркивание _
\d - цифры 0-9
\s - символ пробелов такие как - пробелы, табы, переносы строк итд
В regex есть удобная функциональность инверсии выражений. Например если вместо \d мы напишем \D то выражение будет искать все символы исключая цифры.
Также для инверсии любого общего выражения можно достичь символом ^ но указав его внутри скобок. Например любой символ кроме a-b: [^a-b]
Группировка.
Группировка - важная функциональность регулярных выражений, которая позволяет:
Составлять более сложные запросы.
Извлекать данные из выражений.
Чтобы выделить выражение в группу, нужно обернуть его в скобки ( ). Рассмотрим ситуацию, где у нас есть записи о животных в формате "название животного дата рождения цвет" (разделенных пробелом). Давайте напишем выражение для извлечения только кошек (любого года рождения и цвета), выделив цвет и год рождения в группу:
И так мы получили 2 результата и как вы можете видеть справа мы получили две группы Group 1 и Group 2.
Group 1 и Group 2 совпадают с нашими ожиданиями, но могут быть неудобными для чтения. Давайте воспользуемся еще одной возможностью и дадим им ярлыки. Для этого, внутри круглых скобок, нужно в самом начале добавить "?<label>", где "label" - это название группы. Например:
Справа снизу видно что наши группы теперь имеют человеческий вид - date, color.
Применение регулярных выражений для промышленной задачи.
Итак, у нас перед нами задача: мы получили записи из ветклиники и хотим отфильтровать только валидные записи, а затем извлечь их для последующей аналитики.
Анализ входных данных
Теперь, когда у нас есть данные, нам нужно решить:
Какие данные считаются корректными?
Какие "отклонения" мы можем допустить?
Обычно ответы на эти вопросы предоставляются аналитиком, но в данном случае мы выполним все шаги самостоятельно. Итак, рассмотрим данные:
не стоит обращать внимание на хомяков весом почти в 1кг)
Из данных можно сделать вывод:
Первые цифры определяют год, просто 4 фиксированные цифры.
Данные разделены ";" (точкой с запятой) с потенциальными смежными пробелами.
Последняя колонка с весом - это число с плавающей точкой.
Напишем выражение для каждой из групп
дата (?<date>\d{4}) - ровно 4 цифры
имя (?<name>[a-zA-Z]+) слово длины от 1 до бесконечности состоящие из букв алфавита
животное (?<animal>(dog|cat|snake)) - лишь 3 вида допустимых животных собака, кошка, змея написанные строчными буквами
вес (?<weight>\d+\.\d+) - два числа длины минимум 1 и до бесконечности, разделенные точкой
между разделителями есть пробелы \s* (от нуля до бесконечности)
Итак, полученное выражение:
Предположим, что по требованиям нам нужно анализировать только собак, кошек и змей. Тогда наше конечное выражение будет выглядеть вот так:
Это регулярное выражение соответствует вашим требованиям для анализа записей о собаках, кошках и змеях. Оно разделяет данные на четыре группы: год, имя, вид животного и вес. Теперь проверим это выражение на наших данных:
можно заметить что группы совпадают с ожидаемыми значениями
Как мы могли бы улучшить запрос?
Наш первый вариант был слишком "жестким", и мы не предполагали, что животное может иметь заглавную букву. Давайте это поправим:
Добавить ?i что даст нам (?i:(?<animal>dog|cat|snake)) чтобы не учитывать регистр животного
Защита от DOS атак.
Чтобы предотвратить возможность перегрузки системы, уберем использование *, + и укажем максимальный допустимый размер, используя {}.
Новое выражение теперь учитывает и DOG и Cat благодаря ?i:. Все предыдущие записи были также включены, хотя все *, + были исключены из выражений.
Воспользуемые полученным выражением в Java.
Цель - отфильтровать все валидные записи и привести к типам Javav. Я не планировал сильно погружаться в детали реализации Regex классов в Java, поэтому ниже просто покажу рабочее решение:
Код далек от идеала но достаточно прост для понимания.
Pattern, Matcher - классы для работы с Regex в Java.
В коде мы создаем объект класса Pattern и затем создаем Matcher на его основе. Класс Matcher позволяет обойти всe валидныe записи которые формирует наш Regex запрос используя метод matcher.find(). И затем вытаскиваем значения групп используя метод group("имя группы"). Результатом работы будет
И последнее. Полученные результаты совпадают с regex101.com, но нужно помнить, что у Java есть свои аспекты поддержки Regex, которые в редких случаях потребуют небольших изменений в регулярном выражении.
На этом рассказ про regex заканчивается, вот материалы. Материалы на которые стоит обратить внимание:
Птичка, цветочек, прямые линии. Почти неотличимо от обычного регекса)
Регулярные выражения, можно сказать, представляют собой своего рода язык запросов, благодаря которому можно выполнять следующие ключевые задачи:
Валидировать строки
Искать нужные подстроки в строках
Извлекать необходимые данные
Regex не ограничивается только языком Java.
Этот язык используется повсеместно в области информационных технологий. Зная его, вы можете применять свои навыки в множестве контекстов. Поддержка регулярных выражений присутствует в большинстве языков программирования, и множество программ полагаются на регулярные запросы. В какой-то мере regex является стандартом, который полезно знать каждому.
Regex часто кажется сложным для понимания, особенно новичкам.
К сожалению, регулярные выражения, особенно если они написаны неоптимально, могут требовать много усилий для разбора конкретного выражения.
Существует множество решений для упрощения написания и тестирования регулярных выражений.
К счастью, существуют готовые онлайн-решения, которые существенно облегчают процесс понимания. Например, regex101.com - сервис, который мы будем использовать далее. Вот пример того, как мы валидируем формат даты:
Можете пока не вдаваться в подробности. Ниже я объясню как им пользоваться.
Самые основы. Ищем котов.
Давайте начнем с самых основ. Допустим, у нас есть задача: мы хотим найти все упоминания слова 'cat' в строке 'catdogbananacat'. Выражение для этой задачи будет очень простым: 'cat'. Именно так, просто слово.
Теперь давайте посмотрим, что мы найдем, используя утилиту regex101.com:
Мы нашли двух котов. (Заметьте первый кот подсвечен голубым, второй синим - тк найдено 2 упоминания или подстроки в строке).
Символ начала строки ^
Теперь найдем только котов которые стоят в самом начале строки а не в середине или конце, для этого воспользуемся симоволом ^ (циркумфлекс символ или символ "домика" или "крышечки" или caret на английском).
Среди 3х вариантов было найдено два кота которые начинают строку.
И так среди вариантов мы нашли 2 котов которые начинают строку.
Символ конца строки $
Также, аналогично предыдущему, давайте найдем только те варианты, где 'cat' будет заканчивать строку. Для этого воспользуемся символом $. Итак, наше выражение будет cat$.
Найден лишь один который который заканчивает строку.
Усложняем задачу, находим двух котов между которыми есть цифра. Символ числа \d
Теперь усложним задачу и найдем двух котов, между которыми есть цифра. Для этого мы используем \d (от слова 'digit' - цифра). Итак, искомое выражение будет 'cat\dcat'.
Как мы видим лишь один случай найден. Именно один варинт ровно 1 числа между двумя котами.
Знакомимся с \w и последовательностью +
Теперь предположим, что мы ищем двух котов, между которыми может быть несколько цифр, букв или подчеркиваний. Для этого воспользуемся \w, а затем добавим символ +, подсказыва регексу, что символов может быть больше одного. Конечное выражение: cat\w+cat
красным подчеркнуто, чтобы для удобства просмотра)
Перечисляем допустимые символы. Символ [ ]
Теперь сузим поиск и предположим, что мы ищем пару двух котов, между которыми есть лишь буквы a, b, c (либо их вариации). Для перечисления используем квадратные скобки: [abc], и добавим +, чтобы указать, что букв может быть несколько.
первые три вариана не подходя потому что: в первом есть цифра, во втором дефис, в третьем подчеркивание.
Указываем минимальную и максимальную длину. Символ { }
Теперь сузим поиск еще сильнее, предположим что в сумме букв a,b,c между котами может быть не менее 1 и не более 5 символов. Для этого воспользуемся фигурными скобками и получим выражение cat[abc]{1,5}cat
Добавляем вариации. Логическое ИЛИ. Символ |
Теперь допустим мы ищем всех котов между которыми может быть:
Уже знакомый вариант с a,b,c которых не более 5 и не менее 1
Либо слово dog
Для этого воспользуемся логическим выражением или используя | символ. Также чтобы указать что между двумя котами может быть лишь 1 вариант нам нужно использовать круглые скобки чтобы объединить их. Круглые скобки играют еще и другие роли (об этом будет позже). Итого наше выражение cat([abc]{1,5}|dog)cat
К старым результатам добавился catdogcat что и было ожидаемо.
Резюмируя первую часть статьи.
И так мы хорошо поработали, теперь мы научились работать с такими иероглифами как:
^ начало строки, $ конец строки
+ несколько последовательных символов (неограниченное количество)
\d любое число 0-9
\w любой алфавитный, цифровой символ и подчеркивание
[ ] - перечисление допустимх символов
{ } - указание минимальной, максимальной длины повторений
| - логическое ИЛИ которое для большинства случаев требует наличие скобок ( )
Что дальше?
Итак, мы познакомились с довольно простыми вещами, которые не слишком иллюстрируют всю мощь регулярных выражений. В следующих частях мы узнаем еще больше магических символов и применим их для первых промышленных задач.
Извините за баян. Давно на Пикабу, но пишу впервые. На волне комментов разблокировано воспоминание. Едем с Михалычем в лежачей маршрутке, он нахватал минусов и держит моё пиво, а я фотографирую на тапок и получается шакалисто. Поэтому тема сисек не раскрыта, от слова "совсем", но бонус в комментариях, а я ору в голос и бурлистаю. Уух, бляя. Занавес. Вот така хуйня малята, буду держать в курсе. Простите, что под топовым и за сумбур. Чукча не писатель. Вот запятые:,,,,, Можете пинать. Ссылка на ТГ:
Это по-моему с американских фильмов у людей калька пошла. Вот эта фраза: "я не готов это принять" или "я так не думаю", вместо твёрдого привычного "Нет". Ещё на вопрос "как пройти на Ардатовскую улицу" вместо простого "не знаю", это пиндосское " не готов вам ответить", как будто он сейчас сбегает куда надо, выяснит маршрут , вернётся подготовленный и всё объяснит!
"Вот мы берём морковь", "Вот мы завязываем шнурок", "Мы обжариваем курицу", "Мы откручиваем пробку", "Сейчас мы попробуем" и главное пробует в одну харю и т.д., и т.п.
Сижу, в ящике идёт "Битва шефов": ну да идёт и идёт на фоне - меня не парит. Местами интересно.
И каждый первый о себе говорит: "Мы". Это не только кстати в этой передаче. Блоггеры и прочая бестия, через одного так говорят, когда что-то там делают в полном одиночестве.
"Мы" - это кто мы? Чувак, оглянись, ты один там делаешь что-то в кадре. Биполярочка? Ну сажи: Я закидываю в горшок курицу ( или что ты там закидываешь ). Или: Я откручиваю крышку и наливаю лимонад. Нет, обязательно скажет: "Мы откручиваем и ..."
Ладно, "Мы" пошли на кухню, поставим кофемашину на заварку. Кофе охота "Нам" в одиночестве попить.
