regex visualizer

A small regex engine that compiles patterns to an NFA via Thompson's construction, and renders the graph live.
pattern
test string
match
Nodes lit up green are the states currently reachable after consuming the test string so far — the double circle is the accept state. Dashed gray edges are epsilon (ε) transitions, free moves the engine takes without consuming input.
Regular expressions are usually thought of as text-matching syntax, but under the hood a regex engine is a compiler: it turns a pattern into a finite automaton, then simulates that automaton over the input one character at a time. This one uses Thompson's construction — the classic 1968 algorithm for building an NFA out of a regex recursively. Concatenation chains two fragments together with an epsilon (free, input-free) transition; alternation branches out to both options and rejoins; *, +, and ? each add a small loop-back or skip edge around a fragment. There's no backtracking at match time — the engine just tracks the set of states currently reachable, and grows or shrinks that set one input character at a time.
This is the same automata-theory family as the Game of Life and cellular automaton pages, just a different branch of it. A finite automaton's entire state is which of a small, fixed set of nodes are currently active — nothing more. A cellular automaton's state is an entire row (or grid) of cells, simple individually but with unbounded space to spread structure across — which is exactly why rule 110 can be Turing-complete and this NFA can't: it has no way to count or remember anything beyond which states it's currently in.
view source
import { useMemo, useState } from 'react';

type AstNode =
  | { type: 'char'; value: string }
  | { type: 'concat'; parts: AstNode[] }
  | { type: 'alt'; options: AstNode[] }
  | { type: 'star'; child: AstNode }
  | { type: 'plus'; child: AstNode }
  | { type: 'opt'; child: AstNode };

interface NFAState {
  id: number;
  transitions: { symbol: string | null; to: number }[];
}

interface NFA {
  states: NFAState[];
  start: number;
  accept: number;
}

function parse(pattern: string): AstNode {
  let pos = 0;
  const peek = () => pattern[pos];
  const eof = () => pos >= pattern.length;

  function parseAlt(): AstNode {
    const first = parseConcat();
    const options = [first];
    while (!eof() && peek() === '|') {
      pos++;
      options.push(parseConcat());
    }
    return options.length === 1 ? options[0] : { type: 'alt', options };
  }

  function parseConcat(): AstNode {
    const parts: AstNode[] = [];
    while (!eof() && peek() !== '|' && peek() !== ')') {
      parts.push(parseFactor());
    }
    if (parts.length === 0) return { type: 'concat', parts: [] };
    return parts.length === 1 ? parts[0] : { type: 'concat', parts };
  }

  function parseFactor(): AstNode {
    let atom = parseAtom();
    while (!eof() && (peek() === '*' || peek() === '+' || peek() === '?')) {
      const op = peek();
      pos++;
      atom =
        op === '*'
          ? { type: 'star', child: atom }
          : op === '+'
            ? { type: 'plus', child: atom }
            : { type: 'opt', child: atom };
    }
    return atom;
  }

  function parseAtom(): AstNode {
    if (eof()) throw new Error(`unexpected end of pattern at position ${pos}`);
    if (peek() === '(') {
      pos++;
      const inner = parseAlt();
      if (peek() !== ')')
        throw new Error(`missing closing ')' at position ${pos}`);
      pos++;
      return inner;
    }
    if (peek() === '.') {
      pos++;
      return { type: 'char', value: '.' };
    }
    if (peek() === '\\') {
      pos++;
      if (eof()) throw new Error('trailing backslash');
      const c = peek();
      pos++;
      return { type: 'char', value: c };
    }
    const c = peek();
    pos++;
    return { type: 'char', value: c };
  }

  const ast = parseAlt();
  if (!eof())
    throw new Error(`unexpected character '${peek()}' at position ${pos}`);
  return ast;
}

