my.oschina.net/leejun2005/blog/486584
正则可以看做一门DSL，但它却应用极其广泛，可以轻松解决很多场景下的字符串匹配、筛选问题。同时呢有句老话：
“如果你有一个问题，用正则表达式解决，那么你现在就有两个问题了。”
Somepeople,whenconfrontedwithaproblem,think“Iknow,I’lluseregularexpressions.”Nowtheyhavetwoproblems.
今天我们就来聊聊Java正则表达式StackOverflowError的问题及其一些优化点。
1、问题
最近，有同事发现一段正则在本地怎么跑都没问题，但是放到Hadoop集群上总会时不时的抛StackOverflowError。
代码我先简化下：
packagejava8test;
importjava.util.regex.Matcher;
importjava.util.regex.Pattern;
publicclassTest{
publicstaticvoidmain(String[]args){
finalStringTEST_REGEX="([=+]|[s]|[p{P}]|[A-Za-z0-9]|[u4E00-u9FA5])+";
StringBuilderline=newStringBuilder();
System.out.println("++++++++++++++++++++++++++++++");
for(inti=0;i<10;i++){
line.append(
}
line.append("00111111111111111111111111111");
Patternp_a=null;
try{
p_a=Pattern.compile(TEST_REGEX);
Matcherm_a=p_a.matcher(line);
while(m_a.find()){
Stringa=m_a.group();
System.out.println(a);
}catch(Exceptione){
//TODO:handleexception
System.out.println("linesize:"+line.length());
执行之后的结果是：
++++++++++++++++++++++++++++++
Exceptioninthread"main"java.lang.StackOverflowError
atjava.util.regex.Pattern$Loop.match(UnknownSource)
atjava.util.regex.Pattern$GroupTail.match(UnknownSource)
atjava.util.regex.Pattern$BranchConn.match(UnknownSource)
atjava.util.regex.Pattern$CharProperty.match(UnknownSource)
......
起初这个问题是从集群上抛出来的，大家可以看到这个异常有两个特点：
（1）不可用Exception捕获，因为Error直接继承自Throwable而非Exception，所以即使你要捕获也应当捕获Error。
（2）另外一点是大家可以看到抛出的错误并没有指明行号，当这段代码混在一个数百行的工具类，有数十条类似的正则的时候，无疑给定位问题带来了难度，这就需要我们能有一定的单元测试能力。
注：
（1）如果你的环境没有抛出上述错误，尝试调大for循环的次数或者指定jvm参数：-Xss1k
2、问题分析
正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。两类引擎要顺利工作，都必须有一个正则式和一个文本串。DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。
DFA与NFA机制上的不同带来5个影响：
1.DFA对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应用广泛，当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。
2.只有NFA才支持lazy和backreference等特性；
3.NFA急于邀功请赏，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；DFA则是“最长的左子正则式优先匹配成功”。
4.NFA缺省采用greedy量词；
5.NFA可能会陷入递归调用的陷阱而表现得性能极差。
在使用正则表达式的时候，底层是通过递归方式调用执行的，每一层的递归都会在栈线程的大小中占一定内存，如果递归的层次很多，就会报出stackOverFlowError异常。所以在使用正则的时候其实是有利有弊的。
Java程序中，每个线程都有自己的StackSpace。这个StackSpace不是来自Heap的分配。所以StackSpace的大小不会受到-Xmx和-Xms的影响，这2个JVM参数仅仅是影响Heap的大小。StackSpace用来做方法的递归调用时压入StackFrame。所以当递归调用太深的时候，就有可能耗尽StackSpace，爆出StackOverflow的错误。StackSpace的大小随着OS，JVM以及环境变量的大小而发生变化。一般说来默认的大小是512K。在64位的系统中，这个StackSpace值会更大。一般说来，StackSpace为128K是够用的。这时你说需要做的就是观察。如果你的程序没有爆出StackOverflow的错误，可以使用-Xss来调整StackSpace的大小为128K。（eg：-Xss128K)
下面我们要做的就是了解一些正则性能的优化点，规避这种深层次的递归调用。
3、Java正则的一些优化点
3.1Pattern.compile()预编译表达式
如果在程序中多次使用同一个正则表达式，一定要用Pattern.compile()编译，代替直接使用Pattern.matches()。如果一次次对同一个正则表达式使用Pattern.matches()，例如在循环中，没有编译的正则表达式消耗比较大。因为matches()方法每次都会预编译使用的表达式。另外，记住你可以通过调用reset()方法对不同的输入字符串重复使用Matcher对象。
3.2留意选择（Bewareofalternation）
类似“(X|Y|Z)”的正则表达式有降低速度的坏名声，所以要多留心。首先，考虑选择的顺序，那么要将比较常用的选择项放在前面，因此它们可以较快被匹配。另外，尝试提取共用模式；例如将“(abcd|abef)”替换为“ab(cd|ef)”。后者匹配速度较快，因为NFA会尝试匹配ab，如果没有找到就不再尝试任何选择项。（在当前情况下，只有两个选择项。如果有很多选择项，速度将会有显著的提升。）选择的确会降低程序的速度。在我的测试中，表达式“.*(abcd|efgh|ijkl).*”要比调用String.indexOf()三次——每次针对表达式中的一个选项——慢三倍。
3.3减少分组与嵌套
如果你实际并不需要获取一个分组内的文本，那么就使用非捕获分组。例如使用“(:X)”代替“(X)”。
总结下来就是：减少分支选择、减少捕获嵌套、减少贪婪匹配
4、解决方案
4.1临时工方案
try…catch…/增加-Xss，治标不治本，不推荐。
4.2优化正则才是王道
4.2.1语法层面优化
根据3.2提到的，我们这样优化下：
finalStringTEST_REGEX="([=+sp{P}A-Za-z0-9u4E00-u9FA5])+";
4.2.2业务逻辑层面优化
由于我不清楚作者的业务场景，不好做业务优化，总的原则是当你的正则太复杂的时候，可以考虑逻辑拆分，或者部分不走正则，如果把正则当做万能工具可能会得不偿失。
总结：在字符串查找与匹配领域，正则可以说几乎是“万能”的，但是许多场景下，它的代价不容小觑，如何写出高效率、可维护的正则或者怎么能避开正则都是值得咱们思考的问题。
5、NFA引擎正则性能优化Tips
1.优先选择最左端的匹配结果
2.标准量词优先匹配
比如’.*[0-9][0-9]‘来匹配字符串”abcd12efghijklmnopqrstuvw”，这时候的匹配方式是‘.*’先匹配了整行，但是不能满足之后的两个数字的匹配，所以‘.*’就退还一个字符‘w’，还是无法匹配，继续退还一个‘v’，循环退还字符到‘2’发现匹配了一个，但是还是无法匹配两个数字，所以继续退还‘1’
3.谨慎使用捕获性括号()，选择使用非捕获性括号(:expression)
捕获性括号需要消耗一部分内存
4.使用字符组代替分支（替换）条件
例如用[a-d]代替a|b|c|d避免不必要的回溯
5.不要滥用字符组（单个字符时不要用字符组）
.代替[.]
6.使用锚点^$b加速定位
7.从两次中提取必须元素
a{2,4}写成aa{0,2}
8.提取多选结构开头的相同字符
the|this改成th(:e|is)
9.选择字符串中最常出现的字符串放到分支最前面
10.能懒则懒，不要贪婪
在*＋｛m，n｝后面加上问好？就会变成非贪婪模式
总结：引用CFC4N大牛的一句话滥用.点号*星号+加号()括号是不环保，不负责任的做法！
11.简单字符串处理应避免使用正则表达式
Refer：
[1]关于Java正则引起的StackOverFlowError问题以及解决方案
[2]Java正则与栈溢出
[3]优化Java中的正则表达式
[4]从一个正则表达式造成的StackOverflowError说起
[5]正则表达式（三）：Unicode诸问题（下）
[6]StackOverflowErrorwhenmatchinglargeinputusingRegEx
[7]try/catchonstackoverflowsinjava
[8]Java正则达式引起死循环问题解决办法
[9]JAVA正则表达式的溢出问题及不完全解决方案
[10]NFA引擎正则优化TIPS、Perl正则技巧及正则性能评测方法