DSA DSA In Depth
0%
From-Scratch Build

Thompson Lockstep NFA Regular Expression Engine (Zero Backtracking)

A Ken Thompson non-backtracking regular expression compiler and lockstep NFA simulator that guarantees O(|P| * |T|) time even on pathological ReDoS patterns like (a+)+b.

~50 min Advanced Lessons: Build Lab: ReDoS-Proof Regular Expression Engine via Thompson's Construction & NFA Step Simulation, Aho-Corasick Automaton: Trie + BFS Failure Links + Dictionary Suffix Links, Knuth-Morris-Pratt (KMP): Prefix Function π[i] Amortized Linearity & DFA View, Depth-First Search: Parenthesis Theorem, White-Path Theorem & Tree/Back/Forward/Cross Edges, Call Stacks, Dijkstra's Shunting-Yard Algorithm & AST Evaluation, Prefix Tries, Compressed Radix Trees & PATRICIA Trees
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Why Backtracking Regex Engines Explode (ReDoS)

Recursive backtracking engines (like standard PCRE / JavaScript RegExp without linear-time mode) explore one path through the NFA at a time. On ambiguous patterns like (a+)+b against $\text{"a"}^{35}\text{"c"}$, backtracking tries $2^{35}$ ways to partition the $\text{a}$'s before failing.

Ken Thompson's 1968 Lockstep NFA Simulation

Ken Thompson's algorithm simulates all active NFA states simultaneously:

  1. Postfix Compilation: The regex is parsed into postfix notation and assembled into NFA fragments where every state has at most 2 outgoing edges (SPLIT epsilon branches or a single character transition). An expression of length $m$ produces at most $2m$ states.
  2. Generation-Stamped Deduplication: Instead of allocating a hash set at every character step, each NFAState stores an integer lastList. Incrementing this._listId at each character step gives $O(1)$ membership checks and guarantees $|\text{clist}| \le 2m$.
  3. Strict $O(m \cdot n)$ Time: Processing each of the $n$ characters inspects at most $2m$ states, making catastrophic backtracking mathematically impossible.

Curriculum Connections

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Explicit Concatenation & Shunting-Yard Postfix Conversion

  • Core Mechanical Concept: Explicit Concatenation & Shunting-Yard Postfix Conversion
  • Target Module: index.js (Step1)
  • Engineering Specification: Insert explicit concatenation markers between adjacent atoms/closures and convert the infix regex to postfix using operator precedences | < concat < ?, *, +.
  • Verification Invariant: verifies Step 1: Explicit Concatenation & Shunting-Yard Postfix Conversion

Step 2: Ken Thompson Structural NFA Fragment Assembly

  • Core Mechanical Concept: Ken Thompson Structural NFA Fragment Assembly
  • Target Module: index.js (Step2)
  • Engineering Specification: Compile the postfix expression using a stack of Frag(start, outPtrs) objects where dangling output arrows are patched as fragments combine.
  • Verification Invariant: verifies Step 2: Ken Thompson Structural NFA Fragment Assembly

Step 3: O(1) Generation-Stamped Epsilon Closure

  • Core Mechanical Concept: O(1) Generation-Stamped Epsilon Closure
  • Target Module: index.js (Step3)
  • Engineering Specification: Implement _addState(list, state) following SPLIT epsilon edges recursively and tagging state.lastList = this._listId so each NFA state enters list at most once per character.
  • Verification Invariant: verifies Step 3: O(1) Generation-Stamped Epsilon Closure

Step 4: Lockstep State-Set Simulation

  • Core Mechanical Concept: Lockstep State-Set Simulation
  • Target Module: index.js (Step4)
  • Engineering Specification: Implement test(text) by advancing clist to nlist one character at a time and checking if MATCH is in the final state set.
  • Verification Invariant: verifies Step 4: Lockstep State-Set Simulation

Asymptotic & Memory Layout Guarantees

  • Category: Strings & Automata
  • Difficulty: Advanced (~50 minutes)
  • Key Architectural Highlights:
    • Explicit concatenation insertion and Dijkstra Shunting-Yard regex-to-postfix compiler
    • Ken Thompson structural NFA fragment assembly supporting |, *, +, ?, ., and parentheses
    • Lockstep state-set simulation with generation-id deduplication preventing catastrophic backtracking (ReDoS)
  • Tags & Primitives: Thompson NFA, Shunting-Yard Parser, Regular Expressions, Zero Backtracking, ReDoS Immunity

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.