Basics of Compiler Design Study Guide and Chapter Summaries – Torben Mogensen (Anniversary Edition, 2010) BSCS

BSCS students can use this guide to study “Basics of Compiler Design” by Torben Ægidius Mogensen of the Department of Computer Science (DIKU) at the University of Copenhagen. The author offers the 2010 Anniversary Edition free from his own web page. It was written for the introductory compiler course at DIKU, and it covers the standard Compiler Construction syllabus: lexical analysis, parsing, symbol tables, type checking, intermediate code, register allocation and optimisation.

The style is the main reason to pick it. Methods are given as short algorithm sketches rather than code in one language, every chapter from Chapter 2 onward ends with exercises, and some of them come from past exams. The same book also explains function calls, memory management, garbage collection and bootstrapping. It works as a semester textbook for a first compiler course and as quick revision material before a paper.

Book Overview

CourseCompiler Construction / Compiler Design
Degree ProgramsBSCS
LevelUniversity / Undergraduate
EditionAnniversary Edition, 20 August 2010 (first published 2000)
AuthorTorben Ægidius Mogensen
PublisherDepartment of Computer Science (DIKU), University of Copenhagen
ISBN978-87-993154-0-6
LanguageEnglish
Total Chapters13 chapters and 1 appendix
Exercises96 exercises across Chapters 2 to 13 and Appendix A; solutions to selected exercises are on the author’s page
FormatPDF — free from the author’s page

Chapter List

Chapter 1: Introduction

Difficulty: Easy · Key topics: compiler, phases, front end, back end, interpreter, intermediate code, domain-specific language

The chapter defines a compiler as a translator from a high-level language to machine language that also reports obvious programmer mistakes, and explains why high-level code is shorter, faster to write and portable across machines. It then splits compilation into phases with well-defined interfaces, from lexical analysis to machine-code generation, and leaves assembly and linking to the vendor’s tools. Interpreters are contrasted as simpler and easier to port but usually slower. The chapter lists reasons to study compilers, including writing compilers for domain-specific languages, maps the later chapters and ends with the author’s permission-to-use notice.

Key Points:

  • A compiler translates a high-level language into machine language and reports obvious programmer mistakes along the way.
  • The phases are lexical analysis, syntax analysis, type checking, intermediate-code generation, register allocation, machine-code generation, and assembly and linking.
  • The first three phases form the front end and the last three the back end; assembly and linking are not covered in the book.
  • Each phase establishes stronger invariants for the next, so the type checker can assume there are no syntax errors and code generation can assume there are no type errors.
  • An interpreter processes the syntax tree directly; it is simpler and more portable than a compiler but usually slower.
  • Compilation and interpretation can be mixed, for example by compiling to an intermediate code that is then interpreted.

Practice Tip: Take a small program in a language you know and list which phase would reject each kind of mistake: an illegal character (lexer), a missing bracket (parser), an undeclared variable (type checker). This is exactly the split the book uses.

Common Mistake: Treating lexing, parsing and type checking as one job called syntax checking. They are separate phases, and each one catches a different kind of error.

Important Questions:

  • What are the phases of a compiler? Lexical analysis, syntax analysis, type checking, intermediate-code generation, register allocation, machine-code generation, and assembly and linking.
  • What is the difference between a compiler and an interpreter? A compiler translates the whole program before it runs; an interpreter walks the syntax tree and executes it directly, which is simpler and more portable but usually slower.

Chapter 2: Lexical Analysis

Part 1 · Difficulty: Medium · Key topics: regular expressions, NFA, DFA, subset construction, DFA minimisation, lexer generators, longest match, closure properties

A lexer turns a character string into tokens and discards white-space and comments. The chapter defines regular expressions with union, concatenation and repetition, adds the shorthands + and ? and character sets, and builds an NFA from an expression piece by piece. The subset construction then converts the NFA to a DFA using epsilon-closures and fixed-point iteration, and a partition-refinement algorithm minimises the result. Combining the token definitions into one DFA, with priority for earlier rules and the longest-match convention, gives a working lexer. The chapter ends with what regular languages can and cannot express, followed by 16 exercises.

Key Points:

  • Regular expressions are built from single letters, the empty string (epsilon), union |, concatenation and repetition *; repetition binds tightest, then concatenation, then union.
  • Shorthands such as [a-z], + and ? add no expressive power but can save an exponential amount of space.
  • An NFA accepts a string if some path of transitions, including epsilon-transitions, ends in an accepting state; a DFA has no epsilon-transitions and at most one transition per symbol from each state.
  • The subset construction can turn an n-state NFA into a DFA with up to 2^n – 1 states, but this rarely happens for the tokens of programming languages.
  • A regular language has a unique minimal DFA, found by splitting groups of states until every group is consistent.
  • A lexer combines all token NFAs into one DFA, lets earlier definitions win ties, and takes the longest match, backtracking to the last accepting state when needed.
  • A language that needs unbounded counting, such as a^n b^n, is not regular.

