DD2488 Compiler Construction 9.0 credits

Kompilatorkonstruktion

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.

Show course information based on the chosen semester and course offering:

Offering and execution

No offering selected

Select the semester and course offering above to get information from the correct course syllabus and course offering.

Course information

Content and learning outcomes

Course contents *

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.

Course Disposition

No information inserted

Literature and preparations

Specific prerequisites *

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.

Equipment

No information inserted

Literature

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

Examination and completion

Grading scale *

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

Examination *

  • 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.

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.

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Philipp Haller

Further information

Course web

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

Offered by

EECS/Computer Science

Main field of study *

Computer Science and Engineering

Education cycle *

Second cycle

Add-on studies

No information inserted

Contact

Philipp Haller (phaller@kth.se)

Ethical approach *

  • 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.

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.


In this course, the EECS code of honor applies, see:
http://www.kth.se/en/eecs/utbildning/hederskodex