java中的正则表达式中的无限循环

Question

我的目的是匹配这种不同的网址:
url.com
my.url.com
my.extended.url.com
a.super.extended.url.com
等等......

所以,我决定构建正则表达式,在网址的开头和结尾有一个字母或数字,并且有一个包含字母数字字符和点的无限数量的"子域".例如,在"my.extended.url.com"中,"my"中的"m"是正则表达式的第一个类,"com"中的"m"是正则表达式的最后一个类,而"y.", "扩展".和"网址".是正则表达式的第二类.

使用下面代码中的模式和主题,我希望find方法返回false,因为此url必须不匹配,但它使用100%的CPU并且似乎保持无限循环.

    
    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);