2025 (Current Year) Faculty Courses School of Computing Undergraduate major in Mathematical and Computing Science
Compiler Construction
- Academic unit or major
- Undergraduate major in Mathematical and Computing Science
- Instructor(s)
- Yasuhiko Minamide
- Class Format
- Lecture (Face-to-face)
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 5-6 Tue (M-B104(H103)) / 5-6 Fri (M-B104(H103))
- Class
- -
- Course Code
- MCS.T334
- Number of credits
- 200
- Course offered
- 2025
- Offered quarter
- 4Q
- Syllabus updated
- Mar 19, 2025
- Language
- Japanese
Syllabus
Course overview and goals
This course introduces the fundamental concepts on programming languages, and explains how programs are executed on computers and how a compiler works. In order to deepen understanding of concepts and theory, students do programing assignments on compilers by using the programming language Scala.
Course description and aims
By the end of this course, students will be able to:
1. Explain how programs are executed on computers.
2. Explain, for each component of a compiler, what it is for, how it works, and what algorithms it uses.
3. Implement an interpreter and a compiler for simple programming languages.
Keywords
interpreter, compiler, parsing, code generation, register allocation, garbage collection
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
Students learn theories and techniques through lectures and obtain programming skills through programming exercises.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | Overview: how is a program executed |
interpreter, compiler, bytecode compiler |
| Class 2 | Automata and lexical analysis |
token, regular expression, NFA, DFA |
| Class 3 | Review on context-free grammars |
derivation, parse tree, CYK algorithm |
| Class 4 | Parsing (1): predictive parsing |
Recursive descent parsing, LL(1) |
| Class 5 | Parsing (2): basic LR parsing |
LR(0) |
| Class 6 | Parsing (3): extensions of LR parsing |
SLR, LR(1) |
| Class 7 | Type systems and type checking |
Type systems, polymorphism, subtyping, type checking |
| Class 8 | Mid-term exam |
Test level of understanding |
| Class 9 | Semantics of programming languages and interpreter |
evaluation strategy, operational semantics, interpreter |
| Class 10 | Code generation (1): overview, assembly language |
assembly language, X86-64, calling convention |
| Class 11 | Code generation (2): intermediate language, translation to intermediate language and assembly language |
3 address code, translation to intermediate language and assembly language |
| Class 12 | Liveness analysis and register allocation |
data flow analysis, live variables, interference graph, graph coloring |
| Class 13 | Register allocation and code generation |
Precolored nodes, coalesce |
| Class 14 | Garbage collection |
mark and swap collection, copying collection |
Study advice (preparation and review)
To enhance effective learning, students are encouraged to spend approximately 100 minutes preparing for class and another 100 minutes reviewing class content afterwards (including assignments) for each class.
They should do so by referring to textbooks and other course material.
Textbook(s)
None required
Reference books, course materials, etc.
Course materials are provided during class.
The following is reference books related to this course.
Modern Compiler Implementation in Java, Andrew W. Appel．
Compilers: Principles, Techniques, and Tools, Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
Evaluation methods and criteria
Assessment is based on the score of mid-term exam and programming.
Related courses
- MCS.T224 ： Programming I
- MCS.T303 ： Programming II
- MCS.T214 ： Theory of Automata and Languages
- MCS.T233 ： Computer Systems
Prerequisites
Students require the knowledge of automata， context-free grammars, and assembly languages.
Students require to be able to write programs in Scala.
Students need to work on programming exercises on their PC (Mac, Windows, Linux).