Обратно проследяване на черна дупка

Рано или късно всеки разработчик се сблъсква с това, защото случайно създаването на такъв регулярен израз е по-лесно от лекото.

Типична ситуация е, когато регулярният израз засега работи нормално и изведнъж, върху някакъв текст, интерпретаторът започва да "виси" и има 100% от процесора.

Нашият контур ще бъде както следва:

  1. Нека първо разгледаме проблема в реална ситуация.
  2. След това ще опростим реалната ситуация до "корените" и ще видим откъде идва.

Помислете за HTML търсене например.

Искаме да намерим тагове с атрибути, тоест съвпадения на формата .

Най-лесният начин да направите това е] *>. Но също така не е съвсем правилно, тъй като тагът може да изглежда по следния начин: "href =" # ">. Тоест, в атрибута" quoted "може да има символ>. Най-простият regexp ще спре на него и ще намери .

И ни трябва целият етикет.

За да се справите правилно с подобни ситуации, трябва да ги отчетете в регулярния израз. Ще изглежда така .

Ако се преведе на езика на регулярни изрази, тогава:

  1. - началото на маркера
  2. (\ s * \ w + = (\ w + | "[^"] * ") \ s *) * - произволен брой двойки от формата дума = стойност, където„ стойност “може да бъде и дума \ w +, или цитиран низ "[^"] * " .

Все още не отчитаме всички детайли на HTML граматиката, тъй като са възможни низове в „единични“ кавички, но засега това е достатъчно. Основното е, че регулярният израз се оказа достатъчно прост и разбираем.

Нека тестваме полученият регулярен израз в действие:

Чудесно, всичко работи! Намерих както дълъг маркер "href =" # ">, така и един .

И сега - демонстрация на проблема.

Ако стартирате примера по-долу, той може да замрази браузъра:

Някои регулярни изрази могат да се справят с това търсене за разумен период от време, но повечето не могат.

Какъв е проблема? Защо един прост регулярен израз на такава малка линия „виси“ плътно?

Нека да опростим нещата, като премахнем маркера и възможността да включим цитираните низове:

Това завършва с демонстрация на „практическия пример“ и се преминава към анализ на случващото се.

Обратно проследяване

Като още по-прост регулярен израз, помислете за (\ d +) * $ .

В повечето двигатели на регулярни изрази, например в Chrome или IE, това търсене отнема много дълго време (внимавайте, може да „замрази“ браузъра):

Какво става, какво не е наред с regexp?

Внимателен читател, който го погледне, вероятно ще бъде изненадан, защото е „някак странен“. Тук кванторът * изглежда ненужен.

Ако искате да намерите номер, можете също толкова добре да търсите \ d + $ .

Да, този регулярен израз е изкуствен, но след като се справихме с него, ще разберем практическия пример, даден по-горе. Причината да са бавни е същата.

Като цяло синтаксисът е съвсем приемлив с regexp "всичко е така". Проблемът е как се извършва търсенето по него.

Нека да видим какво се случва, когато търсим в низ 123456789z: