Regular Expressions

You should not be permitted to write production code if you do not have an journeyman licence in regular expressions or floating point math. —Rob Pike

a regular expression is two things wearing one syntax: a seventy-year-old theorem about finite automata, and the single most-used text-processing tool on unix. 𐃏 this page takes both seriously: the theory tells you exactly what the notation can and cannot express, and the theory’s failure modes (backtracking blowups, backreference NP-hardness, the html-parsing folklore) are precisely where practitioners get burned.

quick reference#

. single character
\ escape
? optional character
* zero or more of previous
+ one ore more
| or on the word level
[] or for specific characters
^ not
\d digit
\s whitespace (tabs, carriage returns, null)
\b word boundary
\d{4} equiv \d\d\d\d
parenthesis and ? makes the stuff in parens optional
same for + and *
\w{n} n letter words
\w{n,k} n or k letter words

quantifiers and greed#

?*+ are “quantifiers”

*+ are greedy

*? is the non-greedy version

greedy quantifiers grab the longest match they can and give characters back only when forced; non-greedy ones grab the shortest and extend only when forced. the classic burn: <.*> applied to <b>bold</b> matches the whole string (the greedy .* runs to the last >), while <.*?> matches just <b>.

try not to use ranges: [0-9]. the reason is locales: under collation orders other than C, a range like [a-z] can match characters you did not intend (accented letters, sometimes even uppercase, depending on the locale’s sort order). posix classes [[:digit:]], [[:alpha:]] or perl-style \d, \w say what you mean regardless of locale.

three notations, one language class#

fix a finite alphabet \(\Sigma\). regular expressions over \(\Sigma\) are built inductively: \(\emptyset\), \(\varepsilon\), and each literal \(a \in \Sigma\) are regular expressions, and if \(r, s\) are, then so are the union \(r \mid s\), the concatenation \(rs\), and the kleene star \(r^{*}\). that is the entire language — everything else in the quick reference above (+, ?, {n,k}, character classes) is syntactic sugar: \(r^{+} = rr^{*}\), \(r? = (r \mid \varepsilon)\), and [abc] is \((a \mid b \mid c)\) (Epp, Susanna S., 2019).

kleene’s theorem. the following three formalisms describe exactly the same class of languages — the regular languages:

• regular expressions,
• nondeterministic finite automata (NFAs), with or without \(\varepsilon\)-transitions,
• deterministic finite automata (DFAs).

each direction of the equivalence is a compilation algorithm you can actually run: regex to NFA is thompson’s construction, NFA to DFA is the subset construction, and DFA back to regex is state elimination. 𐃏 the string-matching-by-automaton connection is developed in (Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford, 2009).

thompson’s construction: regex to NFA#

compile the regex bottom-up over its parse tree; every subexpression becomes an NFA fragment with one start state and one accepting state, glued together with \(\varepsilon\)-transitions:¹

• literal \(a\): two states joined by an edge labelled \(a\).
• union \(r \mid s\): a new start state with \(\varepsilon\)-edges into the fragments for \(r\) and \(s\); their accepting states get \(\varepsilon\)-edges into a new common accepting state.
• concatenation \(rs\): the accepting state of \(r\)’s fragment is identified with (or \(\varepsilon\)-linked to) the start state of \(s\)’s fragment.
• star \(r^{*}\): a new start-accept pair; \(\varepsilon\)-edges let you skip the fragment entirely (zero repetitions) or loop from its accept back to its start (more repetitions).

each operator adds at most two states, so a regex of length \(n\) compiles to an NFA with \(O(n)\) states, each carrying at most two outgoing edges. simulating that NFA directly — carrying the set of live states across the text — matches a text of length \(m\) in \(O(nm)\) time, no exponential anywhere. 𐃏

subset construction: NFA to DFA, worked#

the DFA that simulates an NFA keeps one state per set of NFA states reachable on some input. compute only the reachable sets and the blowup is usually tame (worst case \(2^{n}\), and that worst case is achievable).

