Lesson 21 · Compiling the star - Build a Regex Engine

Compiling the star

The star becomes a Split that loops. One arrow enters the element and comes back; the other skips past. This is the same fork as alternation, wired into a cycle.

The goal

Compile `x*` into a Split that either enters x (looping back) or skips ahead.

Start here - the target

TO DO

Scenario: Star compiles to a looping Split

Giventhe AST for "a*"

Whenit is compiled into an NFA

Thenthe start is a Split state whose first branch enters the Char 'a' state

Andthe 'a' state's out arrow loops back to that same Split, and the Split's second branch is the fragment's dangling exit

Background

Zero-or-more is a loop. The Split for a* has one arrow that enters the a state and one that bypasses it. Crucially, the a state’s exit is patched back to the Split - so after matching one a, the machine returns to the fork and can either go around again or leave. The bypass arrow (Out1) stays dangling as the fragment’s single exit. That’s the whole star: a fork where one prong is a cycle.

Because the machine can take the bypass immediately, a* correctly matches zero as; because the loop returns to the same Split, it matches any number. Notice there’s no backtracking here and no risk of exponential blowup - the loop is just an arrow in a graph. That structural difference from chapter two’s recursive star is exactly why the NFA will stay fast. Tomorrow, + and ? are the same Split with the loop arrow placed differently.

Make it work

// Split: one branch into a, one branch onward (the exit).
s := &State{Kind: Split, Out: a.start}
patch(a.out, s)           // a loops back to the Split
return Frag{start: s, out: []**State{&s.Out1}} // Out1 is the exit

CheckpointDONE

`*` compiles to a Split that loops through its element or skips it. Commit and stop here.