回溯
正则表达式/\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
,因此向前回溯一个位置,开始执行外部循环,接着再次放弃,再次尝试执行一次内部循环。该过程会尝试这两个循环的所有可能路径。这意味着每多出一个字符,其工作量就会加倍。甚至只需较少的一堆字符,就可使匹配实际上永不停息地执行下去。