function compile(ast: AstNode): NFA {
  const states: NFAState[] = [];
  const newState = (): number => {
    states.push({ id: states.length, transitions: [] });
    return states.length - 1;
  };
  const addEdge = (from: number, to: number, symbol: string | null) => {
    states[from].transitions.push({ symbol, to });
  };

  function build(node: AstNode): { start: number; end: number } {
    switch (node.type) {
      case 'char': {
        const s0 = newState();
        const s1 = newState();
        addEdge(s0, s1, node.value);
        return { start: s0, end: s1 };
      }
      case 'concat': {
        if (node.parts.length === 0) {
          const s0 = newState();
          return { start: s0, end: s0 };
        }
        let frag = build(node.parts[0]);
        for (let i = 1; i < node.parts.length; i++) {
          const next = build(node.parts[i]);
          addEdge(frag.end, next.start, null);
          frag = { start: frag.start, end: next.end };
        }
        return frag;
      }
      case 'alt': {
        const s0 = newState();
        const s1 = newState();
        for (const opt of node.options) {
          const frag = build(opt);
          addEdge(s0, frag.start, null);
          addEdge(frag.end, s1, null);
        }
        return { start: s0, end: s1 };
      }
      case 'star': {
        const s0 = newState();
        const s1 = newState();
        const frag = build(node.child);
        addEdge(s0, frag.start, null);
        addEdge(s0, s1, null);
        addEdge(frag.end, frag.start, null);
        addEdge(frag.end, s1, null);
        return { start: s0, end: s1 };
      }
      case 'plus': {
        const s0 = newState();
        const s1 = newState();
        const frag = build(node.child);
        addEdge(s0, frag.start, null);
        addEdge(frag.end, frag.start, null);
        addEdge(frag.end, s1, null);
        return { start: s0, end: s1 };
      }
      case 'opt': {
        const s0 = newState();
        const s1 = newState();
        const frag = build(node.child);
        addEdge(s0, frag.start, null);
        addEdge(s0, s1, null);
        addEdge(frag.end, s1, null);
        return { start: s0, end: s1 };
      }
    }
  }

  const frag = build(ast);
  return { states, start: frag.start, accept: frag.end };
}

function epsilonClosure(states: NFAState[], set: Set<number>): Set<number> {
  const stack = [...set];
  const closure = new Set(set);
  while (stack.length) {
    const s = stack.pop()!;
    for (const t of states[s].transitions) {
      if (t.symbol === null && !closure.has(t.to)) {
        closure.add(t.to);
        stack.push(t.to);
      }
    }
  }
  return closure;
}

function step(
  states: NFAState[],
  current: Set<number>,
  char: string,
): Set<number> {
  const next = new Set<number>();
  for (const s of current) {
    for (const t of states[s].transitions) {
      if (t.symbol !== null && (t.symbol === char || t.symbol === '.')) {
        next.add(t.to);
      }
    }
  }
  return epsilonClosure(states, next);
}

function runStates(nfa: NFA, input: string): Set<number> {
  let current = epsilonClosure(nfa.states, new Set([nfa.start]));
  for (const ch of input) {
    current = step(nfa.states, current, ch);
    if (current.size === 0) break;
  }
  return current;
}

// Layered layout: each state's column is the longest path from the start
// state, ignoring back-edges (loops from `*`/`+`) so cycles don't cause
// infinite recursion. Small toy NFAs only, so no need for anything fancier.
function computeLayers(states: NFAState[], start: number): number[] {
  const layer = new Array(states.length).fill(0);
  const visited = new Array(states.length).fill(false);
  const onStack = new Array(states.length).fill(false);

  function dfs(s: number, depth: number) {
    if (onStack[s]) return;
    if (visited[s] && depth <= layer[s]) return;
    layer[s] = depth;
    visited[s] = true;
    onStack[s] = true;
    for (const t of states[s].transitions) dfs(t.to, depth + 1);
    onStack[s] = false;
  }

  dfs(start, 0);
  return layer;
}

const NODE_R = 16;
const LAYER_W = 100;
const ROW_H = 56;
const MARGIN = 36;
// Extra headroom above the node rows, reserved for routing edges that span
// more than one layer (the "skip zero repetitions" edge of a `*`/`+`/`?`,
// or its loop-back) up and over the nodes in between, instead of a single
// bowed curve that cuts straight through whatever sits in the middle.
const CHANNEL_MARGIN = 34;
const CHANNEL_Y = 14;

interface Layout {
  width: number;
  height: number;
  pos: { x: number; y: number }[];
}

