Skip to content

Latest commit

 

History

History
58 lines (34 loc) · 8.41 KB

014-回溯引用.md

File metadata and controls

58 lines (34 loc) · 8.41 KB

14.1 使用回溯引用匹配出现过的字符串

回溯引用可以匹配到捕获组曾经匹配过的结果。你可以使用它来匹配HTML的开启标签和闭合标签、以及他们之间的文本。我们可以把启示标签放入一对花括号中(创建捕获组),这样我们在匹配闭合标签的时候可以再次使用捕获组所匹配到的字符。表达式如下<([A-Z][A-Z0-9]*)\b[^>]*>.*?</\1>。这个表达式中只有一对圆括号,匹配的表达式为[A-Z][A-Z0-9]*,它可以匹配到一个HTML起始标签。回溯引用\1会尝试匹配第一个捕获组所匹配的结果。回溯引用之前的/是一个字面量字符,它所匹配的是HTML闭合标签里的斜杠。

回溯引用中的数字是从左至右计算的。第一个圆括号中的内容对应回溯引用中的\1,第二对圆括号对应\2。如果圆括号不是用于创建捕获组,那么它不会计入回溯引用的数字中。这意味着如果你在表达式中插入一个非捕获组,之前的回溯引用中的数字不会受到影响。这个特性在修改复杂的表达式的时候非常有用。

同一个回溯引用可以多次使用。例如([a-c])x\1x\1可以匹配 axaxa , bxbxb。

大多数引擎支持99个捕获组以及两位数的回溯引用。所以如果你有99个捕获组,那么\99可以匹配第99个捕获组。

14.2 引擎内部原理

让我们来看一下表达式<([A-Z][A-Z0-9]*)\b[^>]*>.*?</\1>是如何匹配字符串Testing <B><I>bold italic</I></B> text的。表达式的第一个token是<,所以引擎会不断向前搜索字符串知道它匹配到字符串的第一个<。下一个token是[A-Z],同时引擎也知道这个token处于第一个捕获组之中。这个token匹配到字符 < 后面的 B。引擎继续匹配下一个token[A-Z0-9],它所要匹配的字符是 >,匹配没有成功,但是这个token是一个星号,这表示这个token可以不出现。引擎继续把下一个token\b词语边界)和字符 > 匹配,这次匹配成功了,因为当前位置处于 B 和 > 之间。词语边界匹配的是位置,所以下个token[^>]还是和字符 > 匹配。

此时第一个捕获组已经匹配完成,引擎会保存匹配结果到回溯引用\1。在这个例子中保存的是字符 B。

接下来引擎继续匹配的工作,下一个token[^>]不能和字符 > 匹配。和之前一样,这个token后面有一个星号,所以这次失败是可以接受的。引擎在字符串中的位置还是停留在 > ,并且下一个token是>,这次匹配显然是成功的。

接下来的token是.,并且它的后面是一个非贪婪的星号。由于星号最少匹配0次,所以引擎首先会跳过token.将下一个token<和写一个字符 < 匹配,匹配成功了。但是下一个token/不能和字符 I 匹配,所以引擎向前回溯至token.,并把它的匹配范围向右侧扩展一位,.可以匹配字符 < ,接下来匹配token<和字符 I,匹配不成功,引擎再次向前回溯。

引擎会持续回溯,知道token.匹配到字符串<I>bold italic。此时token<匹配到字符串中第三个 < ,并且tokenI匹配字符 I,此时下一个token是\1,这是一个回溯引用也就是之前保存的 B,此时 B 不能和 I 匹配。此时引擎继续发生回溯,又经过连续4次回溯后token.匹配字符串<I>bold italic</I>。此时表达式中剩余的三个token</\1>正好能和字符串 </B>匹配,所以整个表达式匹配完成了,匹配的结果是<B><I>bold italic</I></B>

注意捕获组所保存的结果会随着引擎的回溯发生改变,如果引擎回溯的位置超过了之前的捕获组,那么捕获组就重新进行匹配,那么捕获组保存的结果也就更新了。这种情况在上一个例子中并没有发生。

14.3 回溯至捕获组内部

