sed和python正则表达式之间的不一致

Question

如果这是在某个地方发布我道歉,但我粗略的搜索没有发现任何东西.

在做一些Python编程时,我注意到以下命令:

re.sub("a*((ab)*)b", r"\1", "aabb")

返回空字符串.但是sed中的等效命令:

echo "aabb" | sed "s/a*\(\(ab\)*\)b/\1/"

回报ab.

我觉得python正则表达式开头的"a*"指令与两者都匹配a,导致"(ab)*"匹配零次,但我不知道sed是如何出现的ab.有谁知道造成这种情况的两个正则表达式引擎之间有什么区别？我相信它们都默认贪婪地匹配星星,但我发现sed可能从右边而不是左边匹配.任何见解将不胜感激.

Answer 1

您构建的有趣谜题。据我所知，python 和 sed 的正则表达式引擎都基于 Henry Spencer 的正则表达式库（与 Perl 的一样），该库依赖于回溯。（不幸的是，我找不到我所依据的文章）。

无论如何，这不应该是一个实现细节：Python 的行为违反了 POSIX 标准，该标准要求 RE (a) 在最早的可能点进行匹配，以及 (b) 匹配从该点开始的最长的可能字符串。（看man 7 regex（在 Linux 上）了解这一点以及更多内容。）

为了找到最长的匹配，回溯（“NFA 类型”）正则表达式引擎必须在找到一个匹配后继续检查替代项。因此，实施者偷工减料也就不足为奇了。显然，python 的行为是不合格的，因为它无法找到最长的匹配。根据 sed 手册页，“出于性能原因”，sed 也不总是符合要求。但显然这件事是正确的。

顺便说一句，您的命令并不完全等效：re.sub将执行尽可能多次的替换，而 seds/a/b/只会执行一次。sed 版本应该是：

echo "aabb" | sed "s/a*\(\(ab\)*\)b/\1/g"

这解释了为什么我们在 python 中得到空字符串：REaab第一次匹配，第二b次匹配剩余的部分，删除每个部分（因为它全部与正则表达式的a*最后一个匹配）。b您可以通过以下变体看到这一点：

>>> re.sub("a*((ab)*)b", r"X\1Y", "aabb")
'XYXY'