Lexical Analysis

Lexical analysis (also called scanning or tokenisation) is Phase 1 of the compiler pipeline. Its job is straightforward:

Read the source code character by character and group those characters into tokens — the smallest meaningful units of the language.

Think of it like reading an English sentence. You don't process the sentence one letter at a time — you naturally chunk letters into words, then punctuation. The lexer does the same for source code.

Position in the Compiler Pipeline

The lexer sits between the raw source text and everything else. Without it, the parser would have to deal with whitespace, comments, and individual characters — a nightmare. The lexer cleans all of that up.

Three terms are essential for understanding lexical analysis:

Common Token Types

Whitespace (spaces, tabs, newlines) and comments are not tokens — the lexer discards them silently.

Let's trace the lexer on a real C-style statement:

The lexer scans left to right. Each time it finds the longest matching pattern, it emits a token and advances:

Token stream output:

The parser never sees whitespace — it receives a clean sequence of typed tokens.

Another Example — a Function Declaration

Token stream:

The lexer implements a longest-match rule (also called maximal munch):

At each position, consume the longest sequence of characters that matches any pattern.

This is why <= is ONE token (LESS_EQUAL), not two (LESS, EQUAL). The lexer always prefers the longer match.

Lexer Algorithm

Under the hood, most lexers are implemented as a Deterministic Finite Automaton (DFA). Each token type corresponds to a regular expression; those regular expressions are combined into a single DFA that runs in O(n) time on a source file of length n.

Keyword vs Identifier — How the Lexer Decides

Keywords like int, while, return look exactly like identifiers by their character pattern. Lexers handle this two ways:

Method 1 — Keyword table:

• Recognise while as an IDENTIFIER first
• Then look it up in a keyword table
• If found → reclassify as KEYWORD

Method 2 — Higher priority pattern:

• Keyword patterns are given higher priority than the IDENTIFIER pattern
• The DFA resolves the ambiguity by picking the keyword path first

A lexical error occurs when the lexer encounters a sequence of characters that does not match any valid token pattern.

Common Lexical Errors

What Happens on a Lexical Error?

Most lexers use error recovery to continue scanning and report multiple errors at once:

1. Panic mode — skip characters until a valid token can be formed, then continue
2. Insert/delete — hypothetically insert or delete one character to make progress
3. Emit an ERROR token — the parser will then reject the token stream at the syntax phase

Lexical errors are the easiest category to recover from — the lexer simply skips the bad character and resynchronises at the next recognisable token.

The lexer's output — a stream of (type, lexeme) pairs — is everything the parser needs. Lexical analysis effectively converts a character-level view of the program into a word-level view, making every subsequent phase far simpler to implement.