Limitations of regex in parsing semantics

• 09 April 2025
• PL theory

Parsing languages is a widely researched subject. Languages are mostly structured. Linear languages appear in the form of bytecode or stack-based assembly formats that have the benefit of being streamed. Ideally, we would also need a way to linearize structure from a string. In order for this to be remotely possible, there are formalisms required, at least according to mainstream PL design approaches.

• Context-free grammars and pushdown automata for syntactic analysis
• Attribute grammars or other formalisms for semantic analysis
• Full Turing machines for complete language processing

Could regular expressions achieve this? No.

This is also regarded as obvious and there is a hilarious anecdote on StackOverflow where a question was posed about parsing HTML with regular expressions.

1. Introduction #

Regular expressions constitute a formal language for pattern matching that corresponds to regular languages, the weakest class in the Chomsky hierarchy. We will look into why alternative parsing mechanisms with higher computational capabilities are required for the analysis of hierarchically structured PLs and formal systems.

We make the claim that regular expressions, as finite state automata, cannot recognize nested hierarchical structures of arbitrary depth due to their inherent memory limitations which makes them inadequate for parsing Turing-complete languages which require at minimum the computational power of a pushdown automaton (PDA) for syntax analysis and a Turing machine for semantic evaluation.

2. Automata theory #

2.1 Formal definitions #

We begin by reviewing existing definitions before our analysis.

Definition 2.1.1 A deterministic finite automaton (DFA) is a 5-tuple $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ where:

• $Q$ is a finite set of states
• $\mathrm{\Sigma }$ is a finite alphabet
• $\delta :Q\times \mathrm{\Sigma }\to Q$ is the transition function
• $q_0\in Q$ is the initial state
• $F\subseteq Q$ is the set of accepting states

Definition 2.1.2 A nondeterministic finite automaton (NFA) is a 5-tuple $M=(Q,\mathrm{\Sigma },\mathrm{\Delta },q_0,F)$ where:

• $Q,\mathrm{\Sigma },q_0,F$ are defined as in the DFA
• $\mathrm{\Delta }:Q\times {\mathrm{\Sigma }}_{ϵ}\to \mathcal{P}(Q)$ is the transition relation, where ${\mathrm{\Sigma }}_{ϵ}=\mathrm{\Sigma }\cup ϵ$ and $\mathcal{P}(Q)$ is the power set of $Q$

Definition 2.1.3 A regular language is a language that can be recognized by a DFA or NFA.

Definition 2.1.4 A regular expression over an alphabet $\mathrm{\Sigma }$ is inductively defined as:

• $\mathrm{\varnothing }$ (empty set) is a regular expression
• $ϵ$ (empty string) is a regular expression
• For each $a\in \mathrm{\Sigma }$, $a$ is a regular expression
• If $r$ and $s$ are regular expressions, then:
  • $(r\cdot s)$ (concatenation)
  • $(r|s)$ (alternation)
  • $(r^{\ast })$ (Kleene star) are regular expressions

