正则中的回溯定义与用法分析【JS与java实现】

本文实例分析了正则中的回溯定义与用法。分享给大家供大家参考，具体如下：

关于“回溯”我也是第一次接触，对它也不算很了解。下面就把我所了解的做为一个心德记录下来，以备查看。

我们所使用的正则表达式的匹配基础大概分为：优先选择最左端（最靠开头）的匹配结果和标准的匹配量词（*、+、？和{m, n}）是匹配优先的。

“优先选择最左端的匹配”顾名思义就是从字符串的起始位置开始匹配直到匹配结束这是基础；“标准匹配量词”又分为“非确定型有穷自动机（NFA）”也可以叫做“表达式主导”；另外一种是“确定型有穷自动机（DFA）”也可以叫做“文本主导”。我们目前在JavaScript中所使用的正则表达式为“表达式主导”。表达式主导和文本主导解释起来有些麻烦，先看来一个例子可能会清楚些。

// 使用正则表达式匹配文本
var reg = /to(nite|knight|night)/;
var str = 'doing tonight';
reg.test(str);

在上面的这个例子中，第一个元素[t]，它将会重复尝试，直到目标字符串中找到‘t'为止。之后，就检查紧随其后的字符是否能由[o]匹配，如果能，就检查下面的元素（nite|knight|night）。它的真正含义是“nite”或者“knight”或者“night”。引擎会依次尝试这3种可能。尝试[nite]的过程是先尝试[n]，然后[i]，然后[t]，最后是[e]。如果这种尝试失败，引擎会尝试另一种可能，如此继续下去，直到匹配成功或是报告失败。表达式中的控制权在不同的元素之间转换，所以称为“表达式主导”。

同样是上面的例子“文本主导”在扫描字符串时，会记录当前有效的所有匹配可。当引擎移动到t时，它会在当前处理的匹配可能中添加一个潜在的可能：

字符串中的位置 正则表达中的位置 ……doing tonight 可能的匹配位置：/t↑o(nite|knight|nigth)/

接下来扫描的每个字符，都会更新当前的可能匹配序列。继续扫描两个字符以后的情况是：

字符串中的位置 正则表达中的位置 ……doing tonight 可能的匹配位置：/to(ni↑te|knight|ni↑gth)/

有效的可能匹配变为两个（knight被淘汰出局）。扫描到g时，就只剩下一个可能匹配了。当h和t匹配完成后，引擎发现匹配已经完成，报告成功。“文本主导”是因为它扫描的字符串中的每个字符都对引擎进行了控制。

如果想要弄明白“表达式主导”是如何工作的，那就要看一下我们今天的主题“回溯（backtracking）”。回溯就像是在走岔路口，当遇到岔路的时候就先在每个路口做一个标记。如果走了死路，就可以照原路返回，直到遇见之前所做过的标记，标记着还未尝试过的道路。如果那条路也走不能，可以继续返回，找到下一个标记，如此重复，直到找到出路，或者直到完成所有没有尝试过的路。

在许多情况下，正则引擎必须在两个（或更多）选项中做出选择。当遇到/……x"color: #0000ff">如果需要在“进行尝试”和“路过尝试”之间选择，对于匹配优先量词，引擎会优先选择“进行尝试”，而对于忽略优先量词，会选择“路过尝试”。

第二个问题是按以下这条原则：

距离当前最近储存的选项就是当本地失败强制回溯时返回的。使用的原则是LIFO（last in first out，后进先出）。

我们先来看几个在道路中做标记的例子：

1、未进行回溯的匹配

