我正在研究正则表达式的历史和发展。我发现了以下时间线：
- 1956 - Kleene 在他关于神经网络的论文中引入了正则表达式。
- 1964 - Brzozowsi 引入了正则表达式导数的概念。
- 1968 年 - Thompson 描述了如何编写正则表达式编译器
- 60 年代末/70 年代初
- Thompson 将 QED 编辑器移植到 CTSS，添加了正则表达式支持。
- Thompson 和 Ritchie 将 QED 移植到 Multics，并最终移植到 Unix 1970 年代
- Thompson 受 QED 启发撰写了 ed
- 在 Unix V1 之后的某个时候，Thompson 从 ed 中提取了正则表达式代码来制作 grep
- 在Unix V7中，引入了egrep和fgrep。
Kleene 和 Brzozowski 对正则表达式有相同但不同的定义，Thompson 在他的论文中明确假设他的读者熟悉这些定义。
我感到困惑的是 ed 中的交替（匹配两个正则表达式中的任何一个）发生了什么？ Kleene、Brzozowski 和 Thompson 的论文包括交替。 Thompson 在 QED 中的正则表达式实现包括交替，但 ed 没有。早期的 grep 也没有。
对我来说更奇怪的是，ed 在其正则表达式中引入了对反向引用的支持。也就是说，正则表达式(a.c)\1将匹配abcabc但不匹配abcadc。反向引用允许 ed 和 grep 识别一些非常规语言，而缺乏交替意味着它们无法识别一些常规语言。
为什么 Thompson 取消了对 qed 和 ed 交替的支持？为什么添加了反向引用，但没有添加交替？
答案1
丹尼斯·里奇曾经写过一篇短文，名为QED 文本编辑器的不完整历史。在正文中我们可以读到
“标准 Unix 编辑器”
ed最初是由 Ken Thompson 为 PDP-7 编写的。它保留了基本的文本行方向，但从根本上简化了正则表达式，使其仅包含*运算符：没有交替，没有括号。我的 QED 包含了许多上下文无关语言，但这个版本甚至无法表达所有常规语言。损失并不大。同样，Ken 的 Unix
ed放弃了多个缓冲区和缓冲区执行的概念。 for Unix的后续版本ed（现在用 C 编写）开始增加一些复杂性（例如“正则”表达式中的反向引用，现在并不完全包括所有正则语言或上下文无关语言，但确实侵入了关于上下文相关语言的一些内容。）
从这些简短的段落中，我感觉到肯主要关心的是如何ed使用把事情做完，而不是尝试实现实际上不会被使用的正则表达式。这 ”损失并不大。“可能是肯个人处理文本的方式的标志，他没有需要更改或反向引用（至少不是绝望的）。
正如吉尔斯也在评论中指出，交替的实现可能很慢并且相对内存密集，而反向引用在异常情况下可能很慢，使得反向引用更有可能在有限的硬件上实现。
Unix 团队在开发之初使用的 PDP-7 具有 8k 字内存，而 Ken 为其实现了一种版本的 QED 的 Multics 系统则运行在拥有 64k 字内存的机器上。这很可能是最初实现ed仅具有非常基本的模式匹配设施的另一个原因。
总结：有两个可能的原因
- 限制性硬件（PDP-7）使得实现交替和反向引用等变得不可能/麻烦。
- 编辑器的用途实际上并不需要完整的正则表达式语法。随着转向更强大的硬件（PDP-11），反向引用被重新添加到编辑器中，但当时编辑器的用户之间可能根本不需要进行更改。