What Regular Expressions Cannot Do
A regex can check that a string looks like a date, and it cannot check that its parentheses balance. That is not a missing feature waiting for the next release. A finite machine has a fixed number of states, and a fixed number of states cannot count without limit. Add one piece of memory, a stack, and the machine can recognize everything a parser handles.
The ladder of machines, and the languages each rung can recognize, is a map of which tool fits which input. Lantern's query language sits on the second rung because of one feature, its parentheses, and that is why Chapter 13 gave it a parser rather than a pattern.
Nesting Needs Memory
To check that a string like three opening parentheses followed by three closing ones is balanced, a machine must remember how many parentheses are open. A finite machine's only memory is its current state. Give it states numbered 0 to 3, one per count of open parentheses: an opening parenthesis moves one state up, a closing one moves one state down, and the machine accepts if it ends in state 0. That machine is correct for any input nested at most three deep. A fourth opening parenthesis has no state to go to.
Adding states only moves the limit. A machine with 10 states can be in only 10 conditions. Feed it 11 different numbers of opening parentheses, and two of those counts must leave it in the same state. From then on it cannot tell them apart, so it must accept or reject both alike when the same closing parentheses follow, and for one of them that answer is wrong. A regex can balance brackets up to a fixed depth written into it, never to any depth. Real input has any depth.
The Stack Machine
Give the machine a stack, memory in which only the top item can be reached, and the problem disappears. This is a different machine from the bytecode stack machine of Chapter 13: its stack holds open brackets, not operands. Push on an opening bracket, pop on a closing one, reject a closing bracket that finds the stack empty, and accept if the stack is empty at the end. The stack grows exactly as deep as the nesting, whatever that depth is, so one small machine handles depth 2 and depth 200 alike.
This pushdown machine recognizes exactly the languages a grammar like the one in Chapter 13 describes, called the context-free languages. A recursive-descent parser is one of these machines written as functions. Its call stack from Chapter 3 is the stack: each rule that reads a parenthesized part calls itself, and the call returns when the closing parenthesis arrives. Lantern's query author:"le guin" AND (year<1970 OR year>2000) nests one level, and the next query can nest five. A pattern written for one level fails on the second; the parser handles any depth.
The Ladder
Noam Chomsky's hierarchy of 1956 puts these classes in order. The regular languages, recognized by finite machines and regexes, sit inside the context-free languages, recognized by stack machines and parsers. Those sit inside the context-sensitive languages, a middle rung rarely met in everyday work. All of them sit inside everything a Turing machine can recognize, the top of the ladder and the subject of the next topic.
Each rung adds memory and costs more. A regular language is checked in linear time with a fixed amount of memory. An arbitrary context-free grammar takes cubic time to parse in general, so real languages are designed with restricted grammars that a parser reads in linear time, one token of lookahead at a time. At the top rung there is no bound on time or memory, and The Halting Problem, two topics on, shows that some questions there have no answer at all.
Regexes That Are Not Regular
The regex in your language is usually more than a regular expression. A backreference such as (\w+) \1 matches a word followed by the same word again, which catches "the the" in a sentence. No finite machine can do that, because it would have to remember an arbitrary word. PCRE goes further with recursive patterns, and .NET with balancing groups, and both can match nested brackets. Python's standard re has neither recursion nor balancing groups.
The price of these features is backtracking, from the previous topic. They are precisely the features that linear-time engines give up. A pattern that uses recursion to match nesting is a parser in disguise, with a backtracking engine's worst case and none of a parser's error messages: when it fails, it says only that there was no match.
Why HTML Is Not Parsed With a Regex
HTML nests to any depth. It has optional end tags, it allows a greater-than sign inside a quoted attribute value, and it comes with a standard that specifies how to recover from broken markup. The WHATWG HTML standard defines parsing as the two lowest rungs of the ladder: a tokenizer written as a state machine, and a tree builder that keeps a stack of open elements.
A regex can do the first half only. It can find a tag. It cannot know which open element a closing tag belongs to, or whether that element was closed long ago by the standard's recovery rules. A much-quoted Stack Overflow answer from 2009 turned the point into folklore, and it is right for the reason in the first section: finite memory cannot follow unbounded nesting.
Choosing the Rung
Use a regex for flat, token-level structure: a date, an id, the fields of a log line, the tokens a lexer produces. Use a parser for anything that nests: HTML, JSON, XML, a query language, a configuration format with blocks. The line between the two tools is the line between the first two rungs.
The cost of choosing the wrong rung arrives in production. A regex scraper that works on the page it was tested on breaks on the first nested element it meets. A regex-based HTML sanitizer is bypassed by markup its author never imagined, and that is a real and recurring source of cross-site scripting bugs. The parser that would have handled both is one standard-library import away, runs in linear time and reports where the input went wrong.
- "A clever enough regex can parse HTML or JSON." No finite machine can track nesting to any depth. A cleverer pattern handles one more level, and the next document has one more than that.
- "The regex in my language is a regular expression." Backreferences, lookaround and recursion go beyond the regular languages, and every one of them is paid for in backtracking and its worst case.
- "A regex that passes every test file handles the format." Test files are shallow and polite. The first document nested deeper than the pattern expected fails in production, often by matching the wrong thing rather than by failing.
- "A parser is heavyweight and a regex is the lightweight choice." Lantern's recursive-descent parser is a few dozen lines, runs in linear time and reports errors at a position. The regex that replaces it is shorter only until its third fix.
- "Stripping script tags with a regex makes HTML safe to embed." Event-handler attributes, nested and malformed tags and encoded characters pass straight through. Sanitizing means parsing the markup and keeping an allowlist.
- Use a regex for flat patterns and a parser for anything that nests. The line between them is the line between the first two rungs.
- Split recognition along that line: tokens by a state machine, structure by a parser. It is the design of Chapter 13's lexer and parser, and of the HTML standard.
- Parse HTML, JSON and XML with the standard library's parser or a maintained one, never with a pattern. The parser already knows the recovery rules your pattern would have to rediscover.
- Sanitize markup by parsing it and keeping only allowlisted elements and attributes. Deleting what a pattern finds leaves everything the pattern did not imagine.
Knowledge Check
A team needs to validate that brackets in user-written formulas are balanced. Formulas are rarely nested more than three deep. What is the problem with a regex?
- Regexes cannot match bracket characters without escaping
- It works to a depth fixed in the pattern, never to any depth
- It works on any depth but runs in quadratic time
- It needs lookahead, which Python's re does not support
Why is a stack the memory that nesting needs?
- It stores every character read so far, so nothing is lost
- It lets the machine jump back to any earlier position
- The most recently opened bracket is always the one to close
- It has a fixed size, which keeps the machine finite
Which input belongs on the regular rung, where a regex is the right tool?
- A JSON document from a partner's API
- The timestamp field of a fixed log line
- A Lantern query with parenthesized groups
- An HTML fragment pasted into a comment
A pattern uses a backreference to find repeated words. What does that feature cost?
- Nothing, because backreferences are compiled into the finite machine
- Only extra memory for the captured word, with the same time bound
- A backtracking engine, with its exponential worst case on failure
- A recursive pattern, which Python's standard re provides for it
The HTML standard splits parsing into a tokenizer and a tree builder. Which half could a regex-like state machine perform?
- The tokenizer, which finds tags and text in a flat stream
- The tree builder, which matches each closing tag to its opener
- Both halves, if the pattern uses enough lookahead and lookbehind
- Neither half, because HTML allows broken markup in any place
A regex scraper passed every test page, then returned wrong prices in production. What is the most likely cause?
- The production pages used a different character encoding than tests
- A production page nested an element deeper than the tests ever did
- The regex engine cached old matches from the earlier test runs
- Backtracking ran out of time and returned a partial match early
You got correct