ID3006 Compilers and Execution Environments 7.5 credits

Kompilatorer och exekveringsmiljöer

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

  • Education cycle

    Third cycle
  • Main field of study

  • Grading scale

Course offerings

Spring 18 for programme students

  • Periods

    Spring 18 P4 (7.5 credits)

  • Application code

    61375

  • Start date

    19/03/2018

  • End date

    04/06/2018

  • Language of instruction

    English

  • Campus

    KTH Kista

  • Tutoring time

    Daytime

  • Form of study

    Normal

  • Number of places

    No limitation

Information for research students about course offerings

Every year, period 2 together with ID2202.

Intended learning outcomes

The overall aim of the course is to provide an understanding of
how a programming language is implemented including common
theories and recent research results and how these theories and
research results 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.
 - describe and apply current research trends in compilers and execution environments in all areas mentioned above

Course main content

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

Research area overview: major conferences and journals. Current hot topics and connection to other research areas.

Eligibility

Literature

Examination

Approved written examination, approved home assinments, and approved application of current research (in the form of using it for a research paper, report, or project, etc).

Requirements for final grade

Godkänd skriftlig tentamina, godkända inlämningsuppgifter och godkänd tillämpning av nuvarande forskning (till exempel: användning i en forskningsartikel, forskningsreport, eller forksningsprojekt).

Offered by

ICT/Software and Computer system

Contact

Christian Schulte, cschulte@kth.se 087904264

Examiner

Christian Schulte <cschulte@kth.se>

Version

Course syllabus valid from: Spring 2011.