Practice Tip: Write regular expressions for a keyword, an identifier, an integer and a float, then draw the NFA for one of them with the book’s construction. You will see why the combined DFA needs priority rules for input such as if17.

Common Mistake: Minimising a DFA that has missing transitions without handling dead states. An undefined transition is not treated like a move to a dead state, so equivalent states can wrongly stay separate unless dead states are removed or made explicit first.

Important Questions:

  • How does the subset construction convert an NFA to a DFA? Each DFA state is a set of NFA states; starting from the epsilon-closure of the NFA start state, it adds a transition for each symbol until no new sets appear, and a set is accepting if it contains an accepting NFA state.
  • How does a lexer choose between overlapping tokens such as a keyword and an identifier? The rule written first has priority, and the lexer takes the longest possible match.

Chapter 3: Syntax Analysis

Part 1 · Difficulty: Hard · Key topics: context-free grammars, derivation, ambiguity, operator precedence, Nullable, FIRST, FOLLOW, LL(1), recursive descent, SLR, parser generators

Parsing recombines tokens into a syntax tree and rejects invalid text. The chapter defines context-free grammars with terminals, nonterminals and productions, shows derivations and syntax trees, and explains how ambiguity arises and how expression grammars are rewritten to encode operator precedence. Predictive parsing is built from Nullable, FIRST and FOLLOW sets, giving LL(1) parsers as recursive descent or as table-driven stack automata, together with left-recursion elimination and left-factorisation. The stronger SLR method uses shift and reduce actions, parse tables built from items, and precedence declarations to resolve conflicts, and the chapter closes with practical use of LR parser generators.

Key Points:

  • A context-free grammar has terminals, nonterminals, a start symbol and productions of the form N -> X1 ... Xn.
  • A grammar is ambiguous if some string has more than one syntax tree; a production of the form Exp -> Exp + Exp is the classic cause.
  • Precedence and associativity can be built into the grammar by layering nonterminals, or declared separately to an LR parser generator.
  • Nullable, FIRST and FOLLOW are computed by fixed-point iteration, and an LL(1) table has a conflict when two productions compete for the same entry.
  • Left-recursion must be eliminated and common prefixes left-factorised before a grammar can be LL(1).
  • LR parsers are table-driven bottom-up parsers with two actions, shift and reduce; the book teaches SLR, and most generators use the stronger LALR(1).
  • Deterministic stack automata cover only some context-free languages, unlike the regular case where DFAs and NFAs are equally powerful.

Practice Tip: Take the expression grammar from the chapter, compute Nullable, FIRST and FOLLOW by hand and build the LL(1) table. If a cell holds two productions you have found a conflict worth fixing before you write any code.

Common Mistake: Giving a left-recursive grammar to a recursive-descent parser or an LL(1) table. The FIRST sets of the productions overlap, so the parser cannot choose; remove the left-recursion first.

Important Questions:

  • What is an ambiguous grammar? One in which some string has more than one syntax tree, for example 2+3*4 read as either a sum of a product or a product of a sum; it is fixed by rewriting with precedence levels or by precedence declarations in an LR generator.
  • How is direct left-recursion eliminated? A group of productions N -> N a | b becomes N -> b N' and N' -> a N' | (empty), which generates the same strings without recursing on the left.

Chapter 4: Scopes and Symbol Tables

Part 2 · Difficulty: Easy · Key topics: binding, scope, static binding, symbol table, persistent table, imperative table, hashing, name spaces

The chapter explains how names are connected to their declarations. A declaration binds a name, uses refer back to it, and when scopes nest, the closest enclosing declaration wins, which is called static or lexical binding. A symbol table needs empty, bind, lookup, enter and exit operations. Persistent versions use lists or functions, so leaving a scope simply recalls the old table, while an imperative version uses a stack with scope markers or an auxiliary stack to undo changes. The chapter then examines the cost of linear lookup, hashing as the usual remedy, and whether variables, functions and types share one name space.

Key Points:

  • A use of a name refers to the closest enclosing declaration in the syntax tree; this is static (lexical) binding and is assumed in the rest of the book.
  • Dynamic binding depends on the execution order, so it cannot be resolved at compile time.
  • A symbol table supports empty, bind, lookup, enter and exit.
  • A persistent table keeps the old version when updated, so exiting a scope is just recalling it; an imperative table must record overwritten bindings and scope markers on a stack.
  • List and stack tables use linear search, so lookup time grows with the table; hashing makes lookup close to constant time.
  • Languages differ on whether variables, functions and types share one name space.

