python - 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 都是贪婪的，但是...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 howto - Repeating Things 中有很好的解释。在两段中用“一步一步的例子……”来介绍。 IMO 完全按照描述的方式执行 regex docs : "当目标字符串被扫描时，REs 由 '|' 分隔从左到右尝试。”

演示

顺便说一句，“(|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 优化了正则表达式。可以从模式中删除“a”选项来重现匹配的“aab”+“b”。

$ 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 的所有内容，因为我无法从当前文本中证明这一点。