stepwise
Compiler pipeline1/7 - Lexical analysis
Back to demos

Scroll-driven sequence

A compiler's five phases as a scroll-driven sequence - with sub-chapters: splits into Scopes and Overloads, sharing one proportional span in the scrubber so the chapter visibly fills halfway as its children pass. Every dotted term opens a glossary tooltip; the glossary appends itself from the provider's entries.

01

Lexical analysis

The converts source text into - keywords, identifiers, literals, operators.

Lorem ipsum dolor sit amet, consectetur adipiscing elit. The scanner walks the input character by character, grouping runes into maximal munches. Whitespace and comments are discarded here; they carry no meaning to the parser downstream. Sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.

Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris. Every token carries a source span, so later diagnostics can point at the exact column where something went wrong. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.

Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. The token stream is a flat array - the cheapest possible representation, because the parser will rebuild structure from it anyway.

02

Syntax analysis

The consumes the token stream and builds a of syntactic constructs.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt. Each node in the tree represents a construct - a function, a loop, an expression. Grammar rules are checked here: a missing semicolon fails before any semantic work begins. Ut labore et dolore magna aliqua ut enim ad minim veniam.

Quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Recursive descent handles most grammars comfortably; the tricky cases are left recursion and operator precedence, both solved with precedence climbing. Duis aute irure dolor in reprehenderit in voluptate.

Velit esse cillum dolore eu fugiat nulla pariatur. The tree is immutable from here on - downstream passes annotate it rather than rewrite it, which keeps every phase's input trustworthy. Excepteur sint occaecat cupidatat non proident.

03

Semantic analysis

The annotates the - declarations resolve, overloads narrow, expressions get types. Two sub-passes below: scopes first, then overload resolution.

04

Semantic analysis - Scopes

Sub-chapter 1 of 2 - every identifier resolves through a chain to its declaration.

Sed ut perspiciatis unde omnis iste natus error sit voluptatem accusantium doloremque laudantium. Variables resolve to their declarations through a scope chain, walking outward from the innermost block until a binding matches. Totam rem aperiam, eaque ipsa quae ab illo inventore veritatis.

Nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit aut fugit. Shadowing is legal when the inner declaration's type is compatible; the outer binding becomes unreachable by name for the rest of the inner block. Neque porro quisquam est, qui dolorem ipsum quia dolor sit amet.

05

Semantic analysis - Overloads

Sub-chapter 2 of 2 - candidates narrow as argument types become known.

Consectetur, adipisci velit, sed quia non numquam eius modi tempora incidunt. Candidate sets shrink as each argument's type is inferred; when exactly one survives, the call resolves. Ambiguity is a hard error. Ut labore et dolore magnam aliquam quaerat voluptatem.

Atque corrupti quos dolores et quas molestias excepturi sint occaecati. The output is a fully annotated tree: every node knows its type, and every identifier knows its declaration. Cupiditate non provident, similique sunt in culpa qui officia.

06

Optimization

The rewrites the - dead code out, loops unrolled, allocated.

Ut enim ad minima veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam. Dead code is removed, loops are unrolled when profitable, and common subexpressions are folded. Correctness invariants are preserved at every step - an optimizer that changes meaning is worse than no optimizer. Nisi ut aliquid ex ea commodi consequatur.

Quis autem vel eum iure reprehenderit qui in ea voluptate velit esse quam nihil molestiae. Passes run to a fixed point or a budget, whichever comes first; the order matters, and bad orders undo each other's work. Et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum.

Atque corrupti quos dolores et quas molestias excepturi sint occaecati. Register allocation maps the infinite virtual registers of the IR onto the finite physical registers of the target, spilling the rest to stack slots. Cupiditate non provident, similique sunt in culpa qui officia.

07

Code generation

The backend emits target instructions - each abstract op becomes concrete machine code an consumes.

Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus. Each abstract operation becomes a concrete machine instruction or ISA pattern. The result is a linear stream - an artifact the assembler or linker consumes. Quod maxime placeat, facere possimus, omnis voluptas assumenda est.

Omnis dolor repellendus. Temporibus autem quibusdam et aut officiis debitis aut rerum necessitatibus saepe. Instruction selection, scheduling, and peephole fixes happen here; a bad schedule costs cycles on every execution of the hot loop. Itaque earum rerum hic tenetur a sapiente delectus.

Ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat. The emitted object file carries relocation records so the linker can patch addresses it could not know at compile time. This is the end of the pipeline - what leaves is bytes.

Glossary

Every term referenced above, in declaration order - collected automatically from the provider, no list passed by hand. Inside this appendix, references become anchor links instead of nested tooltips. The intro, footer, columns, and each row are all overridable.

Token

The atomic unit the lexer emits: a category (keyword, identifier, literal) plus a source span. The parser rebuilds structure from a flat stream of these.

Lexer

Converts raw source text into tokens, discarding whitespace and comments. Its output feeds the parser; nothing downstream ever sees the original characters again.

Parser

Consumes the token stream and builds an AST according to the grammar. A missing semicolon fails here, before any semantic work begins.

AST

Abstract syntax tree - the parsed structure of the program. The typechecker annotates it, and lowering turns it into an IR the optimizer can rewrite.

Typechecker

Assigns a type to every expression in the AST and resolves identifiers to declarations. Most user-facing diagnostics originate here, while the tree still mirrors the source.

Scope

The region of the program in which a name is visible. The typechecker resolves identifiers by walking outward through nested scopes to their declaration.

Overload

Multiple declarations sharing a name, distinguished by signature. The typechecker narrows candidates using the argument types in scope.

IR

Intermediate representation - the optimization-friendly form the AST lowers into. The optimizer rewrites it until a budget or a fixed point, then codegen consumes it.

Optimizer

Rewrites the IR - dead code elimination, inlining, loop transforms - preserving meaning. Feeds its output to register allocation on the way to codegen.

Register allocation

Maps the IR's infinite virtual registers onto the target's finite physical machine registers, spilling the rest to stack slots. Runs after the optimizer settles.

Code generation

The backend: selects instructions, schedules them, and emits an object file with relocation records the linker patches. The end of the pipeline - what leaves is bytes.

Linker

Combines object files, resolves symbols, and patches the relocation records that codegen left behind. Addresses unknowable at compile time become final here.

12 entries - declared once in GLOSSARY - rendered by <GlossaryAppendix />

- end of pipeline -