Practice Tip: Trace the C block from the start of the chapter with a stack-based table: push x and y, push a marker, push the inner x, then pop back to the marker. Check that y ends with the value 6.

Common Mistake: Assuming a symbol table can be thrown away when its scope closes. That works for simple blocks, but classes, modules and closures need the table to survive after the scope is exited.

Important Questions:

  • What is the difference between persistent and imperative symbol tables? A persistent table preserves the old version on every update, so scope exit is trivial; an imperative table is updated in place and needs an explicit stack to restore the previous state.
  • What is static binding? The declaration that defines a name is chosen by the structure of the syntax tree, as the smallest enclosing scope that declares it, not by what happened at run time.

Chapter 5: Interpretation

Part 2 · Difficulty: Medium · Key topics: interpreter, abstract syntax tree, symbol table, example functional language, function calls, dynamic checking

After parsing, a program exists as an abstract syntax tree, and the simplest way to run it is to interpret it. An interpreter has one function per syntactic category, each taking a syntax tree and a symbol table and returning a value. The chapter defines a small first-order functional language of mutually recursive functions with integers, booleans, conditionals, let-expressions and calls, and writes the interpreter for expressions, function calls and whole programs, where main receives the input as an integer. It closes by weighing interpretation against static checking and compilation: it is easy and portable, but time is spent inspecting the tree and checking types on every execution.

Key Points:

  • An interpreter is a function from an abstract syntax tree and a symbol table to a value, and it calls itself recursively on subexpressions.
  • In the example language a program is a list of mutually recursive function declarations, and execution calls main with one integer argument.
  • Variables and functions have separate name spaces in the example language.
  • Values carry their types, so the interpreter checks types while running (dynamic typing).
  • Interpretation spends more time deciding what to do than doing it; static checking and compilation move that inspection to a single earlier pass.
  • Static type checking may reject programs that would have run without error, and it adds a delay between editing and running.

Practice Tip: Implement the expression part of the interpreter in a language you know, using a map as the symbol table, then run a small recursive function through it. Count how often the tree is inspected for a single call to see the overhead the chapter describes.

Common Mistake: Letting a function body see the caller’s variables. The body should be evaluated in a fresh symbol table built only from its own parameters.

Important Questions:

  • Why is interpretation slower than running compiled code? Every operation first inspects the syntax tree, checks the argument types and attaches type information to the result, so most of the time goes into deciding what to do.
  • What is the symbol table used for in an interpreter? It binds variable names to their current values (and function names to their declarations) while the tree is evaluated.

Chapter 6: Type Checking

Part 2 · Difficulty: Medium · Key topics: static and dynamic typing, strong and weak typing, attributes, type environments, function types, overloading, type conversion, implicit types

Some correctness rules, such as static type correctness, cannot be checked by a context-free grammar, so they are checked in a phase after parsing. The chapter separates static from dynamic and strong from weak typing, and places C, Java, SML, JavaScript, Scheme and machine code in that design space. For the example language of chapter 5 it type checks expressions with inherited attributes (the variable and function symbol tables) and a synthesised attribute (the type), then function declarations and whole programs, requiring main to have type int to int. A final section sketches assignments, data structures, overloading, type conversion and implicit types.

Key Points:

  • Static typing checks before execution and dynamic typing during execution; strong typing guarantees that operations get argument types they are defined for, while weak typing gives no such guarantee.
  • C is statically typed but not fully checked: a union can store an integer and read it back as a pointer.
  • Synthesised attributes pass up the syntax tree (the type of an expression); inherited attributes pass down (the symbol tables).
  • Function types are written like (int,bool) -> int, and variables and functions are kept in separate tables.
  • The error function returns, and the checker guesses a type to continue, so only the first reported error is fully trustworthy.
  • A program must contain a main function of type (int) -> int.
  • Overloading, type conversion and implicit types need extra machinery beyond the simple checker.

Memory Tip: Think of attributes as traffic on the tree: what a node learns about itself flows up (its type), and what it needs from outside flows down (the symbol tables).

Common Mistake: Mixing up static versus dynamic with strong versus weak. They are separate axes: C is static yet weak in places, while JavaScript is dynamic and silently converts strings to numbers.

Important Questions:

  • What is the difference between static and dynamic typing? Static typing checks types for the whole program before it runs; dynamic typing checks them while the program executes.
  • What is the difference between synthesised and inherited attributes? Synthesised attributes are computed from the children and passed up the tree, while inherited attributes are passed down from the parent or from earlier siblings.

Chapter 7: Intermediate-Code Generation

