1

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?

8

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 theory1. 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.
  • 1
    Thanks a lot. I have now understood why regular expressions work so good in some contexts and bad in others. It also gives good reasons to explain to others why Regex might not be the right thing. – Thomas Weller Mar 9 '16 at 16:56
  • 1
    I agree that nowadays young people would study regular languages as part of the Chomsky hierarchy, but looking back, when most papers in early 1960s referred to regular expressions, it would mean "Kleene's regular expressions". (E.g., Derivatives of Regular Expressions, Brzozowski (1964), Regular Expressions and State Graphs for Automata, R. McNaughton, H. Yamada (1960).) Kleene's Representation of Events in Nerve Nets and Finite Automata was published in 1951. This post makes long story short. – Damkerng T. Mar 9 '16 at 18:43
  • 1
    @DamkerngT. Super interesting, thanks! Clearly the term "regular" with regards to linguistic structure was in use prior to Chomsky's hierarchy, and it looks like that's where Chomsky got the term. I think, though, Chomsky was still the guy (with contributions from Schützenberger) to formalize regular grammars, and indeed generative grammars on the whole – Ken Bellows Mar 9 '16 at 19:51
  • 1
    This answer can be improved. In formal language theory, the term regular was introduced by Kleene in 1954 in his paper that introduces regular languages and regular expressions. The terms language and grammar were introduced in 1956, by Chomsky; in a 1959 paper, he uses the term regular grammar for what we have since known as Chomsky Normal Form; we now use the term regular grammar for a different class of grammars, that describe the regular languages. – reinierpost Apr 21 '17 at 22:50
  • I emailed Noam Chomsky to ask if he intended any connection between his "regular grammar" and Kleene's "regular event." He said he doesn't remember, but that it is probably just a coincidence of terminology. See my Q and A on the Computer Science stack exchange: cs.stackexchange.com/questions/74329/… – cristoper Apr 22 '17 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.