Introduction to Compiler Design

Introduction to Compiler Design is a textbook is intended for an introductory course on compiler design, suitable for use in an undergraduate programme in computer science or related fields.

The book presents techniques for making realistic, though non-optimising compilers for simple programming languages using methods that are close to those used in "real" compilers, albeit slightly simplified in places for presentation purposes. All phases required for translating a high-level language to machine language is covered, including lexing, parsing, intermediate-code generation, machine-code generation and register allocation. Interpretation is covered briefly.

The book aims to be neutral with respect to implementation languages, so algorithms are presented in pseudo-code rather than in any specific programming language, and suggestions for implementation in several different language flavours are in many cases given. The techniques are illustrated with examples and exercises.

The author has taught compiler design at the University of Copenhagen for over a decade, and the book is based on material used in the undergraduate compiler design course there.

Additional material for use with this book is available below. More material will be added later.

Publication details

Introduction to Compiler Design is published by Springer Verlag, and is now in its third edition (since December 2023).

Read more at Springer Verlag's page.

Material for the first edition can be found here.

Lecture slides

Cosmin Oancea from DIKU, who uses the book in a course, has made his slides available. They do not follow the book exactly, and there are some assignment-specific material, but they may be a good starting point for making your own.

Solutions to selected exercises

solutions.pdf

There is an overweight of solutions to exercises from Chapters 1--2. This might be remedied later.

Known misprints in the 2nd edition

Only significant misprints are reported, misspellings and such are left for the reader to figure out.

• Page 42: Change "denotes itself as a nonterminal" to "denotes itself as a terminal" near the top of the page.
• Page 57: The last two lines in the reductionj of Nullable(T) should be

    = Nullable(R) \/ (false /\ Nullable(T) /\ false)
    = Nullable(R)

• Page 67: In Figure 2.18: In the function parseR, two occurences of tNode('R' should be replaced by nNode('R'.
• Page 77: In Figure 2.27: The last three lines of the "reduce p" should read

    let go s = table[top(stack),n] ;
    push(n,stack) ;
    push(s,stack)
  

  instead of

    push(n,stack) ;
    push(s,stack)
        where table[top(stack),n] = go s
  

  as the stack has to be read before pushing n.

  Alternatively, just wrap the two pushes in parentheses, so it is clear that the where-clause covers both.

• Page 79: In Figure 2.32, the state containing only G should not be marked as a final state (doubly circled).
• Page 153, Exercise 6.4: Some negation symbols got lost in the publication process. De Morgan's law should state that !(p||q) is equivalent to (!p)&&(!q).

Known misprints in the 3rd edition

Only significant misprints are reported, misspellings and such are left for the reader to figure out.

• Page 111 (Fig. 4.3): Add "else error()" after "then v₁" in the code for function calls.
• Page 166: Delete the sentence "Note, also, that we need (at least) two instructions from our RISC-V subset to implement an IF-THEN-ELSE instruction that uses < as the relational operator, while we need only one for comparison by =." (near the bottom of the page).
• Page 167: On the right-hand-side of the third-to-last entry in the table, label_f occurs twice. The second occurrence should be label_t. The two registers should also be swapped, so the instruction reads   bge  r_s, r_t,  label_f . Also, the label definitions in this entry and the entry above should not be indented.