Thompson's construction

Thompson's construction translates a regular expression into a nondeterministic finite automaton (NFA) that recognizes the same language^[1]^[6]. It proceeds by structural recursion on the expression: a single symbol becomes an automaton with a start state, an accepting state and one transition between them, and concatenation, alternation and Kleene star each combine the automata of their subexpressions by adding at most two new states and a few epsilon-transitions, transitions that consume no input. An expression of size $m$ becomes an automaton with at most $2 m$ states. Simulating the automaton on all paths at once, by keeping the set of states it could be in after each character, decides whether a string of length $n$ matches in $O (mn)$ time. Ken Thompson published the method in 1968, as a compiler from regular expressions to IBM 7094 machine code for the QED text editor^[1]. It underlies grep and, through Russ Cox's RE2, the regular expression engines that guarantee linear-time matching^[7]^[12].

§ 01

Construction

Each regular expression $r$ is mapped to an automaton $N (r)$ with one start state, which has no incoming transitions, and one accepting state, which has no outgoing transitions^[6]. The base cases are the empty string, an automaton whose start state has an epsilon-transition to its accepting state, and a symbol $a$ , whose start state has a transition labelled $a$ . The inductive cases are:

The three inductive cases. For st, the accepting state of N(s) is connected to the start state of N(t). For s | t, a new start state branches into both automata, which both lead to a new accepting state. For s*, the new start state can skip N(s) entirely, and the end of N(s) can loop back to its start.

Every step adds at most two states, and every state has either one outgoing transition on a symbol, or at most two outgoing epsilon-transitions, or none. Consequently $N (r)$ has at most $2 m$ states and $4 m$ transitions, where $m$ is the number of symbols and operators in $r$ . That every state has at most two successors is what makes the simulation cheap.

A small regular expression parser: literals, the wildcard ., alternation, the postfix operators *, + and ?, and parentheses.

(* Regular expressions and a small parser: literals, ., |, *, +, ? and
   parentheses. *)
type re =
  | Chr of char | Any | Eps
  | Seq of re * re | Alt of re * re
  | Star of re | Plus of re | Opt of re
 
let parse s =
  let pos = ref 0 and n = String.length s in
  let peek () = if !pos < n then Some s.[!pos] else None in
  let rec alt () =
    let l = seq () in
    if peek () = Some '|' then (incr pos; Alt (l, alt ())) else l
  and seq () =
    match peek () with
    | None | Some ('|' | ')') -> Eps
    | _ -> let a = post () in
      (match peek () with None | Some ('|' | ')') -> a | _ -> Seq (a, seq ()))
  and post () =
    let rec loop a = match peek () with
      | Some '*' -> incr pos; loop (Star a)
      | Some '+' -> incr pos; loop (Plus a)
      | Some '?' -> incr pos; loop (Opt a)
      | _ -> a in
    loop (atom ())
  and atom () =
    match peek () with
    | Some '(' -> incr pos; let r = alt () in incr pos; r
    | Some '.' -> incr pos; Any
    | Some c -> incr pos; Chr c
    | None -> Eps
  in
  alt ()

Practical implementations do not build the empty-labelled start and accepting states of every fragment; they build each fragment directly in front of the state that must follow it, and represent epsilon-transitions by Split states with two successors. This is how Thompson's own code and Cox's implementations work^[1]^[7], and it produces at most one state per symbol or operator, plus the final accepting state.

The construction and the set-of-states simulation.

open Regex
 
(* An NFA state either consumes one character, or splits into two
   epsilon-transitions, or accepts. States are numbered in an array. *)
type state =
  | Char of char option * int     (* None matches any character *)
  | Split of int * int
  | Jump of int                   (* a single epsilon-transition *)
  | Match
 
type nfa = { states : state array; start : int }
 
(* Thompson's construction, building each fragment in front of the state
   that follows it. Every operator adds at most two states. *)
let compile re =
  let st = ref [||] and count = ref 0 in
  let add s =
    if !count = Array.length !st then
      st := Array.append !st (Array.make (max 8 !count) Match);
    !st.(!count) <- s; incr count; !count - 1 in
  let rec go re next =
    match re with
    | Eps -> next
    | Chr c -> add (Char (Some c, next))
    | Any -> add (Char (None, next))
    | Seq (a, b) -> go a (go b next)
    | Alt (a, b) -> let sa = go a next in let sb = go b next in add (Split (sa, sb))
    | Opt a -> add (Split (go a next, next))
    | Star a ->
      let loop = add (Jump 0) in               (* patched below *)
      let body = go a loop in
      !st.(loop) <- Split (body, next); loop
    | Plus a ->
      let loop = add (Jump 0) in
      let body = go a loop in
      !st.(loop) <- Split (body, next); body
  in
  let final = add Match in
  let start = go re final in
  { states = Array.sub !st 0 !count; start }
 
