Lexical Analysis: Source to Tokens

Raw source is just a byte stream. The lexer (scanner) converts it into a flat sequence of tokens, each carrying a kind and a lexeme (the raw text). Separating lexing from parsing is a classic compiler decision: the grammar for tokens is regular (finite automata suffice), while the grammar for programs is context-free (needs a stack). Keeping the phases separate makes both simpler.

A typical token stream for x = 1 + 2;:

IDENT("x")  ASSIGN  INT(1)  PLUS  INT(2)  SEMI

Each token carries its kind, its literal text, and usually source coordinates (file, line, column) for error messages. The parser never looks at raw characters — only at this stream.

Multiple lexemes can belong to the same token kind: "hello" and "world" are both STRING_LITERAL. Conversely, the same byte sequence can be a different token in different contexts — >>= is a single SHIFT_ASSIGN token in C, not three separate tokens. The lexer must commit to one reading.

Whitespace and comments are usually consumed and discarded by the lexer, so the parser never sees them — though some languages (Python, Haskell) generate INDENT/DEDENT tokens from whitespace.

Each token kind is described by a regular expression. The lexer spec is an ordered list of (regex, action) pairs:

[0-9]+          -> INT_LITERAL
[a-zA-Z_][\w]*  -> IDENT_OR_KEYWORD
"=="            -> EQ
"="             -> ASSIGN
[ \t\n]+        -> skip

Keywords (if, while, return) are handled by classifying identifiers after matching: every [a-zA-Z_][\w]* match goes through a keyword table lookup. This avoids enumerating each keyword as a separate regex — and prevents iffy from being lexed as if + fy.

Order matters: == must appear before =, or the = rule fires first and you get EQ_EQ wrong. Real lexer generators (Flex, re2c) sort by priority rules you declare.

Regular expressions are compiled to NFAs (Non-deterministic Finite Automata) via Thompson's construction, then subset-constructed into a DFA (Deterministic FA) that the scanner runs in $O(n)$ time over the input.

• An NFA can have $\varepsilon$-transitions and multiple edges on the same character — it's easy to build from a regex but nondeterministic to run.
• A DFA has exactly one transition per (state, character) pair — trivial to execute as a table lookup.
• The subset construction can blow up: an NFA with $n$ states yields a DFA with up to $2^n$ states, but in practice the lexer DFAs for real languages have hundreds of states, not millions.

Tools like Flex generate this DFA automatically and emit a C switch-or-table scanner. Hand-written scanners (Clang's) skip the automaton and do the DFA implicitly in code.

The transformation chain from regex specs to a running scanner:

When multiple rules could match at the current position, the lexer uses maximal munch: always take the longest possible match. This is why ++ is a single INC token rather than two PLUS tokens — the lexer greedily extends the match as far as the DFA can go before it falls out of an accepting state.

Edge cases the rule creates:

• --> in C: parsed as -- > (decrement then greater-than) because --> is not a C token. Maximal munch wins for --, then > is separate.
• x = a+++b: a++ + b or a + ++b? C standard says maximal munch: a++ + b.
• Raw string literals in C++ (R"(...)") require special-case handing because (...) can be any delimiter — impossible to describe with a plain DFA.

A toy scanner to make this concrete:

import re

TOKEN_SPEC = [
    ('INT',    r'\d+'),
    ('IDENT',  r'[A-Za-z_]\w*'),
    ('ASSIGN', r'='),
    ('PLUS',   r'\+'),
    ('SEMI',   r';'),
    ('SKIP',   r'[ \t\n]+'),
]
_RE = re.compile('|'.join(f'(?P<{name}>{pat})'
                          for name, pat in TOKEN_SPEC))
KEYWORDS = {'if', 'else', 'while', 'return'}

def tokenize(src: str):
    for m in _RE.finditer(src):
        kind = m.lastgroup
        if kind == 'SKIP':
            continue
        lexeme = m.group()
        if kind == 'IDENT' and lexeme in KEYWORDS:
            kind = lexeme.upper()   # IDENT -> IF, WHILE, etc.
        yield kind, lexeme

list(tokenize('x = 1 + 2;'))
# => [('IDENT','x'),('ASSIGN','='),('INT','1'),
#     ('PLUS','+'),('INT','2'),('SEMI',';')]

Python's re.finditer with alternation already implements longest match via POSIX leftmost-longest semantics — effectively simulating a DFA scan.

Things that make production lexers harder than the textbook:

• Multiline strings / nested comments. Most regexes are not powerful enough for nested constructs (/* /* */ */). Lexers track depth with a counter — a stateful extension outside pure regular languages.
• Unicode identifiers. Modern languages (Python 3, Rust, Swift) allow Unicode letters. The DFA table explodes unless you use Unicode category properties (\p{L}) and a sparse table representation.
• Context-sensitive lexing. Some grammars require lexer modes or scanner states (flex %x). Example: Python's f-strings switch between string mode and expression mode and back.
• Error recovery. A professional lexer doesn't just crash on @#!. It emits an ERROR token and resumes, giving the parser a chance to report something useful.
• Speed. Clang's hand-rolled lexer outperforms Flex-generated scanners partly because it can short-circuit — e.g., isIdentStart[c] as a 256-entry bool table before touching any state machine.

The lexer acts as a lazy iterator: the parser calls next_token() on demand, so the entire source is never tokenized upfront. This matters for large files and streaming inputs.

The token stream is deliberately impoverished: no nesting, no tree structure. It is just a linear sequence. But that's the contract — the parser's job is to impose structure. The lexer's only obligation is to give it a clean, classified stream with no whitespace noise.

Here's the interface boundary in a simple C compiler:

typedef struct {
    TokenKind kind;
    const char *start;  /* pointer into source buffer */
    int len;
    int line;
} Token;

Token next_token(Lexer *lex);  /* called by parser */

Knowing where lexing ends and parsing begins is not just pedagogy — it tells you exactly which bugs belong to which phase when something goes wrong.