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.
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.
|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.
| • 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.
|Compilers, grammars, parsers, abstract syntax treesStatic analysis - a.o. type checking, Code generation, basic blocks and traces, instruction selection, liveness analysis, register allocation|
|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.|
|Experience with imperative, object oriented, and functional programming languages. Language and automata theory.||Required materials|
|Lectures notes available from Blackboard|
|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|
|Benjamin Pierce. Types and Programming Languages. MIT Press, 2002. • Michael Scott. Programming Language Pragmatics. Morgan Kauffman, 2009.|
|Dick Grune, Henri Bal, Ceriel Jacobs, and Koen Langedoen. Modern Compiler Design. John Wiley & Sons, 2000.|
|Opportunities||Block KW4, Block KW4|