← Lectures
Back

1 / 6

Next

Slide 1 of 6: What "regular" means

Arrow keys move through the slides while these controls have focus.

The theatre is not shown, because your system asks for reduced motion. The lecture itself is below, in full.

Lecture · 6 slides

What regular expressions cannot match

The most famous answer on Stack Overflow is a refusal. Somebody asked how to match nested HTML tags with a regular expression and received, instead of a pattern, several hundred words of escalating horror about the nature of the request. It is very funny and it is also correct, and almost nobody who quotes it can say why.

The why is not a matter of taste or difficulty. There is a precise mathematical boundary around what a regular expression can recognise, it was established in the 1950s before anyone had written one, and HTML is on the other side of it. Not "hard to do". Not "messy". Outside the class of things the tool is capable of expressing, in the same way that a ruler cannot measure temperature.

Knowing where that boundary is turns out to be immediately practical. It tells you which problems to stop attempting, it explains the one performance failure that takes web servers down, and it explains why the regular expressions you actually use every day contain features that are, formally speaking, not regular at all.

AssumesYou have written a regular expression and had it not do what you meant.

  1. Slide 1

    What "regular" means

    The word is not a compliment. It names a specific class of languages, defined by what a machine with no memory can recognise.

    start --a--> s1 --b--> s2 --c--> accept
    plaintext

    That is a finite automaton: a fixed set of states, and a rule for moving between them on each character. It has no counter, no stack, and no memory beyond which state it is in. A language is regular exactly when some such machine accepts it, and a regular expression is a notation for writing one of these machines down.

    Everything follows from the missing memory. The machine cannot count, because counting requires somewhere to put the number. It can only remember what a fixed number of states can encode, and that number is decided before it ever sees the input.

  2. Slide 2

    The thing it cannot do

    Because it cannot count, it cannot match anything that requires knowing how many of something it has seen — and that includes every nested structure.

    Consider a language of balanced brackets: (), (()), ((())), and so on. To recognise it you must count how many opening brackets you have passed so you can require the same number of closing ones. There is no bound on the depth, so no fixed number of states suffices, and no regular expression can do it. This is provable rather than merely observed, by an argument called the pumping lemma, and it has been settled since 1961.

    HTML is the same problem wearing a costume. A div may contain a div to any depth, so matching a tag against its partner is bracket-matching, so it is outside the class. The Stack Overflow answer is not being dramatic. It is reporting a theorem.

  3. Slide 3

    The hierarchy this sits in

    Regular languages are the bottom rung of a ladder Noam Chomsky described in 1956, and knowing the next rung up tells you what to reach for instead.

    The next class is context-free, which is finite states plus a stack, and a stack is exactly the memory needed to match brackets. That is why parsers use them and why the parsing stage of a compiler is built on a context-free grammar rather than on regular expressions. Above that are context-sensitive languages and then everything a Turing machine can decide.

    The practical reading is a rule of thumb with theory behind it. If the thing you are matching can nest, you need a parser. If it cannot, a regular expression is not just adequate but ideal — it will run in time linear in the input with no memory at all, which is a guarantee no parser gives you.

  4. Slide 4

    Most regex engines are not regular

    Here is where the theory and the tools come apart, and the gap is the source of both the power and the danger of what you actually use.

    (\w+)\s+\1
    plaintext

    That \1 is a backreference: match whatever the first group matched, again. It requires remembering an arbitrary string, which a finite automaton by definition cannot do — so this pattern is not a regular expression in the formal sense at all, however much it looks like one. Lookahead, recursion in some engines, and backreferences all push past the boundary.

    Which means "regex cannot match nested structures" is not quite true of the tools on your machine. Some engines can, with recursive patterns. The honest statement is that the moment you use those features you have left the class that came with the linear-time guarantee, and the guarantee is the thing you were getting in exchange for the limitation.

  5. Slide 5

    Why some patterns take forever

    Leaving that class has a price, and it is the price that occasionally takes a website off the internet.

    ^(a+)+$
    plaintext

    Given a string of twenty a characters followed by a b, a backtracking engine will try every way of dividing those twenty characters between the inner and outer group before concluding there is no match. That is over a million attempts for a twenty-character input, and each extra character doubles it. The pattern looks harmless. It is a denial-of-service vulnerability with a name — ReDoS — and it has taken down Stack Overflow and Cloudflare, in both cases from a pattern somebody wrote in an afternoon.

    The cause is backtracking, which is how engines implement the non-regular features. An engine built on automata, like Go's or Rust's, cannot suffer this at all — it runs in linear time always — and it pays by refusing to support backreferences. That trade is a direct consequence of the boundary this lecture has been circling.

  6. Slide 6

    What they are genuinely excellent at

    Having spent five slides on limits, the honest other half is that within the class this is one of the great tools, and the museum has a joke about it on the wall.

    Lexing is regular by nature, which is why the first stage of every compiler is a set of regular expressions in all but name. Validation of flat formats, splitting on delimiters, finding a pattern in a log — all of these are linear time, constant memory, and expressible in a line. The prime-number regex hanging in the Cabinet of Curiosities is the extreme demonstration: it decides primality by unary bracket-matching, which works precisely because it uses backreferences and is therefore not regular at all. The exhibit is funny because it is a trick.

    Use them where the input is flat, and reach for a parser the moment it can contain itself. That is the whole rule, and unlike most engineering advice it is not a judgement call — somebody proved it before the first regular expression was ever run.

Works in the collection

The arguments above are hanging on the walls of the museum, in one form or another. These are the ones worth looking at next.

The rest of the programme

  1. Compiled, interpreted, and the space betweenA distinction that stopped describing anything decades ago, why it persists, and what is actually different about the machinery underneath.
  2. What a compiler actually doesFour jobs in a row, each mechanical, none magic: text to tokens, tokens to a tree, a tree to a judgement, and a judgement to instructions.
  3. Functional programming and object orientationTwo ways of arranging a program, what each one genuinely makes easy, and the trade-off underneath the argument that neither side can escape.
  4. The principles of object orientationEncapsulation, inheritance, polymorphism and SOLID, one at a time: what each actually claims, which held up, and which its own community abandoned.
  5. Types: what they can and cannot proveA type checker proves one thing about every possible run of your program. Knowing which proposition explains both the enthusiasm and the disappointment.
  6. Null, and the mistake its inventor apologised forTony Hoare called it his billion-dollar mistake. What was actually wrong with it, what the alternatives cost, and why the fix took forty years to arrive.
  7. What abstraction costsAbstraction is sold as free and is not. What you buy, what you pay, and how to tell before writing it which of the two is larger.
  8. Immutability, and what it is not free ofValues that never change buy sharing, comparison and time travel. They are not free, and it is worth knowing where they are expensive before you commit.
  9. Recursion, and why it feels like cheatingA function that calls itself looks like an unpaid debt. What makes it terminate, what it costs on the stack, and why some problems resist any other shape.
  10. Big-O, and what it deliberately ignoresComplexity notation throws away constants, hardware and every input you will actually see. Knowing what it discards is what makes the number useful.
  11. Concurrency is not parallelismOne is a way of structuring a program, the other a way of executing it. Keeping them apart explains why async helps a web server and threads often do not.
  12. Errors: exceptions, values, and what each hidesThrowing makes the happy path readable and the failure paths invisible. Returning errors as values does the opposite. Neither side has won.
  13. Why programs are hard to changeSoftware is called soft because it can be edited. Why editing gets harder every year, what the mechanism is, and which of the usual remedies work.

← All lecturesAtrium