Hacker News Revived Nikita Popov’s Regex Essay, and Reopened a Crucial Divide

Hacker News revived a 14-year-old Nikita Popov essay, reopening a conflict that programming shorthand often conceals. The article argues that modern regex engines can recognize languages far beyond formal regular languages. The Hacker News response focused on the price of that extra reach.

Popov published the essay on June 15, 2012, while frequently answering PHP questions on Stack Overflow. His target was a familiar prohibition: HTML cannot be handled with regular expressions because HTML is not regular.

That rule remains useful, but Popov showed why its theoretical explanation can be misleading. A PCRE pattern is not limited to the mathematical object called a regular expression. Recursion, backreferences, assertions, conditionals, and subroutine calls give some engines a much wider range.

The renewed debate is therefore not about whether Popov found a clever pattern. It concerns what developers mean by regex, which guarantees survive implementation choices, and when recognition becomes a poor substitute for parsing.

Why Hacker News Revived a 2012 Regex Argument

The essay returned because its central distinction remains unresolved in everyday software vocabulary.

Popov’s 2012 essay starts by separating two meanings that developers routinely combine. Formal regular expressions describe regular languages. Production regex engines often implement additional operators that exceed that formal class.

A regular language can be recognized with finite state, meaning the matcher does not need an unbounded stack tied to input depth. Common examples include identifiers, simple numeric formats, fixed token patterns, and many search filters.

PCRE, short for Perl-Compatible Regular Expressions, adds constructs that change this picture. A subpattern can call itself, letting the matcher follow nested structures. A backreference can require later text to equal text captured earlier.

Those features make the term “regular expression” historically familiar but mathematically imprecise. Developers usually use regex as a family name for pattern languages. Formal-language specialists may reserve the term for expressions equivalent to finite automata.

The distinction drove the August discussion. One side argued that the essay risks conflating true regular expressions with PCRE-specific pattern matching. Others answered that Popov explicitly announced this distinction before examining the broader programmer meaning.

Both readings identify something important. The essay carefully states its scope, yet its provocative title invites readers to treat unlike engines as one technology. A PCRE pattern using recursion tells developers little about what JavaScript, RE2, Rust, POSIX, or another implementation accepts.

The discussion also moved beyond theory. Commenters raised readability, engine differences, memory use, backtracking, denial-of-service exposure, and AI-generated expressions. Those concerns explain why a 2012 essay still feels current.

Modern code assistants can produce dense patterns without ensuring that maintainers understand their execution. They can also suggest syntax unsupported by the target engine. Greater access to regex generation does not remove the need to choose the right matcher.

The original article remains valuable because it challenges an oversimplified limit. The renewed discussion matters because it supplies the missing operational question: what does that additional expressiveness cost?

PCRE Regex Power Comes From Features Outside Regular Languages

The article’s central result belongs to PCRE-style engines, not every system carrying a regex label.

Popov begins with the Chomsky hierarchy, which groups formal languages by the grammar needed to generate them. Regular languages sit inside context-free languages, which sit inside context-sensitive languages.

Traditional regular expressions occupy the smallest group. Concatenation, alternation, character classes, and repetition can describe every regular language. They cannot, by themselves, remember an unlimited nesting depth or duplicate an arbitrary captured substring.

PCRE recursion changes the first limitation. Popov uses a recursive group to recognize strings containing equal counts of a characters followed by b characters. That language is context-free but not regular.

The mechanism is compact. A pattern consumes one a, recursively invokes the surrounding group, and then consumes one b. Each deeper call adds a corresponding pair around the nested match.

Current PCRE2 documentation still describes recursive pattern syntax. It gives balanced parentheses as a direct example. A group matches an opening parenthesis, ordinary inner characters or another group invocation, and a closing parenthesis.

That is a meaningful capability. Traditional finite-state matching can support only a predefined nesting limit. Recursive matching can follow the input’s nesting depth, subject to the engine’s resource limits and behavior.

