java - 匹配正则表达式时程序永远运行

Question

我不知道为什么，但是当我尝试运行这个程序时，它看起来会永远运行下去。

package fjr.test;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Test3 {

    public static void main(String[] args){

        String regex = "dssdfsdfdsf wdasdads dadlkn mdsds .";

        Pattern p  = Pattern.compile("^([a-zA-Z]+ *)+$"); 

        Matcher match =  p.matcher(regex); 

        if(match.matches()){
            System.out.println("Yess"); 
        }else{
            System.out.println("No.. "); 
        }

        System.out.println("FINISH..."); 
    }

}

我需要做的是匹配包含一堆仅由空格分隔的单词的模式

Answer 1

您的程序可能遇到了所谓的灾难性回溯。

如果您有一点时间，让我们看看您的正则表达式是如何工作的...

_{快速复习:正则表达式的工作原理:状态机始终从左到右读取，必要时回溯。}

在左侧，我们有我们的模式:

/^([a-zA-Z]+ *)+$/

这是要匹配的字符串:

dssdfsdfdsf wdasdads dadlkn mdsds .

在 regex101 调试器中，您的正则表达式执行了 78540 步失败。这是因为您使用了贪婪 和非所有格(回溯) 的量词。

...长话短说，因为输入字符串匹配失败，正则表达式中的每个量词都会导致无限回溯 - 每个字符都从+ 然后 * 然后两者，然后从 ()+ 释放一组以回溯更多。

以下是您应该遵循的一些解决方案:

避免大量的量词!

如果您修改表达式，您会发现该模式在逻辑上与以下内容相同:

/^[a-zA-Z]+( +[a-zA-Z]+)*$/

这使用逻辑归纳的步骤来减少楼上的正则表达式以更快地匹配远，现在是97步!

尽可能使用所有格量词!

正如我提到的，/^([a-zA-Z]+ *)+$/ 是邪恶的，因为它以一种可怕的方式回溯。我们在 Java 中，我们能做什么？

此解决方案仅适用于 [a-zA-Z] 和 匹配不同的项目。我们可以使用所有格组!

/^([a-zA-Z]++ *+)++$/
            ^  ^  ^

这些简单的“+”表示“如果我们从这里匹配失败，我们不会回溯”。这是一个非常有效的解决方案，并且消除了对回溯的任何需求。只要你有两个不同的组，中间有一个量词，就使用它们。如果您需要一些关于有效性的证据，这里是我们的记分卡:

另请阅读:

• The Stack Overflow Regex Reference
• ReDoS - Wikipedia

在线演示:

• RegEx demo 1
• RegEx demo 2