From characters to words

Open a .wahoo file in a hex editor and the illusion disappears: there are no lines, no keywords, no indentation, only a sequence of bytes, one of which happens to be the newline character. When we read coin lives = 3 we see four words at a glance. A compiler has to discover them, and the part of it that does so is the lexer (also called scanner or tokenizer).

Its job is modest: walk the characters from left to right, group them into the smallest units that mean something, label each unit, and throw away what does not matter to the language (spaces, comments). Everything later in the compiler works on that list of labelled units instead of on raw text, which makes it much simpler.

§Tokens, lexemes and classes

Wahoo has five classes of token:

• Keywords, 18 reserved words: world pipe coin power_up damage by question else bounce run from to flag star goomba and or not.
• Names: a letter or underscore followed by letters, digits or underscores (lives, is_prime, _tmp). Type names such as coins are ordinary names; the checker, not the lexer, knows they denote types.
• Numbers: decimal digits, with optional underscores for readability (1_000), up to 2147483647.
• Text: characters between double quotes, with the escapes \n \t \" \\.
• Symbols: ( ) { } , : -> = + - * / % == != < <= > >=.

§Regular expressions and finite automata

Each token class can be described by a regular expression, a pattern built from single characters with three operations: concatenation (one thing then another), alternation (|, one thing or another) and repetition (*, zero or more times):

name    = [A-Za-z_] [A-Za-z0-9_]*
number  = [0-9] [0-9_]*
text    = " ( [^"\\\n] | \\ . )* "
le      = < =

In 1951 Stephen Kleene, studying what McCulloch and Pitts's model of neurons could recognise, proved that the languages described by regular expressions are exactly those recognised by finite automata: machines with a fixed, finite set of states that read one character at a time and move from state to state. There is no memory beyond the current state, which is precisely why a lexer can be so fast: one table lookup per character. (Its limits too: a finite automaton cannot check that parentheses are balanced, which is why structure is left to the parser. The sister site Math of AI has interactive automata and the pumping lemma that proves it.)

That “mechanically” is what made lexer generators possible. Ken Thompson's 1968 construction turns a regular expression into a nondeterministic automaton with a handful of states per symbol; the subset construction turns that into a deterministic one; and a table-driven loop runs it. In 1975 Mike Lesk and Eric Schmidt (then an intern at Bell Labs, later CEO of Google) wrote Lex, which takes a list of regular expressions with actions and generates the C code for a complete lexer. Its descendant Flex is still in use.

§Longest match wins

Regular expressions alone leave ambiguities. Is <= one token or < followed by =? Is power_up a keyword, or the name power followed by _up? Lexers resolve them with two rules:

1. Maximal munch: at each position, take the longest lexeme that matches any class. So <= is a single token and coins is the name coins, not the keyword coin plus an s.
2. Priority: if two classes match the same longest lexeme, the earlier one wins. Wahoo scans every word as a name and then looks it up in the keyword table, which amounts to “keywords before names”.

Wahoo's lexer is written by hand, like those of Clang, rustc, Go and V8: a hand-written scanner is easy to make fast and makes it easy to give good error messages. Here is how it handles the symbols that can be one or two characters long; it peeks at the next character before deciding:

let kind = match (c, next) {
    ('-', Some('>')) => two(self, TokenKind::Arrow),   // ->
    ('=', Some('=')) => two(self, TokenKind::EqEq),    // ==
    ('<', Some('=')) => two(self, TokenKind::Le),      // <=
    ('<', _) => TokenKind::Lt,                         // <
    ('=', _) => TokenKind::Assign,                     // =
    // ...
    _ => { self.error(Kind::UnexpectedChar(c), start); return; }
};

§When line breaks matter

Most languages treat a newline as just more white space. Some do not. Python's lexer emits INDENT and DEDENT tokens when indentation changes, so the parser sees blocks as if they had braces. Go's lexer inserts a semicolon at the end of a line that ends with a name, a literal or a closing bracket. JavaScript's parser inserts missing semicolons too, with a famous trap: a return followed by a line break returns undefined, whatever comes on the next line.

Wahoo takes a lighter approach: every token carries a flag saying whether it is the first one on its line. The parser uses it in exactly two places. A flag only takes a value from the same line, so

flag
wahoo("done")

is a flag with no value followed by a print, not a flag returning the result of the print. And a name followed by ( is only a call when both are on the same line.

§Lexical errors

Few things can go wrong at this level: a character that belongs to no token (@, ;), a text that never closes, an escape the language does not know, a number too big for 32 bits, digits glued to letters (3lives). The interesting decision is what to do next. Stopping at the first error is simple but frustrating, so Wahoo's lexer reports the problem, skips the offending character and carries on, so that one stray character does not hide everything after it. It also knows a few habits from other languages and turns them into hints: a ! suggests not, a ; explains that statements end at the line break, a single quote that texts use double quotes.

error[E001]: unexpected character `!`
 --> game.wahoo:3:12
  |
3 |   question !alive {
  |            ^ Toad can't read this
  = hint: negation is written `not`

With the characters grouped into words, the compiler can start asking how the words fit together. That is the parser's job.

§References

1. S. C. Kleene (1956). “Representation of Events in Nerve Nets and Finite Automata”. In Automata Studies, Princeton University Press (first circulated as a RAND report in 1951).
2. R. McNaughton and H. Yamada (1960). “Regular Expressions and State Graphs for Automata”. IRE Transactions on Electronic Computers, EC-9(1).
3. K. Thompson (1968). “Regular Expression Search Algorithm”. Communications of the ACM, 11(6).
4. M. E. Lesk and E. Schmidt (1975). Lex — A Lexical Analyzer Generator. Bell Laboratories Computing Science Technical Report 39.
5. A. V. Aho, M. S. Lam, R. Sethi and J. D. Ullman (2006). Compilers: Principles, Techniques, and Tools, 2nd ed., chapter 3. Addison-Wesley.