Popov then maps context-free grammar rules into named PCRE subpatterns. The (?(DEFINE)...) construct holds definitions without consuming input. Named subroutine calls let one rule invoke another.

His extended example translates portions of the RFC 5322 email grammar into this notation. The result resembles a grammar embedded inside a regex literal, with spacing and comments enabled through extended mode.

This supports the essay’s striking claim: PCRE-style recursion can recognize context-free languages after incompatible left recursion is transformed. It does not mean every short regex can process every context-free language.

It also does not make the matcher a complete parser. Recognition answers whether input belongs to a language. Parsing creates structured output that records how the input fits the grammar.

That difference becomes decisive for HTML. A matcher might determine whether a well-formed fragment conforms to a grammar. An application usually needs elements, attributes, text nodes, error recovery, entity handling, and document traversal.

Real HTML adds another complication. Browsers process malformed documents through specified recovery behavior. Matching an idealized, well-formed language does not reproduce that behavior.

Popov acknowledges both limits. He recommends a DOM library for generic HTML processing and reserves regex for contained situations. The famous claim is therefore narrower than many retellings suggest.

Backreferences create another step beyond classical regular expressions. A backreference matches the exact text previously captured by a group. The pattern ^(.+)\1$, for example, recognizes a string formed by two identical halves.

A finite automaton cannot generally remember an arbitrary first half and compare it with the second. The engine must retain captured content and explore possible division points. That additional state changes both expressive range and computational behavior.

Popov also combines recursion and lookaround assertions to recognize at least some context-sensitive languages. A lookaround checks surrounding text without consuming it at that position.

He stops short of claiming that PCRE recognizes every context-sensitive language. That restraint matters. The essay distinguishes demonstrated constructions from unanswered questions, even while using an intentionally broad title.

Formal Regex and Backtracking Engines Optimize for Different Promises

The main conflict is not theory against practice; it is predictable execution against a larger pattern language.

An engine limited to regular-language constructs can execute patterns through automata. It tracks the set of states reachable after each input character instead of committing to one path and retreating after failure.

A backtracking engine follows alternatives more like a depth-first search. It selects a branch, continues, and returns to an earlier decision when the later match fails. This approach supports captures and advanced behavior with intuitive semantics.

It can also repeat work. Ambiguous nested quantifiers may create many ways to divide the same input. A nearly matching suffix can force the engine to explore those combinations before reporting failure.

That risk does not appear only when a pattern uses recursion or backreferences. A backtracking implementation can take excessive time on a formally regular pattern. Syntax class and execution strategy are related, but they are not identical.

This point corrected one oversimplification in the online debate. Removing non-regular extensions does not automatically make every implementation linear. The engine must also use an algorithm that avoids exponential path exploration.

Google’s linear-time engine makes a deliberate trade. RE2 guarantees matching time asymptotically linear in input length and operates within a configurable memory budget.

RE2 excludes backreferences and lookaround assertions because its designers do not know how to support those constructs while preserving the same guarantee. It also excludes recursive subroutine calls.

The result is less expressive than PCRE2, but more predictable for services accepting untrusted patterns or processing untrusted text. That difference is an architectural decision, not evidence that one engine universally replaces the other.

PCRE2 provides controls that production systems can use, including match limits, depth limits, alternative execution paths, and careful pattern construction. Those controls reduce exposure, but they require deliberate configuration and testing.

The practical choice depends on who controls the pattern and input. A developer-owned expression over bounded records creates a different risk from a user-supplied expression scanning large payloads in a shared service.

The required output matters too. A search command may need only a Boolean match or a few captures. A compiler, document processor, or configuration reader needs structured results and useful failure locations.

This is why “regex can match it” rarely settles an engineering decision. Capability establishes possibility. It does not establish maintainability, resource bounds, diagnostic quality, or compatibility.

