Compilers and Execution Environments

Innehåll visas utifrån dina val

Om du inte hittar någon sida, schemahändelse eller nyhet på din kurswebb kan det bero på att du inte ser den kursomgången/gruppen inom kursen som innehållet tillhör.

Veta mer om din kurswebb

Din kurswebb är sidorna för en kurs du prenumererar på. Du väljer sedan vilka omgångar/grupper inom kursen du vill ha information från. Är du registrerad på en kursomgång sköts prenumeration och val av kursomgäng automatiskt åt dig. Vill du ändra något av detta gör du det under Mina inställningar.

När du är inloggad på din kurswebb ser du:
  • Kursöversikt, nyheter och schema med information som är filtrerat utifrån dina valda omgångar/grupper inom kursen
  • Allmänna sidor för hela kursen
  • Kurswikin som är sidor som alla, lärare och studenter, kan skapa och redigera
  • Sidor som hör till de omgångar/grupper inom kursen du valt eller som valts för dig

Log in to your course web

You are not logged in KTH, so we cannot customize the content.

The course covers techniques for the implementation of programming languages using compilers in both real and virtual execution environments.


The overall aim of the course is to provide an understanding of how a programming language is implemented including common theories and how these theories are applied. The course will cover techniques for reading, understanding, translating, improving, and executing programs.

This understanding means that after the course a student should be able to:

  • explain the overall structure of a compiler.
  • describe regular expressions and finite automata and use them unambiguously for lexical analysis; combine and apply techniques to construct a deterministic finite automaton from regular expressions.
  • describe context free grammars and apply them to capture common programming language constructs; describe the basic approach of top-down and bottom-up parsing; construct recursive descent, LL(1), LR(0), and SLR parsers; identify whether grammars can be used with a given parsing technique.
  • list and describe tasks carried out during semantic analysis.
  • describe the design principles behind intermediate program representations; explain and apply methods for selecting instructions; describe the organization of activation records and identify the impact of different design decisions for activation records on program execution.
  • define the liveness of variables and compute liveness information from control flow graphs; define the principles of conservative approximations for analyzing programs; construct interference graphs and perform complete register allocation on them reflecting the design of activation records.
  • name key components in an execution environment; describe simple techniques for heap management and garbage collection; identify the amortized costs of different approaches to garbage collection; list common techniques and explain their properties used in virtual execution environments.
  • describe common techniques for program optimization; identify loops in programs using dominators; describe and apply techniques for optimizing loops and memory access.
  • describe how characteristics of hardware architectures influence compilation of programs; give examples of important characteristics.


  • Reading programs: lexical and syntactic analysis. Finite automata, regular expressions, LL- and LR-parsing.
  • Understanding programs: semantic analysis, type checking. Scope control, declarations and expressions.
  • Translating programs: machines and instructions. Intermediate code, instruction selection, stacks and procedure calls.
  • Executing programs: virtual execution environments and run-time systems. Memory management, garbage collection, loading and linking, just-in-time compilation. Dependencies on hardware architecture.
  • Improving programs: optimization. Machine independent optimizations (dataflow analysis, strength reduction, ...) Machine level optimization (register allocation, scheduling, prefetching, power consumption...).


  • IS1200 Computer Hardware Basics or equivalent.
  • 2G1519 Computer Science 2 or ID1218 Applied Programming or equivalent.


Approved written exam (TEN1; 6hp) and approved home assignments (INL1; 1.5hp).

Required Reading

Andrew W. Appel, Modern Compiler Implementation in Java, second edition, Cambridge University Press, 2002. ISBN 0 521 82060 X


New event

Wed 2 nov 13:00-15:00 Föreläsning Location: Ka-301
Feedback News