Backreferences

A backreference like \1 matches the same text that capture group 1 matched. This breaks the regular-language model — backreferences make the grammar context-sensitive.

Examples

(\w+) \1            # repeated word: matches 'the the' but not 'the cat'
(\d+)x\1            # 'NxN' for matching N: '5x5', '42x42'
<(\w+)>.*</\1>     # balanced HTML-ish: <b>bold</b>
(\w)\1+            # 3+ repeated char: 'aaaa', 'oooo'

Why they break linear-time matching

A DFA has finite state — it cannot 'remember' an arbitrary previously- matched string. To check \1, the engine must:

1. Record what group 1 captured (variable-length string).
2. At \1, compare the next input chars char-by-char against that record.

This is fundamentally not expressible as an NFA. It REQUIRES backtracking because the captured value depends on the matching path chosen for group 1.

Pathological case

^(a+)\1$ on 'aaaaaaaaaaaa'

The engine tries each possible length for (a+) — 1, 2, 3, ... — then checks whether twice that many as consume the input. For 2n a's this is O(n) backtracks, each O(n) to compare = O(n²). For nested backrefs, worse.

RE2's position

Google's RE2 (used in Go, gVisor, and many Google services) refuses to support backreferences. From the docs:

The syntax of the regular expressions accepted is the same general syntax used by Perl, Python, and other languages. More precisely, it is the syntax accepted by RE2 and described at https://golang.org/s/re2syntax, except for \C.

No \1. No (?=...). No (?<=...). The bet: linear-time guarantees are worth more than expressiveness for engines that face untrusted regex input (security, multi-tenant search).

For THIS lesson: use Python's re, which supports backrefs via backtracking. Understand WHY they're slow, so you can pick the right tool.

Named backrefs

Same semantics, more readable for complex patterns.