The Hacker News disagreement becomes clearer under this framing. Popov describes what selected engines can express. Critics ask which guarantees applications sacrifice when they rely on that reach.

Those positions are not opposites. They address different layers of the same system. The important mistake is carrying a claim from one layer into another without qualification.

The HTML Question Exposes Recognition’s Practical Limit

Matching a language is not the same job as building a dependable representation of a document.

The common warning against regex-based HTML processing combines several arguments. HTML is nested, real documents are malformed, embedded languages complicate token boundaries, and applications usually need structured output.

Only the first argument directly concerns formal-language expressiveness. PCRE recursion can address nesting. It cannot, by that fact alone, solve the remaining requirements.

Consider an application extracting links. A simple expression may work on controlled markup generated by one template. It can fail when > appears inside a quoted attribute or when script text resembles a tag.

Comments, character references, namespaces, optional tags, and browser recovery rules add more cases. Each new condition expands the pattern while leaving its output less structured than a DOM.

This does not make every HTML regex irresponsible. A narrow expression can be appropriate when the input contract is strict and the failure consequences are small.

The scope must be explicit. “Find a known marker in our generated fragment” is a bounded text task. “Interpret arbitrary web pages like a browser” is a document-processing task.

A parser gives each construct a named role. It can attach source locations, report an unexpected token, recover after an error, and expose a tree for later transformations.

A large regex often compresses those distinctions into groups and control flow. Named subpatterns and extended formatting help, but the engine still returns matches rather than a native syntax tree.

The maintenance gap grows when requirements change. Supporting another grammar production in a parser usually means adding or modifying a rule. In a tightly coupled regex, it can alter backtracking and capture behavior elsewhere.

Testing must therefore cover more than representative valid examples. Teams need invalid inputs, near misses, large inputs, nested inputs, Unicode cases, and adversarial strings designed to trigger expensive paths.

This is also where documentation becomes operational rather than decorative. A complex expression should state its engine, flags, accepted input contract, expected captures, size limits, and reason for not using a parser.

Teams preserving technical decisions can keep those constraints beside searchable implementation records. A shared engineering knowledge base helps future maintainers recover the intent behind terse matching code.

The key decision is not regex versus parser as rival identities. It is whether the task needs recognition, extraction, transformation, recovery, or full interpretation.

Regex remains excellent for tokenization, validation under bounded rules, search, log filtering, and small extractions. A parser becomes preferable when grammar structure is the application’s working data.

Popov’s own conclusion follows that boundary. He rejects the absolute theoretical prohibition while retaining the practical recommendation to use a DOM library for generic HTML processing.

That nuance often disappears online. “Regex cannot parse HTML” survives because it prevents common failures. “Some regex engines can recognize context-free structures” remains true because the underlying capability exists.

A mature engineering rule can hold both statements. Do not confuse a useful default with a theorem, and do not confuse a theoretical construction with a production design.

What the Regex Argument Still Underestimates

Extra expressiveness creates security and maintenance obligations that a successful test suite may not reveal.

Regular expression denial of service, or ReDoS, occurs when a matcher spends excessive time exploring alternatives for crafted input. An attacker may consume processing capacity without sending a large volume of traffic.

The ReDoS guidance describes engines reaching extreme execution times when ambiguous patterns encounter adversarial strings. The danger often appears near a failed match.

A validator might process ordinary input quickly because the first branch succeeds. An attacker can supply a long prefix that fits many paths, followed by one character that invalidates every path.

The engine must then revisit earlier choices. Nested repetition, overlapping alternatives, and optional components can multiply the search space. A concise pattern can conceal this behavior during code review.

Backreferences add another complexity dimension. Research on their expressive limits treats them as a substantial extension supported by many mainstream engines. Their behavior cannot be reduced to ordinary finite-state matching.

Popov’s essay notes that backreference matching introduces NP-complete cases. That is a statement about the general problem, not a prediction that each pattern runs slowly.

