CS2CO16-Compilers

Module Provider: Computer Science
Number of credits: 10 [5 ECTS credits]
Level:5
Terms in which taught: Spring term module
Pre-requisites: CS1PR16 Programming or CS1PC20 Programming in C/C++
Non-modular pre-requisites:
Co-requisites:
Modules excluded:
Current from: 2021/2

Module Convenor: Dr Martin Lester
Email: m.lester@reading.ac.uk

Type of module:

Summary module description:

This module presents the theory and practice of compilers, including how to write a compiler and introductory computation theory. A compiler turns source code written by a human into machine code executable by a computer. Thus knowing how a compiler works allows one to understand the connection between programming and computer architecture. The module also considers broader issues in programming language design and implementation.

Aims:

This module presents the theory and practice of compilers. The first part of the module gives an overview of a compiler and its structure. A compiler for MiniJava is gradually developed in Java, using the parser generator ANTLR. As each new feature is added to the compiler, the relevant parts of the compiler are modified. The second part of the module covers some relevant topics from computation theory and algorithms in greater detail: finite state automata for lexical analysis; parsing algorithms for syntax analysis; and the relevance of the Halting Theory to optimisation. This part also introduces several common optimisations.

Assessable learning outcomes:

On completion of this module, students will be able to:

• Write a compiler for a simple programming language, or modify an existing one;


• Use a parser generator to create a parser for a programming language;


• Describe and explain the purpose of each stage in a typical compiler;


• Compute whether a finite state automaton recognises an input word;


• Convert descriptions of regular languages between natural language, regular expressions and finite state automata;


• Suggest a rule in Backus Naur Form (BNF) for a particular programming language construct;


• Draw a parse tree or left-most derivation for a sentence, given a grammar in BNF;


• Describe how a parsing algorithm works and trace its execution for a simple example;


• Demonstrate that a given grammar is ambiguous;


• Rewrite an ambiguous grammar to enforce the correct precede nce or associativity;


• Explain the role of types in a programming language;


• Suggest what type checks are necessary for a programming language construct or fragment of code;


• Write intermediate code corresponding to high-level language code;


• Describe common programming language optimisations and apply them to high-level language code or intermediate code;


• Critically analyse the correctness and effectiveness of unfamilia r optimisations;


• State the Halting Theorem and its relevance to program optimisation; 


• Informally prove the Halting Theorem;


• Critically analyse decisions in programming language design and implementation.

Additional outcomes:

Knowledge of basic computation theory. An appreciation of some broader issues in programming language design and implementation.

Outline content:

• The typical structure of a compiler and how it enables code reuse; 


• Different ways of specifying a programming language;


• Regular expressions and grammars in Backus Naur Form (BNF) for specifying programming language tokenisation and syntax;


• Lexical analysis and syntax analysis using parser generators, such as lex/yacc or ANTLR; 


• Writing a simple lexical analysis engine or recursive descent parser by hand;
  
• Finite state automata and their relevance to lexical analysis;


• Earley’s parsing algorithm (or some other parsing algorithm) for context free grammars; 


• Semantic analysis : the roles of variable scoping, storage allocation and types in a programming language;


• Intermediate code generation for a variety of common programming language constructs, such as assignment, compound expressions, conditionals, loops, functions, arrays and objects;


• Machine code generation;


• Goals of program optimisation and the importance of considering side effects in ensuring safe optimisation;


• Some common program optimisations;


• Fundamental limits of optimisation, as imposed by the Halting Theorem.

Brief description of teaching and learning methods:

Lectures demonstrate how to write a compiler using a “scaffolding” approach. New features are added to the compiler gradually, allowing students to focus on one phase of the compiler at a time. Lectures also include short exercises for students to complete during the lecture to check their understanding. After a basic compiler has been developed in lectures, lab practicals provide support for students to develop their understanding of the material with support while completing the coursework.

Contact hours:

	Autumn	Spring	Summer
Lectures		16
Practicals classes and workshops		4
Guided independent study:		80
Total hours by term	0	100	0
Total hours for module	100

Summative Assessment Methods:

Method	Percentage
Written exam	70
Set exercise	30

Summative assessment- Examinations:

One 2-hour examination paper (70%) in May/June.

Summative assessment- Coursework and in-class tests:

One assignment about adding a feature to an existing compiler (30%).

Formative assessment methods:

None.

Penalties for late submission:

The Support Centres will apply the following penalties for work submitted late:

• where the piece of work is submitted after the original deadline (or any formally agreed extension to the deadline): 10% of the total marks available for that piece of work will be deducted from the mark for each working day (or part thereof) following the deadline up to a total of five working days;
• where the piece of work is submitted more than five working days after the original deadline (or any formally agreed extension to the deadline): a mark of zero will be recorded.

The University policy statement on penalties for late submission can be found at: http://www.reading.ac.uk/web/FILES/qualitysupport/penaltiesforlatesubmission.pdf
You are strongly advised to ensure that coursework is submitted by the relevant deadline. You should note that it is advisable to submit work in an unfinished state rather than to fail to submit any work.

Assessment requirements for a pass:

A mark of 40% overall.

Reassessment arrangements:

One 2-hour examination paper in August/September.  Note that the resit module mark will be the higher of (a) the mark from this resit exam and (b) an average of this resit exam mark and previous coursework marks, weighted as per the first attempt (70% exam, 30% coursework).

Additional Costs (specified where applicable):

1) Required text books:  None

2) Specialist equipment or materials:  None

3) Specialist clothing, footwear or headgear:  None

4) Printing and binding:  None

5) Computers and devices with a particular specification:  None

6) Travel, accommodation and subsistence:  None

Last updated: 29 July 2021