Entry requirements

Mathematics 15 ECTS credits including Automata theory.

Computer Science 22.5 ECTS credits including Computer Programming, second course, or Algorithms and Data Structures DV1, or the equivalent. Algorithms and Data Structures DV2 and Operating systems are recommended.

Learning outcomes

To pass, the student must understand, how simple imperative programming languages equivalent to C can be compiled to machine code for RISC-like machines.

The students must specifically be able to

• structure a compiler as a sequence of distinct translation steps
• use regular languages to describe the lexical elements of a programming language
• implement lexical analysis using a finite automaton
• use context free languages to describe the syntactic structure of a programming language
• use the parsing methods top-down (recursive descent) and bottom-up (LR)
• use abstract syntax trees to represent the results of the syntactic analysis
• use hash tables to handle information on variable bindings in languages with static and nested visibility rules
• break down theorems and expressions to simpler designs, and translate syntax trees to intermediate code
• implement recursive procedure calls by means of stacks, activation posts and machine registers
• translate the simplified intermediate code of a program to machine-specific instructions

Content

Theory:

Lexical analysis (scanning).

Syntactical analysis (parsing).

Program representation in Abstract Syntax Trees (AST).

Symbol tables and scope rules for C-like languages.

Type-checking for C-like languages.

Different forms of intermediate code (IR).

Generation of intermediate code.

Call stacks and activation posts.

Code generation for RISC-like machines.

Basic blocks, control-flow graphs, liveness analysis, register allocation.

Project:

The students carry out a project in which they implement a compiler from a small subset of C to a RISC-machine.

The project is divided in steps, which are presented separately.

Instruction

Lectures, laboratory sessions, project.

Assessment

The course is examined by written examination (3 credits) and assignments within the project (4 .5 credits).