Entry requirements

Mathematics 15 ECTS credits including Automata theory.

Computer Science 30 ECTS credits including a second course in Computer Programming and Operating systems.

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
• describe 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
• break down statements and expressions to simpler designs, and translate syntax trees to intermediate code
• describe how recursive procedure calls can be implemented by means of stacks, activation posts and machine registers
• translate the simplified intermediate code of a program to machine-specific instructions

Content

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.

Instruction

Lectures, laboratory sessions.

Assessment

The course is examined by written examination (4 credits) and assignments (1 credit).