CloseHelpPrint
Kies de Nederlandse taal
Course module: NWI-IMC004
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)
Coordinator
prof. dr. ir. M.J. Plasmeijer
Other course modules lecturer
Contactperson for the course
prof. dr. ir. M.J. Plasmeijer
Other course modules lecturer
Lecturer
prof. dr. ir. M.J. Plasmeijer
Other course modules lecturer
Lecturer
dr. J. Stutterheim
Other course modules lecturer
Academic year2017
Period
KW3-KW4  (05/02/2018 to 02/09/2018)
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 disciple for any computer scientist.

The construction of a compiler is a natural meeting place of many computer science disciplines. 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.

Finally, one can choose an extension of the basic compiler thus constructed. One can choose to extend SPL with new features, or to generate code for real machine architectures.

Literature
There is no particular text book that will be used during the lectures. Besides the lecture notes from a similar course on Implementation of Programming Languages at Universiteit Utrecht (available from Blackboard), additional optional reading material consists of:

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

Extra information teaching methods: The construction of your own compiler for a Simple Programming Language (SPL) is an important part of this course. We will introduce the techniques needed to construct a compiler and you apply these skills in the construction of your own compiler.The course is divided into 4 units. The first 3 units each treat one particular topic. Unit 1 discusses parsing methods. Unit 2 handles typing and type systems. Unit 3 is about code generation. With each unit you need to implement the corresponding part of a compiler. You do this together with a partner. At the end of the 3 units, you will have created a full compiler for a small language. In unit 4 you choose a topic that you wish to study in detail. You write a paper about it, give a presentation, and perhaps create an extension in your own compiler. The course is finished with an oral exam that covers all material, practical exercises and case-study.
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

Lecture

Tutorial

Zelfstudie

Tests
Tentamen
Test weight1
OpportunitiesBlock KW4, Block KW4

CloseHelpPrint
Kies de Nederlandse taal