the standard example: \((a \mid b)^{*}abb\).¹ thompson’s construction gives eleven states, numbered as in the dragon book:

0 -eps-> 1, 7        1 -eps-> 2, 4
2 --a--> 3           4 --b--> 5
3 -eps-> 6           5 -eps-> 6
6 -eps-> 1, 7        7 --a--> 8
8 --b--> 9           9 --b--> 10   (10 accepting)

the construction itself is a dozen lines of python — a worklist of subset states, \(\varepsilon\)-closure, move:

# thompson NFA for (a|b)*abb, dragon-book state numbering
eps = {0: {1, 7}, 1: {2, 4}, 3: {6}, 5: {6}, 6: {1, 7}}
sym = {(2, 'a'): 3, (4, 'b'): 5, (7, 'a'): 8, (8, 'b'): 9, (9, 'b'): 10}

def closure(S):
    S, stack = set(S), list(S)
    while stack:
        for r in eps.get(stack.pop(), ()):
            if r not in S:
                S.add(r); stack.append(r)
    return frozenset(S)

def move(S, c):
    return closure({sym[q, c] for q in S if (q, c) in sym})

start = closure({0})
names, work = {start: 'A'}, [start]
while work:
    S = work.pop(0)
    row = [names[S], str(sorted(S))]
    for c in 'ab':
        T = move(S, c)
        if T not in names:
            names[T] = chr(ord('A') + len(names)); work.append(T)
        row.append(names[T])
    star = '*' if 10 in S else ' '
    print(f"{row[0]}{star} {row[1]:<24} a->{row[2]}  b->{row[3]}")

A  [0, 1, 2, 4, 7]          a->B  b->C
B  [1, 2, 3, 4, 6, 7, 8]    a->B  b->D
C  [1, 2, 4, 5, 6, 7]       a->B  b->C
D  [1, 2, 4, 5, 6, 7, 9]    a->B  b->E
E* [1, 2, 4, 5, 6, 7, 10]   a->B  b->C

five subset states, E accepting (it contains NFA state 10). now look at rows A and C: identical transitions, both non-accepting — indistinguishable, so minimisation merges them. the minimal DFA has four states. relabelling the merged machine (\(A\) absorbs \(C\); old \(D\), \(E\) become \(C\), \(D\)):

sanity check on \(ababb\): \(A \xrightarrow{a} B \xrightarrow{b} C \xrightarrow{a} B \xrightarrow{b} C \xrightarrow{b} D\). accept, as it should — \(ababb\) ends in \(abb\). and \(abab\) halts in \(C\), non-accepting. the automaton’s state is literally “which prefix of \(abb\) did the last few characters spell”.

what regular cannot do#

a DFA has finitely many states, so it can only remember finitely many things about the prefix it has read. the pumping lemma turns that observation into a weapon.

pumping lemma (regular languages). if \(L\) is regular, then there exists an integer \(p \ge 1\) (the pumping length) such that every string \(w \in L\) with \(|w| \ge p\) can be written \(w = xyz\) where

1. \(|y| \ge 1\),
2. \(|xy| \le p\), and
3. \(xy^{i}z \in L\) for every integer \(i \ge 0\).

proof idea: take \(p\) to be the number of states of a DFA for \(L\). reading the first \(p\) characters of \(w\) visits \(p + 1\) states, so by pigeonhole some state repeats; the substring \(y\) consumed between the two visits traverses a loop, and the machine cannot tell whether you went around that loop zero times or a hundred.²

the classic casualty: \(a^{n}b^{n}\)#

claim: \(L = \{a^{n}b^{n} : n \ge 0\}\) is not regular. suppose it were, with pumping length \(p\). take \(w = a^{p}b^{p} \in L\); certainly \(|w| = 2p \ge p\). any decomposition \(w = xyz\) with \(|xy| \le p\) places \(x\) and \(y\) entirely inside the leading block of \(a\)’s: \(x = a^{s}\), \(y = a^{k}\) with \(k \ge 1\) and \(s + k \le p\). pump up once (\(i = 2\)):

