CS311 – Programming Language Definition & Implementation

Credits 20
Level 3
Semester 1
Prerequisites CS208 Logic & Algorithms
Availability Possible elective
Contact Lectures: 20 | Tutorials: 20 | Labs: 0
Assignments: 80 | Self study: 80
Assessment 30% classwork, 70% written 2-hour examination.
Resit Resit is by a 2-hour examination.
Lecturer Dr Conor McBride | Professor Neil Ghani

General Aims

To provide familiarisation with the definition of programming language syntax and semantics, and the translation of these definitions into an implementation of a programming language.

Learning Outcomes

On completion of the class, a student should be able:

  • to define fully and to implement a simple programming language, this ability resulting from a combination of the detailed learning outcomes which follow
  • to understand the practical implications of language and grammar theory, as it is applied in the context of programming language implementation
  • to read and write specifications of context-free syntax
  • to read and write specifications of context-sensitive syntax
  • to read and write specifications of the meaning of programming languages
  • to read and write specifications of translation from one defined language to another, within the context of a programming language compiler
  • to understand the correlation between well-written specifications in all the above categories and the technique of recursive descent compilation
  • to understand how programming language semantics provides a basis for reasoning about program correctness


Definition of language and programming languages; definitions of syntax and semantics; the concept of a language implementation; languages that can be mechanically interpreted; introduction to soundness and completeness; regular expression languages; structural induction; context-free syntax and BNF [Backus-Naur Form]; language implementation frameworks; lexical analysis; syntax analysis; definition of type rules; type and scope checking; definition of semantics; denotational semantics; operational semantics and abstract machines; axiomatic semantics and Hoare logic.

Recommended Text/Reading*

* This list is indicative only – the class lecturer may recommend alternative reading material. Please do not purchase any of the reading material listed below until you have confirmed with the class lecturer that it will be used for this class.

To be determined by the class lecturer(s).