Regular expressions in practice

Suppose you want to find every mention of Dr. in a corpus. The obvious pattern Dr. also matches Drs and Dry, because a period in a pattern means any character. Written as Dr\., it matches only the period. That is the whole idea of escaping: fourteen characters, . ^ $ * + ? ( ) [ ] { } | \, mean something to the engine, and a backslash returns them to their plain selves.

Notice that the backslash works in both directions. \. turns a special character into a literal one, while \n and \t turn plain letters into a newline and a tab. When a pattern needs a literal backslash it doubles: \\. In Python, write patterns as raw strings, r'...', so the string literal does not eat the backslashes before the regex engine sees them (Python re documentation).

The precedence ladder

Escaping decides what a character means. Precedence decides how the operators bind, and it is where most wrong answers come from. Take the pattern cat|dogs and run it on the string cats dogs cat dog. Students expect cats and dogs. The engine returns cat (inside cats), dogs, and cat again, because the disjunction operator | has the lowest precedence of all: it splits the entire expression into cat on one side and dogs on the other. Parentheses fence the alternation in, so (cat|dog)s reads as cat or dog, then s, and returns cats and dogs.

SLP3 (section 2.6.4) gives the full ladder. Parentheses bind tightest, then the counters (the quantifiers), then plain sequences and anchors, and last of all the disjunction. This is why the* matches theeeee and not thethe: the star applies to the single letter e, not to the whole sequence. It is why the|any matches the or any but never thany. And it is why guppy|ies fails to match guppies: it means guppy or ies, so the fix is gupp(y|ies).

The same ladder explains a subtler example from SLP3. Column [0-9]+ * matches one column label such as Column 1 followed by any number of spaces, because the star applies only to the final space. To repeat over a whole row of labels, Column 1 Column 2 Column 3, the sequence has to be fenced first. SLP3 writes (Column [0-9]+ +)*, which needs a space after every label, so on this row it stops before Column 3; (Column [0-9]+ *)* allows zero trailing spaces and takes the whole row.

Grouping without remembering

Parentheses do two jobs at once. They set the scope of an operator, and they create a capture group that stores whatever the group matched. Sometimes you want only the first job. Thenon-capturing form (?:...) groups without allocating a register, which keeps the numbering of the groups you do care about stable. SLP3 (2.17) uses it to skip fourteen dates and capture only the fifteenth: (?:\d\d/\d\d/\d\d\d\d\s+){14}(\d\d/\d\d/\d\d\d\d). The repeated dates are grouped so that the counter {14} applies to the whole date, and only the last date lands in group 1.

Real patterns are assembled from small pieces, tested, and grown. Start with an email address. It has a local part, an at sign and a domain, so the very simplified pattern on slide 69 is three pieces glued together: [A-Za-z0-9._]+@[A-Za-z0-9._]+. A character class of letters, digits, dots and underscores, repeated at least once, on both sides of the @. The same compose-then-test loop gives a course-code ID pattern in one line: two to four uppercase letters, an optional space, three digits, [A-Z]{2,4}\s?\d{3}, which accepts ICS 582 and COE558 and rejects ICS58 (only two digits) and ICSSS 582 (five letters). The habit is the same in both: build the smallest piece that covers the positives, then run it against the nearest negatives.

The table is an error analysis, and it exposes two failure modes that pull in opposite directions. The class is too narrow: hyphens and plus signs are legal in local parts, so the pattern silently truncates them and matches the wrong substring. That is a recall problem: real addresses the pattern should catch, it catches only in part. The domain side is too loose: it accepts me@localhost, which has no top-level domain. That is a precision problem: strings the pattern should reject, it accepts. Widening the class to [A-Za-z0-9._+-]+ raises recall; requiring a dot followed by at least two letters at the end, \.[A-Za-z]{2,}$, raises precision. Each fix is one small piece, tested on representative samples, and the point of slide 69 is to iterate this way rather than to write a pattern that fits the one address in front of you.

Capture, then reuse

Once a pattern matches, each capture group has stored a substring, and a substitution can put them back in any order. Slide 70 shows the classic sed notation s/(\d{4})-(\d{2})-(\d{2})/$2$3$1/. Work it on an ISO date.

The syntax of the reference differs by tool. sed and Perl write $1 or \1 inside s/.../.../; JavaScript's replace uses $1 and $& for the whole match; Python's re.sub uses \1 in a raw string and \g<0> for the whole match (Python re documentation). SLP3 (section 2.6.7) uses the same trick to move US dates to European order: re.sub(r"(\d{2})/(\d{2})/(\d{4})", r"\2-\1-\3", s) turns 10/15/2011 into 15-10-2011.

A backreference is not only for replacements. Inside the pattern itself, \1 means "the same text that group 1 just captured", so (\w+) \1 finds a doubled word. SLP3's careful version, \b([A-Za-z]+)\s+\1\b, restricts the group to letters, adds word boundaries and allows any whitespace; on the the cat sat on on the mat it returns the and on. This is the mechanism behind the faster-they-ran exercise in the next concept.

