Regular Expressions

Area: Text formats and parsing
Related: Markdown, Custom Markdown Syntax, Two Pointers, PostgreSQL

What is it?

A regular expression (regex) is a small pattern language for describing sets of strings. /^\d{4}-\d{2}-\d{2}$/ describes “four digits, dash, two digits, dash, two digits, and nothing else”. You hand the pattern to a regex engine, and it tells you whether a string matches, where, and what each part captured.

Every mainstream language has one built in, and so do editors, grep, databases and log tools. The core syntax is shared. The details (flags, Unicode, lookarounds, how replacement strings work) differ enough to bite you when you copy a pattern between them.

A regex is a tiny program. The engine runs it against your string, and like any program it can be wrong, unreadable, or slow.

All examples in this note were run in Node 22 unless they say otherwise.

Why it exists

In the 1950s Stephen Kleene described “regular sets” in mathematical logic: the languages you can build from single characters with three operations, concatenation (ab), alternation (a|b) and repetition (a*). In 1968 Ken Thompson turned that into a practical algorithm for the QED editor, then ed, which gave Unix grep (from the ed command g/re/p: globally search for a regular expression and print).

Perl in the late 1980s and 1990s made regexes part of everyday programming and added features that go beyond regular languages: backreferences, lookarounds, lazy quantifiers. PCRE (“Perl Compatible Regular Expressions”) copied that dialect into a C library, and most languages since (JavaScript, Python, Java, .NET, PHP) follow the Perl style.

That history explains the biggest split in the regex world, covered under How engines work below. The maths says matching can always be done in linear time. Perl-style features made that impossible in general, so most engines switched to backtracking, which is exponential in the worst case.

The syntax that matters

Characters and classes

Pattern	Matches
abc	literally abc
.	any character except a line break (see flags)
[abc], [a-z]	one character from the set
[^abc]	one character not in the set
\d, \w, \s	digit, word char ([A-Za-z0-9_]), whitespace
\D, \W, \S	the opposites
\., \*, \\	escaped metacharacters, matched literally
\p{L}, \p{Script=Greek}	Unicode property (JS needs the u or v flag)

Inside [...] most metacharacters are literal. [.*] matches a dot or a star. Only ], \, ^ (at the start) and - (between two chars) are special.

Anchors

Pattern	Means
^, $	start and end of the input (or of each line with the m flag)
\b	word boundary: between a \w and a non-\w
\B	not a word boundary

Anchors match a position, not a character. They have zero width.

Validation without anchors is the classic bug: /\d{4}/.test("abc12345xyz") is true, because it found four digits somewhere. If you mean the whole string, write ^...$.

Quantifiers

Greedy	Lazy	Means
*	*?	0 or more
+	+?	1 or more
?	??	0 or 1
{n}		exactly n
{n,m}	{n,m}?	n to m

Greedy takes as much as it can, then gives back. Lazy takes as little as it can, then takes more. Real output:

'<b>x</b><b>y</b>'.match(/<b>.*<\/b>/)[0]    // '<b>x</b><b>y</b>'
'<b>x</b><b>y</b>'.match(/<b>.*?<\/b>/)[0]   // '<b>x</b>'

Often a negated class is clearer and faster than lazy: <b>[^<]*</b> can’t run past the next tag at all.

Groups, captures and alternation

