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
Non-modular pre-requisites:
Co-requisites:
Modules excluded:
Current from: 2020/1

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;

< li>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.