\begin{equation} xy^{2}z = a^{p+k}\,b^{p} \notin L \quad \text{since } k \ge 1, \end{equation}

contradicting condition 3. so no DFA recognises \(L\): counting unboundedly requires unbounded memory. 𐃏

engines: backtracking vs automata#

two implementation families, wildly different worst cases:³

• backtracking engines — perl, python re, pcre, java, javascript, ruby. compile the pattern to a tree or bytecode and run a recursive depth-first search for a match, retrying alternatives on failure. flexible (backreferences and lookaround come almost for free) but worst-case exponential in the input.
• automata engines — grep, awk, RE2, rust’s regex crate, go’s regexp. thompson NFA simulation with a lazily-built DFA. worst-case linear in the input, but they must forgo the non-regular features.

catastrophic backtracking, measured#

the pattern (a+)+$ against the string \(a^{n}b\) is the canonical bomb: the string cannot match (it ends in b), but before giving up the backtracker must try every way of carving the run of \(a\)’s into “one-or-more groups of one-or-more” — and there are exponentially many carvings.

import re, time

pattern = re.compile(r'(a+)+$')
for n in range(16, 27, 2):
    s = 'a' * n + 'b'
    t0 = time.perf_counter()
    pattern.match(s)
    dt = time.perf_counter() - t0
    print(f"n = {n:2d}   {dt:8.4f} s")

n = 16     0.0017 s
n = 18     0.0062 s
n = 20     0.0234 s
n = 22     0.0867 s
n = 24     0.5005 s
n = 26     1.4948 s

adding two characters multiplies the time by three to four — clean exponential growth. extrapolating, \(n = 40\) takes around a day and \(n = 64\) outlives you. meanwhile the same query through grep’s automata engine, on an input nearly four times longer:

python3 -c "print('a'*100 + 'b')" > long.txt
time grep -cE '(a+)+$' long.txt

0

real	0m0.002s
user	0m0.001s
sys	0m0.001s

two milliseconds, mostly process startup. the asymmetry is not academic: cloudflare’s july 2019 global outage was a single catastrophically-backtracking regex in a waf rule. 𐃏

the features that break regularity#

• backreferences — (\w+) \1 matches a repeated word. this steps outside the regular languages entirely (the language \(\{ww : w \in \Sigma^{*}\}\) is not regular — pumping lemma again), and it costs: matching a pattern with backreferences against a string is NP-hard in general.⁴ every engine that supports them is a backtracker on those patterns, by necessity.
• lookahead and lookbehind — (?=...), (?!...), (?<=...), (?<!...) assert without consuming. lookaround alone does not leave the regular class (regular languages are closed under intersection and complement), but backtracking implementations pay for it with extra search, and automata engines like RE2 simply refuse the syntax rather than surrender their linear-time guarantee.
• the lesson: pcre-style “regexes” are a superset of regular expressions in expressiveness and a downgrade in worst-case behaviour. know which features you are paying for.

the everyday toolkit#

friedl’s mastering regular expressions is the standard practitioner’s book for everything below; the theory above is what it politely skips. all outputs below are real runs against this table:

printf 'alice 34 sydney\nbob 41 perth\ncarol 29 sydney\ndave 55 hobart\n' > people.txt

grep#

grep prints lines matching a pattern; -E turns on extended syntax (the old egrep), -c counts, -v inverts, -o prints only the matching part.

grep -E 'sydney$' people.txt              # lines ending in sydney
grep -Ec '^[a-z]+ [0-9]{2} ' people.txt   # count lines shaped name-age-city

alice 34 sydney
carol 29 sydney
4

sed#

the stream editor: apply an edit script to every line flowing past (Dougherty, Dale and Robbins, Arnold, 1997). the three idioms covering ninety percent of real usage — substitution, addressing, substitution-with-a-class:

printf 'the cat sat on the mat\nthe dog sat on the log\n' | sed 's/sat/stood/'
printf 'one\ntwo\nthree\nfour\n' | sed -n '2,3p'      # print only lines 2-3
printf 'field1,field2,field3\n' | sed -E 's/,/\t/g'   # csv to tsv

