Lexical Analysis

Definition: The first phase of a compiler, the Lexer or Scanner, that converts a raw stream of source code characters into a sequence of meaningful Tokens.

How It Works

Lexer specifications are written as regular expressions per token class, then compiled into an NFA (Thompson’s Construction) and determinized into a DFA (subset construction), so recognition runs in O(n) time with no backtracking
Reads the character stream and groups it into lexemes; Maximal Munch (longest-match) resolves ambiguity by always consuming the longest string that matches a valid token, so <= lexes as one LE token, not < followed by =
Outputs tokens containing a token type, the value/lexeme, line number, and column position (e.g. KEYWORD_IF, IDENTIFIER_x, OPERATOR_ASSIGN), which downstream phases use for error messages
Strips comments and insignificant whitespace, but must still track newlines for line-numbered diagnostics and for whitespace-sensitive languages (Python, Haskell) where indentation itself becomes a token
Keyword recognition is usually just identifier lexing followed by a reserved-word hash table lookup, rather than a separate grammar rule, since if/while/for are lexically identical to identifiers until checked against the table
Lexer generator tools (Lex/Flex, ANTLR, re2c) take the regex table as input and emit the DFA-driven scanning code automatically, so hand-written lexers are relatively rare in production compilers
Some languages need lookahead beyond the current character to disambiguate a token, for example distinguishing a numeric literal’s decimal point from a following method call, which the DFA handles by continuing to consume characters as long as a longer match is still possible
Error recovery at the lexer level typically means skipping the invalid character and reporting “unexpected character,” then resuming scanning, rather than aborting the whole compile on the first bad byte
Thompson’s Construction builds an NFA from a regex by composing small NFA fragments per operator (concatenation, alternation |, Kleene star *); subset construction then merges the NFA’s parallel possible states into single DFA states, trading a larger state count for the guarantee that each input character triggers exactly one transition
Real lexers combine every token’s regex into one big DFA rather than running separate DFAs per token type, so a single left-to-right scan over the input decides which token rule wins at each position via maximal munch
Lexer generators typically minimize the resulting DFA (merging equivalent states) to keep the generated table small enough to fit comfortably in cache, since the table is walked on every single character of every file compiled

Under the Hood

Given: the lexer is scanning the source text x1 <= 5.5;. Step 1: x starts an identifier; the DFA stays in InIdent while it sees 1, since digits are valid after the first letter, and emits IDENT:x1 once it hits the space. Step 2: < moves to SawLess; the next character = completes a maximal-munch match, emitting OPERATOR:LE (<=) as one token instead of LT then ASSIGN. Step 3: 5.5 starts in InNumber, transitions to InFloat at the ., and emits NUMBER:5.5 at the semicolon. Step 4: ; matches a single-character token rule and emits SEMICOLON. Answer: the token stream is [IDENT:x1, LE, NUMBER:5.5, SEMICOLON], four tokens from eleven characters.

Given: lexing int x = 5;.