用[ab"1" cellspacing="0" cellpadding="0" width="400" style="text-align: left; padding-bottom: 0px; widows: 1; text-transform: none; background-color: rgb(247,252,255); text-indent: 0px; margin: 0px; padding-left: 0px; border-spacing: 0px; padding-right: 0px; border-collapse: collapse; font: 12px/25px Tahoma, Helvetica, Arial, 宋体, sans-serif; white-space: normal; letter-spacing: normal; color: rgb(0,0,0); clear: both; word-spacing: 0px; padding-top: 0px; -webkit-text-stroke-width: 0px"> “a↑bc” a↑b"Apple-interchange-newline" />

现在轮到[b"1" cellspacing="0" cellpadding="0" width="402" style="text-align: left; padding-bottom: 0px; widows: 1; text-transform: none; background-color: rgb(247,252,255); text-indent: 0px; margin: 0px; padding-left: 0px; border-spacing: 0px; padding-right: 0px; border-collapse: collapse; font: 12px/25px Tahoma, Helvetica, Arial, 宋体, sans-serif; white-space: normal; letter-spacing: normal; color: rgb(0,0,0); clear: both; word-spacing: 0px; padding-top: 0px; -webkit-text-stroke-width: 0px"> “a↑bc” ab"line-height: 25px; color: rgb(0,128,0)">↑c
添加到备用状态序列中。也就是说，稍后引擎可能从下面的位置继续匹配：从正则表达式中的[b"Apple-interchange-newline" /> “ab↑c” ab"line-height: 25px; color: rgb(0,128,0)">↑c
最终的[c]也能成功匹配，所以整个匹配完成。备用状态不再需要了，所以不再保存它们。

2、进行了回溯的匹配

下面要匹配的文本是“ac”，在尝试[b]之前，一切都与之前的过程相同。显然，这次[b]无法匹配。也就是说，对[……？]进行尝试的路走不通了。因为有一个备用状态，这个“局部匹配失败”产工会导致整体匹配失败。引擎会进行回溯，也就是说，把“当前状态”切换为最近保存的状态。
“a↑c” ab"line-height: 25px; color: rgb(0,128,0)">↑c
在[b]尝试之前保存的尚未尝试的选项。这时候，[c]可以匹配c，所以整个匹配宣告完成。

3、不成功的匹配

现在要匹配的文本是“abx”。在尝试[b]以前，因为存在问号，保存了这个备用状态：
“a↑bx” ab"line-height: 25px; color: rgb(0,128,0)">↑c
[b]能够匹配，但这条路往下却走不通了，因为[c]无法匹配x。于是引擎会回溯到之前的状态，“交还”b给[c]来匹配。显然，这次测试也失败了。如果还有其他保存的状态，回溯会继续进行，但是此时不存在其他状态，在字符串中当前位置开始的整个匹配也就宣告失败。

例子1： 提取字符串   提取 da12bka3434bdca4343bdca234bm   提取包含在字符a和b之间的数字，但是这个a之前的字符不能是c,b后面的字符必须是d才能提取。

例如这里就只有3434这个数字满足要求。那么我们怎么提取呢？

首先我们写出提取这个字符串的表达式： ("htmlcode">

Pattern p = Pattern.compile( "(" );
Matcher m = p.matcher( "da12bka3434bdca4343bdca234bm" );
 while (m.find()){
 System.out.println(m.group( 1 )); //我们只要捕获组1的数字即可。结果 3434
 System.out.println(m.group(0)); // 0组是整个表达式，看这里，并没有提炼出("htmlcode">

\d+\.\d\d[1-9]"color: #ff0000">可以提高效率，侵占量词基本上就是用来提高匹配效率的。

把 \d+\.\d\d[1-9]"color: #800000">PS：这里再为大家提供2款非常方便的正则表达式工具供大家参考使用：
JavaScript正则表达式在线测试工具：

http://tools.jb51.net/regex/javascript
正则表达式在线生成工具：

http://tools.jb51.net/regex/create_reg
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript正则表达式技巧大全》、《JavaScript替换操作技巧总结》、《JavaScript查找算法技巧总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript遍历算法与技巧总结》、《JavaScript中json操作技巧总结》、《JavaScript错误与调试技巧总结》及《JavaScript数学运算用法总结》
希望本文所述对大家JavaScript程序设计有所帮助。