Write a pattern that matches exactly what you meant and predict what it will cost, by deriving the machine a pattern turns into and counting the steps that machine takes on the input you are worried about

Describing a Pattern in Text

Patterns in text, derived from the machine they compile to, including why one of them once took thirty seconds on a forty character line.

8 lessons, written and corrected before you arrived. Reading them here needs no account. The first reads the whole way through; the others open and then stop, because a page nobody owns cannot tell who is reading it. Starting the course gives you your own copy, where every idea has problems standing under it and you can ask about any sentence.

Start reading

01The Set of Strings a Pattern Accepts, and the Three Operations That Build ItA pattern names a set of strings rather than a way of searching, and every convenience in the notation rewrites into one atom and three operations once it is written out.
02Building by Hand the Machine a Pattern Turns Intoopening onlyOne rule for each of the three operations turns a pattern into a machine of states and edges, and the machine comes out no larger than about twice the pattern.
03Following Every Path at Once, So Nothing Ever Has to Be Undoneopening onlyAn engine that carries the set of states a machine could be in reads each character once, never backtracks, and costs the input length times the machine size.
04Collapsing a Set of States Into One Lookup Table, and What That Table Can Costopening onlyTurning every reachable set of states into a single state gives one table lookup per character, and there are short patterns whose table has two to the power of k rows.
05Why a Short Pattern Takes Thirty Seconds on One Lineopening onlyWhere the exponential comes from when an engine that backtracks meets an ambiguous repetition, counted attempt by attempt, with the three shapes that cause it and the three defences that work.
06Back References, Look Around and Why Brackets Cannot Be Matchedopening onlyWhich familiar features a finite machine can carry out and which cannot be one at all, with the argument for why no pattern matches balanced brackets and what a bounded depth costs instead.
07Which Match You Actually Get, and Why Two Engines Disagreeopening onlyOne pattern, one line and four different answers, worked out position by position: greedy against lazy, leftmost first against leftmost longest, and where a captured group comes from.
08Writing a Pattern That Holds Up, and Knowing What It Will Costopening onlyA date pattern built from nothing against a fixed list of eight strings, one change per failing string, ending with the two numbers that price it: the paths through it and the length of the input.