Â鶹´«Ã½ÊÓƵÍøÕ¾

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.

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

Indicative content:

The following are indicative of the topics the module will typically cover:

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

Requisites:

To be eligible to select this module as optional or elective, a student must ​be registered on a programme and year of study for which it is a formally available.