Module description
Aims and Learning Outcomes
To explain the techniques behind compilers, lexers and parsers. To introduce the mathematical formalisms of regular expressions, context-free grammars, and to show their applications to computer languages. To generate code for low level machine languages and to illustrate compiler techniques.
On successful completion of this module, students will:
Have learned:
- How to use regular expressions for lexing programs and data.
- How to design grammars for parsing programs.
- How to implement a parser and an interpreter.
- How to implement a compiler.
Be able to:
- Implement the central components of a small compiler (including lexer, parser and code-generator).
Syllabus
An indication of the types of topics:
1. Formal languages
- alphabets, strings, languages
- mathematical background, sets and relations, proofs
2. Regular expressions
- regular expression matching
- derivatives of regular expressions
- lexing and token generation
3. Finite Automata
- Deterministic Finite Automata (DFA)
- Non-Deterministic Finite Automata (NFA)
- equivalence of DFA, NFA and regular expressions
4. Parsing Techniques
- context-free grammars
- parser combinators
5. Interpreters and Compilers:
- code generation for the WHILE-language
- compilation to the Java Virtual Machine and the LLVM-IR
- compiling a functional language
- compiler optimisation techniques
Assessment details
Please note: The below assessment details for the 2025/26 academic year may be updated. The confirmed details will be available on the Student Handbook and on the module KEATS page at the beginning of the semester.
- 40% Examination
- 60% Coursework
The coursework will consist of multiple pieces to undertake throughout the semester.