Code

COMP2010

Year

2

Prerequisites

Term

2

Taught By

Earl Barr/ Shin Yoo

Aims

This is a practical course 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

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

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)

Lecture presentations, problem classes, lab classes.

The course has the following assessment components:

• Written Examination (2.5 hours, 80%)
• Coursework Section (1 piece, 20%)

To pass this course, students must:

• Obtain an overall pass mark of 40% for all sections combined

The examination rubric is:
Answer BOTH questions of Part I (Q1 and Q2) and ONE question from Part II (Q3 and Q4). All questions carry equal marks.

'Compilers - Principles, Techniques, and Tools' by A.V. Aho, R. Sethi and J.D. Ullman. Addison-Wesley.

'Modern Compiler Implementation in Java' by A.W. Appel. Cambridge University Press.

'Modern Compiler Design' by D. Grune, H.E. Bal, C.J.H. Jacobs, K.G. Langendoen. Wiley.

JLex: A Lexical Analyzer Generator for Java(TM)

JFlex - The Fast Scanner Generator for Java

CUP Parser Generator for Java

Course Homepage (accessible via IS login/password)