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 every finite state machine has a regular expression. Kleene, 1956.
The machine reads one character at a time and remembers only which circle it is in. Start on a digit, then loop on digits, accepting all the while. No stack, no counter, no memory of what came before.
And the machine decides: for every finite input it stops and says yes or no. Everything the scanner does 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: if the character is '0', it is the literal 0 and we are done. Otherwise allocate a string, store digits while there are digits, terminate with a NULL, convert with atoi, and set the symbol to SYM_INTEGER.
On the right, what it leaves behind: the characters '8' and '5' on the heap, the value 85 in the global literal, and the symbol in symbol. The parser reads those three globals and never sees a character.
The while loop is the self-loop of the machine. 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 so far by ten and add it. Leftmost digit first, so 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. The scanner must.
Notation to meaning, in a loop: the string is syntax, the value is what it denotes, and this procedure is the semantics of integer literals.
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.