Looking without moving

The email and date patterns consume text left to right. Some rules cannot be written that way. A password must be at least eight characters, contain a capital letter, and contain a digit, and the three rules overlap: the same characters count for all of them. Lookahead solves this. (?=...) requires that a pattern could match starting here, (?!...) forbids it, and neither consumes anything. SLP3 (section 2.6.8) puts it precisely: the match pointer does not advance, just as with anchors.

So ^(?=.*[A-Z])(?=.*\d).{8,}$ reads: at the start of the line, check that somewhere ahead there is a capital; still at the start, check that somewhere ahead there is a digit; now, still at the start, consume at least eight characters to the end. Because the two checks both begin at position 0 they can look at the same characters, which a consuming pattern could never do.

Negative lookahead is just as useful. SLP3's equation 2.18, ^(?![tT])(\w+)\b, captures a word at the start of a line only if it does not begin with t or T. Without the lookahead you would need a class that lists every other letter.

Slide 72 is a set of six problems with no answers. Each of them uses one tool from the previous two concepts, and together they cover everything the exam can ask about escaping, each capture group and its backreference, and lookahead. Try each one in the workbench before revealing the solution. The check button compares your matches against the expected list and tells you what is missing or extra.

The six problems map one to one onto the tools of the previous two concepts. The tags problem rewards a negated class or an escaped backslash: <[^>]+> reads as "any run of non-closing-brackets inside brackets". The Apple problem is the one where a global i flag backfires, because it would also lowercase Juice, so the case-insensitivity has to live per letter inside a class like [Aa], or inside a scoped group like (?i:apple). The password problem is the argument for lookahead: three overlapping rules, all checked from the same position, none consuming input. The faster-they-ran sentence needs backreferences, capturing the repeated words once and reusing them as \1 and \2. The date swap is the classic capture-group substitution. The boxes problem shows that the whole-match reference, $& or \g<0>, lets you skip a group entirely when you do not need to rearrange anything.

Slides 73 to 75 are the reference card for the whole regex block: every quantifier, character class, capture group and anchor in one place. They are reproduced here as tables so you can scan them during revision, with the two engine differences that the card leaves implicit: how line anchors behave under multiline mode, and which engines allow a variable-length lookbehind.

The lazy form matters more than its size suggests. Greedy .* grabs as much as it can and backs off only if the rest of the pattern fails; .*? takes as little as possible and grows only when it must. Part 08 showed the difference on HTML tags.

Take one input and walk the flags. On the two-line string cat\ncar the pattern ^ca.$ shows the three flags in action. With no flags it matches nothing: ^ wants the very first position, and the dot cannot be a newline, so $ after a 3-letter match can never reach the end. Turning on m gives cat and car, one per line. Adding g reports both; without g a JavaScript exec returns only the first. The i flag is independent: it would let the pattern tolerate Cat too. Each flag flips exactly one assumption, anchor meaning, case, or how many results are returned.

