Lesson S1 · Special topics

Regular expressions

A regular expression is a small pattern that describes text: a word, any digit, three letters in a row, something at the very end. Step through ten lines of Python and watch the re engine move a pointer along a string one character at a time, back up when a guess fails, and hand back what it found. Then see the one pattern shape that can take minutes to fail, and when plain string methods are the better tool.

12 min10 steps5 questionsIntermediate

Fig S1 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01With s = "cat 42 dog 7", what does re.search(r"\d+", s).group() return?

search() returns the first match. \d+ is greedy: it takes the 4 and the 2 and stops at the space, so the match is '42'.

02Which call returns every match as a list?

findall() keeps searching after each match until the end of the string and returns all matches in a list. search() stops at the first one.

03What does the $ in the pattern \d+$ mean?

$ is an anchor: it matches the position at the end of the string (or just before a final newline). It consumes no character.

04In s = "cat 42 dog 7", after m = re.search(r"(dog|cat) (\d+)", s), what is m.group(1)?

The search tries index 0 first. There dog fails and cat matches, so the whole match is 'cat 42'. Group 1 is the first bracketed part: 'cat'.

05Why can re.search(r"(\d+)+x", "1" * 30) take minutes?

A repeat inside a repeat can cut a run of digits in many ways. Because there is no x, every way fails and the backtracking engine tries them all. Each extra digit about doubles the work. \d+x does the same job safely.

Key terms

Glossary

Regular expression (regex): A pattern that describes text, such as \d+ for one or more digits. Python's re module matches regexes against strings.
Character class: A set of characters that one position may match: [a-z], [0-9], or shorthands such as \d (digit), \w (letter, digit or underscore) and \s (whitespace).
Quantifier: Says how many times the part before it repeats: * (zero or more), + (one or more), ? (zero or one), {n,m} (n to m times). By default they are greedy and take as much as they can.
Anchor: A pattern part that matches a position, not a character: ^ for the start of the string, $ for the end.
Group: A part of a pattern in round brackets. It can be repeated as one unit, and the text it matched can be read with group(n).
Alternation: The bar |, meaning or: cat|dog matches either word, trying the left one first.
Backtracking: When a guess fails, the engine goes back to its last choice (for example, giving back a character a quantifier took) and tries another way.
Catastrophic backtracking: A pattern, usually with a repeat inside a repeat, that has so many ways to fail that the engine runs for a very long time. On untrusted input it is an attack called ReDoS.

Fine print

Notes and sources

The r before each pattern makes a raw string, so the backslash in \d reaches the re module unchanged. Every line assumes import re at the top.
The moving pointer shows how a backtracking engine searches. CPython's engine adds shortcuts, such as jumping straight to a place where the first character could match, so it may skip some of the tries drawn here; the results are the same.
For str patterns, \d and \w also match digits and letters from other scripts, such as Arabic-Indic digits. The flag re.ASCII limits them to ASCII.
$ also matches just before a newline at the very end of the string; \Z matches only at the very end.
A run of n digits can be cut into consecutive pieces in 2^(n-1) ways, so 30 digits give 536,870,912. Python 3.11 added possessive quantifiers such as ++ and atomic groups (?>...), which never give characters back and so avoid this blow-up.
A slow pattern run on text from strangers is a known attack, called regular expression denial of service (ReDoS).

Quiz Unlocks after the last step.