Regular expressions: a backtracking matcher
Try it: Regular expressions: a backtracking matcher
How Python's re module matches a pattern: it tries each start position, matches tokens one by one, lets greedy quantifiers take as much as possible and give it back when the rest fails (lazy ones take as little as possible), tries alternatives in order and records groups.
How it works
- search tries start positions 0, 1, 2 …; match tries only position 0; findall collects every non-overlapping match.
- Tokens are matched left to right: literals, ., classes like [a-c] and \d, and zero-width anchors ^, $, \b.
- A greedy quantifier (* + ? {m,n}) takes as many repetitions as it can, then backtracks one at a time; a lazy one (*? +? ??) takes as few as possible and grows only when needed.
- Alternatives in a | b are tried in order; the first that lets the whole pattern match wins.
- Parentheses capture the text their part matched; captures are undone when the matcher backtracks past them.
Default run (63 steps): re.search('(\\w+)@(\\w+)\\.com', 'mail bo@ikb.com now'): try each start position until one matches. … re.search('(\\w+)@(\\w+)\\.com', 'mail bo@ikb.com now') → <re.Match object; span=(5, 15), match='bo@ikb.com'>
Simplified: A subset of re: no flags, lookarounds, backreferences, named groups or possessive quantifiers; pattern and text up to 24 printable ASCII characters. The trace stops after 1900 attempts ("too many steps") where real Python would keep backtracking.
Loading the simulation…