Lexical
Analysis

Lexing is the most mathematically settled phase of a compiler — it rests on the theory of regular languages, which gives us a mechanical path from a specification to fast code. This deck walks that path, then the messy reality of real languages.

The lexer (scanner) is the first phase. It reads the source as a flat stream of characters and groups them into tokens — the atomic words of the language — which it hands, one at a time, to the parser.

The parser is the lexer’s only client. It typically pulls tokens on demand — calling getNextToken() each time it needs to advance — rather than the lexer running to completion and materialising a whole array first.

In principle the parser could read characters directly. In practice every serious compiler splits lexing off. The reasons are simplicity, speed and modularity — and a clean theoretical boundary.

Three terms that are easy to conflate. A pattern describes a set of strings; a lexeme is one concrete string from the source that matches it; a token is the classified result the lexer emits.

A token is more than its type: it carries an attribute (the lexeme, or an interned id, or a parsed numeric value) and a source location for diagnostics.

struct Token {
    kind:  TokenKind,   // IDENT, NUMBER, PLUS, LPAREN, KW_IF, ...
    value: Attribute,   // interned symbol id, parsed integer, string contents
    span:  Span,        // { file, byte_start, byte_end, line, column }
}

The lexer flattens the rich source text into a thin stream. Most whitespace and comments are discarded — they exist for humans, not the grammar — though not always (see right).

  int  total = price * qty;   // running cost

Token patterns are written as regular expressions. A regular expression denotes a regular language — a set of strings — built from just three operators over an alphabet Σ.

digit   = [0-9]
letter  = [a-zA-Z_]
ident   = letter (letter | digit)*
int     = digit+
float   = digit+ "." digit+ ([eE][+-]?digit+)?
ws      = (" " | "\t" | "\n")+

Limits: a regular language cannot count unboundedly — aⁿbⁿ and balanced parentheses are not regular. That is precisely the work the parser will do.

A finite automaton is the machine that recognises a regular language: a finite set of states, a start state, accepting states, and a transition function on input symbols. Two flavours, equivalent in power.

Ken Thompson’s 1968 algorithm builds an NFA from a regex compositionally — one small fragment per operator, glued with ε-transitions. Each fragment has exactly one start and one accept state.

The result is an NFA with at most 2× the number of regex symbols in states — linear size, built in linear time. The ε-transitions encode “choose a branch” and “loop or exit” without committing.

The textbook example. We want all strings over {a,b} ending in abb. Here is a compact NFA — the (a|b)* loop on the start state, then a three-step tail a b b.

State 0 is non-deterministic on input a: both the self-loop and the edge to state 1 are valid. A real run must explore both possibilities — which is exactly what the subset construction makes deterministic.

To run an NFA efficiently we make it deterministic. The subset (powerset) construction builds a DFA whose each state is a set of NFA states — “all the places the NFA could currently be”.

Worst case the DFA has 2ᵛ states (exponential blow-up), but for real token sets it is almost always small. This NFA has no ε-moves, so closures are trivial here.

Running the construction on the (a|b)*abb NFA. Each row is a DFA state (a subset of {0,1,2,3}); we tabulate where a and b lead, discovering new subsets until closed.

The subset construction can leave redundant states — states indistinguishable by any input. Minimisation merges them to give the unique smallest DFA for the language.

Putting the theory together: a token specification is a list of regexes, and a fully mechanical pipeline turns it into a fast scanner. This is exactly what lex and flex do at build time.

An alternative is the derivatives of regular expressions (Brzozowski) approach, which builds the DFA directly from the regex without an explicit NFA — used by tools like re2c.

A DFA tells us whether a string matches a pattern. A scanner must also decide where one token ends when many patterns and lengths are possible. Two rules resolve this.

Backing up to the last accepting state is a form of lookahead — the scanner reads past the token to know where it ends, then rewinds. A few languages need more, or made it infamously hard.

DO 5 I = 1,10    ! loop: DO-statement
DO 5 I = 1.10    ! assign DO5I = 1.10

