Where automata earn their keep
Every compiler starts with a lexer, and tools like lex and flex generate lexers from a list of patterns: one regex per kind of token. Under the hood they do what you've built this week — compile each pattern to an automaton and run it over the source. Today you'll write that lexer generator: give it rules, get tokens.
tokenizeWith([
{ type: "let", pattern: "let" },
{ type: "ident", pattern: "[a-z][a-z0-9]*" },
{ type: "number", pattern: "[0-9][0-9]*" },
{ type: "op", pattern: "=|==|;" },
{ type: "skip", pattern: " *" },
], "let letter == 42;")The longest prefix
A regex matcher answers "does the whole string match?" A lexer asks something different: "how much of the input, starting here, matches?" Run the NFA from position from, and after each symbol check whether the current set contains an accept state; if so, remember that position. Stop when the set becomes empty. The last remembered position is the end of the longest match.
- Before reading anything: if the start closure is accepting, the empty match ends at from.
- After each symbol i: if accepting, best = i + 1.
- When no states are left, no longer match is possible — stop early.
- Return -1 if nothing ever accepted.
Stopping early when the set is empty is what keeps lexing fast: each rule usually dies after a few characters.