Regular Expressions
A regular expression (regex) is a formal pattern that describes a set of strings, used to test membership, extract substrings, or perform substitutions. They originate from formal language theory: a regular expression defines a regular language, and a finite automaton can recognize it. In practice, most regex engines implement extensions — backreferences, lookaheads, possessive quantifiers — that exceed formal regularity but remain practically useful. The two dominant engine architectures are NFA-based (Perl, Python, JavaScript) which support backreferences but can exhibit catastrophic backtracking, and DFA-based (RE2, grep) which run in guaranteed linear time but cannot support all Perl-style extensions.
Key Concepts
Syntax Fundamentals
| Construct | Meaning |
|---|---|
. | Any character except newline (by default) |
*, +, ? | Zero-or-more, one-or-more, zero-or-one (greedy) |
*?, +?, ?? | Non-greedy (lazy) variants |
[abc], [^abc] | Character class, negated class |
^, $ | Start/end of string (or line in multiline mode) |
\d, \w, \s | Digit, word character, whitespace (and negations) |
(a|b) | Alternation |
(...) | Capturing group |
(?:...) | Non-capturing group |
(?=...), (?!...) | Lookahead (positive/negative) |
Engine Architecture — NFA engines (backtracking) try alternatives in sequence and backtrack on failure. This enables backreferences but allows pathological patterns like (a+)+b applied to a long string of as to run in exponential time — so-called ReDoS (regular expression denial of service). DFA engines compile the pattern to a state machine that processes the input in a single left-to-right pass, guaranteeing O(n) matching. Go’s regexp package and Google’s RE2 library enforce this guarantee by rejecting constructs that cannot be compiled to a DFA.
Greedy vs. Lazy Quantifiers — Greedy quantifiers consume as much input as possible, then give back characters if necessary to allow the overall match to succeed. Lazy quantifiers consume as little as possible. On <b>text</b>more</b>, the pattern <b>.*</b> greedily matches the entire string; <b>.*?</b> lazily matches <b>text</b>.
Capture Groups and Backreferences — Parentheses capture the matched text, accessible via \1–\9 in substitution strings or as numbered groups in API results. Named groups ((?P<name>...) in Python, (?<name>...) in JavaScript/Perl) improve readability. Backreferences in the pattern itself require NFA semantics and cannot be handled by a pure DFA.
Lookaround — Lookaheads and lookbehinds assert context without consuming characters. \d+(?= dollars) matches a number followed by ” dollars” without including ” dollars” in the match. Most NFA engines support variable-length lookbehind only in newer versions; DFA engines generally do not support it at all.
Common Pitfalls
- Catastrophic backtracking from nested quantifiers — test patterns against worst-case inputs
- Forgetting to anchor patterns when exact matching is intended
- Using regex for hierarchically structured data (HTML, JSON) where a parser is more appropriate
- Assuming character classes like
\wcover Unicode — in many engines\wis ASCII-only unless a Unicode flag is set
Best Practices
- Use non-capturing groups
(?:...)when the captured value is not needed — it is slightly faster and cleaner - Compile patterns once and reuse them in hot paths
- Prefer RE2-derived libraries in security-sensitive contexts to eliminate ReDoS risk
- Comment complex patterns using verbose/extended mode (
re.VERBOSEin Python,xflag in Perl/Ruby)