StackOverflowError：正则表达式栈溢出错误
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.
“ 如果你有一个问题，用正则表达式解决，那么你现在就有两个问题了。”
问题
最近碰巧遇到了一个使用正则表达式错误！！
我们系统是基于Java语言开发的，其中使用的是JDK8自带的java.util.regex.Pattern类实现正则表达式匹配的。
系统中有一个正则表达式如下。
\{(.|\n)*?\}
其目的是用来区分Json风格字符串与其它字符串的。
但在实际使用中，当传入一个较长的Json字符串时，却发生了如下的错误。
Exception in thread "main" java.lang.StackOverflowError
at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4845)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
at java.util.regex.Pattern$BranchConn.match(Pattern.java:4570)
at java.util.regex.Pattern$CharProperty.match(Pattern.java:3779)
at java.util.regex.Pattern$Branch.match(Pattern.java:4606)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4849)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
at java.util.regex.Pattern$BranchConn.match(Pattern.java:4570)
at java.util.regex.Pattern$CharProperty.match(Pattern.java:3779)
at java.util.regex.Pattern$Branch.match(Pattern.java:4606)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4849)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
at java.util.regex.Pattern$BranchConn.match(Pattern.java:4570)
at java.util.regex.Pattern$CharProperty.match(Pattern.java:3779)
at java.util.regex.Pattern$Branch.match(Pattern.java:4606)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
...
...（非常多行）
分析
通过观察，我们知道这是一个虚拟机 栈溢出 错误。
Java语言中每个线程（Thread）的栈大小是有限制的，每一次函数调用都会生成一个栈帧（Frame），占用一定的栈空间，当栈空间被消耗完虚拟机就会报出StackOverflowError。
再仔细地观察，发现栈信息中显示调用层次非常多，而且类名与代码行重复出现，这意味着栈帧是由递归调用产生的。
到这里，问题发生的原因己经基本可以确定了。
在Java中正则表达式的产生了递归调用，而传入的长Json字符串导致函数调用层次太多，超过虚拟机预设的栈空间，因此，出现了StackOverflowError。
追根溯源
然而，以上的解释纯粹是现象+经验的推断，显然不能满足我的好奇心。
所以，我略略又研究了一下Java正则表达式部分功能的实现。
Java语言在做正则表达式匹配时，首先要进行编译。
使用java.util.regex.Pattern类的compile方法，编译的过程相当于把正则表达式
\{(.|\n)*?\}
转换类似下图的数据结构。
实际编译后的对象结构更复杂些，如下图。
上图每个节点的类型都继承自Pattern$Node类，实现了match方法（即使没有重写方法，也有默认实现）。
当进行字付串匹配时，java.util.regex.Matcher的matches方法会调用第一个节点的match方法，继而形成递归调用链。
正如上面编译后的表达式，有一个以LazyLoop为启始的循环引用，当字符串的每个字符进行匹配时，都产生如下的栈结构。
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
at java.util.regex.Pattern$BranchConn.match(Pattern.java:4570)
at java.util.regex.Pattern$CharProperty.match(Pattern.java:3779)
at java.util.regex.Pattern$Branch.match(Pattern.java:4606)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4849)
由于传入的字符串很长，因此递归调用的层次太多，很快便耗尽线程的栈空间（可以用-Xss配置），接着虚拟机就报出了StackOverflowError错误。
改进
知道了问题，我们着手进行改进。
修改正则表达式如下。
\{[\w\W]*\}
这样，编译后的表达式结构变成为。
而在Pattern$Curly中的match方法使用的是while循环查找而非递归，因此，不会造成栈溢出。
总结
关于正则表达式及其优化，讲解的比较好的链接如下，这里不再赘述。
其中有一点与我这个场景是有关系的。
留意选择（Beware of alternation）
类似“(X|Y|Z)”的正则表达式有降低速度的坏名声，所以要多留心。首先，考虑选择的顺序，那么要将比较常用的选择项放在前面，因此它们可以较快被匹配。另外，尝试提取共用模式；例如将“(abcd|abef)”替换为“ab(cd|ef)”。后者匹配速度较快，因为NFA会尝试匹配ab，如果没有找到就不再尝试任何选择项。……
这一点其实不难理解，表达式编译后 (X|Y|Z) 其实是一个数组，从前到后依次进行匹配。
因此，在Java中写正则表达式最重要的还是：
减少分组与嵌套
如果你实际并不需要获取一个分组内的文本，那么就使用非捕获分组。例如使用“(?:X)”代替“(X)”。
