# Regular Expressions (Regex) A regular expression is a compact notation for describing a *pattern* over text. A single pattern defines a set of strings; an engine then checks whether a given string belongs to that set (matching), finds where it occurs (searching), or rewrites it (substitution). Regexes are one of the most widely reused abstractions in computing: the same syntax works in editors, shells, programming languages, log processors, and validators. The name comes from *regular languages* in formal language theory — the class of languages recognizable by a finite-state machine. In practice, most modern "regex" engines have grown far beyond that theoretical core (backreferences, lookaround), so the term is now looser than its origin. ## Core Building Blocks ### Literals and metacharacters Most characters match themselves (`abc` matches the text `abc`). A handful are *metacharacters* with special meaning: `. ^ $ * + ? ( ) [ ] { } | \`. To match one literally, escape it with a backslash (`\.` matches a real dot). ### Character classes - `[aeiou]` — any one of the listed characters - `[^0-9]` — any character *except* a digit (negation) - `[a-z]` — a range - Shorthands: `\d` (digit), `\w` (word character), `\s` (whitespace), and their negations `\D`, `\W`, `\S` - `.` — any character except newline (usually) ### Anchors and boundaries - `^` — start of line/string - ` — end of line/string - `\b` — word boundary; `\B` — non-boundary Anchors match *positions*, not characters — they consume nothing. ### Quantifiers - `*` — zero or more - `+` — one or more - `?` — zero or one (optional) - `{n}`, `{n,}`, `{n,m}` — explicit counts Quantifiers are *greedy* by default (match as much as possible). Appending `?` makes them *lazy* (match as little as possible): `.*?` versus `.*`. ### Grouping, alternation, backreferences - `(...)` — a capturing group; also scopes quantifiers and alternation - `(?:...)` — a non-capturing group (grouping without the capture cost) - `a|b` — alternation (match `a` or `b`) - `\1`, `\2` — backreferences to earlier captured groups - `(?<name>...)` and `\k<name>` — named captures, in engines that support them ### Lookaround Zero-width assertions that test context without consuming it: - `(?=...)` — positive lookahead - `(?!...)` — negative lookahead - `(?<=...)` — positive lookbehind - `(?<!...)` — negative lookbehind ## How Engines Work There are two broad implementation strategies, and the difference has real consequences: - **DFA/NFA (Thompson-style, automata-based)** — used by tools like [[ripgrep]] and RE2. Match time is linear in the input length. The trade-off: no backreferences or arbitrary lookaround, because those features cannot be expressed as a pure finite automaton. - **Backtracking** — used by PCRE, Perl, Python's `re`, [[JavaScript]], Java, .NET. Supports the full feature set (backreferences, lookaround), but can suffer *catastrophic backtracking*: certain patterns take exponential time on adversarial input. The practical rule: if you only need the "regular" subset, an automata engine is faster and safer. If you need backreferences, you accept the backtracking risk. ## Flavors Are Not Universal "Regex" is a family, not a single standard. Common dialects: - **POSIX BRE/ERE** — the older grep/sed/awk syntax; BRE requires `\(` for grouping - **PCRE** — Perl-Compatible Regular Expressions; the de facto rich standard - **Language built-ins** — [[Python]] `re`, JavaScript `RegExp`, Java `java.util.regex`, Go `regexp` (RE2-based) Behavior differs in escaping rules, lookbehind support, Unicode handling, and default multiline semantics. Always check the specific flavor before assuming a pattern is portable. ## Common Uses - **Validation** — emails, phone numbers, IDs (though full email validation is famously beyond regex) - **Search & replace** — in editors like [[Vim]], IDEs, and command-line tools - **Extraction** — pulling structured fields out of log lines or scraped text - **Tokenization** — a first-pass step in parsers and lexers - **Filtering** — [[grep]]/[[ripgrep]] over files and streams ## Pitfalls and Guidance - **Catastrophic backtracking (ReDoS)** — nested quantifiers over overlapping alternations (e.g. `(a+)+) can hang a backtracking engine on crafted input. Untrusted input plus a backtracking engine is a denial-of-service vector. Prefer RE2-style engines when input is untrusted. - **"Now you have two problems"** — the classic [[Jamie Zawinski]] quip warns against reaching for regex where a real parser belongs. Regex cannot correctly parse recursively nested structures (HTML, balanced parentheses, most programming languages) — those are not regular languages. - **Readability decays fast** — long patterns become write-only. Use named groups, verbose/extended mode (`x` flag) with comments, and break complex logic into named sub-steps. - **Greedy vs lazy surprises** — `.*` grabbing more than intended is one of the most common bugs; reach for lazy quantifiers or more specific character classes. - **Escaping and Unicode** — the same pattern can behave differently across flavors; test against representative data, not just the happy path. ## References - [[Jeffrey Friedl]] — *Mastering Regular Expressions* (O'Reilly) - [[Russ Cox]] — "Regular Expression Matching Can Be Simple And Fast": https://swtch.com/~rsc/regexp/regexp1.html - https://en.wikipedia.org/wiki/Regular_expression - https://regex101.com — interactive tester and explainer ## Related - [[grep]] - [[ripgrep]] - [[Vim]] - [[Python]] - [[JavaScript]] - [[Jeffrey Friedl]] - [[Russ Cox]] - [[Jamie Zawinski]]