3 ms·
Nitpick: Thompson didn't invent regular expressions (that achievement belongs to Stephen Kleene), but he figured out how efficiently parse them with a computer,
by LukeShu 13y ago
Nitpick: Thompson didn't invent regular expressions (that achievement belongs to Stephen Kleene), but he figured out how efficiently parse them with a computer, turning them from a mathematician's toy into something practical.
I don't recall if Thompson is responsible for "modern" regular expression syntax--at least the `*` is borrowed from Kleene's notation. I'd look at Thompson's paper and find out, but I'm having trouble accessing my ACM subscription.
- nostrademons 13y agoThompson is at the very least responsible for the ^ and $ metacharacters.
- LukeShu 13y agoThompson's original paper used used the example espression: a(b|c)*d without any description of what it meant, so I take it that at the very least, that much was borrowed from Kleene. I am having a hard time reading it, to see if anything else was implemented, as I am unfamiliar with Algol-60 or IBM 7094 assembly. He cites Kleene's paper, saying that he assumes the reader is familiar with regular expressions; I'd look at that paper and see what Kleene described, but I can't find a copy of that. Thompson also site a paper by Brzozowski. The abstract for that paper includes: "Kleene's regular expressions, which can be used for describing sequential circuits, were defined using three operators (union, concatenation and iterate)" Which I take to mean that Kleene only came up with the syntax expressed in the example expression at the beginning.