Pattern	Means
(abc)	capture group, numbered from 1 by its opening paren
(?<year>\d{4})	named capture group
(?:abc)	group without capturing (for `
a|b	either side
\1, \k<year>	backreference: the same text a group already matched

Alternation is ordered in backtracking engines. The first alternative that leads to an overall match wins, not the longest:

'foobar'.match(/foo|foobar/)[0]   // 'foo'

Put the longer alternative first, or anchor the pattern so the short one can’t succeed.

Backreferences match the same text, not the same pattern. /^(['"]).*\1$/ matches a string wrapped in matching quotes: "hi" yes, "hi' no.

Lookarounds

Zero-width checks that don’t consume characters.

Pattern	Means
(?=...)	followed by
(?!...)	not followed by
(?<=...)	preceded by
(?<!...)	not preceded by

'$10 and €20 and $30'.match(/(?<=\$)\d+/g)   // ['10', '30']

The classic use is password rules: ^(?=.*\d)(?=.*[a-z]).{8,}$ means “at least 8 chars, contains a digit, contains a lowercase letter”. Each lookahead scans from the start without moving the position.

JavaScript specifics

Flags

Flag	Effect
g	global: find all matches; makes the regex stateful (lastIndex)
i	case-insensitive
m	^ and $ match at line breaks
s	. also matches line breaks (“dotAll”)
u	Unicode mode: code points, \p{...}, stricter syntax
v	newer Unicode mode: set operations in classes, string properties
y	sticky: match only exactly at lastIndex
d	record start/end indices for each group

The lastIndex trap

A regex with g or y remembers where its last match ended, and test and exec start from there. Real output:

const g = /a/g;
g.test('a'); g.test('a'); g.test('a');   // true, false, true
 
const startsWithA = /^a/g;
['apple', 'avocado', 'banana'].filter(w => startsWithA.test(w));
// ['apple']   ← 'avocado' was tested starting at index 1 and failed

Rule: don’t put g on a regex you use with test. Use g only with matchAll, replace/replaceAll and match, which reset lastIndex themselves.

The methods

/\d+/.test(s)                     // boolean
s.match(/\d+/)                    // first match with groups and index (null if none)
s.match(/\d+/g)                   // array of all matched strings, no groups (null if none)
[...s.matchAll(/(\d)(\w)/g)]      // every match WITH groups and index (needs g)
s.replace(/x/g, 'y')              // replace all because of g
s.replaceAll(/x/g, 'y')           // same; throws without g
s.split(/,\s*/)                   // split on a pattern
s.search(/\d/)                    // index of first match, or -1

[...'a1b22c333'.matchAll(/\d+/g)].map(m => [m[0], m.index])
// [['1', 1], ['22', 3], ['333', 6]]
 
'a1b2c'.split(/\d/)     // ['a', 'b', 'c']
'a1b2c'.split(/(\d)/)   // ['a', '1', 'b', '2', 'c']   ← captured separators are kept

Replacement strings have their own mini-language

In the replacement	Inserts
$&	the whole match
$1, $<name>	a group
$`, $'	text before / after the match
$$	a literal $

'John Smith'.replace(/(\w+) (\w+)/, '$2, $1')   // 'Smith, John'
'cost: 5'.replace(/\d+/, '$$$&')                // 'cost: $5'
'x'.replace('x', '$&$&')                        // 'xx'  ← even with a string pattern

That last line is the surprise. If the replacement comes from user input and contains $, it gets interpreted. Pass a function to get the text exactly: s.replace(re, () => userText).

Named groups and indices

const m = /(?<y>\d{4})-(?<m>\d{2})/d.exec('on 2026-10 ok');
m.groups          // { y: '2026', m: '10' }
m.indices.groups  // { y: [3, 7], m: [8, 10] }

Named groups make patterns survive edits. Add a group and $2 silently points somewhere else, but $<m> doesn’t move.

Building a regex from a string

new RegExp('a.c').test('abc')   // true: '.' is still a metacharacter

Escape user input before putting it in a pattern:

const escapeRegExp = (s: string) => s.replace(/[.*+?^${}()|[\]\\]/g, '\\$&');

A standard RegExp.escape has been added to the language. Node 22 doesn’t have it yet (typeof RegExp.escape is 'undefined'), so check your runtime before relying on it.

Also double your backslashes in string literals: new RegExp('\d').source is 'd', because '\d' in a JS string is just d. Write '\\d' or use String.raw.

Unicode

Without the u flag, JavaScript regexes work on UTF-16 code units, not characters. Real output:

/^.$/.test('😀')        // false   ('😀'.length is 2: a surrogate pair)
/^.$/u.test('😀')       // true
/^\w+$/.test('café')    // false   (\w is ASCII only)
/^\p{L}+$/u.test('café')// true
/K/i.test('k')     // false   (U+212A is the Kelvin sign, K)
/K/iu.test('k')    // true    (Unicode case folding)

So: use u (or v) for anything that touches user text. It also makes the syntax stricter, so typos like a stray \- outside a class become errors instead of silently matching something.

The v flag adds set operations inside classes:

/[\p{L}--[a-z]]/v.test('a')   // false: letters, minus ASCII lowercase
/[\p{L}--[a-z]]/v.test('é')   // true

Even with u, . matches one code point, not one user-visible character. A flag emoji or é written as e + combining accent is several code points. For “characters” as people see them, use Intl.Segmenter (see Intl).

How engines work

Automata (Thompson, RE2, Go, Rust)

A regular expression can be compiled to a finite automaton. An NFA (nondeterministic finite automaton) has states and transitions. Thompson’s trick is to simulate it by tracking the set of states you could be in, and moving all of them forward one character at a time.

• Time: O(pattern size × input length). Always. No input can blow it up.
• Cost: no backreferences (they aren’t regular), and lookarounds are limited or missing.
• Used by: RE2 (Google), Go’s regexp, Rust’s regex crate, and the original grep/awk style tools.

A DFA precomputes every set of NFA states as a single state. Fastest to run, but the number of states can explode, so engines build DFA states lazily and fall back when the cache gets big.

Backtracking (Perl, PCRE, JS, Python, Java, .NET, Ruby)

The engine tries one path, and when it fails it backs up to the last choice point and tries the next. A + is a choice (“one more, or stop here?”), and so is every |.

• Good: supports everything: backreferences, lookarounds, lazy quantifiers, possessive quantifiers and atomic groups in some flavours.
• Bad: when there are many ways to split the input between nested or adjacent quantifiers, and the match ultimately fails, the engine tries all of them. That’s exponential.

Catastrophic backtracking, measured

/^(a+)+$/ against 'aaa...a!'. The ! guarantees failure, and the engine tries every way to split the as between the inner and outer +.

Input length (as)	Node 22 (V8)	Python 3 (re)
20	34 ms	38 ms
22		150 ms
24	105 ms	601 ms
26	418 ms
28	1,705 ms

Each extra character roughly doubles the time. At 40 characters it would run for hours. The fix is to remove the ambiguity: /^a+$/ gives the same answers and took well under a millisecond at every length.

It doesn’t need nested quantifiers. A trailing whitespace check /\s+$/ is quadratic on a long run of spaces followed by a non-space, because it starts at each space and scans to the end before failing:

Spaces then x	/\s+$/.test()
10,000	160 ms
20,000	629 ms
40,000	2,516 ms

That exact shape (whitespace trimming with a regex) took Stack Overflow down in 2016, when a post contained about 20,000 consecutive whitespace characters. Cloudflare had a global outage in 2019 from a WAF rule containing .*(?:.*=.*). Both published postmortems; they’re worth reading.

V8’s linear engine

V8 has an experimental non-backtracking engine behind a flag. Real output with node --enable-experimental-regexp-engine and the l flag:

new RegExp('^(a+)+$', 'l') on 28 a's + '!'      → 0.01 ms
                            on 100,000 a's + '!' → 3.91 ms
new RegExp('(a)\\1', 'l')  → Invalid regular expression: /(a)\1/l: Cannot be executed in linear time

Exactly the trade-off from the theory: linear time, but no backreferences. It’s experimental, so don’t ship on it. If you need guaranteed linear time in Node today, the re2 npm package wraps Google’s RE2.

Defending against ReDoS

ReDoS (regular expression denial of service) is sending input designed to hit the slow path.

• Avoid ambiguity. No nested quantifiers on overlapping things ((a+)+, (\w+\s?)*). No adjacent quantifiers that can match the same characters (\d+\d+, .*.*).
• Prefer specific classes to .*. "[^"]*" instead of ".*?".
• Cap the input length before matching.
• Use a linear engine (RE2, Go, Rust) for patterns or input from users.
• Run untrusted matching off the main thread with a timeout (Web Workers in the browser, worker threads in Node).
• Linters (eslint-plugin-regexp, safe-regex style checkers) catch many risky shapes.

