Java regex正则表达式类似死循环问题

深藏阁楼爱情的钟 2022-06-09 10:27 411阅读 0赞

Java regex正则表达式类似死循环问题,详见：http://bugs.sun.com/bugdatabase/view\_bug.do?bug\_id=6988218  
这个问题其实是由于正则表达式很复杂时，java regex复杂度过高（复杂度成指数级），导致类似死循环的问题。  
  
  
测试代码：  
//

public static void main(String[] args) {
    		long begin = System.currentTimeMillis();
    		System.out.println("begin!");
    		//Pattern pattern = Pattern.compile("^([+-]?((0[xX](\\p{XDigit}+))|(((\\p{Digit}+)(\\.)?((\\p{Digit}+)?)([eE][+-]?(\\p{Digit}+))?)|(\\.((\\p{Digit}+))([eE][+-]?(\\p{Digit}+))?)))|[n|N]?'([^']*(?:'')*[^']*)*')");
    		//可以简化成下面这样的，注意  \p、XDigit、Digit之类的是java regex才有的语法
    		Pattern pattern = Pattern.compile("^('([^']*(?:'')*[^']*)*')");
    	    Matcher matcher = pattern.matcher("'%)) order by ANGEBOT.ID");
    	    System.out.println(matcher.find());
    	    
    	    long end = System.currentTimeMillis();
    	    System.out.println((end-begin)/1000+"s used!");
    	    System.out.println("finished!");
    	}

# 考虑解决方案： #

1.  native调用c++方法

2. 调用python或perl代码（exec调用方式，linux开一个进程去执行，这样效率可想而知。。。）

3.考虑优化正则表达式（事后证明是最有效的解决方案，哈哈）

# 测试用例： #

尝试了几种方法，下面的我测试的一些结论，用下面的2组字符串来测试：

第1组：  
text="'%)) order by ANGEBOT.ID";    
regex ="^('(\[^'\]\*(?:'')\*\[^'\]\*)\*')";    
  
  
第2组：  
text = "%)) ERROR: JDWP Unable to 2";  
regex = "(\[^'\]\*)\*'";

# 测试结果： #

java:2个例子都会跑死。。。超过3天,执行时间跟text字符串的长度基本上成指数级增长

python:2个例子都会跑死。。。超过3天，而且python更慢

c++11:用Microsoft Visual Studio 2010， 2个例子瞬间跑完（<10ms），可惜最新的g++4.7都还没有完全实现regex模块功能...

c++ boost:2个例子，regex库跑会内存栈溢出。。。

perl:2个例子瞬间跑完（<10ms）

c pcre/c++ pcre++:2个例子瞬间跑完（<10ms）