Regular languages, finite state machines, and characters into symbols — a finite machine deciding a countable set.
Which sequences of characters denote an integer literal? A regular expression in EBNF: integer = digit { digit } . That is the whole specification, and it is a piece of notation.
How does a machine check it? A finite state machine: circles, arrows labelled with characters, a start, and accepting states. The model is what the code will be measured against.
A C* procedure that walks the machine and, on the way, computes the value: 85 from the characters '8' and '5'. Efficient, and provably the same as the model.
The theme repeats for character literals, strings, identifiers, and then for every statement and expression in the language, just less explicitly. Learn it once here.
Substitute digit into integer and one rule remains: that is what regular means. Every regular expression has a finite state machine and vice versa. Kleene, 1956.
The machine reads one character at a time and remembers only which circle it is in. No stack, no counter, no memory of what came before.
And it decides: for every finite input it stops and says yes or no. The scanner is on the decidable side of Rice's line, because it is about the text and nothing else.
C forbids leading zeros in decimal literals. The first grammar allowed them. So the specification had a bug, found by the model — and fixed in the specification, not in the code.
Two accepting states now: one for the single zero, one for everything else. Still regular, still one machine.
This is the class in miniature: a mistake in notation is a mistake, and it is caught where notation is exact. Selfie's scanner implements this machine.
The digit branch of get_symbol: a '0' is the literal 0. Otherwise allocate a string, store digits while there are digits, terminate with a NULL, convert with atoi, set the symbol to SYM_INTEGER.
What it leaves behind: the characters on the heap, the value 85 in literal, the symbol in symbol. The parser reads those globals and never sees a character.
The while loop is the machine's self-loop; the if is the '0' branch. The code is the model, transcribed.
The character '5' is the byte 53. Subtract 48, the code of '0', and it is the digit 5. Multiply what you have by ten and add it: 8 becomes 80 becomes 85.
And check for wrap-around: a literal with twenty digits does not fit in 64 bits, and the machine will not tell you.
Notation to meaning, in a loop: the semantics of integer literals. Hexadecimal is the same loop with sixteen for ten: one hex digit is four bits, a constant factor shorter.
The language of all C* symbols is regular: gather them into one EBNF rule and substitute until only terminals remain. It terminates, so it is regular, so one finite state machine scans all of C*.
Almost every symbol begins with a unique character: a digit, a quote, a letter, a bracket. Only = and ==, < and <=, > and >=, != need to see one more character. That is a lookahead of one, and it is designed in, not found.
Which is why scanning is fast for the machine — and, not by accident, for the human reading the code.
Countable. The set of all C* symbol sequences is a set of finite strings: listable, numbered. The scanner is a decider for it, and a decider always answers.
Finite. The scanner has no memory but its state, so it cannot count. It cannot match parentheses, and it does not try. That is the parser's job, next week, and it is exactly the difference between a finite state machine and a machine with a stack.
Selfie's own source is 365,784 characters and 51,329 symbols, and it is scanned by the scanner it contains. That is a test with one very large input — and the introduction class said what one input shows. The grader adds a few hundred more. Neither shows absence.
Do not modify any files other than grammar.md and selfie.c. No compiler warnings. Submit by the deadline even if unfinished — a submission with self-grade 5 beats no submission.
Bach · The Well-Tempered Clavier, Book I — Sviatoslav Richter. Twenty-four keys, one prelude and one fugue each, in order: the alphabet of tonal music, scanned from C major to B minor with nothing skipped.
Introduction to the Theory of Computation — Sipser, chapter 1: regular languages, finite automata and the pumping lemma, done properly. And, more technical, Regular Expression Search Algorithm — Thompson, 1968: the construction that turns a regular expression into an automaton, four pages, still in use.