Part 2 · Difficulty: Hard · Key topics: intermediate language, syntax-directed translation, newvar, newlabel, conditions, sequential logical operators, arrays, records, declarations

Compilers usually translate the syntax tree to a machine-independent intermediate language first, which cuts the work from languages times machines to languages plus machines. The chapter defines a low-level intermediate language with labels, assignments, memory loads and stores, jumps, two-way conditionals and calls, and then writes translation functions for each syntactic category. Expressions are translated into a target variable called the place, statements use fresh labels for if and while, and conditions jump to one of two labels, so the sequential operators && and || become jumps. Further sections cover goto and break, floating-point values, arrays in row-major layout, strings, records and declarations.

Key Points:

  • With an intermediate language, n source languages and m machines need n front ends plus m back ends instead of n times m compilers.
  • The intermediate language has labels, assignment, unary and binary operations, memory transfers M[...], GOTO, a two-label IF-THEN-ELSE and CALL.
  • Translation functions use newvar() for fresh variables and newlabel() for fresh labels; names in italics are compile-time values inserted into the generated code.
  • A condition is translated into code that chooses between two inherited labels; to use it as a value, assign 0 first and 1 on the true path.
  • The sequential operators evaluate the second operand only when the first does not decide the result, which is why they turn into jumps.
  • Indexing an array multiplies the index by the element size and adds the base address, for example t := t * 4 then t := t + base.
  • The symbol table must store what later code needs: the variable for a scalar, the base address and dimensions for an array, the field offsets and total size for a record.

Practice Tip: Translate a small while loop by hand with the book’s functions, numbering labels as you go. Then check that every IF-THEN-ELSE is immediately followed by one of its target labels, which is the property chapter 8 relies on.

Common Mistake: Mixing compile-time and run-time work. The place variable, the labels and the operator names exist only inside the compiler, while the generated instructions run later.

Important Questions:

  • Why use an intermediate language? Only one translation from each source language and one back end per machine are needed, a compiled program can be shipped in one machine-independent form, and the intermediate code can even be interpreted.
  • How is a condition such as x < y && y < z translated? The first comparison jumps to the code for the second one when true and to the false label otherwise, and the second comparison jumps to the true or false label of the whole condition.

Chapter 8: Machine-Code Generation

Part 2 · Difficulty: Medium · Key topics: conditional jumps, constants, MIPS patterns, complex instructions, two-address instructions, optimisations

The intermediate language is close to RISC machine code but differs in four ways: it has unlimited variables, a complex CALL, a two-way IF-THEN-ELSE and arbitrary constants. This chapter handles the last two directly. A two-way branch becomes a conditional jump plus, when needed, an unconditional jump, and a branch whose next instruction is one of its labels can be negated or shortened. Large constants are built from several instructions. Using a subset of MIPS, instruction sequences are matched against patterns so that two intermediate instructions become one, such as a single load with an offset. Two-address instructions and a short survey of optimisations follow.

Key Points:

  • Registers are handled in chapter 9 and calls in chapter 10, which leaves conditional jumps and constants for this chapter.
  • IF c THEN lt ELSE lf becomes a branch to lt plus a jump to lf, and the jump is dropped when lf comes next.
  • Machines test conditions differently: a general register (MIPS, Alpha), special condition registers (PowerPC, IA-64) or arithmetic flags (IA-32, Sparc, PA-RISC, ARM).
  • MIPS operands hold only 16-bit constants, so a 32-bit constant takes two instructions; ARM constants are 8-bit values placed at even bit positions.
  • t2 := t1 + 116 followed by t3 := M[t2] can become one lw r3, 116(r1), but only if t2 is not used afterwards.
  • Two-address instructions overwrite one of their operands, so the generator may need an extra move.
  • Optimisations can work on the syntax tree, the intermediate code or the machine code; doing them on intermediate code lets all compilers sharing that language reuse them.

Practice Tip: Write the MIPS patterns for the load, store and arithmetic subset yourself, then apply the book’s prefix-matching idea to a three-line intermediate sequence. Swap two unrelated lines and watch the match change.

Common Mistake: Merging two instructions into one without checking that the temporary variable is dead afterwards. If the temporary is used later, the merged instruction has lost its value.

Important Questions:

  • How is a two-way conditional jump translated to machine code? As a conditional branch to the true label followed by a jump to the false label; the jump is omitted if the false label follows, and the condition is negated if the true label follows.
  • Why can MIPS not load an arbitrary 32-bit constant in one instruction? Instruction operands hold only 16-bit constants, so the upper half is loaded first and the lower half is combined with it in a second instruction.

Chapter 9: Register Allocation

