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://www.inf.ed.ac.uk/teaching/courses/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 fragments of a compiler for an imperative programming language. |
Entry Requirements
| Pre-requisites |
|
Co-requisites |
|
| Prohibited Combinations |
|
Other requirements |
Successful completion of Year 2 of an Informatics Single or Combined Degree, or equivalent by permission of the School.
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: 2010/11 Semester 2, Available to all students (SV1)
|
WebCT enabled: No |
Quota: None |
| Location |
Activity |
Description |
Weeks |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
| Central | Lecture | | 1-11 | | | | 14:00 - 14:50 | | | Central | Lecture | | 1-11 | 14:00 - 14:50 | | | | |
| First Class |
Week 1, Monday, 14:00 - 14:50, Zone: Central. Room 1.4, 22 Buccleuch Place |
| Exam Information |
| Exam Diet |
Paper Name |
Hours:Minutes |
Stationery Requirements |
Comments |
| Main Exam Diet S2 (April/May) | | 2:00 | 12 sides | | | Resit Exam Diet (August) | | 2:00 | 12 sides | Students may only resit with the permission of the Board of Examiners. |
Summary of Intended Learning Outcomes
1 - Understanding of the processes involved in compilation, and knowledge of the techniques applied.
2 - Analysis of compilation tasks.
3 - Implementation of compilation algorithms. |
Assessment Information
Written Examination 75
Assessed Assignments 25
Oral Presentations 0
Assessment
Two practical compiler exercises.
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
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 |
Dr Marcelo Cintra
Tel: (0131 6)50 5118
Email: mc@inf.ed.ac.uk |
Course secretary |
Miss Tamise Totterdell
Tel: 0131 650 9970
Email: t.totterdell@ed.ac.uk |
|
copyright 2011 The University of Edinburgh -
31 January 2011 7:51 am
|
University Homepage