15

如果这是在某处发布，我深表歉意，但我粗略的搜索没有找到任何东西。

在进行一些 Python 编程时，我注意到以下命令：

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

返回空字符串。但是 sed 中的等效命令：

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

返回ab。

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

4

2 回答 2

4

默认情况下，Python 和 sed 都是贪婪的，但是...... Python 正则表达式尝试在所有情况下从左到右进行评估，尽管如果正在尝试的分支无法通过匹配继续，它最终必须回溯到先前的状态。相反，Sed 正则表达式在评估之前进行优化，以防止不必要的回溯，通过将正则表达式重写为更具确定性的形式。因此，组合的可选模式“aab”可能在普通的“a”之前测试，因为最具体的可能字符串首先被尝试。

Python 模式将字符串“aabb”匹配为“aab”+“b”两次（标记在“<>”之间）

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

而 sed 通过一个替换匹配整个“aabb”：

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

Python regex backtrace 算法在regex howto - Repeating Things in two paragraphs 由“A step-by-step example...”一词介绍的很好地解释了。它完全按照正则表达式文档的描述执行 IMO ：“扫描目标字符串时，RE 由 '|' 分隔 从左到右尝试。”

示范

顺便说一句，“(|a|aa)”的顺序。"(aa|a|)" 受到 Python 的尊重

>>> re.sub("(?:|a|aa)((ab)*)b", r"<\1>", "aabb")
'<ab>'
>>> re.sub("(?:aa|a|)((ab)*)b", r"<\1>", "aabb")
'<><>'

但是这个顺序被sed 忽略了，因为 sed 优化了正则表达式。匹配“aab”+“b”可以从模式中删除“a”选项来复制。

$ echo "aabb" | sed "s/\(\|a\|aa\)\(\(ab\)*\)b/<\2>/g"
<ab>
$ echo "aabb" | sed "s/\(aa\|a\|\)\(\(ab\)*\)b/<\2>/g"
<ab>
$ echo "aabb" | sed "s/\(aa\|\)\(\(ab\)*\)b/<\2>/g"
<><>

编辑：我删除了有关 DFA/NFA 的所有内容，因为我无法从当前文本中证明这一点。

于 2012-08-25T18:34:26.767 回答
2

您构建的有趣谜题。根据我的阅读，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 中得到空字符串：RE 匹配aab第一次，其余b第二次匹配，删除每个部分（因为它全部匹配正则表达式a*的最后b一个）。您可以通过以下变体看到这一点：

>>> re.sub("a*((ab)*)b", r"X\1Y", "aabb")
'XYXY'
于 2012-08-25T19:12:09.267 回答