sun jdk 6.0.24中的java.util.regex中的错误？

Question

我的系统上有以下代码块.为什么？

System.out.println( Pattern.compile( 
   "^((?:[^'\"][^'\"]*|\"[^\"]*\"|'[^']*')*)/\\*.*?\\*/(.*)$", 
   Pattern.MULTILINE | Pattern.DOTALL ).matcher( 
   "\n\n\n\n\n\nUPDATE \"$SCHEMA\" SET \"VERSION\" = 12 WHERE NAME = 'SOMENAMEVALUE';"
   ).matches() );

模式(旨在检测表单的注释/*...*/但不在其中'或者")应该是快速的,因为它是确定性的...为什么它需要太长时间？

Answer 1

你正在遭遇灾难性的回溯.

看看你的正则表达式,很容易看出如何.*?和(.*)可以匹配相同的内容,因为它们也可以匹配插入的\*/部分(点匹配所有,记住).加上(甚至更有问题),他们也可以匹配相同的东西((?:[^'"][^'"]*|"[^"]*"|'[^']*')*).

正在尝试所有排列时,正则表达式引擎陷入困境,特别是如果您正在测试的字符串很长.

我刚刚在RegexBuddy中检查了你的正则表达式.它在正则表达式引擎的1.000.000步之后中止匹配尝试.Java将继续搅拌,直到它通过所有排列或直到发生Stack Overflow ...

您可以通过禁止回溯已经匹配的内容来极大地提高正则表达式的性能.您可以使用原子组,将正则表达式更改为

^((?>[^'"]+|"[^"]*"|'[^']*')*)(?>/\*.*?\*/)(.*)$

或者,作为Java字符串:

"^((?>[^'\"]+|\"[^\"]*\"|'[^']*')*)(?>/\\*.*?\\*/)(.*)$"

这减少了正则表达式引擎必须经历的步数从> 100万到58.

但请注意,这只会发现第一次出现注释,因此您必须重复应用正则表达式,直到失败为止.

编辑:我刚刚添加了两个对表达起作用很重要的斜杠.但我不得不改变超过6个字符...... :(