Part 2 · Difficulty: Hard · Key topics: liveness, liveness analysis, interference graph, graph colouring, spilling, heuristics, coalescing moves

A processor has few registers, so register allocation maps many variables onto a small set and spills the rest to memory. The chapter defines a variable as live if its value may be used later, and turns the liveness rules into equations over in and out sets that are solved by fixed-point iteration on numbered instructions. Two variables interfere if one is assigned while the other is live, which gives an interference graph. Allocation is then graph colouring: a heuristic removes nodes with fewer than N neighbours and colours optimistically. Variables that cannot be coloured are spilled with load and store code and the process repeats, using heuristics for choosing spills and removing redundant moves.

Key Points:

  • A variable is live if its value might be used later; uses generate liveness, assignments kill it, and it propagates backwards.
  • Liveness uses successor sets succ[i] and equations for in[i] and out[i], iterated until nothing changes.
  • Variable x interferes with y if x and y differ and some instruction assigns x while y is in its out set, unless that instruction is the move x := y.
  • Graph colouring is NP-complete, so the allocator uses a heuristic: a node with fewer than N neighbours can always be coloured after the rest of the graph.
  • A node that cannot be coloured is spilled: it gets a memory address, each use and definition gets a local copy with a load or store, and allocation is redone.
  • Spill candidates are chosen by heuristics, such as nodes with close to N neighbours or variables that are cheap to spill, for example those not used inside loops.
  • Allocation can run on intermediate code or on machine code, and the allocator must keep a spare register for temporaries.

Practice Tip: Number the instructions of the chapter’s loop program, fill in the gen and kill table and iterate liveness by hand until it stops changing. Then draw the interference graph and colour it with three and with four colours.

Common Mistake: Deciding a graph cannot be coloured because no node has fewer than N neighbours. A square of four nodes has no node with fewer than two neighbours, yet it can be coloured with two colours, which is why the book colours optimistically before spilling.

Important Questions:

  • When can two variables share a register? When neither interferes with the other, that is, when there is no point in the program where one is assigned while the other is still live.
  • What is spilling? Keeping a variable in memory instead of a register when the interference graph cannot be coloured, with a load before each use and a store after each assignment.

Chapter 10: Function Calls

Part 2 · Difficulty: Hard · Key topics: call stack, activation record, frame pointer, prologue, epilogue, caller-saves, callee-saves, static link, call-by-reference, closures

Chapter 7 left calls as a single CALL instruction, and this chapter expands it. Recursion needs an unbounded number of variables, so only the active function’s variables stay in registers and the rest live on a call stack of activation records addressed through a frame pointer. The chapter builds a first frame layout with return address and parameters, then the prologue, epilogue and call sequence, compares caller-saves with callee-saves registers, passes the first few parameters in registers and links the register allocator to decide what must be saved. Later sections handle globals, call-by-reference, nested scopes, variable-sized frames, variable argument lists and functions as values.

Key Points:

  • Each invocation allocates an activation record (frame) on the stack; in the first layout the word at the frame pointer FP holds the return address.
  • The prologue loads parameters from the frame into variables; the epilogue stores the result and jumps to the return address.
  • Caller-saves means the caller saves registers before a call; callee-saves means the called function saves the registers it uses; real conventions often mix the two.
  • Usually 4 to 8 registers carry the first parameters, and the remaining parameters go on the stack.
  • The register allocator can say which registers are live across a call, so only those need saving.
  • With nested function declarations, as in Pascal and SML, a pointer to the enclosing function’s frame (the static link) is passed to the inner function.
  • A function passed as a value is a closure; if functions can be returned, the frame’s variables must be allocated on the heap.

Practice Tip: Draw the stack for a recursive call three levels deep using the layout in figure 10.1, marking FP, the return address and the incoming parameter in each frame, then step through the prologue and epilogue.

Common Mistake: Assuming a nested function finds its parent’s variables at a fixed distance on the stack. Recursive calls put other frames in between, which is why the static link is passed explicitly.

Important Questions:

  • What is an activation record? The chunk of stack memory allocated for one function invocation, holding the return address, parameters, saved registers and spilled variables.
  • What is the difference between caller-saves and callee-saves? In caller-saves the calling function preserves the registers it needs before the call, while in callee-saves the called function saves and restores the registers it uses.

Chapter 11: Analysis and Optimisation

Difficulty: Hard · Key topics: peephole optimisation, data-flow analysis, available assignments, common subexpression elimination, index-check elimination, code hoisting, inlining, tail calls, specialisation