Other performance notes

• Compile once. A regex literal inside a loop body is fine (engines cache literals), but new RegExp(...) in a hot loop recompiles each time.
• A literal prefix helps. Engines search for the fixed part first (ERROR: in /ERROR: (\w+)/), then run the full pattern only near hits.
• indexOf / includes / startsWith are faster and clearer when you don’t need a pattern.

Flavours: the same pattern isn’t the same everywhere

	JS	Python re	PCRE / PHP	Go / RE2 / Rust	POSIX ERE (grep -E)
Engine	backtracking	backtracking	backtracking	automata	depends
Lookbehind	yes (any length)	fixed length only	fixed length (mostly)	no	no
Backreferences	yes	yes	yes	no	in BRE, not ERE (often supported anyway)
Named group	(?<n>)	(?P<n>) only ((?<n>) is an error in 3.13)	both	(?P<n>), newer (?<n>)	no
\d	yes	yes (Unicode digits in str!)	yes	yes	depends on the tool; use [0-9]
Replacement group ref	$1	\1 or \g<1>	$1 or \1	$1 / ${1}	n/a

A few that cause real bugs:

• Python’s \d on str matches any Unicode digit, including Arabic-Indic ٣. int() accepts those too, but other code might not. Use [0-9] or the re.ASCII flag when you mean ASCII.
• Python’s re.match anchors at the start but not the end. Use re.fullmatch for validation.
• POSIX classes like [[:digit:]] and [[:alpha:]] work in grep and Postgres, not in JS.
• Postgres has ~ (match), ~* (case-insensitive), regexp_replace, regexp_matches. Its flavour is Tcl’s ARE, close to Perl but not the same.
• macOS and GNU grep differ on \d, \w and -P (Perl mode). Scripts that work on one break on the other.

