| STUDENTS
> Compilers
|
Compilers
Note:
Whilst every effort is made to keep the syllabus and assessment records correct
for this course, the precise details must be checked with the lecturer(s).
| Code: | 2010 |
| Year: | 2 |
| Prerequisites: | |
| Term: | 2 |
| Taught By: | Licia Capra (100%)
|
| Aims: |
This is a practical course whose primary goal is develop an understanding of the operation
of compilers and the development and specification of computer-based languages. The course pulls
together threads from underlying theory, most notably from logic and from data structures and
algorithms, and builds on these a practical exercise in which students create a compiler of their
own using commonly available compiler development tools.
|
| Learning Outcomes: |
To be able to: build lexical analysers and use them in the construction of parsers; express the grammar of a programming language; build syntax analysers and use them in the construction of parsers; perform the operations of semantic analysis; build a code generator; discuss the merits of different optimisation schemes.
|
Content:
| Anatomy of a compiler | The importance of compilers
Structure of a compiler
Analysis (lexical, syntax and semantic analysis)
Synthesis (intermediate code generation, optimisation and code generation)
Compilers vs. interpreters |
| Lexical analysis (scanning) | Tokens
Regular expressions
Finite state automata (deterministic and non-deterministic)
Translating regular expressions into finite state automata
Automatic lexer generators (JLex/JFlex) |
| Syntax analysis (parsing) | Context-free grammars
Derivations and (concrete/abstract) syntax trees
Handling ambiguous grammars
Bottom-up parsing (LR(k) grammars, shift-reduce parsers)
Automatic parser generators (CUP)
Syntactic error recovery |
| Syntax-directed translation | Syntax-directed definitions
Abstract syntax tree construction |
| Semantic analysis | Symbol table management
Scoping and type checking
Basic implementation techniques (Visitor methodology) |
| Intermediate code generation | Three address code
IR instructions
Translation methodologies |
| Code generation and optimisation | Run-time storage organisation
A simple code generation algorithm
Optimisation of intermediate code
Optimisation of target code (Peephole optimisation) |
Method of Instruction:
Lecture presentations, problem classes, lab classes.
Assessment:
The course has the following assessment components:
- Written Examination (2.5 hours, 80%)
- Coursework Section (1 piece, 20%)
To pass this course, students must:
- Obtain an overall pass mark of 40% for all sections combined
The examination rubric is:
Answer BOTH questions of Part I (Q1 and Q2) and ONE question from Part II (Q3 and Q4). All questions carry equal marks.Resources:
"Compilers - Principles, Techniques, and Tools" by A.V. Aho, R. Sethi and J.D. Ullman. Addison-Wesley.
"Modern Compiler Implementation in Java" by A.W. Appel. Cambridge University Press.
"Modern Compiler Design" by D. Grune, H.E. Bal, C.J.H. Jacobs, K.G. Langendoen. Wiley.
JLex: A Lexical Analyzer Generator for Java(TM)
JFlex - The Fast Scanner Generator for Java
CUP Parser Generator for Java
Course Homepage (accessible via IS login/password)
|
+44 (0)20 7679 7214 - Copyright © 1999-2007
UCL
