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(s):  Timo Kehrer
• Assistant(s):  Jan-Andrea Bard
• Material:  ILIAS
• Podcast:  ILIAS
• Registration:  Academia
• Language: English
• Course repetition: Spring Semester 2026

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örsaal 2 002, Engehalde, E8
• Exercises: Tuesdays 16:15 - 17:00,  Hörsaal 2 002, Engehalde, E8

Exam

• Date: Friday, 6^th June 2025, 10:00 - 11:30
• Location:  Raum 001, Engehalde, E8
• Type: Written Exam
• Registration:  Academia

Repetition exam

• Date: TBA
• Location: TBA
• Type: TBA
• Registration:  Academia