Description
Aims:
This is a practical module whose primary goal is develop an understanding of the operation of compilers and the development and specification of computer-based languages. The course pulls together threads from underlying theory, most notably from logic and from data structures and algorithms, and builds on these a practical exercise in which students create a compiler of their own using commonly available compiler development tools.
Intended learning outcomes:
On successful completion of the module, a student will be able to:
- Build lexical analysers and use them in the construction of parsers.
- Express the grammar of a programming language.
- Build syntax analysers and use them in the construction of parsers.
- Perform the operations of semantic analysis; build a code generator.
- Discuss the merits of different optimisation schemes.
Indicative content:
The following are indicative of the topics the module will typically cover:
Anatomy of a compiler:
- The importance of compilers.
- Structure of a compiler.
- Analysis (lexical, syntax and semantic analysis).
- Synthesis (intermediate code generation, optimisation and code generation).
- Compilers vs. interpreters. Lexical analysis (scanning).
- Tokens.
- Regular expressions.
- Finite state automata (deterministic and non-deterministic).
- Translating regular expressions into finite state automata.
- Automatic lexer generators (JLex/JFlex).
Syntax analysis (parsing):
- Context-free grammars.
- Derivations and (concrete/abstract) syntax trees.
- Handling ambiguous grammars.
- Top-down parsing (LL(k) grammars, recursive descent parsers).
- Bottom-up parsing (LR(k) grammars, shift-reduce parsers).
- Automatic parser generators (CUP).
- Syntactic error recovery.
Syntax-directed translation:
- Syntax-directed definitions.
- Abstract syntax tree construction.
Semantic analysis:
- Symbol table management.
- Scoping and type checking.
- Basic implementation techniques (Visitor methodology).
Intermediate code generation:
- Three address code.
- IR instructions.
- Translation methodologies.
Code generation and optimisation:
- Run-time storage organisation.
- A simple code generation algorithm.
- Optimisation of intermediate code.
- Optimisation of target code (Peephole optimisation).
Requisites:
To be eligible to select this module as optional or elective, a student must ​be registered on a programme and year of study for which it is a formally available.
Module deliveries for 2024/25 academic year
Last updated
This module description was last updated on 19th August 2024.
Ìý