An optimisation replaces a pattern of instructions with a smaller or faster one, often only when a condition about the surrounding code holds. Those conditions come from data-flow analyses that reuse the template of liveness analysis: successor or predecessor sets, gen and kill sets, in and out equations, and a fixed-point iteration. The chapter works out available-assignment analysis for common subexpression elimination, then jump-to-jump elimination and index-check elimination with inequalities. It explains why analyses must err on the safe side, and covers loop optimisation (hoisting and prefetching), inlining, tail-call optimisation and specialisation of calls such as power(x,5).

Key Points:

  • Liveness is a backwards analysis, with information flowing from uses to definitions; available assignments is a forwards analysis.
  • Every data-flow analysis has successors or predecessors, gen and kill sets, in and out equations, and an initialisation for the fixed-point iteration.
  • An assignment x := e becomes available unless x occurs in e, and it kills other assignments that mention x.
  • Index-check elimination collects inequalities from the IF conditions and removes a bounds check that those inequalities already guarantee.
  • Analyses are approximations that err on the safe side: missing an optimisation is acceptable, making an incorrect one is not.
  • Code hoisting moves loop-invariant computations out of a loop, but a hoisted memory access can fail if the loop would never have run.
  • A tail call, a call just before a return, can reuse the caller’s frame and skip its epilogue; specialisation computes the loop on n at compile time, so power(x,5) becomes power5(x).

Practice Tip: Take the chapter’s available-assignments example, change one instruction so that an assignment gets killed, and re-run the iteration to see which common subexpression is no longer removed.

Common Mistake: Treating an uncertain analysis answer as harmless in either direction. For liveness, doubt means live; for available assignments, doubt means not available. Guessing the other way produces wrong code.

Important Questions:

  • What is data-flow analysis? A family of analyses that discover how information flows through a program, using gen and kill sets and in and out equations solved by fixed-point iteration, so that optimisations can check conditions about the surrounding code.
  • What is a tail call and how is it optimised? A call placed just before a return; since no variables are live afterwards, the call sequence can be merged with the epilogue so the callee returns directly to the caller’s caller.

Chapter 12: Memory Management

Difficulty: Medium · Key topics: static allocation, stack allocation, heap allocation, malloc and free, free list, buddy system, reference counting, scan-sweep, two-space collection, generational collection

Arrays and records can live in static memory, on the stack or on the heap, and this chapter compares the three. Static allocation has a fixed size and address, stack allocation is fast and released when the function returns, and heap allocation needs a manager. The chapter builds malloc() and free() from a doubly linked free list, adds joining of freed blocks, and speeds up the search with power-of-two free lists and the buddy system. Automatic management follows: reference counting, scan-sweep tracing with a free list, two-space copying collection, and generational and concurrent refinements, ending with a comparison of the trade-offs.

Key Points:

  • Static allocation fixes size and address at compile time and keeps the memory for the whole run; in C all global variables are static.
  • Stack allocation is quick, since it only moves a pointer, and the memory is released automatically when the function returns.
  • A simple free list is a doubly linked list whose blocks hold a size and two pointers, so a block is at least three words.
  • In the buddy system block sizes are powers of two with one free list per size, and allocation time is logarithmic in the heap size.
  • Reference counting cannot collect circular structures, and a pointer assignment p := q costs four memory accesses.
  • Two-space (copying) collection allocates by moving a pointer, avoids fragmentation and spends time only on live blocks.
  • Generational collectors keep several spaces so that old and large blocks are copied less often.

Practice Tip: Draw the free list after each malloc and free in the chapter’s example, then repeat with the buddy system and compare how much space each one wastes.

Common Mistake: Believing reference counting frees everything that is unreachable. Two blocks that point to each other keep their counts above zero forever, so they are never freed.

Important Questions:

  • What is the difference between manual and automatic memory management? In manual management the programmer calls malloc() and free(), which is error-prone; in automatic management the runtime finds unused blocks itself, using reference counting or tracing collection.
  • How does two-space collection work? Live blocks are copied from the allocation area to a second space of at least the same size when memory runs out, then the roles of the two spaces swap, which removes fragmentation.

Chapter 13: Bootstrapping a Compiler

Difficulty: Medium · Key topics: T-diagrams, Bratman diagrams, half bootstrapping, full bootstrapping, quick-and-dirty compiler, porting a compiler

Bootstrapping answers the chicken-and-egg question of how to get a compiler for a new machine or language when you would prefer to write that compiler in the language it compiles. The chapter introduces Bratman diagrams, also called T-diagrams, for compilers, interpreters, machines and unspecified programs, with the rule that languages must match at every connection. Half bootstrapping uses an existing compiler on another machine, such as an ML compiler running on ARM, to build a compiler for a new target. Full bootstrapping starts from a quick-and-dirty compiler or interpreter, uses it to compile the real compiler, and then recompiles the real compiler with itself for speed.

