正则表达式--递归匹配与非贪婪匹配(2)

递归匹配与非贪婪匹配

的经历：当我们要匹配类似 "<td>内容</td>" 或者 "[b]加粗[/b]" 这样的文本时，我们根据正向预搜索功能写出这样的表达式："<td>([^<]|<(?!/td>))*< /td>" 或者 "<td>((?!</td>).)*</td>"。
当发现非贪婪匹配之时，恍然大悟，同样功能的表达式可以写得如此简单："<td>.*?</td>"。顿时间如获至宝，凡是按边界匹配的地方，尽量使用简捷的非贪婪匹配 ".*?"。特别是对于复杂的表达式来说，采用非贪婪匹配 ".*?" 写出来的表达式的确是简练了许多。
然而，当一个表达式中，有多个非贪婪匹配时，或者多个未知匹配次数的表达式时，这个表达式将可能存在效率上的陷阱。有时候，匹配速度慢得莫名奇妙，甚至开始怀疑正则表达式是否实用。
效率陷阱的产生：
在本站基础文章里，对非贪婪匹配的描述中说到：“如果少匹配就会导致整个表达式匹配失败的时候，与贪婪模式类似，非贪婪模式会最小限度的再匹配一些，以使整个表达式匹配成功。”
具体的匹配过程是这样的：
"非贪婪部分" 先匹配最少次数，然后尝试匹配 "右侧的表达式"。
如果右侧的表达式匹配成功，则整个表达式匹配结束。如果右侧表达式匹配失败，则 "非贪婪部分" 将增加匹配一次，然后再尝试匹配 "右侧的表达式"。
如果右侧的表达式又匹配失败，则 "非贪婪部分" 将再增加匹配一次。再尝试匹配 "右侧的表达式"。
依此类推，最后得到的结果是 "非贪婪部分" 以尽可能少的匹配次数，使整个表达式匹配成功。或者最终仍然匹配失败。
当一个表达式中有多个非贪婪匹配，以表达式 "d(\w+?)d(\w+?)z" 为例，对于第一个括号中的 "\w+?" 来说，右边的 "d(\w+?)z" 属于它的 "右侧的表达式"，对于第二个括号中的 "\w+?" 来说，右边的 "z" 属于它的 "右侧的表达式"。
当 "z" 匹配失败时，第二个 "\w+?" 会 "增加匹配一次"，再尝试匹配 "z"。如果第二个 "\w+?" 无论怎样 "增加匹配次数"，直至整篇文本结束，"z" 都不能匹配，那么表示 "d(\w+?)z" 匹配失败，也就是说第一个 "\w+?" 的 "右侧" 匹配失败。此时，第一个 "\w+?" 会增加匹配一次，然后再进行 "d(\w+?)z" 的匹配。循环前面所讲的过程，直至第一个 "\w+?" 无论怎么 "增加匹配次数"，后边的 "d(\w+?)z" 都不能匹配时，整个表达式才宣告匹配失败。
其实，
为了使整个表达式匹配成功，贪婪匹配也会适当的“让出”已经匹配的字符。因此贪婪匹配也有类似的情况。当一个表达式中有较多的未知匹配次数的表达式时，为了让整个表达式匹配成功，各个贪婪或非贪婪的表达式都要进行尝试减少或增加匹配次数，由此容易形成一个大循环的尝试，造成了很长的匹配时间。本文之所以称