When not to use a regex

• Nested structure. HTML, JSON, Markdown, code. Regular languages can’t count matching brackets. Use a parser. The Custom Markdown Syntax note shows a regex rewriting text inside code blocks for exactly this reason.
• Email validation. The full grammar is huge and still says nothing about whether the mailbox exists. Check for one @ with something on each side, then send a confirmation email.
• URLs. Use new URL(input) and check .protocol and .hostname.
• Dates. A regex can check the shape \d{4}-\d{2}-\d{2}, but not that 2026-02-30 doesn’t exist. Parse it.
• Simple fixed strings. includes, startsWith, split(',').

Regex is good at: tokenizing (one token type at a time, in a loop), finding and extracting from flat text, search and replace in editors, log parsing, and quick shape checks in front of a real parser.

Reading and writing them without pain

• Build up from tests. Write five strings that should match and five that shouldn’t, then grow the pattern until they pass. regex101.com shows matches, groups and a step-by-step explanation per flavour.
• Comment complex patterns. JS has no verbose mode, so build from parts:

const date = /(?<y>\d{4})-(?<m>\d{2})-(?<d>\d{2})/.source;
const time = /(?<h>\d{2}):(?<min>\d{2})/.source;
const timestamp = new RegExp(`^${date}T${time}$`, 'u');

Python (re.VERBOSE) and PCRE ((?x)) let you put whitespace and # comments inside the pattern.

• Name groups, and use (?:...) for groups you don’t need.
• Anchor validation patterns.

A real-world example

A log search box in an internal admin dashboard lets support staff filter server logs:

• Plain text search is the default and uses includes. Most searches don’t need a pattern.
• Regex mode is opt-in. The pattern runs on the server through RE2, so a pasted (a+)+ can’t freeze anything.
• Input length is capped, and each query has a timeout.
• Structured fields (timestamp, level, request id) are extracted once at ingest time with a named-group pattern, and stored as columns, so most filters are plain equality checks.
• Highlighting in the UI uses the d flag’s indices to wrap matches, and builds the highlighted output from text nodes rather than HTML strings.
• User search terms in plain mode are escaped before they go into any pattern.

Gotchas

• g on a regex used with test or exec makes results alternate because of lastIndex.
• No anchors means “contains”, not “is”.
• . doesn’t match newlines without s, and doesn’t match an emoji as one character without u.
• \w, \b and \d are ASCII in JS, even with u. Use \p{L}, \p{N}.
• $& and $1 are interpreted in replacement strings, even when the pattern is a plain string.
• new RegExp('\d') is /d/. Double the backslash.
• Alternation takes the first alternative that works, not the longest.
• match with g drops groups. Use matchAll.
• Nested quantifiers and long runs of a repeated character are where backtracking engines go exponential or quadratic.
• Patterns aren’t portable between JS, Python, Go, Postgres and grep. Test them in the engine that will run them.

Practice

1. Write a pattern for HH:MM 24-hour times that rejects 24:00 and 9:5. Test it with 10 good and 10 bad strings.
2. Extract every key=value pair from a=1; b = two;c=3 with matchAll and named groups.
3. Reproduce the catastrophic backtracking table on your machine, then rewrite (\w+\s?)*$ so it’s linear.
4. Write a tokenizer for arithmetic (12 + (3.5*x)) using one sticky (y) regex per token type, advancing lastIndex by hand.
5. Implement Thompson’s construction: compile a(b|c)*d to an NFA and simulate it with a set of states. Compare its timing with /^(a+)+$/ on the bad input.
6. Port a JS pattern with lookbehind and named groups to Go, and work out what you have to change when RE2 refuses it.

Sources worth reading

• Russ Cox, “Regular Expression Matching Can Be Simple And Fast” (and the follow-up articles on RE2): https://swtch.com/~rsc/regexp/
• MDN, “Regular expressions” guide and the RegExp reference
• regex101 (tester with explanations, several flavours): https://regex101.com/
• Stack Overflow’s July 2016 outage postmortem
• Cloudflare, “Details of the Cloudflare outage on July 2, 2019”
• V8 blog, “An additional non-backtracking RegExp engine”
• Jeffrey Friedl, Mastering Regular Expressions