Бесконечный цикл в регулярных выражениях в Java

Question

Моя цель состоит в том, чтобы соответствовать таким URL-адресам:
url.com
my.url.com
my.extended.url.com
a.super.extended.url.com
и так далее ...

Итак, я решил построить регулярное выражение так, чтобы в начале и конце URL-адреса присутствовали буква или число, а также иметь бесконечное количество «поддоменов» с буквенно-цифровыми символами и точкой. Например, в «my.extended.url.com» «m» из «my» является первым классом регулярного выражения, «m» из «com» ​​является последним классом регулярного выражения, а «y.», «продлен.» и "URL". являются вторым классом регулярных выражений.

Используя шаблон и тему в приведенном ниже коде, я хочу, чтобы метод find возвращал мне значение false, поскольку этот URL-адрес не должен совпадать, но он использует 100% ЦП и, похоже, остается в бесконечном цикле.

 
    String subject = "www.association-belgo-palestinienne-be";
    Pattern pattern = Pattern.compile("^[A-Za-z0-9]\\.?([A-Za-z0-9_-]+\\.?)*[A-Za-z0-9]\\.[A-Za-z]{2,6}");

    Matcher m = pattern.matcher(subject);
    System.out.println("    Start");
    boolean hasFind = m.find();
    System.out.println("    Finish : " + hasFind);
  

Который только печатает:

  
      Start
  

Я не могу воспроизвести проблему с помощью тестеров регулярных выражений.
Это нормально? Проблема связана с моим регулярным выражением?
Может ли это быть из-за моей версии Java (1.6.0_22-b04 / JVM 64 bit 17.1-b03)?

Заранее спасибо за помощь.

Answer 1

Проблема заключается в части ([A-Za-z0-9_-]+\\.?)* регулярного выражения. Обратите внимание, что у него есть квантификатор (+) внутри другого квантификатора (*). Это вызывает катастрофическое обратное отслеживание - в основном, оно должно пробовать экспоненциальное число совпадений, чтобы проверить регулярное выражение, по крайней мере, способ, которым реализованы большинство механизмов регулярных выражений (включая Java).

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

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

Pattern.compile("^[A-Za-z0-9]\\.?([A-Za-z0-9_-]|[A-Za-z0-9_-]\\.)*[A-Za-z0-9]\\.[A-Za-z]{2,6}$");

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

Answer 2

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

Возможно, это регулярное выражение удовлетворительно (оно заканчивается на данной строке): ^[A-Za-z0-9][A-Za-z0-9_-]*(\\.[A-Za-z0-9_-]+)*\\.[A-Za-z]{2,6}$ (см. http://ideone.com/Z0rlg)

Answer 3

Это на самом деле не бесконечный цикл, а просто действительно длительное время.Для всех практических целей мы можем назвать это зависанием.

Ваш регулярный выражения может быть улучшен.Это скажет, что это конец линии.Это может помочь вам сэкономить время.

Редактировать :

 String subject = "www-association-belgo-palestinienne-be";
 Pattern pattern = Pattern.compile("^[A-Za-z0-9]([-_A-Za-z0-9]*)(\\.[-_A-Za-z0-9]+)*\\.([-_A-Za-z0-9]+\\.)*([-_A-Za-z0-9]*)[A-Za-z0-9]$");

 Matcher m = pattern.matcher(subject);
 System.out.println("    Start");
 boolean hasFind = m.find();
 System.out.println("    Finish : " + hasFind);

Answer 4

См. Как вы отлаживаете регулярное выражение? .

В частности, я бы попробовал regexpal и изменил бы обратные слеши Java на одиночные.

Answer 5

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

, и вы увидите, как быстро это будет оценено