回溯

正则表达式/\b([01]+b|\d+|[\da-f]h)\b/可以匹配三种字符串：以b结尾的二进制数字，以h结尾的十六进制数字（即以 16 为进制，字母a到f表示数字 10 到 15），或者没有后缀字符的常规十进制数字。这是对应的图表。

当匹配该表达式时，常常会发生一种情况：输入的字符串进入上方（二进制）分支的匹配过程，但输入中并不包含二进制数字。我们以匹配字符串"103"为例，匹配过程只有遇到字符 3 时才知道进入了错误分支。该字符串匹配我们给出的表达式，但没有匹配目前应当处于的分支。

因此匹配器执行“回溯”。进入一个分支时，匹配器会记住当前位置（在本例中，是在字符串起始，刚刚通过图中第一个表示边界的盒子），因此若当前分支无法匹配，可以回退并尝试另一条分支。对于字符串"103"，遇到字符 3 之后，它会开始尝试匹配十六进制数字的分支，它会再次失败，因为数字后面没有h。所以它尝试匹配进制数字的分支，由于这条分支可以匹配，因此匹配器最后的会返回十进制数的匹配信息。

一旦字符串与模式完全匹配，匹配器就会停止。这意味着多个分支都可能匹配一个字符串，但匹配器最后只会使用第一条分支（按照出现在正则表达式中的出现顺序排序）。

回溯也会发生在处理重复模式运算符（比如+和*）时。如果使用"abcxe"匹配/^.*x/，.*部分，首先尝试匹配整个字符串，接着引擎发现匹配模式还需要一个字符x。由于字符串结尾没有x，因此*运算符尝试少匹配一个字符。但匹配器依然无法在abcx之后找到x字符，因此它会再次回溯，此时*运算符只匹配abc。现在匹配器发现了所需的x，接着报告从位置 0 到位置 4 匹配成功。

我们有可能编写需要大量回溯的正则表达式。当模式能够以许多种不同方式匹配输入的一部分时，这种问题就会出现。例如，若我们在编写匹配二进制数字的正则表达式时，一时糊涂，可能会写出诸如/([01]+)+b/之类的表达式。

若我们尝试匹配一些只由 0 与 1 组成的长序列，匹配器首先会不断执行内部循环，直到它发现没有数字为止。接下来匹配器注意到，这里不存在b，因此向前回溯一个位置，开始执行外部循环，接着再次放弃，再次尝试执行一次内部循环。该过程会尝试这两个循环的所有可能路径。这意味着每多出一个字符，其工作量就会加倍。甚至只需较少的一堆字符，就可使匹配实际上永不停息地执行下去。