Two roads. Generate a table-driven DFA from a spec, or hand-write a state machine as a big switch. Production compilers split surprisingly evenly — many hand-write for speed and control.

// Hand-written scanner core — the dispatch loop
fn next_token(&mut self) -> Token {
    self.skip_trivia();                       // whitespace + comments
    let start = self.pos;
    let c = self.bump();                      // consume one char
    let kind = match c {
        c if is_id_start(c) => self.ident_or_keyword(start),  // maximal munch
        '0'..='9'          => self.number(start),
        '"'                => self.string_literal(start),
        '+' => if self.eat('=') { PlusEq } else { Plus },     // 1-char lookahead
        '=' => if self.eat('=') { EqEq }   else { Assign },
        '\0' => Eof,
        _   => self.error("unexpected character"),
    };
    Token { kind, span: Span::new(start, self.pos) }
}

A generated scanner is a tiny driver loop over a 2-D transition table next[state][char], plus an accept[state] map saying which token a final state emits.

/* The universal table-driven DFA driver */
int next_token(void) {
    int state = START, last_accept = -1, last_pos = pos;
    while (state != DEAD) {
        int c = input[pos];
        int ns = next[state][c];   /* table lookup */
        if (ns == DEAD) break;
        state = ns; pos++;
        if (accept[state]) {       /* remember longest match */
            last_accept = accept[state];
            last_pos = pos;
        }
    }
    pos = last_pos;                /* back up to last accept */
    return last_accept;            /* the token kind, or error */
}

%%
[ \t\n]+        ;            /* skip ws */
"if"            return KW_IF;
[a-z]+          return IDENT;
[0-9]+          return INT;
"=="            return EQ;
.               return yytext[0];
%%

Encoding every keyword as its own DFA path bloats the automaton. The standard trick: recognise any identifier, then look the lexeme up in a keyword table and reclassify if it hits.

fn ident_or_keyword(&self, s: &str) -> TokenKind {
    // one identifier rule in the DFA; keywords are
    // a post-lookup, not separate automaton paths
    match s {
        "if"    => KW_IF,
        "else"  => KW_ELSE,
        "while" => KW_WHILE,
        "return"=> KW_RETURN,
        _       => IDENT,   // interned symbol id
    }
}

Literals carry the most lexical complexity. The lexer both recognises them and decodes their value into the token attribute — parsing 0xFF to the integer 255, resolving escapes in strings.

r"C:\path\no\escapes"      // raw
r#"he said "hi""#          // raw w/ quotes
"""triple
quoted"""                  // multiline

Before any of the theory runs, the lexer must read bytes correctly and feed itself characters efficiently. Two classic concerns: what a character is, and how to buffer the stream.

Every token carries a source span so later phases can point at the exact characters in a diagnostic. The lexer is also the first place errors surface — and it must keep going.

error: unterminated string literal
  --> main.rs:4:13
   |
 4 |   let s = "oops;
   |           ^ unterminated

Python, Haskell and friends use indentation for block structure — but indentation is not regular (it needs to count nesting). The fix: a small stack in the lexer that synthesises INDENT/DEDENT tokens.

if x:
    a = 1
    if y:
        b = 2
    c = 3

KW_IF IDENT COLON NEWLINE
INDENT IDENT = INT NEWLINE
KW_IF IDENT COLON NEWLINE
  INDENT IDENT = INT NEWLINE
  DEDENT
IDENT = INT NEWLINE
DEDENT

C’s grammar is ambiguous without knowing whether an identifier is a type name or an ordinary variable — and the lexer cannot know that from the characters alone. The token depends on the symbol table.

typedef int T;

T  * x;     // declaration: pointer-to-T named x
y  * z;     // expression:  multiply y by z

Two more places where a pure regular lexer breaks down because the structure is recursive — needing a stack or mode switching the bare DFA cannot provide.

`sum = ${a + f(b)} done`

/* outer /* inner */ still comment */

The pattern is the same each time: when the lexical structure becomes recursive, the lexer keeps a tiny piece of explicit state (stack or counter) outside the DFA — a controlled, pragmatic exception to “tokens are regular”.