CS2CO16NU-Compilers

Module Provider: Computer Science
Number of credits: 10 [5 ECTS credits]
Level:5
Semesters in which taught: Semester 2 module
Pre-requisites: CS1PC20NU Programming in C/C++
Non-modular pre-requisites:
Co-requisites:
Modules excluded:
Current from: 2022/3

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.

The Module leads at NUIST is TBD.

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 Theorem 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 naturallanguage, 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 precedence 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 unfamiliar 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