正则中的回溯定义与用法分析【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时，它会在当前处理的匹配可能中添加一个潜在的可能：