I was looking into the history and development of regular expressions. I found the following timeline:
- 1956 - Kleene introduces regular expressions in his paper on nerve nets.
- 1964 - Brzozowsi introduces the idea of a derivative of a regular expression.
- 1968 - Thompson describes how to write a compiler for regular expressions
- late 60's/early 70's
- Thompson ported the QED editor to CTSS, adding regular expression support.
- Thompson and Ritchie ported QED to Multics, and eventually to Unix 1970's
- Thompson wrote ed, inspired by QED
- Sometime after Unix V1, Thompson extracted the regular expression code from ed to make grep
- in Unix V7, egrep and fgrep were introduced.
Kleene and Brzozowski have equivalent, but differing definitions of regular expressions, and Thompson, in his paper, explicitly assumes that his audience is familiar with these definitions.
What I am confused about is what happened to alternation (matches either of two regular expressions) in ed? Kleene, Brzozowski, and Thompson's papers include alternation. Thompson's regular expression implementation in QED includes alternation, and yet ed does not. Neither does early grep.
Weirder to me, ed introduced support for back-references in its regular expressions. That is, the regular expression
(a.c)\1 will match
abcabc but not
abcadc. Back-references allows ed and grep to recognize some non-regular languages, and the lack of alternation means there are some regular languages they can't recognize.
Why did Thompson remove support for alternation between qed and ed? Why did back-references get added, but not alternation?