NWI-IMC004
Compiler Construction
Course infoSchedule
Course moduleNWI-IMC004
Credits (ECTS)6
CategoryMA (Master)
Language of instructionEnglish
Offered byRadboud University; Faculty of Science; Informatica en Informatiekunde;
Lecturer(s)
Lecturer
dr. M. Lubbers
Other course modules lecturer
Lecturer
dr. J.E.W. Smetsers
Other course modules lecturer
Coordinator
dr. J.E.W. Smetsers
Other course modules lecturer
Contactperson for the course
dr. J.E.W. Smetsers
Other course modules lecturer
Academic year2019
Period
KW3-KW4  (03/02/2020 to 30/08/2020)
Starting block
KW3
Course mode
full-time
Remarks-
Registration using OSIRISYes
Course open to students from other facultiesYes
Pre-registrationNo
Waiting listNo
Placement procedure-
Aims
At the end of the course you can build a compiler for a small programming language in a well structured manner, and you know and can use the required algorithms and tools. You can create a grammar for a programming language, build a parser for it, perform static analysis, create an abstract syntax tree, and generate code.
Content
It is important to know how compilers work because many applications actually act as a compiler: they translate input written in some language to output in some other. So, compiler construction is a basic discipline for any computer scientist.
The construction of a compiler is a natural meeting place of many computer science fields. You work with finite automata, grammars, parsers, tree structures and graphs, recursive algorithms, typing systems, code generation algorithms, to name a few.
In this course you will stepwise construct, in your own favourite language, a basic compiler for a small but representative language, SPL (Simple Programming Language). The main steps are 1) the construction of a parser for SPL which generates an abstract syntax tree; 2) the implementation of a type checker / type inferencing system for SPL; 3) a code generation for a simple stack machine.
As final project, you either choose to extend SPL with new features, or to generate code for some concrete machine architecture.
Level

Presumed foreknowledge
Experience with imperative, object oriented, and functional programming languages. Language and automata theory.
Test information
Subsequent exercises of 3 main topics: parsing, typing, code generation, leading to a working compiler for a small programming language. Case-study to a self-selected extension of the compiler (paper, presentation, perhaps implementation). Individual oral exam covering all material, exercises, implementation, and case-study.
Specifics

Topics
Compilers, grammars, parsers, abstract syntax treesStatic analysis - a.o. type checking, Code generation, basic blocks and traces, instruction selection, liveness analysis, register allocation

Test information
Subsequent exercises of 3 main topics: parsing, typing, code generation, leading to a working compiler for a small programming language. Case-study to a self-selected extension of the compiler (paper, presentation, perhaps implementation). Individual oral exam covering all material, exercises, implementation, and case-study.

Prerequisites
Experience with imperative, object oriented, and functional programming languages. Language and automata theory.

Required materials
Reader
Lectures notes available from Blackboard

Recommended materials
Book
Alfred Aho, Ravi Sethi, and Jeffrey Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.
Book
Andrew Appel. Modern Compiler Implementation in Java. Cambridge University Press, 1998
Book
Benjamin Pierce. Types and Programming Languages. MIT Press, 2002. • Michael Scott. Programming Language Pragmatics. Morgan Kauffman, 2009.
Book
Dick Grune, Henri Bal, Ceriel Jacobs, and Koen Langedoen. Modern Compiler Design. John Wiley & Sons, 2000.

Instructional modes
Course occurrence

Exam Q4

Lecture

Resit Exam Q4

Tutorial

Zelfstudie

Tests
Final grade
Test weight1
OpportunitiesBlock KW4, Block KW4