function computeLayout(nfa: NFA): Layout {
  const layers = computeLayers(nfa.states, nfa.start);
  const maxLayer = Math.max(0, ...layers);
  const byLayer = new Map<number, number[]>();
  layers.forEach((l, i) => {
    const arr = byLayer.get(l) ?? [];
    arr.push(i);
    byLayer.set(l, arr);
  });
  const maxRows = Math.max(...[...byLayer.values()].map((a) => a.length));

  const pos: { x: number; y: number }[] = new Array(nfa.states.length);
  for (const [l, ids] of byLayer) {
    const offset = ((maxRows - ids.length) * ROW_H) / 2;
    ids.forEach((id, i) => {
      pos[id] = {
        x: MARGIN + l * LAYER_W,
        y: CHANNEL_MARGIN + MARGIN + offset + i * ROW_H,
      };
    });
  }

  return {
    width: MARGIN * 2 + maxLayer * LAYER_W,
    height: CHANNEL_MARGIN + MARGIN * 2 + Math.max(0, maxRows - 1) * ROW_H,
    pos,
  };
}

interface EdgeInfo {
  from: number;
  to: number;
  symbol: string | null;
  isBack: boolean;
  span: number;
}

function collectEdges(nfa: NFA, layers: number[]): EdgeInfo[] {
  const edges: EdgeInfo[] = [];
  nfa.states.forEach((s) => {
    for (const t of s.transitions) {
      edges.push({
        from: s.id,
        to: t.to,
        symbol: t.symbol,
        isBack: layers[t.to] <= layers[s.id],
        span: Math.abs(layers[t.to] - layers[s.id]),
      });
    }
  });
  return edges;
}

function quadPath(
  x1: number,
  y1: number,
  x2: number,
  y2: number,
  bend: number,
) {
  const mx = (x1 + x2) / 2;
  const my = (y1 + y2) / 2;
  const dx = x2 - x1;
  const dy = y2 - y1;
  const len = Math.sqrt(dx * dx + dy * dy) || 1;
  const nx = -dy / len;
  const ny = dx / len;
  const cx = mx + nx * bend;
  const cy = my + ny * bend;
  return {
    d: `M ${x1} ${y1} Q ${cx} ${cy} ${x2} ${y2}`,
    labelX: 0.25 * x1 + 0.5 * cx + 0.25 * x2,
    labelY: 0.25 * y1 + 0.5 * cy + 0.25 * y2,
  };
}

// Routes an edge spanning multiple layers up into the shared channel above
// all node rows, across, and back down -- rather than a single bowed curve
// through whatever nodes sit between the endpoints. `lane` staggers
// multiple channel edges slightly so they don't sit exactly on top of
// each other.
function channelPath(
  x1: number,
  y1: number,
  x2: number,
  y2: number,
  lane: number,
) {
  const y = CHANNEL_Y + lane * 6;
  const c1x = x1 + (x2 - x1) * 0.25;
  const c2x = x1 + (x2 - x1) * 0.75;
  return {
    d: `M ${x1} ${y1} C ${c1x} ${y}, ${c2x} ${y}, ${x2} ${y2}`,
    labelX: (x1 + x2) / 2,
    labelY: y,
  };
}

const PRESETS = ['a(b|c)*d', 'colou?r', '(ab)*|c', 'a+b?c*'];

interface Props {
  initialPattern?: string;
}