Theorem 2.1.5 (Kleene's Theorem) A language is regular if and only if it can be described by a regular expression.

2.2 The Pumping Lemma for regular languages #

The Pumping Lemma is a method for proving that certain languages are not regular.

Theorem 2.2.1 (Pumping Lemma) For any regular language $L$, there exists a constant $p\ge 1$ (referred to as the pumping length) such that for all strings $s\in L$ with $|s|\ge p$, there exists a decomposition $s=xyz$ such that the following holds.

1. $|y|>0$
2. $|xy|\le p$
3. For all $i\ge 0$, $x{y}^{i}z\in L$

2.3 Proof of non-regularity for context-free languages #

Theorem 2.3.1 The language $L=a^n{b}^n\mid n\ge 0$ is not regular.

Proof: By contradiction. Assume that $L$ is regular. By the Pumping Lemma, there exists a pumping length $p\ge 1$. Consider the string $s=a^p{b}^p\in L$. Since $|s|\ge p$, the Pumping Lemma applies and there exists a decomposition $s=xyz$ with the properties stated in Theorem 2.2.1.

Since $|xy|\le p$, the substring $xy$ must consist entirely of $a$'s. Let $xy=a^k$ for some $k>0$ and consequently $z=a^{p-k}{b}^p$. By the Pumping Lemma, $x{y}^{2}z=a^{k+|y|}{a}^{p-k}{b}^p=a^{p+|y|}{b}^p\in L$. However, this string contains unequal numbers of $a$'s and $b$'s which contradicts the definition of $L$. Hence, $L$ is not regular. $◻$

This is a quick illustration that even the basic nested structure of matching opening and closing symbols ($a^n{b}^n$) exceeds the parsing capacity of regular expressions. In PLs, this is commonly known as the bracket balancing problem. We can trivially implement this using a stack without any issues but then again, that wouldn't be a regular language approach.

3. Representation of hierarchical structures #

3.1 The Chomsky hierarchy #

The Chomsky hierarchy provides a classification of formal grammars and their corresponding languages.

Definition 3.1.1 A formal grammar is a 4-tuple $G=(N,\mathrm{\Sigma },P,S)$ where:

• $N$ is a finite set of non-terminal symbols
• $\mathrm{\Sigma }$ is a finite set of terminal symbols, disjoint from $N$
• $P$ is a finite set of production rules
• $S\in N$ is the start symbol

It classifies grammars based on the restrictions on their production rules.

1. Type-0 (unrestricted): No restrictions on productions. Recognizable by Turing machines.
2. Type-1 (context-sensitive): Productions of the form $\alpha A\beta \to \alpha \gamma \beta$ where $A\in N$ and $\alpha ,\beta ,\gamma \in (N\cup \mathrm{\Sigma }{)}^{\ast }$ with $\gamma \ne ϵ$. Recognizable by linear-bounded automata.
3. Type-2 (context-free): Productions of the form $A\to \gamma$ where $A\in N$ and $\gamma \in (N\cup \mathrm{\Sigma }{)}^{\ast }$. Recognizable by pushdown automata.
4. Type-3 (regular): Productions of the form $A\to aB$ or $A\to a$ where $A,B\in N$ and $a\in \mathrm{\Sigma }\cup ϵ$. Recognizable by finite automata.

3.2 Computational discrepancy between regular and context-free #

Theorem 3.2.1 The class of regular languages is strictly contained within the class of context-free languages.

Proof: Every regular language is trivially context-free since Type-3 grammars are a restricted form of Type-2 grammars. We must show that there exists at least one context-free language that is not regular. The language $L=a^n{b}^n\mid n\ge 0$ is context-free, i.e. it can be generated by the grammar $S\to aSb\mid ϵ$ but not regular according to Theorem 2.3.1. Therefore, the containment is strict. $◻$

3.3 Recursive nesting and memory requirements #

To reiterate, the limitation of regular expressions is their inability to maintain state beyond a fixed, finite amount. This is also besides the issue of unrepresentability of certain grammars.

Theorem 3.3.1 Any language requiring unbounded counting or memory cannot be recognized by a finite automaton.

Proof: Let $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ be a DFA with $|Q|=k$ states. Consider an input requiring the DFA to remember more than $k$ distinct pieces of information. By the pigeonhole principle, at least two different information states must map to the same DFA state. Once these configurations map to the same state, the DFA has basically forgotten the distinction between them and all subsequent computation paths are identical regardless of which original information state led to this point. Thus, no DFA can maintain unbounded memory. $◻$

Another idea is to parse a string line-by-line and use basic production rules. E.g. a Markdown parser with rules applied to every line. A single chunk of regular expression could define rules for matching against each line, although this would not account for the entire CommonMark specification which includes HTML blocks and multiline Markdown tags!

For hierarchical structures like balanced parentheses or matched XML tags, the required memory grows with nesting depth. This category of languages are, by definition, inherently unparsable by regular expressions alone.

4. Proof theoretic approach #

4.1 Logical characterization of regular languages #

Is there a way to characterize regular languages?

Regular languages can be characterized using monadic second-order logic (MSO) over strings.

Theorem 4.1.1 (Büchi-Elgot-Trakhtenbrot) A language $L$ is regular if and only if it is definable in MSO logic over strings.

MSO can express local properties and finite counting but cannot express the global matching constraints required for balanced structures.

4.2 Hierarchical structures as inductive types #

From a proof-theoretic perspective, hierarchical structures like trees are naturally represented as inductive types.

Definition 4.2.1 An inductive type $T$ is defined by constructors $c_1,c_2,\dots ,c_n$ where each constructor has a type signature $c_i:{\tau }_1\times {\tau }_2\times \dots \times {\tau }_{m_i}\to T$ with each ${\tau }_j$ being either $T$ or some other type.

Quick example, binary trees can be defined in standard ML as:

datatype BinaryTree = Leaf | Node of BinaryTree * BinaryTree

Regular expressions correspond to finite automata which cannot recursively traverse such structures.

4.3 Curry-Howard correspondence #

Theorem 4.3.1 (Curry-Howard Isomorphism) There is a one-to-one correspondence between:

• Proofs in intuitionistic logic and typed $\lambda$-calculus terms
• Propositions and types
• Proof normalization and term evaluation

Type checking in PLs requires validating nested structures and scope rules. Any such verification necessitates at minimum a CFG since it must maintain a type environment and verify that variables are declared before use—a non-regular property.

In both cases, we validate recursive tree structures where child elements must satisfy parent constraints according to compositional rules, with XML-like tag matching (i.e. <p>...</p>) being isomorphic to type judgment validation in the STLC where expression typing follows Γ ⊢ e:τ with nesting requirements that demonstrably exceed the pattern-matching capabilities of regular languages.

5. Language recognition #

5.1 Typed $\lambda$-Calculus and PLs #

Most PLs have features that cannot be recognized by regular expressions.

Definition 5.1.1 The simply typed $\lambda$-calculus is defined by the grammar:

• Types: $\tau ::=\text{Base}\mid {\tau }_1\to {\tau }_2$
• Terms: $t::=x\mid \lambda x:\tau .t\mid t_1,t_2$

The problem of type checking—determining if a term $t$ has type $\tau$—asks for maintaining a typing context and variable binding. This is beyond the design of pattern matching in strings even with lookaheads and lookbehinds.

General recursion in Turing-complete languages is supported through fixed-point combinators.

5.2 Recursion and fixed-point combinators #

Definition 5.2.1 The Y combinator is defined as $Y=\lambda f.(\lambda x.f(x,x))(\lambda x.f(x,x))$

For any function $f$, $Y,f$ is a fixed point of $f$, i.e. $Y,f=f(Y,f)$. The Y combinator makes it possible to define recursive functions without explicit recursion in the language. The semantics of such recursive definitions require a pushdown automaton at minimum to evaluate correctly since function calls must be nested and returned in the correct order.

5.3 Formal proof of parsing requirements #

Theorem 5.3.1 Parsing a Turing-complete language requires at minimum a pushdown automaton.

Proof: Consider a simple Turing-complete language with function definitions and calls. To correctly parse this language, we require the following:

1. Match function declarations with their corresponding bodies
2. Variables must be used within their corresponding scope
3. Verify that function calls correspond to declared functions

Let us focus on the specific problem of checking balanced nested function calls, i.e. $L=s\mid s\text{ contains nested function calls}$

This language contains the subset $L^{\prime }=f^n{g}^n\mid n\ge 0$, where $f$ represents a function call and $g$ represents a return. By a proof analogous to Theorem 2.3.1, $L^{\prime }$ is not regular. Therefore, $L$ is not regular and parsing a Turing-complete language requires at minimum a pushdown automaton. $◻$

6. PL constructs #

6.1 Balanced parentheses and nested blocks #

Theorem 6.1.1 The language of balanced parentheses $L=w\in {(,)}^{\ast }\mid \text{parentheses in }w\text{ are balanced}$ is not regular.

Proof: This follows from a direct application of the Pumping Lemma, similar to the proof in Theorem 2.3.1. $◻$

Nearly the same proofs apply to nested code blocks, XML tags and other hierarchical constructs.

6.2 Recursive descent parsing with a stack #

Theorem 6.2.1 Parsing nested structures of unbounded depth requires a stack of unbounded size.

Proof: Consider the language $L=a^n{b}^n\mid n\ge 0$. To recognize strings in this language, a parser must count the number of $a$'s and then verify an equal number of $b$'s. For strings with arbitrarily large $n$, the parser would have to maintain a count that can grow without bound, i.e. unbounded memory. A finite automaton has bounded memory, so it cannot recognize $L$. $◻$

7. Context-sensitive and recursive features #

Parser generators like LALRPOP implement deterministic algorithms such as LALR(1) that handle context-free languages by constructing pushdown automata with fixed lookahead. It offers a massive performance over RDP by pre-computing parse tables and avoiding backtracking with $O(n)$ complexity (or at least near linear in practical cases).

PEG (Parsing Expression Grammar) parsers represent an alternative approach that works well for unambiguous parsing. Unlike CFG parsers, PEG uses unlimited lookahead and ordered choice, i.e. eliminates many cases of unambiguity in patterns that would require semantic predicates in LALR, although it can easily fall into stack depth issues.

The cost of an intuitive grammar composition is memory.

Definition 7.1 A context-sensitive feature requires knowledge of the surrounding context beyond trivial nesting structure.

Examples include:

• Variable declaration before use
• Type checking with polymorphism

Theorem 7.2 Complete Turing-complete language processing requires the power of a Turing machine.

Proof: By definition, a Turing-complete language can encode any computable function. If a weaker computational model could process such a language completely, it would contradict the Church-Turing thesis by computing functions beyond its theoretical capabilities. $◻$

8. Language recognition with categorical semantics #

8.1 Algebraic structure of regular languages #

From a category-theoretic perspective, regular languages can be characterized as the free Kleene algebra generated by an alphabet.

Definition 8.1.1 A Kleene algebra is a structure $(K,+,\cdot ,\ast ,0,1)$ where:

• $(K,+,0)$ is a commutative monoid
• $(K,\cdot ,1)$ is a monoid
• Multiplication distributes over addition
• $a^{\ast }=\sum _{i=0}^{\mathrm{\infty }}{a}^i$ is the Kleene star

Regular expressions form the free Kleene algebra generated by the alphabet $\mathrm{\Sigma }$ which is an algebraic structure that lacks expression.

Definition 8.1.2 An algebraic theory consists of operations and equations specifying how these operations interact.

A wordy way of saying this can be found on Wikipedia, an algebraic theory is a theory that uses axioms stated entirely in terms of equations between terms with free variables, so context-free languages can be characterized using algebraic theories with recursively defined operations.

References #

• Wikipedia - Büchi-Elgot-Trakhtenbrot, Curry–Howard correspondence

• nLab - algebraic theory

• Types and Programming Languages — Pierce, B. C. (2002).

• Hopcroft, J. E., Motwani, R. & Ullman, J. D. (2013). Introduction to Automata Theory, Languages, and Computation. Pearson.

• A completeness theorem for Kleene algebras and the algebra of regular events — Kozen, D. (1994), Cornell University.

• Previous: Portable vectorization in C++23