The engine, in four rules
- Try each start position in turn. An unanchored pattern is attempted at position 0, then 1, then 2… until one attempt succeeds. That's why
cat|dogon "hotdog" takes several attempts. - Walk the pattern left to right. Each token must match at the current text position; if it does, both cursors advance.
- Remember every choice. A quantifier can take more or fewer characters; an alternation can take either branch. Each choice is a bookmark.
- On failure, return to the last bookmark and take the next option. If no bookmarks are left, this start position fails and rule 1 moves on.
That's the whole algorithm used by JavaScript, Python's re, PCRE, Java and .NET. Everything else — greedy vs lazy, lookaround, catastrophic backtracking — falls out of these rules. The same taste for seeing why a rule works, rather than memorizing it, is what ahaboo brings to other topics through explainers you can move and adjust.
Greedy vs lazy
A greedy quantifier (*, +, {2,}) first takes as many characters as it can and gives them back one by one. A lazy one (*?, +?) takes as few as possible and grows only when the rest fails. Both find a match if one exists at that start position — they differ in which match and how many steps it takes. On <b>bold</b>, greedy <.*> returns the whole string; lazy <.*?> returns <b>. Clearer still is saying exactly what may appear: <[^>]*> can't run past a >, so it never needs to backtrack.
Lookahead and lookbehind
(?=px) asks "does px come next?" and then puts the text cursor back where it was. That's why \d+(?=px) matches the digits in "40px" but not the unit. Negative lookahead (?!…) succeeds when the sub-pattern fails. Lookbehind (?<=…) checks the text just before the cursor. Password rules use several lookaheads anchored at the start — each checks one requirement independently. See the password regex.
Catastrophic backtracking (ReDoS)
Pick the (a+)+b example above. On ten a's with no b, the engine must prove there is no match — and it tries every way to split the a's between the inner and outer +: 2n ways. Real incidents follow this shape: Cloudflare's global outage on 2 July 2019 was caused by a WAF rule containing .*(?:.*=.*), and Stack Overflow went down in July 2016 because a whitespace-trimming regex met a post with 20,000 consecutive spaces.
Warning signs: a quantifier inside a quantified group ((x+)*), alternatives that can match the same text ((\d|\w)+), and several .* in a row. Fixes: make each character matchable in only one way, use negated classes instead of .*, or use an engine like RE2. The RegexKit tester runs your pattern in a worker and stops it after 1.5 seconds, so you'll see a warning instead of a frozen tab.