Syllabus and synopsis (Compilers)
This course aims to give a simple but practical account of the programming techniques used in implementing high-level programming languages by compiling into code for stack and register-based machines. The course is based on a working implementation, written in Objective Caml, of a compiler for a language comparable to C or Pascal.
On completion, the students should be able to:
- Understand and explain the main techniques and algorithms used in compilers.
- Describe the runtime structures used to represent constructs in typical programming languages.
- Use compiler construction tools, such as parser generators, to build a simple compiler.
Programming language representation: concrete and abstract syntax, context free grammars. Use of lexer and parser generators. Implementation of expressions and statements in a simple language by postfix code and by simple machine code; simple optimizations. Procedures: value, name and reference parameters, local and non-local variables, static and dynamic binding. Abstract machines and storage management: activation records, static and dynamic chains, stacks and heaps.
The order of topics will probably change a bit to allow more time to complete the lab exercises.
- Lexical analysis.
- Syntax analysis.
- Postfix code for expressions.
- Branching code for control structures.
- Semantic analysis.
- Data structures.
- Parameters and nested procedures.
- Higher-order functions.
- A complete compiler.
- Object-oriented languages.
- Overview of the back end.
- Instruction selection.
- Common subexpressions.
- Register allocation.