Yongkang Liu

Principles of Compilation

Course Detail

Principles of Compilation

This course introduces the complete workflow of a compiler, from source language analysis to optimized target code generation. It combines formal concepts with implementation practice so that students can understand both the theory and the engineering pipeline.

Back to Teaching
Audience Undergraduate students in computer science
Format Lecture + programming exercises
Goal Build a systematic understanding of compiler construction

Lecture Schedule

Lecture 1

Introduction to Compilers and Language Translation

What compilers do, the phases of compilation, interpreters vs. compilers, and representative programming languages.

References: Aho et al., Ch. 1; Appel, Ch. 1.

Lecture 2

Formal Languages and Lexical Analysis

Regular expressions, finite automata, tokenization, and how lexical analyzers are designed and implemented.

References: Aho et al., Ch. 2-3; flex documentation.

Lecture 3

Context-Free Grammars and Parsing Basics

BNF, derivation, parse trees, ambiguity, and the relationship between syntax design and parsing complexity.

References: Aho et al., Ch. 4; Grune and Jacobs, selected sections.

Lecture 4

Top-Down Parsing

Recursive descent, FIRST/FOLLOW sets, LL(1) parsing, and grammar transformation techniques.

References: Aho et al., Ch. 4; lecture notes on LL parsing.

Lecture 5

Bottom-Up Parsing

Shift-reduce parsing, LR ideas, SLR/LALR concepts, and practical parser generators.

References: Aho et al., Ch. 4; yacc/bison tutorials.

Lecture 6

Syntax-Directed Translation

Syntax-directed definitions, attributed grammars, semantic actions, and constructing syntax trees.

References: Aho et al., Ch. 5.

Lecture 7

Semantic Analysis and Symbol Tables

Scope, type checking, symbol management, declaration-use chains, and semantic constraints in programming languages.

References: Aho et al., Ch. 6; Appel, semantic analysis chapters.

Lecture 8

Intermediate Representations

Abstract syntax trees, three-address code, control-flow graphs, and the role of IR in optimization.

References: Aho et al., Ch. 6-8; Cooper and Torczon, IR chapters.

Lecture 9

Run-Time Environments

Activation records, procedure calls, parameter passing, stack management, and memory layout.

References: Aho et al., Ch. 7; Appel, run-time environment chapters.

Lecture 10

Code Generation Fundamentals

Instruction selection, addressing modes, evaluation order, and target-machine considerations.

References: Aho et al., Ch. 8; Muchnick, code generation overview.

Lecture 11

Local Optimization

Constant folding, common subexpression elimination, dead code elimination, and peephole optimization.

References: Aho et al., Ch. 8-9; Muchnick, optimization basics.

Lecture 12

Data-Flow Analysis

Reaching definitions, liveness, available expressions, and iterative data-flow frameworks.

References: Aho et al., Ch. 9; Cooper and Torczon, data-flow analysis chapters.

Lecture 13

Register Allocation

Interference graphs, graph coloring, spilling, and trade-offs in resource-constrained code generation.

References: Appel and George, register allocation; Muchnick, relevant chapter.

Lecture 14

Optimization for Modern Architectures

Instruction scheduling, machine dependence, and practical issues when targeting realistic hardware.

References: Muchnick, advanced optimization sections.

Lecture 15

Mini Compiler Project Workshop

Integrating lexer, parser, semantic analyzer, and code generator into a small end-to-end compiler.

References: Project handout; flex/bison examples; LLVM Kaleidoscope tutorial.

Lecture 16

Course Review and Frontiers

Compiler infrastructure, domain-specific languages, JIT compilation, and connections to modern AI systems.

References: LLVM documentation; selected survey readings.

Core References

  • Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools.
  • Andrew W. Appel. Modern Compiler Implementation.
  • Keith D. Cooper, Linda Torczon. Engineering a Compiler.
  • Steven S. Muchnick. Advanced Compiler Design and Implementation.

Assignments and Assessment

  • Homework: Regular exercises on automata, grammars, parsing, semantic analysis, and optimization.
  • Programming Project: Build a mini compiler or implement key modules such as a lexer, parser, or intermediate-code generator.
  • Class Participation: In-class discussion on design trade-offs in compiler construction.
  • Final Assessment: Written exam or project presentation, depending on course arrangement.

Lecture Slides and Course Materials

  • Lecture 1-4 slides: to be uploaded
  • Lecture 5-8 slides: to be uploaded
  • Lecture 9-12 slides: to be uploaded
  • Lecture 13-16 slides: to be uploaded
  • Programming assignment handouts: to be uploaded

You can later replace these placeholders with direct PDF, PPT, or ZIP download links.