Когда проблема слишком сложна для регулярного выражения?

Question

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

Например: почему полная проверка электронной почты слишком сложна для регулярного выражения?

Answer 1

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

(())()

Совпадают ли все открытые парены с близкими?

Очевидно, что когда мы смотрим на это как на людей, мы можем легко увидеть, что ответ «да». Однако никакое регулярное выражение не сможет надежно ответить на этот вопрос. Для выполнения такого рода обработки вам понадобится полный пуш-автомат (например, DFA со стеком). Это чаще всего встречается в виде синтаксического анализатора, такого как сгенерированный ANTLR или Bison.

Answer 2

Несколько вещей, на которые стоит обратить внимание:

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

регулярные выражения, насколько я их люблю, не хороши в этих трех вещах. И помните, будьте проще! Если вы пытаетесь построить регулярное выражение, которое делает «все», то вы, вероятно, делаете это неправильно .

Answer 3

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

Answer 4

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

Возьмите адреса электронной почты (согласно вашему примеру). Это простое регулярное выражение (взятое из друзей RegEx) соответствует 99% всех электронных писем:

\b[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}\b

Это коротко и точно, и вы редко будете сталкиваться с проблемами с ним. Однако, как отмечает автор сообщения RegEx, если ваш адрес электронной почты находится в редком домене верхнего уровня ".museum", он не будет принят.

Чтобы правильно сопоставить все адреса электронной почты, необходимо придерживаться стандарта, известного как RFC 2822 . В нем описывается множество способов форматирования адресов электронной почты, и это чрезвычайно сложно.

Вот пример регулярного выражения, пытающегося придерживаться RFC 2822:

(?:[a-z0-9!#$%&'*+/=?^_`{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_`{|}~-]+)*|"
(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|\\[\x01-\x09\x0b\x
0c\x0e-\x7f])*")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9]
(?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.)
{3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\x01-\x08
\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])

Это, очевидно, становится проблемой уменьшения прибыли. Лучше использовать легко поддерживаемую реализацию, которая соответствует 99% адресов электронной почты, а не монструозной, которая принимает 99,9% из них.

Регулярные выражения - отличный инструмент для ваших инструментов программистов, но они не являются решением всех ваших проблем с анализом. Если вы обнаружите, что ваше решение RegEx начинает становиться чрезвычайно сложным, вам нужно либо попытаться логически разбить его на более мелкие регулярные выражения для соответствия частям вашего текста, либо вам нужно начать искать другие методы для решения вашей проблемы. Точно так же есть просто проблемы, которые Регулярные выражения, в силу их природы, не могут решить (как сказал один из авторов, не придерживаясь Regular Language ).

Answer 5

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

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

По сути, вы далеко зайдете своими регулярными выражениями, если начнете думать о «балансировочных группах» (функция вычитания групп захвата .NET) или о «рекурсии» (Perl 5.10 и PCRE).

Answer 6

Вот хорошая цитата Рэймонда Чена:

Не заставляйте регулярные выражения делать то, что они не умеют делать. Если вы хотите сопоставить простой шаблон, то сопоставьте простой шаблон. Если вы хотите заниматься математикой, то занимайтесь математикой. Как сказал комментатор Мориц: «Хитрость заключается не в том, чтобы тратить время на разработку комбинированного молотка / отвертки, а просто в использовании молотка и отвертки».

Источник

Answer 7

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

Добавьте к смеси расширения Perl, обратные ссылки и т. Д., И вскоре у вас будет парсер, который трудно читать, трудно модифицировать и трудно рассуждать о его свойствах (например, есть ли вход, с которым этот парсер будет работать в экспоненциальное время).

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

Answer 8

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

Answer 9

Наряду с потрясающими выражениями, существуют принципиальные ограничения для слов, которые могут быть обработаны с помощью регулярного выражения. Например, вы не можете не написать регулярное выражение для слова, описанного n символами a, тогда n символами b, где n может быть любым, более строго .

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

Answer 10

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

• Разбор HTML
• Подтверждение адреса электронной почты
• Языковые парсеры

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

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

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