Key Points:

  • In a T-diagram a compiler shows its source language on the left, its target language on the right and its implementation language at the bottom.
  • At every connection the languages must match, and a program must stand on something that can run it, down to a real machine.
  • Half bootstrapping relies on an existing compiler for the language that runs on a different machine.
  • Full bootstrapping is needed when no compiler exists yet: write a quick-and-dirty (QAD) compiler or interpreter in an existing language first.
  • Compiling the real compiler with itself gives a faster compiler with the same functionality, because it is no longer built by the QAD compiler.
  • A compiler with the right functionality may still not run on the machine it targets, so bootstrapping can be incomplete.

Practice Tip: Redraw the book’s M+ example on paper with a different colour for each language. If a language label does not match at a joint between two shapes, the diagram is wrong.

Common Mistake: Skipping the final self-compilation step. The compiler built with the QAD compiler works but runs slowly; compiling it with itself produces the same output faster.

Important Questions:

  • What is bootstrapping? Writing a compiler in the language it compiles and then using a compiler for that language, or a quick-and-dirty one, to compile it, so that the finished compiler compiles itself.
  • What is the difference between half and full bootstrapping? Half bootstrapping uses an existing compiler for the language that runs on another machine; full bootstrapping is used when no compiler exists and one must first be written in another language.

Appendix A: Set Notation and Concepts

Appendix · Difficulty: Easy · Key topics: sets, membership, union, set-builder notation, sets of sets, set equations, monotonic functions, distributive functions

The book uses set notation and set equations throughout, for NFAs, FIRST and FOLLOW sets, liveness and other data-flow analyses, so this short appendix refreshes the basics. A set is written by listing its elements, and neither order nor repetition matters. The appendix covers membership, the empty set, union and the properties of set operations. It then introduces set-builder notation and sets of sets, and ends with set equations: solving them by fixed-point iteration, why monotonic functions guarantee a solution, how distributive functions allow a faster work-list method, and how to handle simultaneous equations.

Key Points:

  • The sets {2, 1, 3} and {2, 1, 2, 3, 1, 1} are the same set, because order and repetition do not matter.
  • x in M tests membership, and “select x in M” picks an arbitrary element of the set.
  • The union of two sets contains all elements from both.
  • Set-builder notation describes a set by a property that its elements satisfy.
  • A set equation can be solved by starting from the empty set and iterating until the set stops growing, which is guaranteed to end for monotonic functions on finite sets.
  • Distributive functions allow a work-list algorithm that is faster than plain iteration.

Practice Tip: Compute the epsilon-closure of one NFA state as a set equation, writing out every iteration. It is the same pattern the book later uses for FIRST, FOLLOW and liveness.

Common Mistake: Treating a set like a list. When you test whether an iteration has stopped, {a, b} and {b, a, a} are equal, so compare contents, not order or length of what you wrote down.

Important Questions:

  • What is a set equation? An equation in which a set is defined in terms of itself through a function, such as X = F(X); its solution is a fixed point.
  • How is a set equation solved? Start with the empty set, apply the function repeatedly and stop when the result no longer changes; monotonic functions make this reach a fixed point.

How to Study This Book

The book has 13 chapters and one appendix, and it is designed to be read in order. Section 1.5 divides it into a first part (chapters 2 and 3, reading program text) and a second part (chapters 4 to 10, the middle and back end of interpreters and compilers), followed by optimisation, memory management and bootstrapping in chapters 11 to 13. Read Chapter 1 in an evening, because it gives the map of phases that every later chapter refers to.

Chapters 2 and 3 are the heaviest part of a first compiler course. Chapter 2 builds on regular expressions, NFAs and DFAs, so go through the subset construction in Section 2.6 slowly and redo the worked example on paper. Chapter 3 is the longest chapter at about 60 pages. Study Sections 3.1 to 3.13 for grammars, ambiguity and LL(1) parsing first, and only then move to the SLR sections 3.14 to 3.17. The book prints suggested exercises inside the text, and doing those as you go is more useful than saving all exercises for the end.

Chapters 4, 5 and 6 are short, between 8 and 14 pages each, so they go quickly. Chapters 5 and 6 use the same small functional language, defined by grammar 5.1 in Section 5.3, so read them together and keep that grammar open while you work. If sets, fixed points or monotonic functions feel unfamiliar, read Appendix A before Section 2.6, because the same idea returns in FIRST and FOLLOW, in liveness and in every analysis of chapter 11.

Chapters 7 to 10 form the back end and depend on each other, so do not skip around. Chapter 7 defines the intermediate language that chapters 8, 9 and 10 all use. Chapter 9 needs the fixed-point iteration from Chapter 2 and gives you liveness, which chapter 11 reuses. Chapter 10 needs the idea of spilling from chapter 9 before the caller-saves and callee-saves discussion makes sense. Expect to spend the most time on chapters 3, 7 and 9.