在看上面那个例子的时候,你是否注意到我们使用了词语边界\b,使用词语边界是为了确保表达式不会匹配到错误的标签,例如<boo>bold</b>。你也许认为这种错误不会发生,因为捕获组会匹配 boo ,而 boo 和闭合标签中的 b 无法匹配。事实上引擎也是这么运行的,但是之后引擎发生了回溯。

让我们来看一下相同的例子,如果没有使用\b,表达式<([A-Z][A-Z0-9]*)[^>]*>.*?</\1>是如何匹配Testing <B><I>bold italic</I></B> text的。表达式的前半段都和之前的例子相似,直到\1第一次匹配字符 b,这次匹配没有成功,引擎回溯至.,token.向前多匹配一个字符也就是 < 。之后token\1将匹配字符 /,也没有匹配成功。之后引擎不断的回溯,直到字符串末尾的void,void也不能和\1匹配。

接下来引擎将回溯至捕获组的内部,因为表达式[A-Z0-9]*可以匹配字符 oo ,也可以匹配 o ,或者什么也不匹配。这一次回溯表达[A-Z0-9]*将匹配 o,并且此时捕获组也发生了更新,新的值为 bo。接下来的token[^>]*匹配到了 o,表达式>.*?</匹配到 >bold</,接下的token\1不能和字符 b匹配。

接下来引擎又会发生和之前类似的回溯,直到回溯再次进入捕获组。这一次表达式[A-Z0-9]*将不匹配任何字符。捕获组将匹配 b,并更新保存的结果,表达式[^>]*匹配到 oo,>.*?</匹配到>bold</。现在token\1可以和字符 b匹配了。最后一个token>也和最后一个字符匹配上了。到此为止整个表达匹配完成,但是这并不是我们想要的结果。

有很多方法能解决这个问题,其中一种是使用词语边界。当表达式[A-Z0-9]*首次发生回溯,并将捕获组的匹配结果减少为 bo之后,紧接着的\b无法匹配字符 o 和 o之间的位置,这将导致引擎立即再次触发回溯。下一次回溯后,捕获组匹配的结果减短为 b,通过词语边界不能匹配字符 b 和 o 之间的位置。此时已经无法继续回溯了,整个表达式匹配失败。

这个例子中,我们需要使用词语边界的原因是HTML标签中包含了属性,如果你要匹配的字符串中不包含属性,那么不使用词语边界也不会发生错误。这是因为当表达式[A-Z0-9]*发生回溯之后,紧接着的token>无法和后面的字符匹配,这会导致引擎立即再次触发回溯,直到整个表达式匹配失败。

14.4 量词和回溯引用

正如前面的例子提到的,捕获组中保存的结果会不断更新。回溯引用每次都会使用最新的保存结果。表达式([abc]+)([abc])+很大的区别。虽然它们都可以匹配 cab,但是前一个表达式中捕获组保存的结果是 cab ,而后者只保存 b。因为在第二个表达式中加号使得捕获组重复匹配了三次,第一次的结果是 c ,然后是 a ,再然后是 b。 最新的保存结果会覆盖之前的结果,所以最终结果是 b。

这也意味着表达式([abc]+)=\1可以匹配 cab=cab,而表达式([abc])+=\1不能。这是因为当引擎匹配token\1的时候,捕获组保存的结果是 b,而 b 不能和等号后面的 c 匹配。在这个简单的例子中这个错误很容易察觉,但是在复杂的表达式中却很难发现这种错误,所以我们在使用它的时候一定要注意捕获组捕获的内容到底是什么。

14.5 应用实例:检查重复词语

当我们在编辑文本的时候,可能误把同一个单词连续输入两次,例如 the the。我们可以使用\b(\w+)\s+\1\b来查找他们。

14.6 字符集中不能使用圆括号和回溯引用

字符集中的圆括号不能作为元字符使用,这种场景下的圆括号仅仅表示字面量字符。所以表达式[(a)b]可以匹配a, b, (, 和 )。

回溯引用同样不能在字符集中使用,这会导致错误,或者被识别为一个转移符。在JavaScript中它被识别为八进制转义。


如果文章出现错误,请给我提Issues - - Github地址

需要进一步翻译的内容:

  • 重复一个捕获组vs捕获一个重复的匹配组

原文