DD2488 Compiler Construction 9.0 credits

Kompilatorkonstruktion

Please note

The information on this page is based on a course syllabus that is not yet valid.

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.

  • Education cycle

    Second cycle
  • Main field of study

    Computer Science and Engineering
  • Grading scale

    A, B, C, D, E, FX, F

Course offerings

Autumn 18 komp18 for programme students

Autumn 19 komp19 for programme students

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.

Course main content

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.

Eligibility

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

Recommended prerequisites

Working knowledge of Java. IS1200 Computer Hardware Engineering and DD1352 Algorithms, Data Structures, and Complexity or similar courses.

Literature

I en liknande kurs användes: A.W. Appel, Modern compiler implementation in Java, second edition.

Examination

  • PRO1 - Project, 5.0, grading scale: A, B, C, D, E, FX, F
  • TEN1 - Examination, 4.0, grading scale: A, B, C, D, E, FX, F

In this course all the regulations of the code of honor at the School of Computer science and Communication apply, see: http://www.kth.se/csc/student/hederskodex/1.17237?l=en_UK.

Offered by

EECS/Computer Science

Contact

Philipp Haller (phaller@kth.se)

Examiner

Philipp Haller <phaller@kth.se>

Supplementary information

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.

Version

Course syllabus valid from: Spring 2019.
Examination information valid from: Spring 2019.