Регулярные выражения php что это

Регулярные выражения. Всё проще, чем кажется

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

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

Содержание

Что такое регулярка и с чем ее едят?

Где писать регулярки?

Самые простые регулярки

Специальные символы квантификаторов

Lookahead и lookbehind (опережающая и ретроспективная проверки)

Регулярные выражения в разных языках программирования

Что такое регулярка и с чем ее едят?

Если по простому, регулярка- это некий шаблон, по которому фильтруется текст. Мы можем написать нужный нам шаблон (регулярку) и таким образом искать в тексте необходимые нам символы, слова и т.д. Также их используют, например, при заполнении поля E-mail на различных сайтах, т.е. создают шаблон по типу: someEmail@gmail.com. Это я взял как пример, не более. Теперь, разобравшись, что это, приступим к изучению. Обещаю, скучно не будет)

Где писать регулярки?

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

Сразу дам ссылку на сайт, чтобы вы могли уже писать вместе со мной https://www.regextester.com/

Коротко о том, как пользоваться сайтом. Сверху, в графе Regular Expression вы пишете само регулярное выражение, а под ним, в графе Test String вы пишете строку, которую вы хотите фильтровать. Если были найдены соответствия между регулярным выражением и текстом, в тексте эти соответствия будут помечены синим цветом, вы их сразу увидите, даже не сомневайтесь.

Самые простые регулярки

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

Пример регулярки

Вот и всё, надеюсь вы поняли регулярные выражения, спасибо за внимание.

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

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

Квантификаторы

Понимаю, звучит страшно, но на деле все просто. Сейчас разберемся.

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

— символ повторяется ровно n раз

— символ повторяется в диапазоне от m до n раз

— символ повторяется минимум m раз (от m и более)

Почему же он взял еще ssss? Он взял не совсем его, а лишь его часть, так как в нем тоже есть 3 буквы s подряд. Дело в том, что регулярка не будет учитывать, отдельное это слово или нет. Пробелы тоже идут как символы! Поэтому будет выбран любой фрагмент, которому соответствует 3 идущие подряд буквы s

Интересный момент получается, он выбрал все. Почему же? Ответ: та же ситуация, что и в прошлый раз. Он увидел ssss, взял 3 идущие подряд s вместе и еще одну s, которая рядом, ведь она тоже соответствует регулярку (а ведь мы помним, что мы указали диапазон от одного до трех раз)

Ну и напоследок, давайте напишем шаблон, где символ s будет повторяться минимум три раза. Для этого напишем следующее: s ( <3,>обозначает, что символ s будет повторяться от трех раз и до бесконечности).

Специальные символы квантификаторов

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

Давайте разбираться. Начнем со знака вопроса. Допустим у нас есть строка colour color и мы хотим найти либо colour, либо color. Мы можем написать так: colou?r.

Давайте изменим строку и напишем что-то по типу colouuuuur color. И допустим мы хотим указать, что u должен либо не быть, либо быть сколько угодно раз. Для этого мы можем написать colou*r.

То есть либо u у нас нет, либо повторяется много раз.

Символ + работает почти также, за исключением того, что символ должен повторяться минимум 1 раз. То есть в данном случае слово color не будет соответствовать, так как там u не присутствует (то есть повторяется 0 раз, а у нас символ должен повторяться минимум 1 раз)

Специальные символы

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

Поговорим об одиночном символе. Это значит, что будет выбираться любой символ, который повторяется только один раз. Например, вернемся к нашей строке Some text и выберем букву t, после которой идет любой символ. Для этого напишем t.

Выберется te, так как после t идет один любой символ (в данном случае е)

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

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

Перейдем к экранированию. Звучит страшно, но на деле все проще простого. Например, в тексте some text. мы хотим выделить точку. Но ведь точка у нас уже зарезервирована как специальный символ (напоминаю, точка обозначает любой одиночный символ). И чтобы сделать так, чтобы точка на считалась как спец. символ мы можем написать \. и тем самым говоря, что точка у нас будет как обычный символ.

Теперь идут, простые вещи. \d у нас обозначает любую цифру. Например в тексте some text123, если написать \d у нас будут выделяться только цифры.

\D делает все наоборот: берутся все символы, кроме цифр. То есть, если написать \D будет браться все, кроме цифр (и пробелы, кстати, тоже).

\w берет буквы, а \W берет, все, кроме букв (в том числе и пробелы).

Теперь расскажу про еще одно применение символа ^. Его можно использовать как отрицание, тем самым исключая символ или группу символов. Например, в слове test мы хотим выбрать все, кроме буквы t и для этого мы можем написать так: [^t]

Именно в такой последовательности символ ^ будет обозначать отрицание.

Lookahead и lookbehind (опережающая и ретроспективная проверки)

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

Также мы можем сделать наоборот и выбрать символ s, если после него НЕ идет символ d. Для этого вместо знака равно мы должны поставить восклицательный знак (!), т.е. написать вот так: s(?!d)

Теперь поговорим о lookbehind. Допустим, у нас есть строка s ws ds ts es и мы хотим выбрать символ s, до которого будет символ d. Для этого мы можем написать так: (?

Почему же lookbehind подчеркивается красной линией? Дело в том, что lookbehind не всегда поддерживается и не везде такая регулярка будет работать. Нужно искать способ заменить этот lookbehind, но это зависит от поставленной задачи, поэтому нельзя сказать, как именно ее заменять. Будем надеяться, что в скором временем будет полная поддержка этой возможности.

Чтобы сделать наоборот, то есть выбрать все символы s, до которых НЕ будет идти символ d, нужно опять же поменять знак равно на восклицательный знак: (?

Регулярные выражения в разных языках программирования

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

Здесь мы создаем строку с текстом, который хотим проверить, создаем объект класса Regex и в конструктор пишем нашу регулярку (как я и говорил, я не буду заострять внимание на том, что такое объект класса и конструктор). Потом создаем объект класса MatchCollection и от объекта regex вызываем метод Matches и в параметры передаем нашу строку. В результате все сопоставления будут добавляться в коллекцию matches.

Java

Здесь похожая ситуация. Создаем объект класса Pattern и записываем нашу строку. CASE_INSENSITIVE означает, что он не привязан к регистру (то есть нет разницы между заглавными и строчными символами). Создаем объект класса Matcher и пишем туда регулярку.

JavaScript

Здесь тоже все просто. Вы создаете объект regex и пишете туда регулярку. И затем просто создаете объект matches, который будет являться коллекцией и вызываете метод exec и в параметры передаете строку.

Заключение

Итак, мы разобрали, что такое регулярные выражения, где они используются, как их писать и использовать в контексте языков программирования. Скажу сразу, написание регулярок приходит с опытом. Практикуйтесь, и я уверен: все у вас получится! А на этом я с вами прощаюсь. Спасибо за внимание и приятного всем дня)

Источник

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

Чтобы найти в строке какое-то совпадение, достаточно просто записать это совпадение внутри двух слэшей.

Её использование выглядит следующим образом:

Давайте приведём пример. Найдём, слово «век» в строке «человек».

Для того, чтобы быстрее составлять регулярки, есть онлайн-сервисы. Они позволяют не переписывать шаблон и запускать каждый раз код, а делать всё это прямо в браузере. Я неоднократно пользовался сервисом https://regex101.com/ и вам его рекомендую.

Я ввёл в шаблон «/ку/» и строку «кукушка». В результате получил 2 совпадения.

Помимо этого у сервиса есть вкладка «Code generator», на которой вы сразу сможете получить готовый код на PHP для своего примера:

Символы

Давайте теперь перейдём к более интересным примерам.

Давайте найдём такие совпадения для строки «кукушки не кушают шоколадки». Паттерн примет следующий вид: «/к./». То есть буква «к» и любой символ.

Видим, что нашлось немало совпадений. Давайте добавим теперь после точки ещё одну букву «ш».

Теперь совпадения только два.

Нужно найти несколько подряд идущих точек? Да не вопрос! Заэкранируйте их все:

Квантификаторы

Если что-то должно повториться точное число раз, например, 3, то пишется просто <3>.

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

Немного примеров:
Символ точки, повторяющийся от одного и более раз

Восклицательный знак, перед которым либо есть вопросительный знак, либо нет

Модификаторы

Глобальный поиск

А не обратили ли вы внимание на букву g после закрывающего слеша в паттерне?

Видите? Теперь только одно совпадение осталось.

Жадность

Есть ещё один довольно популярный модификатор, который позволяет сделать поиск либо жадным, либо нежадным. Жадный поиск захватывает максимально возможную подстроку. Давайте рассмотрим вот такой пример:

Видите, какую строку захватило? А если бы нам хотелось остановиться на первой букве «к»? Тогда нам просто нужно было бы сделать поиск нежадным. Для этого используется модификатор «U»

В PHP он при этом указывается после закрывающего слеша паттерна:

Вообще, все остальные модификаторы как и «U» указываются после слеша, это только для модификатора g пришлось сделать две разные функции.

Итак, давайте сформулируем основные тезисы по жадности и нежадности:

Классы символов

Очень часто в регулярках возникает потребность в перечислении символов, которые подходят под условия. Например, нужно найти символ двоеточия, после которого идут три цифры. Для таких случаев используют классы символов. Это символы, помещённые в квадратные скобки. Примеры таких классов:

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

Пример: двоеточие, после которого идут три цифры от 0 до 3

Если нужно сделать отрицание, то внутри таких кавычек перед остальными ставится символ «^».

Давайте теперь применим наши уже имеющиеся знания для проверки того, что нам передали корректный российский номер телефона. Пусть у нас будет следующее простое правило: номер должен начинаться с +7, а далее должны идти 10 цифр от 0 до 9.

Якоря в регулярных выражениях

Также нам часто приходится говорить о начале строки. Для этого есть якорь «^».

Несмотря на то, что в строке есть два слова «кукушки», под шаблон попало только первое, так как оно находится в начале строки.

Давайте вернёмся к примеру с телефонами. В прошлый раз мы использовали шаблон «/+76<10>/». Однако, если строка содержит больше цифр в конце, то она просто отбросит лишнее.

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

А корректный попадает:

Многострочный режим

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

«ИЛИ» в регулярках

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

Маски

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

Пример задачи: нужно из строки Меняем автора статьи 123 c «Иван» на «Пётр» извлечь идентификатор статьи и имена авторов.

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

Нагляднее всего это можно увидеть на примере:

Видите, справа у нас появились дополнительные совпадения? В PHP мы можем сделать из этого отдельные переменные!

Делается это проще простого:

Соответственно, нам остаётся лишь определить переменные под всё это дело:

А ещё маске можно дать имя прямо в шаблоне, вот так:

В коде будет выглядеть вот так:

И мы можем получить id статьи вот так:

Ещё один реальный пример

Практически на любом современном сайте все адреса вида: https://php.zone/post/892

Дальше он ищет статью в базе данных с таким идентификатором и возвращает её пользователю.

Это далеко не вся инфа о регулярках, но этого достаточно для 95% решения реальных задач. Забивать голову остальным и упарываться не советую 🙂

Домашка

У вас есть переменная

С помощью регулярных выражений выдерните из этой переменной 2 значения и положите их в переменные:

Источник

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

Что такое регулярные выражения PHP?

Для чего используются регулярные выражения:

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

Теперь рассмотрим практические примеры использования упомянутых выше функций.

Preg match PHP

В приведенном ниже коде показан вариант реализации данного примера:

Preg split PHP

Мы возьмем фразу и разобьем ее на массив; шаблон предназначен для поиска единичного пробела:

Preg replace PHP

Метасимволы

Теперь рассмотрим сложный PHP regexp пример, в котором проверяется валидность адреса электронной почты:

Результат: адрес электронной почты name@company.com является валидным.

Пояснение шаблона «[/^[a-zA-Z0-9._-]+@[a-zA-Z0-9-]+.[a-zA-Z.]<2,5>$/] «

Метасимволы являются полезными, когда речь идет о сопоставлении на соответствие шаблонам.

Заключение

Пожалуйста, оставьте ваши комментарии по текущей теме статьи. Мы очень благодарим вас за ваши комментарии, отклики, лайки, дизлайки, подписки!

Источник

Истинное могущество регулярных выражений

«Ты не можешь парсить HTML с помощью регулярных выражений, потому что HTML не является регулярным. Используй XML парсер, и будет тебе счастье»

Что же на самом деле означает «регулярный»?

В контексте теории формальных языков что-то называется «регулярным», когда оно имеет грамматику, в которой любое правило вывода имеет одну из следующих форм:

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

Эта грамматика говорит о том, что:

В этом примере цифры от 0 до 9 будут терминалами (поскольку их нельзя разбить на составляющие), а N будет единственным нетерминалом (поскольку его можно разделять дальше).

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

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

Что могут описывать регулярные выражения

Итак, возникает закономерный вопрос: регулярные выражения могут описывать только регулярные грамматики, или они способны на большее? Ответом на него будет и да, и нет.

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

Но когда программисты говорят о «регулярных выражениях», они не подразумевают формальные грамматики. Они говорят о производных регулярных выражениях, реализованных в их языках программирования. И эти реализации регэкспов весьма поверхностно связаны с изначальным понятием регулярности.

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

Для сохранения простоты, я сфокусируюсь только на PCRE-реализации регэкспов. Просто потому, что я знаю её лучше всего (поскольку она используется в PHP). Множество прочих реализаций весьма с ней схожи, поэтому большую часть нижеизложенного можно применить и к ним тоже.

Иерархия языков

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

Как видите, она делит формальные языки на четыре типа: регулярные языки (тип 3) — наименее мощные, за которыми следуют контекстно-свободные языки (тип 2), контекстно-зависимые языки (тип 1) и, наконец, всемогущие неограниченные языки (тип 0).

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

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

(Напоминание: когда я говорю «регулярные выражения», я подразумеваю их в программистском смысле, а не в смысле теории формальных языков).

Описание контекстно-свободных языков

Ответ на вопрос выше: да, возможно!

Следовательно, регулярные выражения способны описывать как минимум некоторые не регулярные, контекстно-свободные грамматики. Но могут ли они описать их все? Чтобы ответить на этот вопрос, посмотрим прежде на определение контекстно-свободных грамматик.

В контекстно-свободной грамматике все правила вывода имеют вид:

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

В качестве примера рассмотрим следующую грамматику:

Это отрывок из PHP-грамматики (всего лишь несколько простых правил). Синтаксис немного отличается от того, что мы использовали раньше, но его можно легко понять. Один из аспектов, который стоит отметить, состоит в том, что имена T_SOMETHING здесь также являются терминальными символами. Такие символы обычно называют токенами, они кодируют собой более абстрактные понятия. Например, T_FUNCTION представляет из себя ключевое слово function, а T_STRING — токен-метка (подобно getUserById или some_other_name).

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

Возвращаясь к актуальному вопросу: так могут ли регулярные выражения связывать все контекстно-свободные грамматики? Снова ответ: да!

Это чрезвычайно легко доказать, поскольку регулярные выражения (по крайней мере, PCRE и ему подобные) предоставляют синтаксис для построения грамматик, очень похожий на приведённый выше:

То, что вы видите выше — это регулярное выражение для описания e-mail адреса с помощью RFC 5322. Оно построено с помощью простого преобразования БНФ-правил из RFC в нотацию, которую понимает PCRE.

Синтаксис чрезвычайно прост: все определения правил оборачиваются в DEFINE-утверждение, которое в основном означает, что все эти правила не должны непосредственно чему-то соответствовать, их достаточно просто декларировать. Только часть ^(?&addr_spec)$ в самом конце определяет, что же в конце-концов тут описывается.

Таким образом, приведённый выше синтаксис позволяет просто отобразить грамматику на регулярное выражение:

Единственная загвоздка в том, что регулярные выражения не поддерживают левостороннюю рекурсию. Т.е., если взять приведённое выше определение списка параметров:

Вы не сможете в точности конвертировать его в основанный на грамматике регэксп. Следующее не сработает:

Причина этого в том, что non_empty_parameter_list появляется в крайней левой части своего собственного определения. Это называется левосторонней рекурсией и очень часто встречается в определениях грамматик. Причина в том, что LALR(1) парсеры, которые чаще всего используются для разбора, обычно обрабатывают левостороннюю рекурсию лучше, чем правостороннюю.

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

Теперь должно быть абсолютно ясно, что регулярные выражения способны описывать любой контекстно-свободный язык (и, следовательно, почти все языки, с которыми сталкиваются программисты). Единственная проблема: несмотря на то, что регулярные выражения могут описывать контекстно-свободные грамматики, они обычно не могут разбирать их. Разбор подразумевает преобразование какой-либо строки в абстрактное синтаксическое дерево. Для этого невозможно использовать регулярные выражения, по крайней мере PCRE (хотя, конечно, в Perl’e, где есть возможность вставлять произвольный код в регулярное выражение, вы можете практически всё. ).

А сейчас позвольте мне снова заострить внимание на том, о чём я мимоходом упоминал ранее: синтаксически корректный HTML — контекстно-свободен. Следовательно, вы можете описывать его, используя регулярные выражения, в противовес распространённому мнению. Просто не забывайте о двух вещах: во-первых, большая часть HTML, с которым вы сталкиваетесь, не синтаксически корректная (обычно, она даже не является закрытой). И во-вторых, только то, что вы можете, не означает, что вы должны. Вы можете писать свой софт на Brainfuck, однако существуют причины, почему вы этого не делаете, верно?

Моё мнение по теме таково: где бы вы не нуждались в общей HTML-обработке, используйте DOM-библиотеку на свой вкус. Она правильно обработает некорректный HTML и примет на себя всю тяжесть разбора. С другой стороны, если вы имеете дело со специфическими случаями, то быстрые регулярные выражения часто наилучший выход. И я должен признаться: хотя я обычно говорю людям не разбирать HTML с помощью регулярных выражений, сам я, как известно, делаю это частенько. Просто потому, что часто сталкиваюсь со специфическими ситуациями, когда использовать регэкспы элементарно проще.

Контекстно-зависимые грамматики

Теперь, когда мы подробно рассмотрели контекстно-свободные языки, давайте поднимемся вверх на ещё одну ступеньку в иерархии Хомского: к контекстно-зависимым языкам.

Для них структурные правила будут иметь следующую форму:

Чтобы сделать изложенное более понятным, попробуем интерпретировать следующие правила:

По-русски это будет звучать так:

Заменить `A` на `c`, но только в том случае, если у него имеется `a b` слева.
Заменить `B` на `Q H`, но только в том случае, если у него имеется `a` слева и `c` справа.
Заменить `B` на `C`, но только если у него есть `H` слева.

Контекстно-зависимые языки — это то, что вы редко встретите в «нормальном» программировании. Они более важны в области обработки естественных языков (поскольку естественные языки определённо не являются контекстно-свободными. Слова имеют различное значение в зависимости от контекста). Но даже люди, занимающиеся обработкой естественных языков, работают с так называемыми «мягко контекстно-зависимыми языками», поскольку для моделирования их достаточно, а разбор происходит намного быстрее.

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

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

Чтобы получить понятие, почему обе грамматики имеют одинаковую выразительную силу, посмотрите на следующий пример преобразований:

Ладно, вернёмся к регулярным выражениям. Могут ли они так же описывать и контекстно-зависимые языки?

На этот раз я не смогу вам дать определённого ответа. Конечно, они могут описывать некоторые контекстно-зависимые языки, но я понятия не имею, могут ли они описывать их все.

PCRE-регэксп для этого языка следующий:

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

можно преобразовать в следующее DEFINE-правило регэкспов:

Но факт невозможности прямого преобразования контекстно-зависимой грамматики в регэксп сам по себе не означает, что регулярные выражения на могут описывать их все. Например, приведённый выше язык 0> тоже имеет грамматику, которая требует ретроспективного утверждения переменной ширины. Может быть, что-то подобное возможно и для других контекстно-зависимых грамматик. Я честно не знаю.

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

Неограниченные грамматики

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

Насколько в точности сильны неограниченные грамматики? Настолько, что сильнее их не бывает: они Тьюринг-полны. Существует даже «язык программирования», основанный на неограниченных грамматиках: Thue. Поскольку он Тьюринг-полный, то может делать всё, на что способны остальные языки программирования.

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

К сожалению, я не могу рассказать ещё что бы то ни было о том, как связаны регулярные выражения и неограниченные грамматики. Чёрт, я даже не смог найти пример адекватной неограниченной грамматики (которая не была бы неукорачивающей).

Но сейчас, поскольку мы заговорили о Тьюринг-полноте, перейдём к следующему моменту:

Регулярные выражения с обратными ссылками являются NP-полными

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

Т.е. содержащие вот такой очень простой регэксп:

То, что этот регэксп описывает, называется «языком копий» и является ещё одним типичным примером контекстно-зависимых языков.

Аналогичным образом вы можете описать с помощью обратных ссылок прочие примеры грамматик, приведённые выше:

Объяснение того, как это работает, выходит за рамки данной статьи, но вы можете прочитать об этом прекрасный топик на StackOverflow.

Как видите, простое добавление обратной ссылки (без поддержки рекурсивной подмаски) уже увеличивает силу регулярных выражений. Оно в принципе настолько могущественно, что делает описание регулярными выражениями NP-полной задачей.

Что означает «NP-полная»? NP-полнота — это один из классов в теории сложности вычислений для решения задач, в который впадают многие «тяжёлые» проблемы. Примерами NP-полных задач являются задача коммивояжера (TSP), задача выполнимости булевых формул (SAT) и задача о ранце (BKP).

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

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

Чтобы доказать, что регулярные выражения с обратными ссылками в точности NP-полны, можно просто взять одну из хорошо известных NP-полных задач и доказать, что она может быть решена с помощью использования регулярных выражений. В качестве примера я выбрал 3-CNF SAT задачу.

3-CNF SAT расшифровывается как «Задача выполнимости булевых формул в 3-конъюнктивной нормальной форме» и достаточно проста для понимания. Имеется булева формула следующего вида:

Она состоит из ряда условий, разделённых операторами И. Каждое из этих условий состоит из трёх переменных (или их отрицаний), разделённых операторами ИЛИ. 3-CNF SAT спрашивает: существует ли решение у этой булевой формулы (например, истина)?

Приведённую выше булеву формулу можно преобразовать в следующее регулярное выражение:

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

Подводя итог

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

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

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

Источник