How did Regex get its name?

Question

As a software developer, I have used Regex quite a few times, without thinking about the name too much. The abbreviation can be resolved to "regular expression", but what do those terms mean?

"Regular" could mean something ordinary or normal. Regexes are not normal, they are very specialized. It could also mean symmetric or periodic. While a periodic input could be parsed easily with Regex, the Regex itself must neither be symmetric nor parse something periodic. The best match I see is in the meaning "adhering to rules / having discipline".

"Expression" can also have a few meanings. I think it goes into mathematical direction like "term". An expression in the programmer's world is probably related to the grammar of a programming language.

Is that reasonable? If not, where does the name come from and what does it mean?

Answer 1

The word "regular" has a broader meaning that includes the definitions you gave, and more. In a general sense, "regular" means something like "follows a predictable pattern". It could describe something periodic or symmetric, or it could just describe a group of things where all items have a certain form. In the case of regular expressions, the programming term is inherited from theoretical computer science and (originally) linguistic theory, and you have to drill down a few layers to find the original thing that was referred to as having a "regular" structure.

A regular expression is an "expression" (in this case just a generic term meaning some letters and symbols grouped as a single phrase) that describes a "regular language"; to put it simply, in order for a sentence to be part of the language described by a regex, it must follow the rules presented in the regex.

Next, a regular language is any language that can be generated by a "regular grammar". This is a term that comes from linguistic theory¹. Here the word "regular" has a specific technical meaning related to the structure of the grammar's rules that really doesn't apply at all to regular expressions or languages. This is where the "regularity" comes in. All rules in a regular grammar must have a very small, specific, predictable structure, or the grammar doesn't count as "regular" any more.

So in short, a regular expression describes the rules that sentences must follow in order to belong to the language generated by a certain regular grammar.

---

1: If you're interested in the history and use of these terms in mathematical logic and linguistic theory, here's a basic overview and some links for more research (thanks to @DamkerngT. and @reinierpost for input):

• This use of the term "regular" was probably introduced first by the mathematician and logician Stephen Kleene in his 1951 RAND Corporation report "Representation of events in nerve nets and finite automata" (pdf link), slightly modified and republished in 1956 as a formal paper with the same name (published in Automata Studies, Princeton University Press).
  • In this paper (section 7, beginning on pg. 46), Kleene uses the term "regular events" to describe the inputs and processing rules of "nerve nets" (neural networks) and finite automata (also called "finite state machines"); finite automata were later proven to be logically equivalent to regular expressions.
  • Particularly relevant quote (section 7.1, paragraph 3): "Our objective is to show that all and only regular events can be represented by nerve nets or finite automata."
• The terms "regular language" and "regular grammar" were coined by Noam Chomsky as a part of the Chomsky hierarchy, a categorization of different grammars based on the complexity of the languages they describe.
  • Chomsky's original paper describing his hierarchy was his 1956 paper "Three models for the description of language" (pdf link) (published in IRE Transactions on Information Theory), but he does not use the term "regular" in this paper; instead he uses the term "finite-state grammars".
  • The term "regular grammar" appears to have been introduced in Chomsky's follow-up 1959 paper "On Certain Formal Properties of Grammars" (pdf link).