Lesson 22 · Compiling plus and quest

Compiling plus and quest

`+` and `?` are the star's siblings - the same Split, just placed differently. Plus loops after the element; quest forks before it with no loop.

The goal

Compile `x+` and `x?` using a Split placed after the element (plus) or before it (quest).

Start here - the target

TO DO

Scenario: Plus and quest compile to a single Split

Giventhe AST for "a+"

Whenit is compiled into an NFA

Thenthe start is the Char 'a' state, whose out leads to a Split that loops back to 'a' or exits

Andfor "a?", the start is a Split that either enters the Char state or skips straight to the exit, with no loop

Background

Once star clicks, + and ? are small variations on where the Split sits. For a+ (one or more), the machine must run through a first, so the fragment starts at the a state; its exit leads into a Split that either loops back to a or moves on. That guarantees at least one match before the loop is even reachable. For a? (zero or one), a Split sits before a with no loop at all: one branch enters a, the other skips it, and both paths lead to the exit.

Seeing all three quantifiers as placements of one Split is the satisfying payoff of Thompson construction - a tiny, uniform toolkit builds every repetition. Your NFA compiler can now handle the same core syntax the backtracker did. What it can’t do yet is actually run: you have graphs but no way to feed input through them. The next two lessons build that simulator, starting with the trick that tames all these Split forks.

Make it work

// plus: enter a first, THEN a Split that loops or exits
s := &State{Kind: Split, Out: a.start}
patch(a.out, s)
return Frag{start: a.start, out: []**State{&s.Out1}}
// quest: a Split before a; both a's exit and the skip arrow dangle

CheckpointDONE

`+` and `?` compile to a single Split, completing the quantifiers in the NFA. Commit and stop here.