One detail to read closely in the table: (?<!#)\b\d+ needs its \b. Without the boundary, the engine could pick up the 2 of #42, because the position before that digit has 4 in front of it, not #, so the negative lookbehind does not object and the lookahead for a digit succeeds. The \b forces the match to begin where a word begins, so the 2 is ruled out and only 7 survives.

Part 07 showed you this pattern as a list of six rules; now that you can read regex syntax, walk it character by character. Before GPT-2's BPE merges touch a sentence, one regex cuts it into pieces. On We're 350 dogs! Um, lunch? the pieces are We, 're, ␣350, ␣dogs, !, ␣Um, ,, ␣lunch and ?, nine in all, where ␣ marks a leading space that stays inside the piece. That regex is the pre-tokenizer, and the whole behavior of the tokenizer on numbers, punctuation and spaces is decided by it.

The pattern from the GPT-2 repository's encoder.py is 's|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+. It is a disjunction of six alternatives, and the engine tries them left to right at every position, taking the first that matches. Read it as six rules in priority order.

Order is the design. Contractions come first so that We're becomes We plus 're: at position 0 no contraction matches, so the letter rule takes We and stops at the apostrophe; at position 2 the contraction rule fires before the punctuation rule can grab the apostrophe alone. Had the letter rule come first the result would be the same for We, but if punctuation came before contractions you would get ' and then re, and the model would never learn that 're is one unit.

The space handling is the subtle part. Letters and digits carry an optional leading space, so a word is normally tokenized together with the space before it: ␣dogs is one piece, and the model learns that word-initial pieces look different from word-internal ones. Runs of spaces are handled by \s+(?!\S): whitespace that is not followed by a non-space. On Hello␣␣␣world that alternative takes the first two spaces and stops, because the third space is followed by w, and the third space is then picked up by ?\p{L}+ as part of ␣world. The result is Hello, ␣␣, ␣world. Trailing whitespace at the end of a document also goes to \s+(?!\S), because at the end of the string nothing follows and the negative lookahead succeeds. The final plain \s+ fires only in the one case the rule above cannot handle: a single whitespace character directly before a non-space that no ␣? prefix will take, which means a lone newline or tab before a word. On a⏎b it produces the ⏎ piece.

Why regex and not re

The slide imports the third-party regex module under the name re. The reason is \p{L} and \p{N}. These are Unicode property classes: every character whose General_Category is Letter, and every character whose category is Number, as defined in Unicode Standard Annex 44. Python's built-in re does not support them; the regex module does, and so does JavaScript with the u flag (regex module documentation, MDN). The payoff is script independence. On مرحبا بالعالم ١٢٣ the same pattern returns مرحبا, ␣بالعالم and ␣١٢٣: Arabic letters are letters and Arabic-Indic digits are digits without any special case in the pattern. A pattern written with [A-Za-z] and [0-9] would still cut at the spaces, because the negated punctuation class excludes whitespace, but all three pieces would come out through the punctuation rule, indistinguishable from runs of symbols.

For the exam, two ways to make a pattern Unicode-aware: use property classes such as \p{L} and \p{N} instead of ASCII ranges, and apply Unicode normalization (NFC or NFKC, from part 05) to the input before matching so that composed and decomposed forms of the same letter cannot split a match.

What the pieces are for

The purpose of the cut is to separate words, numbers, punctuation, contractions and whitespace before BPE sees the text. Then the merges run inside each piece. This is literally how encoder.py is written: it loops over re.findall(self.pat, text) and calls self.bpe(token) on each piece separately (GPT-2 repository). A merge can join d and ogs inside ␣dogs, but no merge can ever join dogs with the ! that follows it, because they were never in the same piece. Byte-level operation, from part 06, applies inside each piece too, which is why the tokenizer is also a byte-level one.

The cut lines are a design choice, and later tokenizers move them. tiktoken's r50k pattern for GPT-2 is the same language hardened for speed: '(?:[sdmt]|ll|ve|re)| ?\p{L}++| ?\p{N}++| ?[^\s\p{L}\p{N}]++|\s++$|\s+(?!\S)|\s, with possessive quantifiers ++ that refuse to backtrack and an explicit end-of-string whitespace rule. cl100k_base, used by GPT-4, caps numbers at three digits with \p{N}{1,3}+ and makes contractions case-insensitive (tiktoken repository). Hugging Face's ByteLevel pre-tokenizer applies the same GPT-2 pattern unless you switch its use_regex option off (Hugging Face tokenizers documentation). SuperBPE (introduced in part 07) goes the other way: after a first stage that learns subwords inside pieces, a second stage is allowed to merge across whitespace, and Liu et al. (2025) report up to 33 percent fewer tokens at a 200k vocabulary. Every one of these is a change to the pre-tokenizer, not to the BPE algorithm.

Slide 78 closes the regex block with four engineering habits. Three of them you have already practiced in this part without being told. The email pattern grew from an error analysis of four addresses: start simple, add cases as failures appear. The workbench tasks are unit tests: a fixed list of inputs with expected outputs, rerun after every edit. The GPT-2 pattern was explicit about Unicode: property classes and, from part 05, normalization before matching. The fourth habit is the one that bites in production.

Catastrophic backtracking

Consider (a+)+b against aaaaaaaa!. The pattern says: one or more groups, each of one or more a's, followed by b. There is no b, so the answer is no. But a backtracking engine does not know that until it has tried every way of splitting the eight a's between the inner plus and the outer plus: all eight in one group, seven then one, one then seven, two then six, and so on. The number of ways to partition n a's into ordered runs is 2^(n-1), and each of them ends at the same exclamation mark. Add one a and the work doubles. This is catastrophic backtracking.

Russ Cox (2007) documents the classic case: a pattern of a? repeated n times followed by a repeated n times, matched against a string of n a's. At n = 29 Perl needs over sixty seconds, while a Thompson NFA, which simulates all states at once, takes about twenty microseconds. OWASP lists (a+)+ among its evil patterns because a single crafted input can pin a server's CPU, an attack it calls ReDoS. Both sources agree on the cause: an engine that explores alternatives one at a time, on a pattern with overlapping ways to match the same text.

Three fixes, in order of preference. Rewrite the pattern so that quantifiers do not nest over the same characters: a+b matches exactly the same strings as (a+)+b. Lazy quantifiers do not prevent the explosion either: (a+?)+b backtracks just like (a+)+b, because laziness only changes the order in which splits are tried, not how many exist. Use possessive quantifiers or atomic groups where the engine offers them: tiktoken's \p{L}++ is precisely this, a plus that refuses to give characters back. Or run a linear-time engine such as RE2, Go's regexp or Rust's regex crate, which reject backreferences and lookaround in exchange for a guarantee that time is linear in the input.