Chapters 11, 12 and 13 can be treated as separate units. Chapter 11 is worth reading if your course covers optimisation, and it is easy once you have done liveness. Chapter 12 stands almost alone and pairs well with an operating systems course. Chapter 13 is only about 10 pages, and T-diagrams are easy to practise on paper. The book never gives you a complete working compiler in one programming language: it uses small example languages and algorithm sketches, so pair it with a lexer and parser generator project from your course.

What the book does not cover is also worth knowing. Assembly and linking are left out on purpose, there is no SSA form or LLVM, just-in-time compilation is only mentioned briefly, and parser generators are described in general terms rather than as a tutorial for one tool. The author’s page offers solutions to selected exercises and a list of known misprints, which are worth keeping open while you read.


Used In These Programs

This book is used for the Compiler Construction course in: BS Computer Science. Browse all Compiler Design books or all Computer Science books.

Who Should Read This

This book is written for BSCS students taking a first Compiler Construction or Compiler Design course. It was created for the introductory compiler course at the University of Copenhagen, first taught soon after the first programming course and later moved to the second year, so it assumes comfort with recursion, trees and basic data structures but no earlier compiler knowledge. It also suits self-learners who want to write an interpreter or a small domain-specific language, because the front-end chapters apply to any structured text. It is not the right book if you need production-level detail such as SSA form or LLVM, or a full working compiler to copy. For the memory chapter, Think OS and Operating Systems: Three Easy Pieces explain how processes and virtual memory look from the operating-system side, and Open Data Structures covers the hash tables behind fast symbol tables.


Applicable Universities

This book is useful for students at Pakistani universities offering BS Computer Science with a compiler construction course, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.

Official Copy of Basics of Compiler Design

The author offers the complete 2010 book as a free PDF on his homepage at the University of Copenhagen, together with solutions to selected exercises and a list of known misprints. Click below to open the official page and download the PDF.

→ Visit Official Page

FAQs

Is Basics of Compiler Design free?

Yes. The author makes the full PDF free to download from his page at the University of Copenhagen. It is not under an open licence: the book says that copying and printing for personal use is permitted, and that a lecturer may print copies for students at printing cost. Selling it for profit needs the author’s agreement, so use the official page rather than reposting the file.

Which edition is this?

This is the Anniversary Edition dated 20 August 2010, ten years after the first edition of 2000. The chapter on analysis and optimisation was added in 2008, the chapter on interpretation in 2009, and the memory management chapter and Appendix A in 2010. The author’s page says the 2010 edition will not be updated further.

How many chapters and exercises does it have?

There are 13 chapters and one appendix. Chapter 1 has no exercises, and Chapters 2 to 13 plus Appendix A have 96 exercises in total, with Chapter 3 on parsing having the most at 22. The author’s page also offers solutions to selected exercises.

Is it good for complete beginners?

It is written for students who have finished an introductory programming course, so you should be comfortable with recursion, trees and basic data structures. No earlier compiler knowledge is needed. The theory in Chapters 2 and 3 uses set notation and fixed-point iteration, and Appendix A is there to refresh those ideas.

Does it cover lexical analysis, parsing, register allocation and garbage collection?

Yes. Chapter 2 covers regular expressions, NFAs, DFAs and lexer generators, Chapter 3 covers context-free grammars, LL(1) and SLR parsing, Chapter 9 covers register allocation by graph colouring, and Chapter 12 covers reference counting, scan-sweep and copying garbage collection.

Is it still current in 2026?

The fundamentals are. Lexing, parsing, type checking, intermediate code, register allocation and garbage collection are taught the same way today. What shows its age is the machine side: examples use MIPS and other processors of that period, there is no SSA form or LLVM, just-in-time compilation is only mentioned briefly, and tools such as Lex and ANTLR appear only in passing. Use it for the ideas and add current tool documentation from your course.

Related Books

Basics of Compiler Design gives you the whole compiler pipeline in one free, language-neutral book, from regular expressions to bootstrapping. Browse more Computer Science books for the rest of your semester.

Basics of Compiler Design (Anniversary Edition, 20 August 2010) by Torben Ægidius Mogensen, Department of Computer Science, University of Copenhagen (DIKU). Copyright Torben Ægidius Mogensen 2000–2010, ISBN 978-87-993154-0-6. The author permits copying and printing for personal use and offers the PDF free on his homepage. Official source: https://hjemmesider.diku.dk/~torbenm/Basics/. This page links to the official site and does not host or copy the book.

Leave a Comment