带有反向引用的不可能的回溯

Question

据我了解

(.)(?<!\1)

不应该匹配。实际上，phppreg_replace甚至拒绝编译它，而ruby的也是如此gsub。pythonre模块似乎有不同的看法：

import re
test = 'xAAAAAyBBBBz'
print (re.sub(r'(.)(?<!\1)', r'(\g<0>)', test))

结果：

(x)AAAA(A)(y)BBB(B)(z)

任何人都可以对此行为提供合理的解释吗？

更新资料
这种行为似乎是限制了在re模块。替代regex模块似乎可以正确处理断言中的组：

import regex

test = 'xAAAAAyBBBBz'

print (regex.sub(r'(.)(?<!\1)', r'(\g<0>)', test))
## xAAAAAyBBBBz

print (regex.sub(r'(.)(.)(?<!\1)', r'(\g<0>)', test))
## (xA)AAA(Ay)BBB(Bz)

请注意，与有所不同pcre，regex它还允许可变宽度的查找：

print (regex.sub(r'(.)(?<![A-Z]+)', r'(\g<0>)', test))
## (x)AAAAA(y)BBBB(z)

最终，regex将被包含在标准库中，如PEP 411中所述。

Answer 1

这看起来确实像是Pythonre模块中的一个限制（我从Microsoft的支持电话中学到的一种“错误”的好说法）。

我猜想这与以下事实有关：Python不支持可变长度的后向断言，但是它不够聪明，无法确定\1始终是固定长度的。我不能说为什么在编译正则表达式时不抱怨这一点。

很有趣：

>>> print (re.sub(r'.(?<!\0)', r'(\g<0>)', test))
(x)(A)(A)(A)(A)(A)(y)(B)(B)(B)(B)(z)
>>>
>>> re.compile(r'(.*)(?<!\1)') # This should trigger an error but doesn't!
<_sre.SRE_Pattern object at 0x00000000026A89C0>

因此最好不要在Python的后置断言中使用反向引用。正向后看并不会好得多（它在这里也像正向前向相匹配）：

>>> print (re.sub(r'(.)(?<=\1)', r'(\g<0>)', test))
x(A)(A)(A)(A)Ay(B)(B)(B)Bz

而且我什至无法猜测这里发生了什么：

>>> print (re.sub(r'(.+)(?<=\1)', r'(\g<0>)', test))
x(AA)(A)(A)Ay(BB)(B)Bz