How Regular Expressions Work: From Theory to Practice
Regular expressions are everywhere a programmer looks. They power search and replace in your editor, form validation on websites, log parsing, and the routing rules in half the tools you use. They also have a reputation for being write-only, the kind of thing you craft once, get working, and never dare to touch again. That reputation is earned, but it fades once you understand what a regular expression actually is. Underneath the punctuation is a small, precise idea with roots in 1950s mathematics.
What a regular expression actually is
A regular expression is a pattern that describes a set of strings. The pattern cat describes exactly one string. The pattern ca+t describes cat, caat, caaat, and so on forever. When you run a regex against some text, the engine is answering a single question: does this input belong to the set of strings my pattern describes?
The idea comes from Stephen Kleene, who formalized what he called regular languages in the 1950s[1] as part of early work on computation. A regular language is a set of strings simple enough to be recognized by a machine with no memory[2] of where it has been, only a current state. That constraint sounds limiting, and it is, which turns out to be the whole point.
The machine behind the pattern
A classic regular expression can be compiled into a finite automaton, a tiny state machine. The machine starts in a state, reads the input one character at a time, and follows a transition for each character. If it lands in an accepting state when the input runs out, the string matches.
There are two flavors worth knowing about. A deterministic finite automaton, or DFA, has exactly one path through the states[3] for any input, so it runs in time proportional to the length of the input and nothing worse. Tools like grep and Google's RE2 library work this way. A nondeterministic finite automaton, or NFA, can have several possible paths at once[4], and most of the regex engines built into programming languages (JavaScript, Python, Java, PCRE) use a backtracking approach that explores those paths by trial and error. Backtracking buys extra features, like backreferences, at a cost we will get to.
The syntax you actually use
Most of regex is a handful of building blocks combined.
abc literal text
. any single character
[a-z] a character class: one lowercase letter
\d \w \s a digit, a word character, whitespace
^ $ start and end of the line
a* zero or more of a
a+ one or more of a
a? zero or one a
a{2,4} between two and four a's
(ab) a group
cat|dog alternation: cat or dog
\. an escaped literal dot
A pattern to loosely match an email might read ^[\w.+-]+@[\w-]+\.[\w.-]+$. It is not a full specification of valid email, and that is usually the right call, because the full specification is a nightmare and you mostly want to catch typos.
Greedy versus lazy
By default, quantifiers are greedy. They match as much as they possibly can, then give characters back only if the rest of the pattern fails. This is the single most common source of surprise. Run <.*> against <b>hello</b> and it matches the entire string, because .* grabs everything up to the last > before backing off.
Add a ? to make a quantifier lazy, and it matches as little as possible instead. <.*?> against the same input matches just <b>. Greedy and lazy produce different results from the same text, so knowing which one you have is often the difference between a pattern that works and one that quietly does the wrong thing.
When regex bites back: catastrophic backtracking
Backtracking engines have a failure mode that can take down a server. Certain patterns, especially nested quantifiers, create an exponential number of ways to match a string. Consider (a+)+$ run against a long run of a characters followed by a single X.
input: aaaaaaaaaaaaaaaaaaaaaaaaaa X
pattern: (a+)+$
The engine tries one way to split the a characters between the inner and outer +, fails at the X, backs up, tries another split, fails again, and works through an astronomical number of combinations before giving up. A few dozen characters can hang the match for seconds or longer. When an attacker can supply the input, this becomes a denial of service bug with its own name, ReDoS.
The defenses are practical. Avoid nesting one quantifier inside another when you can. Prefer engines that do not backtrack, such as RE2, for untrusted input. Use atomic groups or possessive quantifiers where your engine supports them, since they tell the engine not to give characters back. And put a sane length limit on any text you are about to match.
Practical advice
Reach for a regex when you are matching simple, flat patterns in text, and reach for a real parser when the structure nests. HTML, JSON, and source code are not regular languages, and trying to match balanced tags or brackets with a regex leads to pain. The famous rant about parsing HTML with regular expressions is funny because it is true.
When a pattern grows past a line or two, help the next reader, who is probably you. Many engines support a verbose mode that lets you add whitespace and comments inside the pattern. Name your capture groups instead of referring to them by number. Anchor your pattern with ^ and $ when you mean to match a whole string, since an unanchored pattern happily matches a fragment in the middle. Test against real data, including the ugly inputs, not just the clean example you had in mind.
The takeaway
A regular expression is a tiny language that compiles to a tiny machine. That machine is why a well-formed pattern can scan a megabyte of text in a blink, and the backtracking variant is why a careless pattern can stall on a short, hostile input. Learn the handful of operators, keep each pattern small and anchored, and treat anything with nested quantifiers as a thing to test under load before it ever sees a user.