為什麼 ed 支持反向引用但不支持正則表達式中的交替？
我正在研究正則表達式的歷史和發展。我找到了以下時間表：
1956 - Kleene 在他關於神經網路的論文中介紹了正則表達式。
1964 - Brzozowsi 引入了正則表達式導數的概念。
1968 - Thompson 描述瞭如何為正則表達式編寫編譯器
60年代末/70年代初
- Thompson 將 QED 編輯器移植到 CTSS，添加了正則表達式支持。
- Thompson 和 Ritchie 將 QED 移植到 Multics，並最終移植到 1970 年代的 Unix
- 湯普森在 QED 的啟發下寫了 ed
- 在 Unix V1 之後的某個時候，Thompson 從 ed 中提取正則表達式程式碼來製作 grep
- 在 Unix V7 中，引入了 egrep 和 fgrep。
Kleene 和 Brzozowski 對正則表達式有相同但不同的定義，而 Thompson 在他的論文中明確假設他的聽眾熟悉這些定義。
我感到困惑的是 ed 中的交替（匹配兩個正則表達式中的任何一個）發生了什麼？Kleene、Brzozowski 和 Thompson 的論文包括交替。QED 中 Thompson 的正則表達式實現包括交替，而 ed 沒有。早期的 grep 也沒有。
對我來說更奇怪的是，ed 在其正則表達式中引入了對反向引用的支持。也就是說，正則表達式
(a.c)\1將匹配abcabc但不匹配abcadc。反向引用允許 ed 和 grep 辨識一些非正常語言，而缺乏交替意味著它們無法辨識一些正常語言。為什麼 Thompson 取消了對 qed 和 ed 之間交替的支持？為什麼添加了反向引用，而不是交替？
Dennis Ritchie 曾經寫過一篇短文，名為《QED 文本編輯器的不完整歷史》。在文中，我們可以讀到
“標準 Unix 編輯器”
ed最初是由 Ken Thompson 為 PDP-7 編寫的。它保留了基本的文本行方向，但從根本上簡化了正則表達式，只包含*運算符：沒有交替，沒有括號。在我的 QED 包含許多上下文無關語言的地方，這個版本甚至無法表達所有正常語言。損失不大。同樣，Ken 的 Unix
ed拋棄了多個緩衝區和緩衝區執行的概念。for Unix的後續版本ed（現在用 C 編寫）開始增加一些複雜性（例如，“正則”表達式中的反向引用，它現在並不完全包括所有正則語言或上下文無關語言，但確實侵入了一點關於上下文相關的語言。）從這些簡短的段落中，我感覺到 Ken 主要關心的是使用
ed來完成任務，而不是嘗試實現實際上不會被使用的正則表達式。“這並沒有太大的損失。 ”這可能是 Ken 處理文本的個人方式的標誌，他不需要更改或反向引用（至少不是拼命地）。正如 Gilles在評論中指出的那樣，交替的實現可能很慢並且相對記憶體密集，而反向引用在不尋常的情況下可能會很慢，這使得反向引用更有可能在有限的硬體上實現。
Unix 團隊在開發之初使用的 PDP-7 有 8k 字的記憶體，而 Ken 為其實施一個版本的 QED 的 Multics 系統在擁有 64k 字的機器上執行。
ed這很可能是最初的實現只有非常基本的模式匹配工具的另一個原因。總結：兩個可能的原因是
- 限制性硬體 (PDP-7) 使得實現交替和反向引用等變得不可能/繁瑣。
- 編輯器的用途實際上不需要完整的正則表達式語法。隨著向更強大的硬體 (PDP-11) 的遷移，反向引用被重新添加到編輯器中，但當時可能根本不需要編輯器的使用者之間進行交替。