Lexical Analysis

Lexical analysis is where a compiler first makes sense of the raw character stream it's been given, grouping characters into the smallest meaningful units — tokens — that every later stage will work with instead of ever touching raw text again.

A lexer (or tokenizer/scanner) reads the raw stream of characters making up the source code and groups them into tokens — the smallest meaningful chunks, like keywords, identifiers, numeric or string literals, operators, and punctuation. It also typically discards things irrelevant to meaning, like whitespace and comments.

Working character-by-character is tedious and error-prone for every later stage of the compiler; converting the raw text into a clean, well-labeled stream of tokens lets the parser (the next stage) reason about the program's structure without ever having to worry about spacing, comment syntax, or exactly how a number or string was originally spelled out in the source file.

Every compiler and interpreter for every real programming language performs lexical analysis as one of its very first steps — it's also how syntax highlighting in code editors and IDEs works, since recognizing keywords, strings, and comments for coloring is fundamentally the same tokenizing problem.

Think of reading a sentence written with no spaces: "thecatsatonthemat". Before you can understand its grammar, you first have to split it back into words: "the", "cat", "sat", "on", "the", "mat". That word-splitting step — turning a stream of individual letters into a stream of meaningful words — is exactly what a lexer does to source code, splitting a stream of characters into meaningful tokens.

The lexer recognizes int as a reserved keyword, x as a user-defined identifier, = as an assignment operator, 10 as a numeric literal, and ; as a statement terminator — five tokens produced from eleven raw characters (including the space and semicolon), with the specific spacing used in the original source now discarded as irrelevant.

A lexer is typically implemented as (or generated from) a finite automaton — a set of states and transitions that can recognize each token type using simple, fast character-by-character scanning, without needing anything as powerful as full parsing to do its job.

Common token categories include keywords (reserved words with special meaning, like if or return — a language typically forbids using these as ordinary identifiers), identifiers (user-chosen names for variables, functions, types), literals (a directly written value, like 42, 3.14, or "hello"), operators (+, -, ==), and delimiters/punctuation ((, ), {, }, ;, ,).

Maximal munch (or "longest match") is the standard rule lexers use to resolve ambiguity: when multiple valid tokens could start at the current position, the lexer greedily consumes the longest one that still forms a valid token — this is why, for example, <= is scanned as one single token rather than as < followed separately by =.

Whitespace and comments are almost always discarded by the lexer rather than passed on to the parser, since they carry no meaning for the language's grammar (with some notable exceptions, like Python, where indentation is itself semantically meaningful and must be tokenized specially rather than simply discarded).

Assuming a lexer needs to understand a language's full grammar — it deliberately does not; recognizing valid tokens (is this a number, an identifier, an operator) requires far less power than parsing the overall structure those tokens form, which is exactly why the two are kept as separate stages.

Forgetting that keywords are just identifiers that happen to be reserved — a lexer typically first recognizes something as a general identifier pattern, then checks it against a fixed keyword list to decide whether to reclassify it as a specific keyword token instead.

Not handling the maximal-munch rule correctly when hand-writing a simple tokenizer, causing a token like <= to be incorrectly split into two separate tokens, < and =, breaking any code that uses that operator.

Underestimating how many edge cases real-world lexing involves — string escape sequences, different numeric literal formats (hex, octal, scientific notation), multi-line comments, and Unicode identifiers all add genuine complexity beyond the simple cases usually shown first.

Using a lexer-generator tool (like flex, or a hand-rolled but systematic state-machine-based scanner) rather than ad hoc string manipulation, when building a custom lexer, to correctly and efficiently handle the many edge cases real source code contains.

Reading a compiler's own tokenization error messages ("unexpected character", "unterminated string literal") as a strong signal that the problem is at the most basic, earliest textual level — often a stray character, unmatched quote, or unsupported symbol — rather than a deeper structural issue.

Building syntax highlighting or a simple linter's first pass around the same tokenizing logic a real compiler would use, since recognizing keywords, strings, comments, and identifiers is the same underlying problem.

Regular languages and finite automata The set of valid tokens in most programming languages can be described by regular expressions, and a lexer is essentially a direct implementation of the finite automaton (state machine) those regular expressions correspond to — this theoretical connection (regular languages, DFAs and NFAs) is precisely why lexer-generator tools like flex can take a set of regex-like token definitions and automatically produce an efficient scanner, rather than requiring one to be hand-written.

Lexer/parser interaction and lookahead Most lexers produce tokens lazily, one at a time, as the parser asks for them, rather than tokenizing the entire file upfront — and many parsing techniques need to "look ahead" at the next token (or several) before deciding how to interpret the current one, which is why a lexer typically supports peeking at upcoming tokens without permanently consuming them.

While lexing is usually described as context-free (each token is recognized independently of surrounding tokens), some real languages need context-sensitive lexing for particular constructs — Python's significant indentation requires tracking indentation levels and emitting synthetic INDENT/DEDENT tokens, and some languages' lexers must consult a symbol table mid-scan to disambiguate whether an identifier is a type name or a variable name (a classic problem in C's grammar, sometimes called the "lexer hack").

What is the difference between a lexer and a parser?

A lexer converts a raw stream of characters into a stream of tokens (the smallest meaningful units — keywords, identifiers, literals, operators). A parser then takes that stream of tokens and determines the program's overall grammatical structure, typically producing a tree like an AST.

What is "maximal munch", and why does it matter?

The rule that a lexer should always consume the longest possible valid token starting at the current position. It matters because without it, multi-character operators like <= or ++ could be ambiguously split into shorter, incorrect tokens like < and =.

How does a lexer decide whether a word like "if" is a keyword or an identifier?

It typically first recognizes the word using the same general pattern used for identifiers, then checks the resulting text against the language's fixed list of reserved keywords — if it matches, the lexer reclassifies the token as that specific keyword rather than a generic identifier.

Why are comments and whitespace usually discarded by the lexer rather than passed to the parser?

Because they carry no grammatical or semantic meaning in most languages — the parser only needs to reason about the tokens that actually determine the program's structure and behavior, so removing irrelevant characters early keeps every later stage simpler.

int x = 10;

// tokenized as:
[KEYWORD: int] [IDENTIFIER: x] [OPERATOR: =] [NUMBER: 10] [SEMICOLON: ;]