An Overview of Introduction to Compilers and Language Design

This resource is authored by Douglas Thain of the University of Notre Dame. Beyond this textbook, you can explore his other professional contributions via his links to [About], [Teaching], [Research], [Papers], [Talks], [Service], [Blog], and [Lab].

What is a Compiler?

At its core, a compiler is a tool that performs a transformation:

A compiler translates a program written in a high-level language into a program written in a lower-level language.

Mathematically, we can view this as a function $f$: $\text{Source Code}_{\text{HighLevel}} \xrightarrow{f(\text{compiler})} \text{Target Code}_{\text{LowLevel}}$

For those studying computer science, creating a compiler from the ground up is considered a rite of passage. It is a rewarding yet demanding endeavor that bridges the gap between abstract theory and pure practice—it is, in fact, both.

Course Objectives & Prerequisites

The goal of this text is to provide a one-semester guide to compiler construction. By the end, readers will be capable of developing a basic compiler that converts a C-like language into functional X86 or ARM assembly.

Student Readiness Checklist

To get the most out of this material, students should have completed the following:

• Proficiency in the C programming language.
• Completion of a Data Structures course.
• Understanding of Computer Architecture.

Publication Details

The current version is the 2nd Edition (2020), with the most recent revision dated January 15, 2021.

---

Access and Distribution

The author provides permission for these PDFs to be printed, downloaded, and utilized for academic or personal purposes. However, to ensure students always have the most current version:

Download and save PDFs locally $\rightarrow$ Direct students to compilerbook.org.

Curriculum Roadmap

The book is structured to lead the reader through the various stages of compilation. The following diagram illustrates the conceptual flow of the chapters:

Table of Contents

• Front Matter: Chapter 0
• Foundations: Chapter 1 (Introduction) & Chapter 2 (Quick Tour)
• The Frontend:
  • Chapter 3: Scanning
  • Chapter 4: Parsing
  • Chapter 5: Parsing in Practice
  • Chapter 6: The Abstract Syntax Tree
• The Middle-end:
  • Chapter 7: Semantic Analysis
  • Chapter 8: Intermediate Representation
  • Chapter 9: Memory Organization
• The Backend:
  • Chapter 10: Assembly Language
  • Chapter 11: Code Generation
  • Chapter 12: Optimization
• Appendices:
  • Appendix A: Sample Course Project
  • Appendix B: The B-Minor Language
  • Appendix C: Coding Conventions

Supplemental Materials

To support the learning process, the compilerbook-examples GitHub repository is available. This repository includes:

1. Various parsers and scanners.
2. A foundational code structure for the project compiler.
3. Comprehensive test suites for the following stages:
   • scanner
   • parser
   • typechecker
   • code_generator

Example Code Structure

A typical entry in the project might look like this:

// Sample C-like structure for B-Minor
int main() {
    int x = 10;
    return x + 5;
}

Feedback and Corrections

If you spot an error, please notify the author.

• Email: dthain@nd.edu
• Subject Line: Compiler Book Errata

The author will correct the mistake and provide acknowledgment in the subsequent edition.