Department of Computer Science

Lexical & Syntax Analysis of Programming Languages (LSA) 2010/1

Workload - Private Study - Assessment - Description - Learning Outcomes - Content - Teaching Materials - Recommended Books

Module Prerequisites

Prerequisite knowledge

Students must have a prior knowledge of programming in C. CCC provides a suitable introduction, but cannot be made a compulsory pre-requisite. Students will be assumed to have a knowledge of formal languages and automata. For most students this will have been acquired in MCS but others (e.g. CS/Maths students) must ensure that they have this knowledge from somewhere else (e.g. first-year CS tutorials).

Prerequisite modules

• CAR - Computer Architectures
• MCS - Mathematics for Computer Science

Workload

• Lectures: 14 x 1hr
• Practicals: 4 x 2hrs
• Private Study: 76.5hrs
• Assessment: 1.5hrs

Private Study

In addition to reading, students will be expected to work on problem sheets and on practical work that is not possible to complete in the timetabled practical sessions.

Assessment

Closed Assessment

• Summer Week 8, 1.50 hours

Assessed by a 90-minute closed examination (worth 50 marks): Answer 1 compulsory question plus 1 other from a choice of 2.

Formative Feedback

Students must complete a number of exercises. Students are encouraged to ask the lecturer and demonstrators for assitance and suggestions. Sample solutions are released week-by-week and general feedback is also posted on the module web page.

Description

The number of people who write compilers is small, so why is a module about compiler construction a compulsory part of a computer science course? One reason is that, though few graduates of the course will end up writing compilers, all will have to use them. Also many of the techniques used in compilers have application in other areas such as dialogue and human-computer interface design. This module will give a broad introduction to syntax-directed compilation of programming languages. The module does not cover code generation, which is covered in the third-year module, Code Generation and Optimisation (CGO).

Learning Outcomes

The aim of this module is to introduce the student to the theory and practice of programming language compilation. It works through the `front end' of compilation: lexical and syntax analysis. By the end of the module the student will be in a position to write a lexical scanner and a parser for a context-free language, including the use of compiler tools. The student will also have a solid understanding on the underlying theory of formal languages. Finally, the student should have a better appreciation of good programming practice in terms of program compilation.

Content

Lecture notes are arranged in chapters. A single chapter may span over several lectures. Chapters include:

1 Introduction
2 Abstract syntax
3 Lexical analysis
4 Flex, a lexical analyser generator
5 Grammars and Parse Trees
6 Top-down parsing
7 Bison, a parser generator
8 Bottom-up parsing
9 Parser combinators (if time permits)

Practical classes:

1 Lexical scanning
2 Flex
3 Recursive descent
4 Bison

Teaching Materials

Notes and exercise sheets will be provided. Information and feedback will be posted on the module web pages.

Recommended Books

Last updated: 1^st June 2011