Home

Research

Publications

Teaching

Project Proposals

Computing Home

DCU Home

 

CA448 - Compiler Construction 1

[ Intro ] [ Notes ] [ Exercises ] [ Assignments ] [ End of Year Exam ] [ Links ]

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