正则表达式回溯法|极客教程

正则表达式回溯法，正则表达式匹配字符串的这种方式，有个学名，叫回溯法。回溯法也称试探法，它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。

本质上就是深度优先搜索算法。其中退到之前的某一步这一过程，我们称为“回溯”。从上面的描述过程中，可以看出，路走不通时，就会发生“回溯”。即，尝试匹配失败时，接下来的一步通常就是回溯。

回溯引用匹配

假如你有一段文本，你想把这段文本里所有连续重复出现的单词（打字错误，其中有一个单词输了两遍）找出来。显然，在搜索某个单词的第二次出现时，这个单词必须是已知的。回溯引用允许正则表达式模式引用前面的匹配结果（具体到这个例子，就是前面匹配到的单词）。

文本：

This is a block of of text,
several words here are are
repeated, and and they
should not be.

执行正则表达式：
[ ]+(\w+)[ ]+\1

执行结果：
正则表达式回溯法

这里，[ ]+ 匹配一个或多个空格，\w 匹配一个或多个字母数字字符， []+ 匹配随后的空格。注意， \w 是括在括号里的，它是一个子表达式。这个子表达式不是用来进行重复匹配的，这里根本不涉及重复匹配的问题。这个子表达式只是把整个模式的一部分单独划分出来以便在后面引用。这个模式的最后一部分是 \1，这是一个回溯引用，而它引用的正是前面划分出来的那个子表达式。当 (\w+) 匹配到单词 of 的时候，\1 也匹配单词 of ，当 (\w+) 匹配到单词 are 的时候，\1 也匹配单词 are ，当 (\w+) 匹配到单词 and 的时候，\1 也匹配单词 and 。

回溯引用指的是模式的后半部分引用在前半部分中定义的子表达式。\1 代表着模式里的第1个子表达式，\2 代表着第2个子表达式，以此类推。可以把回溯引用想象成变量。
回溯引用只能用来引用模式里的子表达式（用 ( 和 ) 括起来的正则表达式片段）。
回溯引用匹配通常从1开始计数（\1 、\2 等）。在许多实现里，第0个匹配（\0）可以用来代表整个正则表达式。
不同的正则表达式在实现回溯引用的语法方面旺旺有着巨大的差异。JavaScript 使用 \ 来标识回溯引用（\ 与 $ 配合进行替换操作时是例外）。

回溯引用在替换操作中的应用

文本：

Hello, 940710020@qq.com is my email address.

执行正则表达式：
(\w+[\w\.]*@[\w\.]+\.\w+)

替换成：
<a href="mailto: $1">$ 1</a>

执行结果：
正则表达式回溯法

替换操作需要用到两个正则表达式：一个用来给出搜索模式，另一个用来给出匹配文本的替换模式。回溯引用可以跨模式使用，在第一个模式里被匹配的子表达式可以用在第二个模式里。这里使用的模式 (\w+[\w\.]*@[\w\.]+\.\w+) 用来匹配电子邮件地址，并把它写成了一个子表达式。这样一来，被匹配到的文本就可以用在替换模式里了。

在一个用来保存用户信息的数据库里，电话号码被保存为333-555-1234。现在，你需要把电话号码重新排版为(313)555-1234。

文本：