为什么 sed 没有非贪婪正则表达式？ [已关闭]

Question

我不是在问

sed

中是否有贪婪的正则表达式，我已经知道没有。我要问的是：

众所周知，

sed

是现有的最好的或最好的流编辑器之一，但是为什么这个工具的开发人员没有实现非贪婪的正则表达式呢？与这个工具可以做的所有事情相比，它看起来很简单。

Answer 1

历史

非贪婪匹配是Perl 兼容正则表达式的一个功能。 PCRE 只作为 Perl 语言的一部分提供，直到 1997 年 libpcre 实现为止，而

sed

的 POSIX 实现于 1992 年首次引入——它引用的标准 C 库正则表达式例程的实现甚至早于 1997 年。 ，于 1988 年出版。

---

标准-主体定义

sed

的POSIX规范支持BRE； POSIX 中仅指定了 BRE（“基本正则表达式”）和 ERE（“扩展正则表达式”），并且两种形式都不包含非贪婪匹配。

因此，为了将 PCRE 支持（或者非贪婪匹配支持）标准化以包含在所有

sed

 实现中，首先需要在 POSIX 正则表达式定义中进行标准化。

但是，鉴于 PCRE 支持可能不受欢迎的实际原因，这种情况在实践中不太可能发生（除非作为存在或不存在的扩展，由实施者选择）；请参阅以下部分：

实施注意事项

---

sed

通常被认为是“核心工具”，因此仅以最小的依赖性实现。需要 libpcre 才能安装
• sed

  ，从而使 libpcre 成为操作系统的一部分，甚至需要包含在大小非常重要的映像中（initrd/initramfs 映像等）。

  有多种实现正则表达式的策略可用。历史（非常高性能）实现将表达式编译为非确定性有限自动机，可以在给定固定正则表达式的情况下针对大小为 n 的字符串在 O(n) 时间内执行。 libpcre 实现使用回溯——这允许更容易地实现非贪婪匹配、前向和后向等功能——但通常会比线性性能差得多。

• 请参阅
https://swtch.com/~rsc/regexp/regexp1.html

，了解 Thompson NFA 相对于回溯实现的性能优势的讨论。