COMP0012 Compilers

This database contains the 2018-19 versions of syllabuses.

Note: Whilst every effort is made to keep the syllabus and assessment records correct, the precise details must be checked with the lecturer(s).

Academic session

2018-19

Module

Compilers

Code

COMP0012

Module delivery

1819/A4U/T2/COMP0012 Undergraduate

Related deliveries

None

Prior deliveries

COMP207P

Level

Undergraduate

FHEQ Level

L4

FHEQ credits

15

Term/s

Term 2

Module leader

Barr, Earl

Contributors

Barr, Earl

Sarro, Federica

Module administrator

Ball, Louisa

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.

Learning outcomes

On successful completion of the module, a student will be able to:

  1. build lexical analysers and use them in the construction of parsers;
  2. express the grammar of a programming language;
  3. build syntax analysers and use them in the construction of parsers;
  4. perform the operations of semantic analysis; build a code generator;
  5. discuss the merits of different optimisation schemes.

Availability and prerequisites

This module delivery is available for selection on the below-listed programmes. The relevant programme structure will specify whether the module is core, optional, or elective.

In order to be eligible to select this module as optional or elective, where available, students must meet all prerequisite conditions to the satisfaction of the module leader. Places for students taking the module as optional or elective are limited and will be allocated according to the department’s module selection policy.

Programmes on which available:

  • BSc Computer Science (Year 1)
  • MEng Computer Science (International Programme) (Year 1)
  • MEng Computer Science (Year 1)
  • MEng Mathematical Computation (International Programme) (Year 1)
  • MEng Mathematical Computation (Year 1)

Prerequisites:

There are no formal prerequsities.

Content

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)

An indicative reading list is available via http://readinglists.ucl.ac.uk/departments/comps_eng.html.

Delivery

The module is delivered through a combination of lectures, tutorials, seminars, written and programming exercises, and project work.

Assessment

This module delivery is assessed as below:

#

Title

Weight (%)

Notes

1

Written examination (2hrs 30mins)

80

 

2

Coursework 1

10

 

3

Coursework 2

10

 

In order to pass this Module Delivery, students must:

  • achieve an overall weighted Module mark of at least 40.00%;

AND, when taken as part of BSc Computer Science; MEng Computer Science, and MEng Mathematical Computation:

  • achieve a mark of at least 30.00% in any Components of assessment weighed ≥ 30% of the module.

Where a Component comprises multiple Assessment Tasks, the minimum mark applies to the overall component.