(* Simulate the NFA on all paths at once: keep the set of states the
   automaton could be in, as a list plus a mark per state. *)
let steps = ref 0
let matches nfa s =
  let n = Array.length nfa.states in
  let mark = Array.make n (-1) in
  let rec add gen acc i =
    if mark.(i) = gen then acc
    else begin
      mark.(i) <- gen; incr steps;
      match nfa.states.(i) with
      | Split (a, b) -> add gen (add gen acc a) b
      | Jump a -> add gen acc a
      | Char _ | Match -> i :: acc
    end in
  let current = ref (add 0 [] nfa.start) in
  String.iteri (fun k ch ->
      current := List.fold_left (fun acc i ->
          match nfa.states.(i) with
          | Char (c, next) when c = None || c = Some ch -> add (k + 1) acc next
          | _ -> acc) [] !current) s;
  List.exists (fun i -> nfa.states.(i) = Match) !current

The NFA for (a|b)*abb, the textbook example.

open Thompson
 
let show_state i = function
  | Char (Some c, j) -> Printf.printf "  %2d: '%c' -> %d\n" i c j
  | Char (None, j) -> Printf.printf "  %2d: any -> %d\n" i j
  | Split (a, b) -> Printf.printf "  %2d: split %d, %d\n" i a b
  | Jump a -> Printf.printf "  %2d: jump %d\n" i a
  | Match -> Printf.printf "  %2d: match\n" i

Running it.

start 4
   0: match
   1: 'b' -> 0
   2: 'b' -> 1
   3: 'a' -> 2
   4: split 7, 3
   5: 'a' -> 4
   6: 'b' -> 4
   7: split 5, 6
"abb"     true
"aabb"    true
"babb"    true
"abab"    false
"bbbabb"  true
""        false

§ 02

Simulation

A string is accepted if some path through the NFA, following epsilon-transitions freely and consuming one character per symbol transition, leads from the start state to the accepting state. The simulation keeps the set of all states that some path could have reached after reading the first $i$ characters, closed under epsilon-transitions. To read the next character it follows the matching transitions from every state in the set and closes the result again. Each step touches each state at most once, so the whole run takes $O (mn)$ time and $O (m)$ space^[1]^[7]. The set of states is exactly what Thompson's generated code maintained, as two lists of machine-code addresses, the current and the next^[1].

§ 03

Backtracking

Most regular expression libraries, including those of Perl, Python, Java and JavaScript, do not simulate the automaton but search it depth-first: they try one alternative, and if the rest of the match fails, they return and try the next. This supports features that are not regular, such as backreferences, but a single match can take exponential time^[7]. Matching with backreferences is NP-complete^[9], but the exponential behaviour also appears on expressions that are perfectly regular.

A backtracking matcher on the same syntax, and the two matchers compared on a?ⁿaⁿ against aⁿ.

open Regex
 
(* A backtracking matcher, which tries alternatives one at a time, in the
   manner of most regex libraries. k is what to match after re. *)
let bsteps = ref 0
let rec bt re s i k =
  incr bsteps;
  match re with
  | Eps -> k i
  | Chr c -> i < String.length s && s.[i] = c && k (i + 1)
  | Any -> i < String.length s && k (i + 1)
  | Seq (a, b) -> bt a s i (fun j -> bt b s j k)
  | Alt (a, b) -> bt a s i k || bt b s i k
  | Opt a -> bt a s i k || k i
  | Star a -> bt a s i (fun j -> j > i && bt re s j k) || k i
  | Plus a -> bt (Seq (a, Star a)) s i k
let backtrack re s = bt re s 0 (fun j -> j = String.length s)

Steps taken: recursive calls for the backtracking matcher, states added for the NFA simulation.

  n   backtracking        NFA
  5            309         51
 10          15344        176
 15         655339        376
 20       26214374        651
 25     1006632929       1001