Many expressions with captures and backreferences finish quickly on ordinary input. Complexity results warn that no efficient general solution covers every case unless major assumptions in complexity theory change.

Recursion introduces separate resource concerns. A pattern following deeply nested input consumes engine-managed depth or equivalent state. Implementations apply limits and differ in how recursion interacts with backtracking.

Engine version also matters. PCRE2 changed recursion semantics over time to align more closely with Perl in certain situations. A pattern tested under one version can behave differently after migration.

Portability is therefore limited even between engines described as Perl-compatible. Syntax support, Unicode rules, capture values, matching order, and recursion semantics can differ.

AI-generated regex raises the stakes because generation reduces the friction that once limited complexity. A developer can request a single expression for a grammar and receive something syntactically convincing within seconds.

The generated pattern may target the wrong flavor. It may pass the examples in the prompt while missing malformed input, consuming excessive resources, or returning captures with unexpected semantics.

Reviewers should treat generated regex as generated code. They need to identify the engine, understand each nontrivial construct, run adversarial tests, and enforce input and execution limits.

Readability is not a cosmetic concern here. Unreadable control flow prevents maintainers from identifying overlapping alternatives or noticing when a small edit creates catastrophic backtracking.

Extended mode provides whitespace and comments in engines that support it. Named groups reduce dependence on shifting numeric indexes. Smaller composed patterns can clarify responsibilities.

Those practices help, but composition must respect engine syntax. Some host languages interpolate strings before the regex compiler sees them, producing another layer of escaping and possible injection.

Untrusted fragments should never be inserted into a pattern without engine-appropriate escaping. Untrusted users should not receive unrestricted access to a backtracking matcher inside a shared service.

The skeptical conclusion is narrower than “never use advanced regex.” It is that each advanced construct spends part of a system’s predictability budget.

Developers should be able to name what they receive in return. Recursion may provide concise recognition for a bounded nested structure. A backreference may enforce an equality constraint that would otherwise require procedural code.

If the benefit is only avoiding a small parser, the trade becomes harder to justify. Parsers often provide better errors, clearer evolution, and output that downstream code can use directly.

Three Signals Will Decide Whether the Lesson Sticks

The lasting outcome depends on engine selection, generated-code review, and whether teams test failure behavior instead of examples alone.

The first signal is wider, explicit engine selection. Developers should stop treating regex as one portable language and document whether a pattern targets PCRE2, RE2, JavaScript, Java, .NET, Rust, or another implementation.

If libraries and platforms make execution guarantees visible, the Hacker News argument becomes easier to resolve. Developers can discuss a defined engine instead of debating an overloaded label.

The second signal is how coding assistants handle regex requests. Useful systems should ask for the target flavor, input bounds, trusted-data assumptions, and required captures before generating complex expressions.

They should also explain unsupported constructs and propose a parser when the requested output is structured. If assistants continue producing dense patterns without those checks, maintenance and security failures will increase.

The third signal is routine adversarial testing. Teams should measure successful matches, late failures, long repeated input, deep nesting, Unicode boundaries, and inputs shaped to maximize ambiguity.

A pattern that passes ten friendly examples has established correctness only for those examples. It has not established acceptable worst-case behavior or compatibility with production limits.

These signals strengthen Popov’s broader lesson while narrowing its application. Modern pattern engines can exceed the formal limits suggested by their name. That fact deserves to be understood, not used as a universal design endorsement.

The revived essay also offers a useful correction for both camps. Formal theory matters because it explains which guarantees are available. Implementation details matter because deployed engines do not all preserve those guarantees.

For developers following the Hacker News debate, the next action is concrete. Identify the engine behind your most complex production pattern, document its input contract, and test its slowest failure case. Then ask whether the application needs recognition or a structured parse.

If the pattern remains clear, bounded, and measurable, keep it. If its correctness depends on undocumented flavor behavior or fragile backtracking, replace the hidden grammar with an explicit parser.