Compiler Construction
About this course
Programs that run on a computer are written in a computer language, and the languages used for writing computer programs have significantly evolved over time. By abstracting from the details of the underlying computer architecture, higher-level languages aim at making the process of developing a program simpler and more understandable than when using a lower-level language. Modern languages offer us a variety of different concepts for expressing (executable) programs. Domain-specific (modeling) languages are even created specifically to solve problems in a particular domain of interest. However, programs written in a higher-level language must be translated into a lower-level, executable representation, which requires various forms of compilers doing this job for us.
This course will provide students with an introduction to modern compiler construction. The first two-thirds of the course will cover classical topics ranging from scanning and parsing over semantic analysis and interpretation to code generation and optimization. In the exercises, we will develop a fully functional interpreter for our own programming language. The remaining third of the course is dedicated to study the transition form classical compiler techniques into principles of model-driven software development. In the exercises, we will develop a fully functional, domain-specific modeling environment.
Organisation
- Lecturer: Timo Kehrer
- Instructor (Exercises): Sandro Hernández Goicochea
- Material: ILIAS
- Podcast: ILIAS
- Registration (for Bachelor’s Students): KSL
- Registration (for Master’s Students): Academia
- Registration: Academia
- Language: English
- Course repetition: Spring Semester 2027
Prerequisites
Students should have basic programming skills with proficiency in at least one programming language, a solid understanding of algorithms and data structures, and foundational knowledge in discrete mathematics.
Learning outcomes
By the end of the course, students will be able to:
- Explain the architecture and purpose of compilers, differentiating between different types, and contrasting compilers with interpreters.
- Design and implement lexical analyzers by hand, understanding the roles of lexemes and tokens and applying appropriate error-handling techniques.
- Understand the roles of lexemes and tokens, and use regular expressions and finite automata to specify lexical patterns.
- Employ scanner generators to automatically construct scanners, and implement lexical analyzers by hand.
- Understand and apply the theory of context-free grammars, including their representations in BNF and EBNF, for specifying the syntax of programming languages.
- Construct syntax trees from grammar definitions, implement predictive top-down parsers following the recursive descent method.
- Understand and apply parser generation techniques, including LL(1) and LR (LR(0), SLR, LALR) methods, using tools that implement table-driven parsing strategies.
- Define and implement semantic analysis routines, including symbol table management, and syntax-directed translation for intermediate code generation.
- Generate and optimize intermediate and machine-level code, applying key techniques like register allocation and liveness analysis to enhance runtime performance.
Why should I take this course?
The magic of computer languages:
- Ever wanted to make your own programming language or wondered how they are designed and built?
- If so, this is already enough. But there are also very practical reasons:
Little languages are everywhere:
- Even if you will most likely not be faced with the task of implementing a fully-fledged compiler in your professional life, there is a good chance you will find yourself in need of writing a parser in order to process various documents written in tiny little languages.
Domain-specific Languages and Model-driven Development
- There has been a hype on DSLs and Model-driven development in the past, and larger software development projects in various domains successfully adopted these paradigms.
- Building sophisticated model-driven software engineering environments is the backbone of running these projects.
Schedule
- Lectures: Tuesdays 14:15 - 16:00, Hörraum 106, Hauptgebäude H4
- Exercises: Tuesdays 16:15 - 17:00, Hörraum 106, Hauptgebäude H4
| Date | Lecture Topic | Exercise Topic |
|---|---|---|
| 17-02-26 | Introduction | Ex01: Warm-Up - Stack and Syntree |
| 24-02-26 | – No class – | (additional time to work on Ex01) |
| 03-03-26 | Lexical Analysis: Handwritten Scanners | Ex02: A Handwritten Scanner |
| 10-03-26 | Lexical Analysis: Scanner Generators | Ex03: A Generated Scanner |
| 17-03-26 | Syntax Analysis: Grammars and Syntax Trees | Ex04: Grammar and Syntax Tree for SPL' |
| 24-03-26 | Syntax Analysis: Top-Down Parsing | Ex05: A Handwritten Parser |
| 31-03-26 | Syntax Analysis: Parser Generators | Ex06: A Generated Parser – JavaCC Continued |
| 07-04-26 | – No class – | (additional time to work on Ex05 and Ex06) |
| 14-04-26 | Excursus: LR Parsing | Wrap-Up on Ex05 |
| 21-04-26 | Semantic Analysis and Interpretation (I) | Wrap-Up on Ex06 |
| 28-04-26 | Semantic Analysis and Interpretation (II) | Ex07: A Tree-Walk Interpreter |
| 05-05-26 | PEGs, Packrats and Parser Combinators (Guest Lecture by Oscar Nierstrasz) | (additional time to work on Ex07) |
| 12-05-26 | Code Generation and Optimization | (additional time to work on Ex07) |
| 19-05-26 | Beyond Classical Compiler Construction: Modeling Language Engineering | Wrap-Up on Ex07 |
| 26-05-26 | Q&A |
Exam
- Date: TBA
- Location: TBA
- Type: TBA
- Registration (for Bachelor’s Students): KSL
- Registration (for Master’s Students): Academia