Breaking Down Words: The Art of Lexical Analysis in Compiler Design

This article is Part 2 of the Compiler Design series. Part 1 covers the full six-stage compilation pipeline — start there if you haven’t already.

The first thing a compiler does when it sees your source code is deceptively simple: it reads it. Not for meaning, not for structure — just character by character, grouping those characters into the smallest meaningful units of the language. That process is lexical analysis.

What is Lexical Analysis?

Lexical analysis is the first phase of compilation. The lexical analyser (also called the scanner or lexer) reads source code one character at a time and groups characters into tokens — sequences that represent keywords, identifiers, operators, literals, and punctuation.

Take this short C program:

#include <stdio.h>

int main() {
    printf("Hello, World!");
    return 0;
}

To the compiler at this stage, that file is just a sequence of characters. By the end of lexical analysis it becomes a structured stream of typed tokens that every subsequent stage — parsing, semantic analysis, code generation — can work with cleanly.

The Key Stages of Lexical Analysis

1. Input Buffering

Before scanning begins, the source code is read from disk and stored in a contiguous memory block — the input buffer. This serves two purposes: it’s faster to read from memory than disk one character at a time, and it allows the scanner to look ahead by one or more characters (essential for distinguishing > from >=, for example).

2. Scanning (Tokenisation)

The scanner reads the input buffer character by character. When it accumulates characters that match a known token pattern, it emits a token and moves on. Whitespace and comments are discarded — they carry no semantic meaning.

For the Hello, World! program, the scanner produces:

Token: #include
Token: <
Token: stdio.h
Token: >
Token: int
Token: main
Token: (
Token: )
Token: {
Token: printf
Token: (
Token: "Hello, World!"
Token: )
Token: ;
Token: return
Token: 0
Token: ;
Token: }

3. Identifying and Classifying Tokens

Every token is assigned a type and a value. Token types fall into five categories:

• Keywords — reserved words with fixed meaning: if, while, return, int
• Identifiers — user-defined names for variables, functions, and types: main, printf, sum
• Operators — symbols for operations: +, -, =, <, >=
• Literals — constant values: 0, 3.14, "Hello, World!"
• Punctuation — structural delimiters: {, }, (, ), ;, ,

The typed token stream for the same program looks like this:

<PREPROC_DIRECTIVE, "#include">  <OPERATOR, "<">  <HEADER, "stdio.h">  <OPERATOR, ">">
<KEYWORD, "int">  <IDENTIFIER, "main">  <PUNCTUATION, "(">  <PUNCTUATION, ")">
<PUNCTUATION, "{">
<IDENTIFIER, "printf">  <PUNCTUATION, "(">  <STRING_LITERAL, "Hello, World!">  <PUNCTUATION, ")">  <PUNCTUATION, ";">
<KEYWORD, "return">  <NUMBER, "0">  <PUNCTUATION, ";">
<PUNCTUATION, "}">

4. Filtering Invalid Tokens

Not every character sequence forms a valid token. If the scanner encounters a sequence that doesn’t match any token pattern — for example, @ in C (which has no defined meaning), or a numeric literal like 123abc that starts like a number but then contains letters illegally — it flags a lexical error.

An important nuance: the lexer only catches lexical errors — violations of what constitutes a valid token. A typo like fr instead of for would not be caught here; fr is a perfectly valid identifier to the lexer, which simply emits <IDENTIFIER, "fr">. That error only surfaces later, during syntax analysis, when the parser finds an identifier where it expected the keyword for.

The Advanced Process: From Characters to Lexemes

The simplified flow above hides some important detail. In practice, lexical analysis also involves:

Creating Lexemes

A lexeme is the specific sequence of characters in the source code matched to a token type. The distinction matters: many identifiers share the same token type but have different lexemes.

Here’s the full lexeme-to-token mapping for the Hello World program:

Lexeme: #include       → Token: Preprocessor Directive
Lexeme: <              → Token: Less-Than Operator
Lexeme: stdio.h        → Token: Header File Name
Lexeme: >              → Token: Greater-Than Operator
Lexeme: int            → Token: Keyword
Lexeme: main           → Token: Identifier
Lexeme: (              → Token: Left Parenthesis
Lexeme: )              → Token: Right Parenthesis
Lexeme: {              → Token: Left Curly Brace
Lexeme: printf         → Token: Identifier
Lexeme: (              → Token: Left Parenthesis
Lexeme: "Hello, World!"→ Token: String Literal
Lexeme: )              → Token: Right Parenthesis
Lexeme: ;              → Token: Semicolon
Lexeme: return         → Token: Keyword
Lexeme: 0              → Token: Numeric Literal
Lexeme: ;              → Token: Semicolon
Lexeme: }              → Token: Right Curly Brace

Eliminating Whitespace and Comments

Whitespace (spaces, tabs, newlines) and comments exist for the programmer’s benefit — the compiler has no use for them. The scanner strips both before generating the token stream. This is why code formatting has zero effect on compiled output.

Generating the Final Token Stream

After scanning, classification, and filtering, the lexer hands a clean token stream to the next stage: syntax analysis. In abstract terms, the Hello World program becomes:

Preprocessor Directive < Header File Name >
Keyword Identifier Left-Paren Right-Paren Left-Brace
Identifier Left-Paren String-Literal Right-Paren Semicolon
Keyword Numeric-Literal Semicolon
Right-Brace

All the noise — whitespace, comments, #include expansion — is gone. What remains is a precise, structured description of the tokens in the program, ready for the parser to check against the language grammar.

Three Terms Worth Knowing Cold

Token — A character sequence representing a single programming language element: keyword, identifier, operator, literal, or punctuation mark.

Lexeme — The actual character sequence in the source code that corresponds to a specific token. Every token instance has exactly one lexeme.

Token Stream — The ordered sequence of all tokens produced by the lexer. This stream is the output of lexical analysis and the input to syntax analysis.

Why Lexical Analysis is Non-Trivial

It sounds mechanical — and in one sense it is — but a production lexer has to handle:

• Longest match — >= must be scanned as a single token, not > followed by =
• Keyword vs identifier — return is a keyword; return_value is an identifier. The difference depends on word boundaries
• Context sensitivity — In some languages, the same character means different things in different contexts (e.g. * as multiplication vs pointer dereference in C)
• Unicode — Modern source files aren’t ASCII-only; identifier names can contain accented characters or emoji in some languages
• Performance — Lexers process millions of characters per second in large codebases; efficiency matters

Most production compilers implement their lexer using finite automata (DFA/NFA) — the formal theoretical model that maps exactly onto this character-matching problem. Many also generate the lexer automatically from regular expression specifications using tools like lex or flex. Regular expressions (not full context-free grammars) are sufficient for token patterns — and that weaker power is precisely why a separate parser is needed for the next stage.

What Comes Next

With a clean token stream in hand, the compiler moves to syntax analysis (parsing), where it checks whether the token sequence conforms to the grammar of the language and builds an Abstract Syntax Tree. That’s the subject of the next article in this series.