ENTER: edit the pattern → edit the input → done editing: A–Z 0–9 ( ) [ ] \: * + ? . ^ - append (← deletes) P: next preset pattern + input SPACE: run the simulation from the start, one character per beat S: single step F: run to the end instantly V: re-derive the verdict for all ten presets and show the tally ↑ / ↓: animation speed Supported syntax: literals, ., *, +, ?, |, (...) groups, and character classes [ABC], [A-Z], [^AEIOU]. Matching is a full match — the accept state has to be live once the whole input is consumed, not merely reachable somewhere along the way. White states are live. Bright edges consume a character and carry its label; dim edges are epsilon. The ringed state accepts. The readout under the diagram shows the postfix form, the syntax tree in prefix notation, and the **peak number of simultaneously active states** — which is the whole difference between an NFA and a DFA, arriving as a number.
A regular expression engine you can watch run: type a pattern, see it parsed into a syntax tree, compiled to an NFA by Thompson's construction, drawn as a state machine, and then simulated one character at a time with the live states lit up. THE INTERESTING DECISION: ONE INVARIANT, USED THREE TIMES Syntax tree nodes are created in postfix order, so **a parent always has a higher index than its children.** Everything downstream is then a single forward loop over the node array: * Thompson's construction — when the loop reaches a node, both children's NFA fragments already exist. No fragment stack, no patch lists, no recursion. Every fragment has exactly one entry and one exit state, and its exit always has zero outgoing edges when created, which is why composition can just add edges to it and never needs a dangling-pointer list. * The diagram layout — computed during construction. Each node records its fragment's contiguous state index range, so composing two fragments is a translate of one index range. That is what makes the picture structured: concatenation runs left to right, alternation stacks vertically, repetition is bracketed by a split and a join. Laying out a Thompson NFA after the fact, from the edge list alone, gives spaghetti. * The printed syntax tree — each node's string built from its children's. This matters because goboscript local variables are undefined behaviour inside a recursive procedure, so a recursive-descent parser would have to keep every local in a ply-indexed list. Shunting-yard plus the index invariant means nothing here recurses at all. The NFA is stored as a flat edge list, not per-state transition slots. Simulation is then one pass over the edges per input character no matter how many states are live, and the epsilon closure is a fixed-point iteration over the same list. That closure is what makes (A) terminate rather than loop forever, and what keeps the match linear in the input instead of exponential — the failure mode that makes backtracking engines hang on (a)b. VERIFICATION V runs all ten presets through this engine and compares each verdict against a table generated by Python's own re.fullmatch. Result: 10/10, including the deliberately non-matching /A(B|C)*D/ vs ABCX. The compiled .sb3 was also run under the headless harness and its internal state dumped. For /A(B|C)*D/: postfix ABC|&D&, syntax tree &(&(A,*(|(B,C))),D) * 12 states, 14 edges — exactly what Thompson's construction predicts (2 per literal × 3, +2 for the alternation, +2 for the star, +2 for D) * peak 7 simultaneously active states over ABCBCD, and the accept state live at the end The banner tool is a second, independent implementation of the same pipeline in Python; it reports 12 states, 14 edges and 7 live states after ABCBC, which agrees with the project state dump node for node. HONEST LIMITATIONS * Uppercase only, and literal matching is therefore case-insensitive: Scratch's = cannot distinguish "a" from "A", and key_pressed cannot report shift state. No escapes (\., \), no anchors (^ outside a class, $), no {m,n} counted repetition, no capture groups or backreferences, no shorthand classes (\d, \w). Groups are grouping only. No leftmost-longest search — it is a full match. Wrap the pattern in ....* to get search behaviour. * Pattern capped at 26 characters and input at 44, mostly so the diagram stays legible. All original - code, art and sound. See Inside is open.
