1999-2000 session

CS2111 Design and Implementation of Programming Languages

Level: 2
Credit Rating: 10
Pre-requisites: A programming language, preferably C
Co-requisites: none
Pre-requisite for: none
Duration: 12 weeks in first semester
Lectures: 24 in total, 2 per week
Examples Classes: None
Laboratories: 16 hours in total, 8 2-hour sessions, partly credited to CS2910/CS2920
Assessment: 2-hour examination 90%, laboratory 10%.
Laboratory mark also contributes to CS2910/CS2920.
Lecturer: Mr P J Jinks
As well as CS2042, which discusses the code generated by compilers, there are several third-year modules in the Core (0) and Computing Science (1) programmes which discuss languages and compilers; this module is not a prerequisite for any of them, but will provide useful background information.

This module examines imperative programming languages, using examples to show how their design interacts with both usability and ease of implementation. It is intended not only for the minority of students who might someday need to build a compiler, but also for the majority of students who need to understand both the merits of various imperative language concepts and also the utility of simple languages in many programming activities.
The module will examine common concepts, illustrated by examples from real programming languages, rather than simply examining several languages in turn.

A student completing this module should understand:
- the basic syntactic and semantic concepts underlying typical imperative programming languages,
- the components of a simple compiler and how to combine them,
and be able to:
- use various standard techniques and tools to design and implement effective textual interfaces (including command languages) for programs,
- and in particular, apply these skills in the 3rd year project.
One side-effect is that you will learn a lot more about C and various useful UNIX tools, as they are used in many of the examples and practical exercises.
Reading List

K C Louden, Programming Languages: Principles and Practice, (ISBN 0-534-932-770)
Thorough coverage of language design, with some information about implementation. Covers imperative, function programming. 
Bal H.E. and D Grune, D., Programming Language Essentials, (ISBN 0-201-631-792) Addison-Wesley 1994
A condensed version of Louden's book.
Levine, J. et al., Lex and Yacc (2nd edition), (1-56592-000-7) O'Reilly and Associates, 1992
A few misprints, but otherwise superb description of lex and yacc.
Either of the first 2 books will be useful, although the first is more complete. The third book is mainly for reference. A longer list of useful references will be given out in the lectures.

Introduction [3]

Representation and meaning.
Little languages: sh, make, grep. Expressions.
Recognising languages [5]

Lex and yacc. Parse trees.
Implementing Expressions [2]

Code sequences and generation algorithms for typical computers.
Control Structures [2]

Concatenation, selection, repetition, repeaters and completers.
Procedures and functions.
Identifiers [4]

Static scope and dynamic extent, declarations, arrays.
Block structure, heap, garbage collection.
Types [3]

Strong typing, coercion, primitive and composite types, pointers.
Abstract data types, modules, objects.
Implementing Identifiers and Types [1]

Language Design [2]

Error detection and correction, puns and synonyms, orthogonality.
A complete Compiler [2]

Lexical, syntactic, semantic, code generation and optimisation
phases. Combining phases into passes.