input:  int  x  =  5 ;
DFA:    i-n-t -> matches IDENTIFIER pattern, then keyword table hit -> TYPE
        x     -> matches IDENTIFIER, not in keyword table -> IDENTIFIER
        =     -> matches ASSIGN (not `==`, since next char isn't `=`)
        5     -> matches INT_LITERAL
        ;     -> matches SEMICOLON

Answer: [TYPE:int, IDENT:x, ASSIGN:=, INT:5, SEMICOLON:;], five tokens.

Given: a Python source line total = total + 1 follows a line at zero indentation. Step 1: the tokenizer measures leading whitespace (4 spaces) before scanning the rest of the line as normal tokens. Step 2: since the indentation increased from the previous logical line, the tokenizer emits a synthetic INDENT token before IDENT:total. Answer: the token stream begins [INDENT, IDENT:total, ASSIGN, IDENT:total, PLUS, INT:1, NEWLINE], turning whitespace structure into ordinary tokens a normal parser can consume.

Why It Matters

Simplifies parser implementation by turning an arbitrary raw character stream into a structured, finite token sequence the parser can reason about with lookahead, instead of re-deriving token boundaries from characters at every grammar rule
Runs in a single linear pass, so pushing work into the lexer rather than the parser keeps overall compile time closer to O(n) for that phase
Precise line/column tracking at this stage is what lets every later phase, parser, type checker, and code generator, report errors that point at the right place in the original source
A well-defined token boundary is a prerequisite for tooling beyond compilation: syntax highlighters, formatters, and IDE “go to definition” features all start from the same token stream a compiler’s lexer produces
Lexing throughput sets a hard floor on compile speed: no later phase can be faster than the rate at which characters are turned into tokens, since every subsequent phase operates on the token stream, not raw text

Common Pitfalls

Greedy/maximal-munch errors: lexing >> in C++ template code like vector<vector<int>> as a single right-shift operator instead of two closing angle brackets genuinely broke C++03 and required a parser-side fix in C++11
Context-sensitive lexing: C’s grammar requires the lexer to know whether an identifier was previously typedef’d, to disambiguate (A)(B) as a cast versus a function call, meaning the “pure” lexer/parser separation leaks in practice
Off-by-one line/column tracking when lexemes span multiple lines, such as multi-line string literals or block comments
Mishandling Unicode: treating source as raw bytes instead of decoded code points breaks identifiers or string literals containing multi-byte UTF-8 sequences
Forgetting that regex-based token definitions can themselves be ambiguous, for example a language allowing both 0x1F hex literals and an identifier starting with 0x... needs an explicit precedence rule for which pattern wins
Assuming lexing has no cost: pathological regex patterns compiled naively into backtracking engines (rather than a proper DFA) can make lexing quadratic or worse on adversarial input
Treating whitespace as always insignificant: languages with significant indentation need the lexer itself to track a stack of indentation levels, and getting that stack logic wrong produces confusing IndentationError-style failures far from their real cause
Not planning for incremental re-lexing: IDEs that re-lex an entire file on every keystroke waste work a proper incremental lexer avoids by re-scanning only the region actually edited

Comparison

Approach	Speed	Backtracking	Typical tool
Hand-written scanner	Fast, tunable	None if written carefully	Production compilers wanting full control (Clang, V8)
DFA-generated lexer	Fast, O(n)	None by construction	Flex, re2c
Regex-engine-based (backtracking)	Can be slow on pathological input	Yes	Quick scripting, not compiler-grade
Hand-rolled recursive lexer	Slower, simpler to write	Depends	Prototypes, small DSLs

Concept	Role
NFA (Thompson’s Construction)	Direct translation of a regex, may have multiple active states at once
DFA (subset construction)	Deterministic merge of the NFA, exactly one active state at a time
DFA minimization	Collapses equivalent states to shrink the transition table

Example

Clang’s lexer is entirely hand-written C++ for maximum control over diagnostics and performance, rather than generated from Flex, because production compilers need precise, context-aware error messages that generic lexer generators don’t produce well. It also reuses the same lexer for syntax highlighting, refactoring tools, and clang-format, which is only practical because lexing is cheap, deterministic, and independent of the rest of the compiler.

Python’s tokenizer emits synthetic INDENT/DEDENT tokens by tracking whitespace at the start of each logical line, turning its whitespace-sensitive layout into ordinary tokens the parser can consume like any other. Go takes a related but different approach: its lexer inserts semicolons automatically at the end of lines that look statement-complete, following a small set of rules, which is why Go source rarely needs explicit semicolons even though the language’s grammar is defined with them.

Given: a syntax highlighter in a code editor needs to color a 10,000-line file as the user types, on every keystroke. Step 1: a naive implementation re-lexes the entire file from scratch on every change, an O(n) operation per keystroke that becomes noticeably laggy on large files. Step 2: an incremental lexer instead re-scans starting from the edited region and stops as soon as it reaches a token stream that matches what was already cached beyond that point. Answer: incremental lexing turns an O(n)-per-keystroke cost into something close to O(1) for small, localized edits, which is why production editors and language servers invest specifically in incremental lexing rather than relying on a batch compiler’s lexer unmodified.

Referenced by

Dig deeper

Spot an error in this note?