Master’s studies

Syllabus for Compiler Design I

Kompilatorteknik I

Syllabus

  • 5 credits
  • Course code: 1DL321
  • Education cycle: First cycle
  • Main field(s) of study and in-depth level: Computer Science G2F, Technology G2F
  • Grading system: Fail (U), 3, 4, 5.
  • Established: 2012-03-08
  • Established by: The Faculty Board of Science and Technology
  • Applies from: week 02, 2012
  • Entry requirements: 60 credits including at least 15 credits in mathematics, including Automata Theory, and 30 credits in computer science, including Operating Systems and second course in computer programming.
  • Responsible department: Department of Information Technology

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

Reading list

Applies from: week 02, 2012