Skip to content
Tutorials Center
My learning

Topics

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

  1. 1 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.
  2. 2 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.
  3. 3 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.
  4. 4 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.
  5. 5 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

  1. 6 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.
  2. 7 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.
  3. 8 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.
  4. 9 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.
  5. 10 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.
  6. 11 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.
  7. 12 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

  1. 13 Context-Free Grammars Learn context-free grammars for compilers: terminals, nonterminals, productions, derivations, parse trees, BNF and EBNF, with grammars as Python dicts.
  2. 14 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.
  3. 15 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.
  4. 16 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

  1. 17 Top-Down Parsing Basics Understand top-down parsing: leftmost derivations, backtracking, why left recursion loops, and how one token of lookahead gives predictive parsing.
  2. 18 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.
  3. 19 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.
  4. 20 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.
  5. 21 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.
  6. 22 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.
  7. 23 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.
  8. 24 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.
  9. 25 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.
  10. 26 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.
  11. 27 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

  1. 28 Syntax-Directed Translation Learn syntax-directed translation: attributes, synthesized and inherited values, S-attributed and L-attributed grammars, and semantic actions with Python code.
  2. 29 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.
  3. 30 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.
  4. 31 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

  1. 32 Intermediate Representations Learn what an intermediate representation is and compare ASTs, three-address code, SSA, stack bytecode and register code with runnable Python examples.
  2. 33 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.
  3. 34 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.
  4. 35 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.
  5. 36 Local Optimizations Learn local compiler optimizations inside a basic block: constant folding, algebraic simplification, strength reduction, CSE and dead code, with a runnable optimizer.
  6. 37 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.
  7. 38 Data-Flow Analysis Learn data-flow analysis: reaching definitions, live variables and available expressions, solved with a worklist algorithm in runnable Python.
  8. 39 Static Single Assignment Understand SSA form: phi functions, dominators, dominance frontiers and renaming, with a runnable Python SSA construction for a loop.
  9. 40 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

  1. 41 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.
  2. 42 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.
  3. 43 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.
  4. 44 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.
  5. 45 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.
  6. 46 Register Allocation Learn register allocation: live ranges, interference graphs, graph coloring, spilling and linear scan, with runnable Python allocators.
  7. 47 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.
  8. 48 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.
  9. 49 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.
  10. 50 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

  1. 51 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.
  2. 52 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.
  3. 53 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.
  4. 54 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.
  5. 55 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.
  6. 56 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.
  7. 57 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

  1. 58 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.
  2. 59 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.
  3. 60 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.
  4. 61 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.