Tiny Thompson NFA Regex Engine in C

A minimalist, high-efficiency implementation of Ken Thompson's classic regular expression matching algorithm in pure C. This engine compiles regular expressions into a Non-deterministic Finite Automaton (NFA) and simulates it in linear time, avoiding catastrophic backtracking vulnerabilities found in traditional regex engines.

---

Features

• Thompson's Construction: Converts infix regular expressions to postfix (re2post) and builds an explicit NFA via bytecode/instruction fragments with pointer patching.
• Guaranteed Linear Time: Runs in $O(mn)$ time complexity (where $m$ is the length of the regex and $n$ is the length of the string), preventing ReDoS (Regular Expression Denial of Service) attacks.
• Supported Operators:
• Literals: Exact character matching (e.g., abc)
• Wildcard (.): Matches any single character
• Kleene Star (*): Zero or more occurrences
• Alternation (|): Logical OR (e.g., a|b)

---

How It Works Under the Hood

1. Infix to Postfix Translation (re2post): The engine parses the raw regex string, implicitly inserts explicit concatenation operators (\x01), and converts it into postfix notation to make fragment building straightforward.
2. NFA Compilation (compile): Using a stack of NFA "fragments" (containing a start state and an open patch list for exit points), it stitches together instructions (CHAR, ANY, SPLIT, MATCH) and resolves jump pointers via memory patching.
3. State Simulation (match): Instead of exploring paths recursively (which causes exponential blowup), the matcher tracks active simulation state lists step-by-step for each character in the input string, handling SPLIT epsilon transitions dynamically.

---

Quick Start

1. The API (regex.h)

The engine exposes two primary functions:

• Inst *compile(char *pattern); — Compiles a regex pattern into an NFA instruction tree.
• int match(char *str, Inst *prog); — Evaluates a null-terminated string against the compiled NFA.

2. Usage Example

#include "regex.h"
#include <stdio.h>

int main() {
    // Compile pattern "a*"
    Inst *re = compile("a*");
    if (!re) {
        fprintf(stderr, "Failed to compile regex\n");
        return 1;
    }

    if (match("aaaa", re)) {
        printf("Match found!\n");
    }

    return 0;
}

---

Building & Testing

To compile your source files and run tests:

gcc -O3 -Wall -Wextra main.c regex.c -o regex_engine
./regex_engine

---

Credits & References

Based on the legendary article series by Russ Cox detailing Ken Thompson's 1968 paper "Regular Expression Search Algorithm" (CACM).