export default function RegexVisualizer({
  initialPattern = 'a(b|c)*d',
}: Props) {
  const [pattern, setPattern] = useState(initialPattern);
  const [testInput, setTestInput] = useState('acbcd');

  const compiled = useMemo(() => {
    try {
      return { nfa: compile(parse(pattern)), error: null as string | null };
    } catch (e) {
      return { nfa: null, error: e instanceof Error ? e.message : String(e) };
    }
  }, [pattern]);

  const layout = useMemo(
    () => (compiled.nfa ? computeLayout(compiled.nfa) : null),
    [compiled.nfa],
  );
  const layers = useMemo(
    () =>
      compiled.nfa
        ? computeLayers(compiled.nfa.states, compiled.nfa.start)
        : [],
    [compiled.nfa],
  );
  const edges = useMemo(
    () => (compiled.nfa ? collectEdges(compiled.nfa, layers) : []),
    [compiled.nfa, layers],
  );

  const active = useMemo(() => {
    if (!compiled.nfa) return new Set<number>();
    return runStates(compiled.nfa, testInput);
  }, [compiled.nfa, testInput]);

  const isMatch = compiled.nfa ? active.has(compiled.nfa.accept) : false;

  return (
    <div className="regex-visualizer">
      <div className="field">
        <label htmlFor="rv-pattern">pattern</label>
        <input
          id="rv-pattern"
          type="text"
          value={pattern}
          maxLength={40}
          spellCheck={false}
          onChange={(e) => setPattern(e.target.value)}
        />
      </div>

      <div className="presets">
        {PRESETS.map((p) => (
          <button
            key={p}
            type="button"
            className={pattern === p ? 'active' : ''}
            onClick={() => setPattern(p)}
          >
            {p}
          </button>
        ))}
      </div>

      {compiled.error && <p className="error">{compiled.error}</p>}

      {compiled.nfa && layout && (
        <>
          <div className="graph-scroll">
            <svg
              width={layout.width}
              height={layout.height}
              role="img"
              aria-label={`NFA graph for pattern ${pattern}`}
            >
              <defs>
                <marker
                  id="rv-arrow-sym"
                  viewBox="0 0 10 10"
                  refX="9"
                  refY="5"
                  markerWidth="6"
                  markerHeight="6"
                  orient="auto-start-reverse"
                >
                  <path d="M 0 0 L 10 5 L 0 10 z" fill="#e6e6e6" />
                </marker>
                <marker
                  id="rv-arrow-eps"
                  viewBox="0 0 10 10"
                  refX="9"
                  refY="5"
                  markerWidth="5"
                  markerHeight="5"
                  orient="auto-start-reverse"
                >
                  <path d="M 0 0 L 10 5 L 0 10 z" fill="#5a5f66" />
                </marker>
              </defs>

              {/* incoming arrow into the start state */}
              <path
                d={`M ${layout.pos[compiled.nfa.start].x - NODE_R - 20} ${layout.pos[compiled.nfa.start].y} L ${layout.pos[compiled.nfa.start].x - NODE_R} ${layout.pos[compiled.nfa.start].y}`}
                stroke="#e6e6e6"
                strokeWidth={1.5}
                markerEnd="url(#rv-arrow-sym)"
                fill="none"
              />

              {(() => {
                let lane = 0;
                return edges.map((edge, i) => {
                  const p1 = layout.pos[edge.from];
                  const p2 = layout.pos[edge.to];
                  const { d, labelX, labelY } =
                    edge.span > 1
                      ? channelPath(p1.x, p1.y, p2.x, p2.y, lane++)
                      : quadPath(p1.x, p1.y, p2.x, p2.y, edge.isBack ? 46 : 14);
                  const isEps = edge.symbol === null;
                  return (
                    <g key={i}>
                      <path
                        d={d}
                        fill="none"
                        stroke={isEps ? '#5a5f66' : '#e6e6e6'}
                        strokeWidth={isEps ? 1 : 1.5}
                        strokeDasharray={isEps ? '3 3' : undefined}
                        markerEnd={
                          isEps ? 'url(#rv-arrow-eps)' : 'url(#rv-arrow-sym)'
                        }
                      />
                      <text
                        x={labelX}
                        y={labelY - 5}
                        textAnchor="middle"
                        fontSize={11}
                        fill={isEps ? '#5a5f66' : '#7cf29c'}
                        fontFamily="var(--mono)"
                      >
                        {isEps ? 'ε' : edge.symbol === ' ' ? '␣' : edge.symbol}
                      </text>
                    </g>
                  );
                });
              })()}

              {compiled.nfa.states.map((s) => {
                const p = layout.pos[s.id];
                const isActive = active.has(s.id);
                const isAccept = s.id === compiled.nfa!.accept;
                return (
                  <g key={s.id}>
                    <circle
                      cx={p.x}
                      cy={p.y}
                      r={NODE_R}
                      fill={isActive ? '#7cf29c' : '#0e1113'}
                      stroke={isActive ? '#7cf29c' : '#4a4f56'}
                      strokeWidth={1.5}
                    />
                    {isAccept && (
                      <circle
                        cx={p.x}
                        cy={p.y}
                        r={NODE_R - 4}
                        fill="none"
                        stroke={isActive ? '#0b0d0f' : '#4a4f56'}
                        strokeWidth={1.5}
                      />
                    )}
                    <text
                      x={p.x}
                      y={p.y}
                      textAnchor="middle"
                      dominantBaseline="central"
                      fontSize={11}
                      fontFamily="var(--mono)"
                      fill={isActive ? '#0b0d0f' : '#8a8f98'}
                    >
                      {s.id}
                    </text>
                  </g>
                );
              })}
            </svg>
          </div>

          <div className="tester">
            <div className="field">
              <label htmlFor="rv-test">test string</label>
              <input
                id="rv-test"
                type="text"
                value={testInput}
                maxLength={40}
                spellCheck={false}
                onChange={(e) => setTestInput(e.target.value)}
              />
            </div>
            <span className={`result ${isMatch ? 'match' : 'no-match'}`}>
              {isMatch ? 'match' : 'no match'}
            </span>
          </div>

          <p className="hint">
            Nodes lit up green are the states currently reachable after
            consuming the test string so far — the double circle is the accept
            state. Dashed gray edges are epsilon (ε) transitions, free moves the
            engine takes without consuming input.
          </p>
        </>
      )}

      <style>{`
        .regex-visualizer {
          border: 1px solid #2a2d31;
          background: #0e1113;
          padding: 1rem;
        }
        .regex-visualizer .field {
          display: flex;
          align-items: center;
          gap: 0.6rem;
          flex-wrap: wrap;
        }
        .regex-visualizer .field label {
          color: var(--muted);
          font-size: 0.75rem;
          text-transform: uppercase;
          letter-spacing: 0.04em;
          width: 5.5rem;
          flex-shrink: 0;
        }
        .regex-visualizer input[type='text'] {
          font-family: var(--mono);
          font-size: 0.9rem;
          color: #e6e6e6;
          background: #000;
          border: 1px solid #2a2d31;
          padding: 0.35rem 0.6rem;
          flex: 1;
          min-width: 8rem;
        }
        .regex-visualizer input[type='text']:focus {
          outline: none;
          border-color: var(--accent);
        }
        .regex-visualizer .presets {
          display: flex;
          gap: 0.4rem;
          flex-wrap: wrap;
          margin: 0.6rem 0 0 calc(5.5rem + 0.6rem);
        }
        .regex-visualizer .presets button {
          font-family: var(--mono);
          font-size: 0.75rem;
          color: #8a8f98;
          background: rgba(0, 0, 0, 0.4);
          border: 1px solid #2a2d31;
          padding: 0.2rem 0.5rem;
          cursor: pointer;
        }
        .regex-visualizer .presets button:hover {
          color: #e6e6e6;
        }
        .regex-visualizer .presets button.active {
          color: #0b0d0f;
          background: var(--accent);
          border-color: var(--accent);
        }
        .regex-visualizer .error {
          color: #e58a8a;
          font-size: 0.8rem;
          margin: 0.75rem 0 0;
        }
        .regex-visualizer .graph-scroll {
          overflow-x: auto;
          margin-top: 1rem;
          border: 1px solid #2a2d31;
          background: #000;
        }
        .regex-visualizer .tester {
          display: flex;
          align-items: center;
          gap: 0.75rem;
          flex-wrap: wrap;
          margin-top: 1rem;
        }
        .regex-visualizer .tester .field {
          flex: 1;
          min-width: 12rem;
        }
        .regex-visualizer .result {
          font-size: 0.8rem;
          padding: 0.3rem 0.6rem;
          border: 1px solid #2a2d31;
        }
        .regex-visualizer .result.match {
          color: #0b0d0f;
          background: var(--accent);
          border-color: var(--accent);
        }
        .regex-visualizer .result.no-match {
          color: var(--muted);
        }
        .regex-visualizer .hint {
          color: var(--muted);
          font-size: 0.75rem;
          margin: 0.75rem 0 0;
          max-width: 60ch;
        }
      `}</style>
    </div>
  );
}