Compiler Design Tutorial
Learn Compiler Design step by step: 61 lessons in 9 chapters with examples, quizzes, diagrams and projects.
Start learning →
of lessons completed
Getting Started
- What Is a Compiler? Learn what a compiler is, how it differs from an interpreter and a transpiler, why compiler design matters, and run a tiny compiler and VM in Python.
- Bootstrapping and Cross-Compilers Learn how compilers are built with themselves: T-diagrams, bootstrapping from a small subset, self-hosting, three-stage builds, cross-compilers and the Canadian cross.
- The Phases of a Compiler Walk through every compiler phase, from lexical analysis to code generation, and run a toy pipeline that prints the output of each stage.
- The Preprocessor and Macro Expansion Learn how a preprocessor works: includes, conditional compilation, object-like and function-like macros, stringizing, pasting, macro pitfalls and hygiene, with a runnable model.
- Meet Our Toy Language Meet Tiny, the small language you will compile throughout this track: its tokens, grammar, sample programs and a runnable reference interpreter.
Lexical Analysis
- Tokens, Lexemes and Patterns Learn the difference between tokens, lexemes and patterns, how keywords differ from identifiers, and hand-write a character-by-character scanner in Python.
- Regular Expressions for Lexers Use regular expressions to describe tokens, learn longest-match and priority rules, and build a complete tokenizer with Python's re module and named groups.
- Finite Automata: DFA and NFA Understand DFAs and NFAs, transition tables and dead states, and simulate both in Python to recognize identifiers, numbers and patterns like (a|b)*abb.
- From Regex to NFA to DFA Turn a regular expression into an NFA with Thompson's construction, then into a DFA with subset construction, and see DFA minimization in runnable Python.
- Writing a Complete Lexer Build a full hand-written lexer in Python: a Token class, line and column tracking, numbers, strings with escapes, comments, operators and EOF.
- Writing a Flex Program (Lex Scanner Generator) Learn the structure of a Flex (Lex) program: definitions, rules and user code, longest match, start conditions, and run a Python stand-in of the same rules.
- Lexical Errors and Recovery Handle lexical errors well: invalid characters, unterminated strings and comments, error tokens, caret diagnostics and panic-mode recovery, in Python.
Context-Free Grammars
- Context-Free Grammars Learn context-free grammars for compilers: terminals, nonterminals, productions, derivations, parse trees, BNF and EBNF, with grammars as Python dicts.
- Ambiguity, Precedence and Associativity Learn why ambiguous grammars break compilers, how to layer rules for operator precedence and associativity, and fix the dangling else, with a Python tree counter.
- Eliminating Left Recursion and Left Factoring See why top-down parsers need grammars without left recursion and with left factoring, learn both algorithms and run them in Python on real grammars.
- FIRST and FOLLOW Sets Learn how to compute nullable symbols, FIRST and FOLLOW sets for a context-free grammar with a fixed-point algorithm, and run the code in Python.
Parsing
- Top-Down Parsing Basics Understand top-down parsing: leftmost derivations, backtracking, why left recursion loops, and how one token of lookahead gives predictive parsing.
- Writing a Recursive Descent Parser Build a recursive descent parser in Python: one function per grammar rule, precedence from layered rules, statements, blocks, calls and clear errors.
- Abstract Syntax Trees Learn how parse trees differ from abstract syntax trees, design AST node classes with dataclasses, build them in a parser, unparse them and use visitors.
- LL(1) Table-Driven Parsing Build an LL(1) parsing table from FIRST and FOLLOW sets, run a stack-based predictive parser step by step, and detect conflicts such as the dangling else.
- Pratt Parsing and Operator Precedence Learn Pratt parsing with binding powers: prefix, infix and postfix operators, right associativity and the ternary operator, plus the shunting-yard algorithm.
- Bottom-Up Parsing: Shift-Reduce Learn how bottom-up parsers work: handles, rightmost derivations in reverse, shift and reduce actions, stack traces, and a shift-reduce simulator in Python.
- Operator-Precedence Parsing Learn grammar-based operator-precedence parsing: operator grammars, the three precedence relations, shift and reduce decisions, precedence functions and a runnable parser.
- LR(0), SLR and LALR Parsers Build LR parsers step by step: items, closure and goto, the canonical collection, action and goto tables, conflicts, and how SLR, LALR and LR(1) differ.
- Canonical LR(1) Parsers and Conflict Resolution Build canonical LR(1) item sets with lookaheads, compare them with SLR and LALR on three grammars, and see how state merging creates reduce/reduce conflicts.
- Syntax Errors and Error Recovery Learn how parsers report syntax errors and keep going: panic mode, synchronization tokens, phrase-level recovery, and how to write helpful diagnostics.
- Parser Generators and Tools Compare Yacc and Bison, ANTLR, PEG parsers and parser combinators, then write a working parser-combinator calculator in Python from scratch.
Semantic Analysis
- Syntax-Directed Translation Learn syntax-directed translation: attributes, synthesized and inherited values, S-attributed and L-attributed grammars, and semantic actions with Python code.
- Symbol Tables and Scopes Learn how compilers track names with symbol tables and scope chains: shadowing, declare-before-use, a resolver pass, and runnable Python examples.
- Type Checking Learn how a compiler type checker works: static vs dynamic typing, type rules, a checker pass over the AST and clear error messages, with runnable Python.
- Type Inference and Unification Learn how compilers infer types without annotations: type variables, unification, the occurs check and let-polymorphism, with a runnable Python inferer.
Intermediate Code and Optimization
- Intermediate Representations Learn what an intermediate representation is and compare ASTs, three-address code, SSA, stack bytecode and register code with runnable Python examples.
- Generating Three-Address Code Learn to generate three-address code from an AST: temporaries, labels, lowering if and while, short-circuit booleans, and a runnable Python generator.
- Backpatching and Code for Control Flow Generate jump code for boolean expressions, if, if-else and while with backpatching: truelists, falselists, markers, short-circuit evaluation and a runnable generator.
- Basic Blocks and Control Flow Graphs Learn how compilers split three-address code into basic blocks, build a control flow graph, find dominators and loops, with runnable Python code.
- Local Optimizations Learn local compiler optimizations inside a basic block: constant folding, algebraic simplification, strength reduction, CSE and dead code, with a runnable optimizer.
- DAG Representation and Value Numbering Represent a basic block as a directed acyclic graph to share common subexpressions, then learn local value numbering with constants and commutativity, with runnable code.
- Data-Flow Analysis Learn data-flow analysis: reaching definitions, live variables and available expressions, solved with a worklist algorithm in runnable Python.
- Static Single Assignment Understand SSA form: phi functions, dominators, dominance frontiers and renaming, with a runnable Python SSA construction for a loop.
- Loop and Global Optimizations Learn loop-invariant code motion, strength reduction, loop unrolling, inlining and tail-call elimination, with runnable Python demonstrations.
Code Generation and Runtimes
- Runtime Environments: Stack, Heap and Frames Learn how compiled programs use memory at run time: activation records, call stacks, calling conventions, static links and closures, with a simulation.
- Parameter Passing Modes and Activation Records Compare call by value, reference, copy-restore and name, see how arguments live in activation records, and compare access links with a display, using runnable models.
- Static (Lexical) vs Dynamic Scoping Compare static (lexical) and dynamic scoping with a runnable interpreter: the same program gives different answers, closures break, and binding costs differ.
- Code Generation and Instruction Selection Learn how a code generator turns intermediate code into machine instructions: targets, instruction selection by tree tiling, and a runnable toy CPU.
- Assemblers, Linkers and Loaders Follow code from assembly to a running program: the two-pass assembler, symbol tables, relocation entries, symbol resolution in the linker, and what the loader does.
- Register Allocation Learn register allocation: live ranges, interference graphs, graph coloring, spilling and linear scan, with runnable Python allocators.
- Instruction Scheduling and Software Pipelining See how compilers reorder instructions to hide latency: dependence graphs, pipeline stalls, list scheduling, register pressure and software pipelining of loops, with runnable models.
- Memory Management and Garbage Collection Learn how languages manage heap memory: manual freeing, reference counting, mark-and-sweep and copying collectors, with runnable Python simulations of each.
- Bytecode and Virtual Machines Design a bytecode instruction set, compile an AST to it and run it on a stack-based virtual machine in Python, then compare it with CPython's own dis output.
- Interpreters, JIT and Ahead-of-Time Compilation Compare tree-walking interpreters, bytecode VMs, just-in-time and ahead-of-time compilers, and run a tiny tiered JIT with guards and an AOT inliner in Python.
Projects
- Project: An Expression Calculator Compiler Build a complete expression compiler in Python: a lexer, a Pratt parser, an AST, a bytecode compiler and a stack VM, with error carets and a differential test.
- Project: A Complete Toy Language Finish the Tiny language in Python: a lexer with positions, a recursive descent parser, a scope and type checker, a closure-aware interpreter and friendly errors.
- Project: Compiler and VM for the Toy Language Turn the Tiny interpreter into a compiler: generate stack bytecode with locals, globals and calls, add AST and peephole optimizers, a disassembler and a VM.
- Project: A JSON Parser and Pretty-Printer Build a complete JSON parser and pretty-printer in Python: a lexer, a recursive descent parser, error messages with a caret, and a test against the json module.
- Project: A Regex Engine Build a working regular expression engine in Python: parse patterns to a tree, compile to an NFA program, run Thompson simulation, and test it against re.
- Project: A Transpiler to Python Build a source-to-source compiler in Python that translates the Tiny language into Python code, handles scopes and closures, and maps errors back to source lines.
- Project: A Mini Linux Shell Build a small Linux-style shell in Python: tokenize quotes and operators, parse pipelines and lists, expand variables, and execute commands, pipes and redirections.
Practice and Review
- Practice Exercises with Solutions Practice compiler design with exercises on lexing, grammars, FIRST and FOLLOW, parsing, optimization and virtual machines. Every solution runs in your browser.
- Testing and Debugging a Compiler Learn how to test and debug a compiler: golden tests, error message tests, random program fuzzing, differential testing against Python and test case shrinking.
- Compiler Design Interview Questions Prepare for compiler design interviews and exams: core concept questions, trick questions and GATE-style problems with answers, plus runnable checks in Python.
- Compiler Design Cheat Sheet A one-page compiler design cheat sheet: phases, grammar classes, parser comparison, FIRST/FOLLOW rules, optimizations and handy formulas with examples.