为什么sed没有非贪婪的正则表达式

Question

我不是在问sed中是否有贪婪的正则表达式,我已经知道没有.我要问的是:众所周知,sed是最好的或者是最好的流编辑器之一.那么为什么这个工具的开发人员没有实现非贪婪的正则表达式.与此工具可以执行的所有操作相比,它看起来很简单.

Answer 1

历史

非贪婪匹配是Perl兼容正则表达式的一个特性.PCRE仅在1997年libpcre实现之前作为Perl语言的一部分提供,而POSIX实现sed最初是在1992年引入的 - 并且它引用的标准C库正则表达式例程的实现甚至早于1988年出版.

标准 - 身体定义

POSIX规范sed支持BRE; 只有BRE("基本正则表达式")和ERE("扩展正则表达式")在POSIX中完全指定,并且两种形式都不包含非贪婪匹配.

因此,为了将PCRE支持(或者,非贪婪匹配支持)标准化以包含在所有sed实现中,首先需要在POSIX正则表达式定义中标准化.

但是,考虑到PCRE支持可能不合适的实际原因,在实践中这种情况极不可能发生(除非作为扩展存在,否则,在执行者的选择下).请参阅以下部分:

实施注意事项

• sed通常被认为是"核心工具",因此仅使用最小的依赖性来实现.因此,为了安装需要libpcre sed会使libpcre成为操作系统的一部分,即使在大小非常高的图像(initrd/initramfs图像等)中也需要包含它.
• 可以使用多种策略来实现正则表达式.历史(非常高性能)实现将表达式编译成非确定性有限自动机,其可以在给定固定正则表达式的大小为n的字符串的O(n)时间内执行.libpcre实现使用回溯 - 这允许更容易地实现诸如非贪婪匹配,前瞻和后观等功能 - 但通常具有远比线性差的性能).

有关Thompson NFA在回溯实现方面的性能优势的讨论,请参阅https://swtch.com/~rsc/regexp/regexp1.html.