This course will be discontinued.
Last planned examination: Autumn 2024
Decision to discontinue this course:
The course will be discontinued at the end of HT 2024 according to the Head of school decision: J-2023-1526.
Decision date: 2023-06-12
The course was given for the last time in Autumn 2022. The last opportunity for examination in the course is given in Autumn 2024.
Students who wish to complete the course after it has been given for the last time should contact the examiner.
A compiler is a large and fascinating piece of software. In order to construct a compiler one must master complex algorithms and data structures, syntax analysis, and details of the target platform's architecture and instruction set.
Once you have understood how a compiler works, not only will you be able to construct your own compiler, but you will also realize why existing programming languages are designed the way they are and what limitations exist when designing a computer language.
The major assignment in this course is the construction of a compiler for a small but powerful language.
Content and learning outcomes
Describing programming languages and other formal languages using regular expressions and grammars.
Methods for lexical and syntax analysis and their relationships to models of computation such as finite automata and pushdown automata. Syntax analysis using LL and LR parsing. Tools such as scanner and parser generators.
Semantic analysis, translation into intermediate code, instruction selection and register allocation.
Intended learning outcomes
The student should be able to
- explain the steps involved in the compilation process, from source code to target code,
- understand a given grammar or regular expression and determine which strings belong to the corresponding formal language,
- write regular expressions and grammars for various formal languages, such as programming languages,
- choose an appropriate formal notation to describe a given formal language,
- explain LL-analysis and LR-analysis,
- use scanner and parser generators,
- explain the aspects of the architecture of a computer or a virtual machine relevant to a compiler,
- write programs that perform various steps of the compilation process.
Literature and preparations
Single course students:
SF1671 Mathematics, Basic course, with Discrete Mathematics, DD1337 Programming, DD1338 Algorithms and Data Structures, DD1352 Algorithms, Data Structures and Complexity, IS1200 Computer Hardware Engineering or corresponding courses
Working knowledge of Java. IS1200 Computer Hardware Engineering and DD1352 Algorithms, Data Structures, and Complexity or similar courses.
Examination and completion
If the course is discontinued, students may request to be examined during the following two academic years.
- PRO1 - Project, 5.0 credits, grading scale: A, B, C, D, E, FX, F
- TEN1 - Examination, 4.0 credits, grading scale: A, B, C, D, E, FX, F
Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.
The examiner may apply another examination format when re-examining individual students.
Opportunity to complete the requirements via supplementary examination
Opportunity to raise an approved grade via renewed examination
- All members of a group are responsible for the group's work.
- In any assessment, every student shall honestly disclose any help received and sources used.
- In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.
Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.Course web DD2488
Main field of study
This course cannot be counted in the degree if the student has taken ID1215 or ID2202.
This course is given if we have enough with teaching resources.
In this course, the EECS code of honor applies, see: