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:
- Formal languages
- alphabets, strings, languages
- mathematical background, sets and relations, proofs
- Regular expressions
- regular expression matching
- derivatives of regular expressions
- lexing and token generation
- Finite Automata
- Deterministic Finite Automata (DFA)
- Non-Deterministic Finite Automata (NFA)
- equivalence of DFA, NFA and regular expressions
- Parsing Techniques
- context-free grammars
- parser combinators
- 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
2024/25 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.
Semester 1 only study abroad students will be required to take this exam in an alternative assessment format in the January exam period.
Full year study abroad students will be required to take this exam in person in January.