Anatomy of a Pattern
Characters, classes, anchors, alternation, quantifiers, groups
Literals & Character Classes
Read `[abc]`, `[^0-9]`, and `\d \w \s` and predict the single character each accepts, expand every shorthand into the explicit set it stands for, and tell when a class is tighter than a literal.
Anchors & Alternation
Pin a match to the input's edges with `^` and `$`, isolate a whole word with `\b`, branch with `|`, and predict which substring the eager engine commits to when the bar's reach and the anchors collide.
Quantifiers & Groups
Trace how a quantifier repeats just the token on its left, watch greedy take the maximum and hand characters back while lazy `+?` grows from the minimum, and tell which span each numbered, non-capturing, or named group captures.
The NFA
Thompson construction, state machines, the regex as a graph
Thompson Construction
Compile a regex into an NFA one operator at a time, stamping a two-state fragment for each literal and ε-wired forks, loops, and seams for the operators, and predict the graph each one adds.
NFA Traversal
Run a string through an NFA by carrying the whole set of states the engine could occupy, expanding it for free across ε-arrows on every step, and deciding the match from whether the accept state lands in the final set.
The DFA
Subset construction, when engines convert, the speed trade
Subset Construction
Turn an NFA into a DFA by naming each reachable state-set as one DFA state, then watch the conversion stay cheap until a pattern makes the state count double toward 2 to the n.
DFA vs NFA Engines
Sort the real engines into the two families that either compile a machine or explore choices, see why one can never hang while only the other supports backreferences, and pick the family a given constraint demands.
Backtracking & Catastrophe
Recursive descent, capture, backreferences, the patterns that hang
Recursive Descent & Capture
Walk a backtracking engine through a pattern with capture groups, predict the span each numbered group records, and trace why a failed branch erases the capture it just wrote.
Backreferences
Use `\1`, `\2` to match the exact text a group already captured, predict why that re-read forces the backtracking engine class, and decide when a backreference fits versus when structure needs a different tool.
Catastrophic Backtracking
Trace why `^(a+)+$` matches instantly but hangs on a near-match, count the equivalent splits the engine retries on failure, and defuse the blowup with an atomic group, a possessive quantifier, or a rewrite.
Beyond ASCII
Unicode properties, grapheme clusters, normalization, the multi-codepoint character
Unicode Properties
Query the Unicode property table with `\p{L}`, `\p{N}`, and `\p{Script=Arabic}`, predict what `\w` actually matches in a given engine, and reach for property escapes when ASCII assumptions break.
Grapheme Clusters & Normalization
Match a whole user-visible character with \X when the dot would split it into codepoints, predict when two spellings of the same glyph fail a literal pattern, and normalize both sides before matching.