Undergraduate Course: Compiling Techniques (INFR09007)
Course Outline
| School | School of Informatics |
College | College of Science and Engineering |
| Course type | Standard |
Availability | Available to all students |
| Credit level (Normal year taken) | SCQF Level 9 (Year 3 Undergraduate) |
Credits | 10 |
| Home subject area | Informatics |
Other subject area | None |
| Course website |
http://course.inf.ed.ac.uk/ct |
Taught in Gaelic? | No |
| Course description | This course describes the phases of a modern programming language compiler with an emphasis on widely-used techniques. The course project will require students to implement a complete compiler for a simple educational programming language, targeting an abstract machine such as the JVM.
|
Entry Requirements (not applicable to Visiting Students)
| Pre-requisites |
|
Co-requisites | |
| Prohibited Combinations | |
Other requirements | This course is open to all Informatics students including those on joint degrees. For external students where this course is not listed in your DPT, please seek special permission from the course organiser.
This course has the following mathematics prerequisites:
1 - General background: integers/real numbers, set theory: union, intersection,...
2 - Graph theory, in particular, directed/undirected graphs, cyclic/acyclic graphs, labeled graphs, trees, subgraph isomorphism, graph colouring.
3 - Algebraic structures, in particular, lattices and join/meet. |
| Additional Costs | None |
Information for Visiting Students
| Pre-requisites | None |
| Displayed in Visiting Students Prospectus? | Yes |
Course Delivery Information
|
| Delivery period: 2013/14 Semester 2, Available to all students (SV1)
|
Learn enabled: No |
Quota: None |
|
Web Timetable |
Web Timetable |
| Course Start Date |
13/01/2014 |
| Breakdown of Learning and Teaching activities (Further Info) |
Total Hours:
100
(
Lecture Hours 20,
Seminar/Tutorial Hours 8,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
68 )
|
| Additional Notes |
|
| Breakdown of Assessment Methods (Further Info) |
Written Exam
75 %,
Coursework
25 %,
Practical Exam
0 %
|
| Exam Information |
| Exam Diet |
Paper Name |
Hours & Minutes |
|
| Main Exam Diet S2 (April/May) | | 2:00 | | | Resit Exam Diet (August) | | 2:00 | |
Summary of Intended Learning Outcomes
1 - Understanding of the challenges involved in compilation (semantic gap between input and output languages, compiler efficiency and code quality)
2 - Understanding of the phases involved in compilation, and knowledge of the techniques applied.
3 - Ability to understand design decisions in modern compilers and to justify these.
4 - Ability to develop and apply modifications to standard compilation techniques wherever this is necessary.
5 - Ability to analyse compilation tasks and to apply standard compilation techniques.
6 - Ability to implement standard compilation algorithms.
7 - Gain an understanding of the challenges involved in compilation for modern architectures and the approaches taken in modern compilers
|
Assessment Information
Written Examination 75
Assessed Assignments 25
Oral Presentations 0
Assessment
Two practical compiler exercises (Part 1 on the compiler front-end and IR generation, part 2 on semantic analysis and code generation)
If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year. |
Special Arrangements
| None |
Additional Information
| Academic description |
Not entered |
| Syllabus |
* Introduction: structure of a compiler
* Lexical analysis: tokens, regular expressions, Lex
* Parsing: context-free grammars, predictive and LR parsing, Yacc
* Abstract syntax: semantic actions, abstract parse trees
* Semantic analysis: symbol tables, bindings, type-checking
* Stack frames: representation and abstraction
* Intermediate code: representation trees, translation
* Basic blocks and traces: canonical trees and conditional branches
* Instruction selection: algorithms for selection, RISC and CISC
* Liveness analysis: solution of dataflow equations
* Register allocation: colouring by simplification, coalescing
* Advanced Topics: automatic parallelisation, popular open-source compilers: GCC, LLVM
Relevant QAA Computing Curriculum Sections: Compilers and Syntax Directed Tools
|
| Transferable skills |
Not entered |
| Reading list |
* Andrew W. Appel, Modern Compiler Implementation, Cambridge University Press, 1998. Three versions of this book are available which present code fragments from the compiler in the languages C, Standard ML and Java. Students should use whichever version of the book they prefer.
* Alfred V. Aho, Ravi Sethi, Jeffrey D, Ullman, Compilers: Principles, Techniques and Tools. Addison Wesles, 1986.
* Steven Muchnick, Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997
* Reinhard, Wilhelm, Dieter Maurer, Compiler Design. Addison Wesley, 1995.
* Charles N. Fischer, Richard J. LeBlank, Jr., Crafting a Compiler in C. Benjamin/Cummings, 1991.
* Keith Cooper, Linda Torczon, Engineering a Compiler, Morgan Kaufmann
|
| Study Abroad |
Not entered |
| Study Pattern |
Lectures 18
Tutorials 0
Timetabled Laboratories 0
Non-timetabled assessed assignments 30
Private Study/Other 52
Total 100 |
| Keywords | Not entered |
Contacts
| Course organiser | Mr Vijayanand Nagarajan
Tel: (0131 6)51 3440
Email: vijay.nagarajan@ed.ac.uk |
Course secretary | Miss Claire Edminson
Tel: (0131 6)51 7607
Email: C.Edminson@ed.ac.uk |
|
© Copyright 2013 The University of Edinburgh - 13 January 2014 4:26 am
|
University Homepage