the cat stood on the mat
the dog stood on the log
two
three
field1	field2	field3

portability trap: in-place editing is sed -i 's/x/y/' file with GNU sed (linux) but sed -i '' 's/x/y/' file with BSD sed (macos) — BSD’s -i requires a backup-suffix argument, so an empty one must be passed explicitly. scripts that must run on both usually write to a temp file and mv.

awk#

awk splits each line into fields ($1, $2, …, whitespace-delimited by default, -F to change) and runs pattern { action } rules over the stream — a full programming language that happens to fit on one line (Dougherty, Dale and Robbins, Arnold, 1997).

awk '{sum += $2} END {printf "total age: %d, mean: %.1f\n", sum, sum/NR}' people.txt
awk '$3 == "sydney" {print $1}' people.txt   # select rows, project a column
awk -F, '{print $2}' <<< 'a,b,c'             # comma-separated fields

total age: 159, mean: 39.8
alice
carol
b

the first line is SELECT sum(age), avg(age); the second is a WHERE clause with projection. awk is relational algebra for people who refuse to leave the terminal.

capture groups, named groups, substitution#

parentheses capture; (?P<name>...) captures with a name (python syntax); backreferences reuse captures in the pattern or the replacement:

import re

log = "2026-07-07 14:32:01 ERROR disk full on /dev/sda1"

# positional groups
m = re.match(r'(\d{4})-(\d{2})-(\d{2})', log)
print(m.groups())
print(m.group(1))

# named groups
pat = re.compile(r'(?P<date>\S+) (?P<time>\S+) (?P<level>\w+) (?P<msg>.*)')
m = pat.match(log)
print(m.group('level'), '->', m.group('msg'))
print(m.groupdict()['time'])

# re.sub with backreferences: yyyy-mm-dd becomes dd-mm-yyyy
print(re.sub(r'(\d{4})-(\d{2})-(\d{2})', r'\3-\2-\1', log))

# named backreference in pattern and replacement: collapse doubled words
print(re.sub(r'(?P<w>\b\w+) (?P=w)\b', r'\g<w>', "the the cat sat sat down"))

('2026', '07', '07')
2026
ERROR -> disk full on /dev/sda1
14:32:01
07-07-2026 14:32:01 ERROR disk full on /dev/sda1
the cat sat down

named groups cost nothing at match time and save every future reader from counting parentheses. use them in any pattern with more than two groups.

when not to use regex#

• html, xml, json, or anything nested. balanced tags are the \(a^{n}b^{n}\) language in a costume, and the pumping lemma already proved no regular expression recognises that. the folklore reference is the 2009 stackoverflow answer that descends into zalgo-text madness while explaining why regex cannot parse html — comedic in form, correct in substance.⁵ reach for an actual parser; every language ships one.
• recursive structure in general — matched parentheses, nested comments, indentation-scoped blocks. pcre’s recursive patterns ((?R)) can technically handle some of this, at which point you have written an unreadable parser with an exponential worst case. write the readable one instead.
• fixed-format fields — if the input is genuinely columnar, awk field splitting or a split(',') is clearer and faster than a regex with seventeen groups.
• when the pattern outgrows one line. a regex you cannot re-read in six months is a liability; re.VERBOSE with comments is the halfway house, a real tokeniser is the cure.

the meta-rule: a regex is a specification of a regular language. the moment the thing you are matching needs a counter or a stack, the formalism is lying to you — it will half-work on your examples and fail in production on the nested case you did not test.

see also#

• linux — the parent section
• shell — where these one-liners live
• shell commands — grep, sed and awk among their siblings
• vim — a second regex dialect you already half-know
• computational complexity — where claims like “NP-hard” live

References#

Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford (2009). Introduction to Algorithms, MIT Press.

Dougherty, Dale and Robbins, Arnold (1997). Sed \& Awk, O’Reilly Media.

Epp, Susanna S. (2019). Discrete Mathematics with Applications, Cengage Learning.