Catastrophic backtracking в регулярных выражениях

[@nailyangazov]

Полезное напоминание, спасибо. Как раз недавно «нырял» в регулярки, после праздников опять :)

[@edelweard]

Вот очень классная статья по регекспам. Рассматривается, в частности, и описанная проблема, а также имплементация регекспов с помощью конечного автомата: swtch.com/~rsc/regexp/regexp1.html

[@Bas1l]

И вот заодно дико классная классическая книжка по регекспам и не только. Помимо прочего, рассказывают, почему нельзя парсить Html с помощью regex: en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation

[@leron]

Почему нельзя парсить html регулярками — это сюда stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 :)

[@Pastafarianist]

Спасибо за ссылку, это великолепно :)

[@tenshi]

интересно, есть где-нибудь перевод? а то тыкать новичков в английский текст бесполезно…

[@gnomeby]

Можете ли вы в двух словах сказать почему?

[@leron]

Если строго, то html по классификации Хомского принадлежыт к типу 2 (контекстно-свободные), в тоже время регулярки — 3 тип. То есть html нельзя описать (а значит и пропарсить) с помощью regexp.

[@gnomeby]

Я так понимаю, здесь потерялась частица не?

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

[@gnomeby]

А, нет, википедия не врёт, просто неправильно прочитал.

[@lega]

Я думаю что regexp применяют к html в случае когда нужно выкусить кусок текста, а не пропарсить весь документ. В таком применении он бывает удобнее чем html/xml парсеры.

[@akzhan]

другой инструмент.

[@Dragonizer]

Было на Хабре с подробными объяснения, что плохо и как надо.
Атомарная группировка, или Ни шагу назад!

Вот несколько цитат оттуда, чтобы показать, что речь о том же.

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

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

Далее выписываются рассуждения гипотетического Ивана и составленное им регулярное выражение.

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

и регекс с ними со всеми справляется как положено. Довольный, Иван показывает решение интервьюеру. Happy end, занавес? Но почему статья названа так, как она названа??
Интервьюер спрашивает, что должен (если должен) найти регекс в следующей цепочке:
(you're gonna fail sonny unless you correct it (your regex)
Прочитав и побледнев, Ванюша, тем не менее, не моргнув глазом отвечает, что, раз 1-я скобка нигде не закрывается, регекс должен найти 2-ю пару скобок: (your regex). Его просят проверить. Иван вбивает эту цепочку в свой проверочный скрипт

Проверив синтаксис, Иван запускает скрипт и… и ничего не происходит, скрипт как будто «зависает». Не говорит ни «да», ни «нет». Иван и интервьюер молча смотрят на это секунд 10. За это время Иван из бледного становится ярко-розовым: он уже явно чувствует подвох. Но чтО он сделал не так?? В этот момент лэптоп, на котором был запущен (и до сих пор почему-то не завершился) скрипт, начинает отчетливо гудеть, хотя до тех пор работал бесшумно.

А далее объясняется, как на самом деле работает это регулярное выражение (постоянно отступая назад), и повествуется о пользе атомарных группировок.

[@leron]

Спасибо за линк. Добавил в пост.

[@So1]

Some people, when confronted with a problem, think «I know, I'll use regular expressions.» Now they have two problems.

© Jamie Zawinski

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

[@afaber]

Не обойтись? А чем не устраивает PEG?

[@So1]

Тем, что я не знаю (с настоящего момента — не знал) о его существовании.
Спасибо за наводку — добавил в readlater.

[@Xlab]

А если взять какой-нибудь BusyBeaver в 6 состояний и конвертнуть в регэкспу? :) Надо будет посчитать на досуге.

[@Bas1l]

Мне кажется, это не сразу получится: busy beaver--это пример машины тьюринга; а регекспы описываются конечными автоматами, и уступают в мощности машинам тьюринга. Вот тут про это есть.

[@vics001]

Сначала, хотел написать WTF? Запустил на Java проверил различные варианты и мда… действительно не работает.

Вопрос как же так? Обычная регулярка. Простой Недетерминированный автомат => Детерминированный.
Причем тут бэктрекинг??? В автоматах.

[@msa]

Как видим, время исполнения растет экспоненциально.

только если нет оптимизации для такого случая)

$ time perl -E 'my $s = "a" x 1_000_000; say $s =~ /(a+)*b/'

perl -E 'my $s = "a" x 1_000_000; say $s =~ /(a+)*b/'  0.01s user 0.01s system 85% cpu 0.016 total