Compiler Design
How a pile of text you type becomes a running program, explained from absolute zero: hand-drawn pictures first, then the real math and C++ underneath every phase — lexing, parsing, semantic analysis, runtime environments, intermediate code, optimization, and a full working compiler you build yourself.
Written byRohan Sharma
Foundations of Compilation
4 lessons- 8 min read
What is a compiler, really?
Why "translating" is the entire idea behind a compiler, explained with a five-year-old's translator toy before a single line of C++ shows up.
- 8 min read
Compilers vs interpreters vs "kind of both"
Why some languages translate everything upfront, others read and run line by line, and why most real languages today are secretly a mix of the two.
- 10 min read
The six phases of a compiler, end to end
A bird's-eye map of every stage a compiler passes your code through, from raw characters to final machine instructions, using one tiny expression as the running example.
- 9 min read
Bootstrapping: how do you compile a compiler's own language?
The chicken-and-egg puzzle of writing a compiler in the very language it compiles, solved with T-diagrams and the classic three-step bootstrap.
Foundations of Compilation Quiz
10 questions
Lexical Analysis
6 lessons- 8 min read
What is a token? Chopping code into words
Why a compiler's first move is treating your code like a sentence to be broken into words, and the difference between a lexeme, a token, and a pattern.
- 10 min read
Regular expressions and formal languages, from scratch
What it actually means for a string to "belong to a language," building regular expressions from three simple operations, and why they're exactly what a lexer needs.
- 12 min read
Finite automata, from NFA to DFA
The state-machine "board game" that makes regular expression matching actually fast, and the mechanical algorithm that turns a flexible NFA into a fast, deterministic DFA.
- 11 min read
DFA minimization, and how a lexer reads input fast
The exam-favorite numerical: shrinking a DFA to the fewest possible states using the table-filling algorithm, worked step by step, plus how real lexers buffer input efficiently.
- 13 min read
Building a real lexer in C++, character by character
A complete, working hand-written lexer in C++ that turns real source code into a token stream, built directly on the DFA ideas from the previous lesson.
- 9 min read
Lexer edge cases and error recovery
What a lexer should do when it meets characters that don't fit any pattern, and why crashing on the first bad character is the wrong answer.
Lexical Analysis Quiz
13 questions
Parsing & Grammars
7 lessons- 10 min read
Context-free grammars, the rulebook for valid structure
Why "regular" pattern matching runs out of power for real programming languages, and how context-free grammars describe nested structure precisely.
- 9 min read
Ambiguous grammars, and fixing them with precedence and associativity
What it means for a grammar to allow two different valid trees for the same string, why that is a real problem, and the standard rewriting technique that fixes it.
- 12 min read
Top-down parsing with recursive descent, in C++
Turning a layered grammar directly into working C++ functions, one non-terminal at a time, and building a real parser that produces an AST.
- 12 min read
LL(1) parsing: FIRST, FOLLOW, and parse tables
The formal machinery behind recursive descent — FIRST and FOLLOW sets, how to build an LL(1) parse table, and how to detect when a grammar can't be parsed this way at all.
- 11 min read
Bottom-up parsing and LR parsers, building the tree in reverse
How shift-reduce parsing builds a parse tree from the leaves upward using a stack, why it can handle grammars LL(1) cannot, and how the algorithm actually decides what to do.
- 13 min read
Constructing an SLR parsing table by hand
The classic numerical: building LR(0) items, the canonical collection, and a full SLR(1) parsing table for a small grammar, then tracing a real parse against it.
- 13 min read
Building a complete statement parser in C++
Scaling the expression parser up to a real mini-language with variable declarations, if/else, while loops, and blocks — including a clean fix for the dangling-else problem.
Parsing & Grammars Quiz
15 questions
- 9 min read
Syntax-directed definitions, attaching meaning to grammar rules
How compilers attach "meaning-computing" actions directly onto grammar rules, and the two flavors of attribute — synthesized and inherited.
- 9 min read
Abstract syntax trees: throwing away noise, keeping meaning
Why compilers convert the parser's raw output into a leaner AST, and how to design AST node types in C++ that carry only what later phases need.
- 10 min read
Symbol tables: the compiler's phone book for every name
How a compiler remembers what every variable and function name refers to, and why scoping means the same name can mean different things in different places.
- 10 min read
Type checking, teaching the compiler what "makes sense"
How a compiler decides whether "1 + true" is nonsense, using type rules walked over the AST with the symbol table from the previous lesson.
- 9 min read
Scope and name resolution, the rules behind "which x is this?"
Static vs dynamic scoping, shadowing, and why almost every real language chose static scoping — with a worked C++ example showing exactly how resolution happens at compile time.
Syntax-Directed Translation & Semantics Quiz
10 questions
Runtime Environments
4 lessons- 9 min read
The memory layout of a running program
What actually happens in RAM the instant your compiled program starts running — the stack, the heap, and the two static regions, explained with a bedroom-cleaning analogy.
- 11 min read
Activation records: what a function call actually pushes onto the stack
The exact contents of a stack frame, tracing a real recursive function call by call, and why forgetting the return address would break everything.
- 10 min read
Array address calculation, and static vs stack vs heap allocation
The classic numerical: computing exactly which memory address a[i][j] refers to, for both row-major and column-major layouts, plus a clear comparison of the three storage allocation strategies.
- 10 min read
Parameter passing and the heap, made concrete
What actually happens in memory for pass-by-value vs pass-by-reference, and how the heap tracks free and used memory to satisfy new/delete.
Runtime Environments Quiz
15 questions
Intermediate Code Generation
4 lessons- 8 min read
Why compilers bother with intermediate code at all
The N-times-M translation problem every multi-target, multi-source compiler faces, and how one shared middle language solves it.
- 10 min read
Three-address code: the compiler's simplest possible sentence
The exact rules of three-address code, why every instruction is limited to one operation, and how it represents control flow with labels and jumps.
- 10 min read
Quadruples, triples, indirect triples, and DAGs
The classic ways to actually store three-address code in memory, worked by hand for a real expression, plus DAG construction for spotting shared subexpressions.
- 11 min read
A complete TAC generator for a full program, in C++
Wiring up a full three-address code generator across expressions, declarations, assignments, and control flow, tracing a complete real program end to end.
Intermediate Code Generation Quiz
15 questions
- 9 min read
Basic blocks and control flow graphs
Chopping TAC into straight-line chunks with no internal jumps, and connecting those chunks into a graph that shows every possible path through a program.
- 11 min read
Local optimizations and common subexpression elimination
Cleaning up redundant work within a single basic block — dead code elimination, copy propagation, constant folding, and common subexpression elimination — all implemented in C++.
- 13 min read
Data flow analysis: constant propagation and liveness, across the whole graph
Extending optimization beyond a single basic block using data flow equations, worked by hand and in C++, for global constant propagation and liveness analysis.
- 10 min read
Peephole optimization and loop optimizations
Small-window machine-code cleanups you can spot by eye, plus the classic loop optimizations — loop-invariant code motion, strength reduction, and induction variable elimination — worked by hand.
- 9 min read
Putting it together, a complete optimization pipeline
How real compilers order and repeat local optimizations and data flow analyses into one coherent pipeline, traced end to end on a full example.
Local Optimization & Data Flow Analysis Quiz
15 questions
Design Your First Compiler
6 lessons- 11 min read
Capstone 1: choosing your compiler's tech stack
Deciding the language, build system, project layout, and dependencies for a real, from-scratch compiler project — with concrete justification for every choice.
- 11 min read
Capstone 2: designing PocketLang's grammar and rules
Writing PocketLang's complete formal grammar, checking it for LL(1)-friendliness by hand, and defining its full type system and scoping rules before writing any implementation code.
- 12 min read
Capstone 3: implementing PocketLang's lexer and parser
A complete, working lexer and recursive descent parser for PocketLang's full grammar, including the function/call disambiguation the design lesson flagged.
- 12 min read
Capstone 4: semantic analysis and code generation for functions
Extending symbol tables and type checking to handle multiple functions and calls, then generating three-address code for the complete fibonacci program.
- 13 min read
Capstone 5: optimizing and executing PocketLang, for real
Running the Module 7 optimization pipeline on generated TAC, then building a complete stack-based virtual machine that actually executes it and prints real output.
- 10 min read
Capstone 6: testing, packaging, and where to go from here
A complete per-phase test suite for PocketLang, packaging it as a usable CLI tool, and a concrete roadmap for extending it well beyond this course.
Design Your First Compiler Quiz
10 questions
Assessments
9 quizzesFoundations of Compilation Quiz
Foundations of Compilation · 10 questions
Lexical Analysis Quiz
Lexical Analysis · 13 questions
Parsing & Grammars Quiz
Parsing & Grammars · 15 questions
Syntax-Directed Translation & Semantics Quiz
Syntax-Directed Translation & Semantics · 10 questions
Runtime Environments Quiz
Runtime Environments · 15 questions
Intermediate Code Generation Quiz
Intermediate Code Generation · 15 questions
Local Optimization & Data Flow Analysis Quiz
Local Optimization & Data Flow Analysis · 15 questions
Design Your First Compiler Quiz
Design Your First Compiler · 10 questions
Compiler Design Final Assessment
Final assessment · 26 questions