Module Aims

The aims of this module are to give students a comprehensive grounding in the techniques used in the front end of compilers and to give hands-on experience in the construction of compiler front ends through practical examples.

Learning Outcomes

As a result of this module, students will have a good understanding of the following:

• the function of the different phases of the front end of a compiler.
• lexical analysis techniques.
• top-down and bottom-up parsing algorithms.
• semantic analysis techniques.

Indicative Syllabus

• structure of a compiler
• lexical analysis: regular expressions, DFAs, conversion of regular expressions to DFAs, implementation of lexical analysers
• syntax analysis: context-free grammars, derivations, precedence, ambiguity
• top-down parsing: predictive parsing, conversion of grammars to predictive form, recursive descent parsing, LL(1) parsing, constructing LL(1) parsing tables, implementation of top-down parsers
• bottom-up parsing:handles, shift-reduce parsing, LR parsing, constructing LR(0) parsing tables, constructing SLR(1) parsing tables, constructing LR(1) parsing tables, constructing LALR(1) parsing tables, implementation of bottom-up parsers
• semantic analysis: context-sensitive analysis, semantic actions, incorporating semantic actions in top-down parsers, incorporating semantic actions in bottom-up parsers, attribute grammars, symbol tables, type checking

Assessment

Continuous assessment: 30 % End-of-year exam: 70 %

Indicative Reading List

Essential:

Compilers: Principles, Techniques and Tools, Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, Pearson, 2007 ISBN: 978-0-321-49169-5

Supplementary:

Modern Compiler Implementation in Java, Second Edition, Andrew W. Appel, Cambridge University Press, ISBN 0-521-82060-X

Generating Parsers With JavaCC, Tom Copeland, Centennial Books, 2007 ISBN: 0-9762214-3-8