The pattern a?a?…a?aa…a with $n$ optional and $n$ mandatory characters matches $a^{n}$ only if every optional a matches nothing, and the backtracking matcher tries the $2^{n}$ combinations of choices in order, finding the right one last. The simulation takes about $1.5 n^{2}$ steps, because the automaton has about $3 n$ states and the string $n$ characters. Cox used this example in 2007 to argue for Thompson's method^[7]. Such regular expression denial of service is common in practice: Davis and co-authors found super-linear regular expressions in thousands of npm and PyPI modules^[10], and a single backtracking expression took down Cloudflare's network for about half an hour in 2019^[11].

§ 04

Conversion to a DFA

The sets of states that the simulation passes through can be computed once and cached, which turns the NFA into a deterministic automaton: this is the subset construction of Rabin and Scott^[4]. The DFA reads each character in constant time, but it can have up to $2^{s}$ states for an NFA with $s$ states, and for some languages this is unavoidable. The language of strings over ${a, b}$ whose $n$ -th character from the end is $a$ has an NFA with $O (n)$ states, but every DFA for it must remember the last $n$ characters and so has at least $2^{n}$ states.

The subset construction, applied to (a|b)*a(a|b)ⁿ⁻¹.

open Thompson
 
(* The subset construction: each DFA state is a set of NFA states, and
   only the sets reachable from the start are built. *)
let closure nfa roots =
  let seen = Hashtbl.create 16 in
  let rec add i =
    if not (Hashtbl.mem seen i) then begin
      Hashtbl.add seen i ();
      match nfa.states.(i) with
      | Split (a, b) -> add a; add b
      | Jump a -> add a
      | _ -> ()
    end in
  List.iter add roots;
  List.sort compare (List.filter (fun i -> match nfa.states.(i) with
      | Char _ | Match -> true | _ -> false) (List.of_seq (Hashtbl.to_seq_keys seen)))
 
let dfa_size nfa alphabet =
  let known = Hashtbl.create 64 in
  let rec visit set =
    if not (Hashtbl.mem known set) then begin
      Hashtbl.add known set ();
      List.iter (fun ch ->
          visit (closure nfa (List.filter_map (fun i -> match nfa.states.(i) with
              | Char (c, j) when c = None || c = Some ch -> Some j
              | _ -> None) set))) alphabet
    end in
  visit (closure nfa [nfa.start]);
  Hashtbl.length known

Running it.

  n  NFA states  DFA states
  1           6           2
  2           9           4
  4          15          16
  8          27         256
 12          39        4096
 16          51       65536

Engines such as RE2 therefore build the DFA lazily, one state at a time as the input demands, and fall back to the NFA simulation when the cache of states grows too large^[12]. The Brzozowski derivative is another route from a regular expression to a DFA, without building an NFA first.

§ 05

Submatches

Programs usually need to know not only whether a regular expression matched but where its parenthesized groups matched. The set-of-states simulation can track this by attaching to each thread, a state together with the positions of the groups on the path that reached it, and preferring the thread that a backtracking matcher would have found first when two threads reach the same state. This is Pike's virtual machine, used in the sam and Plan 9 regular expression libraries and in RE2^[8].

§ 06

Related constructions

McNaughton and Yamada gave a construction from regular expressions to automata in 1960^[2], and Glushkov independently in 1961^[5]; their position automaton has one state per symbol occurrence plus a start state and no epsilon-transitions, but it can have a quadratic number of transitions, whereas Thompson's has a linear number of both. Textbooks sometimes call Thompson's construction the McNaughton–Yamada–Thompson algorithm^[6]. The converse direction, from an automaton to an expression, is Kleene's theorem^[3].

§ 07

History

Kleene introduced regular expressions in 1956 to describe the events that nerve nets and finite automata can recognize^[3]. Rabin and Scott defined nondeterministic automata and the subset construction in 1959^[4], and McNaughton and Yamada, and Glushkov, converted expressions into automata^[2]^[5]. Thompson's 1968 paper put regular expressions to practical use in searching text: his implementation of the QED editor compiled each expression into IBM 7094 code that simulated the NFA^[1]. He carried the idea into the Unix editor ed and the tool grep. The later popularity of backtracking engines, which Perl made standard, led Cox to restate the case for Thompson's algorithm in 2007^[7], and his RE2 library, released by Google in 2010, combined the NFA simulation, a lazily built DFA and Pike's submatch tracking^[12]. Rust's regex crate and Go's regexp package follow the same design.