回溯

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

回溯 - 图1

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

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

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

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

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

回溯 - 图2

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