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

Как и большинство программистов, я уже много лет использую простые регулярные выражения / сопоставление с образцом, например «/^Foo(bar).*/», но признаю, что когда мне нужно сложное, например, простое электронное письмо чекер:

/^([a-zA-Z0–9._%-]+@[a-zA-Z0–9.-]+\.[a-zA-Z]{2,6})*$/

  1. Я часто пытался найти правильное регулярное выражение с помощью Google.
  2. У меня было очень поверхностное представление о том, как это работает

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

Букварь по Государственным машинам

Не углубляясь в теорию вычислений, нам нужно понять, что такое конечный автомат или формально детерминированные и недетерминированные конечные автоматы (DFA и NDFA / NFA). При сопоставлении строк в последовательности можно использовать конечные автоматы, которые потребляют входные токены (символы) по одному и поддерживают «состояние» сопоставления. Например, чтобы сопоставить «foo» в предложении «для foobar», вы создаете конечный автомат, как показано ниже:

Пошаговое тестирование «для foobar»:

  • «For» → «f-o» потребляются, но «r» не соответствует конечному состоянию «foo», поэтому он терпит неудачу и возвращается к «start» со следующими токенами
  • «Foobar» → «f-o-o» потребляются и соответствуют конечному состоянию (далее оставляется «bar»)
  • "Bar" ничего не соответствует (ни пробелы)

В результате у нас есть 1 совпадающий «foo» в строке «for foo bar», как и ожидалось. Похоже на примитивный пример, но это суть того, как на самом деле работает механизм регулярных выражений конечного автомата. Имейте это в виду, когда мы перейдем к более практичным правилам регулярных выражений.

Группы токенов

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

  • / foo / - соответствует точной строке «foo»
  • / (foo | bar) / - соответствует либо «foo», либо «bar»
  • / [for] / - соответствует токенам в алфавите {f, o, r} в любом количестве и в любой последовательности, поэтому он будет соответствовать «foo», но также и любому другому алфавиту, например « off »,« roof »и части слова, например« f a r me r ”

Использование [] и () с | являются первыми строительными блоками. Вы можете составлять точные, частичные и комбинации A или B.

Конечный автомат для «foo» уже был готов. «Foo» или «bar» (foo | bar) выглядят так:

Маленький шаг - теперь мы можем сочетать разные струны. Становится интереснее - оставайся со мной!

Основные итераторы

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

  • ? 0 или 1 вхождение
  • + равно 1 или больше
  • * равно 0 или больше
  • {min, max} для точного или диапазона вхождений

Вы также можете использовать [] с ограниченным алфавитом:

  • / [fobar] + / → соответствует foofoobar, но также соответствует foobar и тарабарщине, например fbrar, bfaor с повторами

Вместо этого используйте последовательности символов с группировкой в ​​круглых скобках следующим образом:

  • / (foo)? bar / → соответствует foobar и bar
  • / (foo) * bar / → соответствует bar, foobar, foofoobar
  • / (foo) + bar / → соответствует foobar, foofoobar
  • / (foo) {2} bar / → соответствует foofoobar, но не foobar!
  • / (fo {2}) {2} bar / → также работает для foofoobar!

Диаграмма состояний a / (foo) + bar / matcher:

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

/^([a-zA-Z0–9._%-]+@[a-zA-Z0–9.-]+\.[a-zA-Z]{2,6})*$/

^ и $ - это маркеры начала и конца, но в остальном строка выше должна иметь для вас смысл! Если бы у меня был достаточно большой холст, я бы нарисовал DFA для этой проверки адресов электронной почты :)

Итак, используют ли Perl, Python и Java конечные автоматы?

Ну конечно; естественно! Но интересно то, что они используют NFA, а не DFA - для не-автоматных головок это означает, что шаблон регулярного выражения, такой как / (fork | foo) / в строке «foobar», даст первую диаграмму ниже и потребует глубины -first-search похож на процесс, пробующий 1-й путь, затем 2-й.

Те, кто уже являются гуру автоматов, уже знают, что любую NFA можно преобразовать в DFA, и в этом случае выполнение более эффективно, как показано ниже:

Проблема в том, что если у вас было такое регулярное выражение, как / (fox | for | fob | fog | foo) / - NFA может вычислить f-o-x, затем вернуться назад, чтобы попробовать f-o-r, и т. Д. Выполняя работу в 5 раз больше, чем во втором примере. Кен Томпсон изобрел метод оптимизации во время выполнения, который мы называем NFA Томпсона (но я несколько неправильно назову его DFA).

Реализация Thompson NFA в миллион раз быстрее Perl (для конкретных случаев) - Расс Кокс

Почему его не используют сегодня, обсуждают очень часто (по крайней мере, последние 10+ лет на Reddit и YCombinator) - я подвел итоги 10-летнего обсуждения:

  • Реализации Perl / Python / Java используют обратное отслеживание NFA для включения «обратных ссылок» и других удобных улучшений регулярных выражений, которые не могут быть легко реализованы с помощью конечных автоматов DFA.
  • Реализации Perl-совместимого поиска с возвратом (PCRE) в большинстве случаев достаточно быстры и обладают хорошими функциями удобства использования - даже несмотря на то, что патологические случаи могут сделать его в миллион раз медленнее.
  • Расс Кокс показал еще в 2007 году, что реализация DFA примерно равна O (n) по сравнению с реализациями PCRE, которая составляет O (2 ^ n), где n - количество (a | b) вариантов. Это стало проблемой, которую используют DoS-злоумышленники в онлайн-сервисах, где используется регулярное выражение.
  • Google выпустил RE2 реализацию регулярного выражения с конечным числом состояний DFA 10 лет назад для поддержки своего облачного поиска (частично для борьбы с атаками ReDoS).

Прочие мелочи

  • Команды ls и dir не используют регулярное выражение - они используют «подстановку файлов», которая является шагом раскрытия перед передачей командам.
  • Конечные автоматы - это то, как торговые автоматы используются для подсчета монет с минимальными циклами. Это может выглядеть так, если считать никели, десять центов и четвертинки для подсчета 0,30 доллара:

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

Также обратите внимание, что включенное регулярное выражение электронной почты не соответствует стандартам RFC, реальное занимает несколько страниц, но вот ссылка на него + диаграмма состояний, чтобы показать, насколько это может быть сложно!

использованная литература

  1. Расс Кокс анализ Thompson NFA против Perl (PCRE) - https://swtch.com/~rsc/regexp
  2. Библиотека Google RE2 - https://en.wikipedia.org/wiki/RE2_(software)
  3. Основы Regex, NFA, DFA - https://devopedia.org/regex-engines
  4. Практическое руководство по механике регулярного выражения - https://www.youtube.com/watch?v=rhzKDrUiJVk&t=5s
  5. Простое руководство доктора Брейлсфорда по NFA / DFA Regexp - https://www.youtube.com/watch?v=528Jc3q86F8
  6. Недавняя статья Лучшее программирование при использовании Regexp - https://betterprogramming.pub/7-things-you-should-know-before-using-regular-expressions-in-python-c79305e117d9