Library

Collection · 20 machines · curated by @thethinkmachine

Formats and lexers

What a lexer or a form validator does, one machine at a time: identifiers, numbers, comments, string literals, clock times, IP octets, Roman numerals, keywords — and, one step up, the syntax of an expression.

Essay

2 min read

The first phase of every compiler, and every form that checks what was typed into it, is a finite automaton. A lexer reads characters and groups them into tokens — identifiers, numbers, strings, comments — and each kind of token is a regular language. Tools like lex and its descendants take the regular expressions, build an NFA by Thompson’s construction, determinise it, and emit the DFA as a table. The machines in this collection are those DFAs, one token or one format at a time.

Character classes

A real lexer reads bytes, but its DFA’s edges are almost always labelled with classes of bytes: any letter, any digit, anything but a quote. The machines here use one symbol per class — a for a letter, 0 or d for a digit — which keeps the diagrams readable without changing their shape. An identifier is the simplest: a letter or underscore, then letters, digits and underscores.

Numbers

A number in scientific notation is a chain of optional parts, each a fork in the DFA that rejoins the main path. A C integer literal shows a lexer committing on its first character: a leading 0 means octal, 0x hexadecimal, anything else decimal — which is why 08 is an error in C.

Escapes and nesting that is not nesting

A string literal needs one extra state: after a backslash, any character is ordinary. A C comment is the classic trap — after a *, a / ends the comment, but another * keeps the possibility open. Comments in C do not nest, so a finite automaton suffices; languages whose comments do nest need a counter, and their lexers are no longer finite automata.

Validating what people type

A 24-hour time, an ISO date, an IPv4 octet and a whole IPv4 address, Roman numerals — each is a small machine whose subtle states are the prefixes that constrain what may follow. A 2 at the start of an hour allows only 0–3 next; 25 at the start of an octet allows only 0–5. A date validator stops short of February 29th: knowing whether the 29th exists would mean tracking the month and the year mod 4 at once, which is still finite but no longer small.

Try this

In each machine, find the states with fewer outgoing edges than the others. Those are the places where the format constrains the next character — the whole specification, read off the diagram.

One step past regular

The syntax of an arithmetic expression is where lexing ends and parsing begins: parentheses nest to any depth, so the machine needs a stack. Lexers are finite automata because tokens do not nest; parsers are pushdown automata because programs do.

The machines

An identifier DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A number in scientific notation DFA · 8 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A C comment, /* … */ DFA · 5 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A string literal with escapes DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A keyword: if, in, int or for DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A 24-hour clock time, HH:MM DFA · 7 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A byte in decimal: 0 to 255 DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Roman numerals from I to MMMCMXCIX DFA · 19 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A phone number, area code optional ε-NFA · 14 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Within one typo of “cat” ε-NFA · 8 states Tested Added 8 Oct 2026Updated 8 Oct 2026 The syntax of an arithmetic expression DPDA · 4 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Well-formed UTF-8 DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Base64 length and padding DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A C integer literal: decimal, octal or hex DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A CSV record with quoted fields DFA · 4 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 An ISO date, YYYY-MM-DD DFA · 14 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A full IPv4 address DFA · 24 states Tested · Minimal · Deterministic Added 9 Oct 2026Updated 9 Oct 2026 An email address, roughly DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A hex colour: #rgb or #rrggbb DFA · 8 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A nested list: [x;[x;x];[]] DPDA · 6 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026