Почему регулярные выражения имеют экспоненциальное время работы?

Можно написать Regex, для которого в некоторых случаях требуется экспоненциальное время работы. Такой пример (aa|aa)*. Если есть вход нечетного числа a, ему требуется экспоненциальное время работы.

Это легко проверить. Если вход содержит только a и имеет длину 51, для вычисления Regex требуется несколько секунд (на моей машине). Вместо этого, если длина ввода равна 52, его вычислительное время не заметно (я тестировал это со встроенным анализатором Regex JavaRE).

Я написал регекс-парсер, чтобы найти причину такого поведения, но я его не нашел. Мой анализатор может построить AST или NFA на основе Regex. После этого он может перевести NFA в DFA. Для этого используется алгоритм построения графиков.

Когда я разбираю Rgex, упомянутый выше, парсер создает NFA с 7 состояниями - после преобразования в DFA осталось только 3 состояния. DFA представляет более разумное Regex (aa)*, которое можно проанализировать очень быстро.

Таким образом, я не понимаю, почему существуют парсеры, которые могут быть настолько медленными. Что является причиной этого? Разве они не переводят NFA в DFA? Если да, почему бы и нет? И каковы технические причины, по которым они так медленно вычисляются?

Ответ 1

Russ Cox содержит очень подробную статью о том, почему это так и история регулярных выражений (часть 2, часть 3).

Согласование регулярных выражений может быть простым и быстрым, используя методы на основе конечных автоматов, которые известны десятилетиями. Напротив, Perl, PCRE, Python, Ruby, Java и многие другие языки имеют реализационные реализации на основе рекурсивного обратного отслеживания, которые просты, но могут быть мучительно медленными. За исключением обратных ссылок, возможности, обеспечиваемые реализациями медленного обратного отслеживания, могут быть реализованы с помощью реализаций на основе автоматов с гораздо более быстрой и стабильной скоростью.

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

Во время написания текстового редактора sam в начале 1980-х годов Роб Пайк написал новую реализацию регулярных выражений, которую Дэйв Преттото извлек в библиотеку, появившуюся в восьмом выпуске. Реализация Pike включала отслеживание подделок в эффективную симуляцию NFA, но, как и остальные источники восьмого издания, не получила широкого распространения. Сам Пайк не понимал, что его техника была чем-то новым. Генри Спенсер обновил интерфейс библиотеки Eighth Edition с нуля, но с помощью backtracking и выпустил его реализацию в общественное достояние. Он стал очень широко использоваться, в конечном итоге послужив основой для медленных реализаций регулярных выражений, упомянутых ранее: Perl, PCRE, Python и т.д. (В его защиту Спенсер знал, что подпрограммы могут быть медленными, и он не знал, что существует более эффективный алгоритм. Он даже предупредил в документации: "Многие пользователи нашли скорость совершенно адекватной, хотя и заменяли внутренности egrep этот код был бы ошибкой".) Реализация регулярного выражения Pike, расширенная для поддержки Unicode, была сделана свободно доступной с sam в конце 1992 года, но особенно эффективный алгоритм поиска регулярных выражений остался незамеченным.

Ответ 2

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

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

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

Я сделал быстрый эксперимент в Perl, и ваше регулярное выражение вычисляет одинаково быстро для нечетного и четного числа a.