PA008 Compiler Construction

Faculty of Informatics
Autumn 2020
Extent and Intensity
3/0/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
Mgr. Libor Caha, PhD. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 10:00–12:50 D3
Prerequisites
Finite automata and regular languages (see IB005); pushdown automata and context-free languages, especially the parsing methods of deterministic context-free languages (LL and LR techniques) - see IA006.
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
At the end of the course students should be able to understand and explain principles, methods, and techniques used in design and implementation of compilers programming languages and the related systems based on analysis of an input text and synthesis of the corresponding output. Students should be able make reasoned decisions about design of these systems. Based on acquired knowledge, students should employ principles and techniques of compiler writing and program analysis in related areas of computer science and system desing.
Learning outcomes
On successful completion of the course students will be able to:
1. Specify and analyse the lexical, syntactic and semantic structures of language features and separate the lexical, syntactic and semantic analyses into phases for a compiler.
2. Implement a scanner, parser, and semantic analyser with/without the aid of automatic SW tools.
3. Write an intermediate (IR) code generator. Turn IR code into machine code. Describe techniques for intermediate code optimisation.
Syllabus
  • Tasks of compiling, phases of a compiler, compiler structure.
  • The role of lexical analysis. Structure, modules and interfaces. Construction.
  • Parsing. The role of parser, interfaces and imlementation.
  • Attribute grammars (AG) and syntax directed translation. Description of language properties via AGs.
  • Semantic analysis, its tasks and implementation. Name and scope analysis, type checking.
  • Run-time enviroments, storage organization and allocation, stack and heap.
  • One-pass and multi-pass compiling. Intermediate code generation
  • Techniques for code generation. register allocation.
  • Error recovery.
  • Local optimization. Flow analyses, global optimization.
  • Compiler generators, techniques and tools.
Literature
  • AHO, Alfred V. Compilers : principles, techniques, & tools. 2nd ed. Boston: Pearson/Addison Wesley, 2007, xxiv, 1009. ISBN 0321486811. info
  • AHO, Alfred V., Ravi SETHI and Jeffrey D. ULLMAN. Compilers, principles, techniques, and tools. Reading: Addison-Wesley Publishing Company, 1987, x, 796 s. ISBN 0-201-10088-6. info
  • APPEL, Andrew W. Modern compiler implementation in Java. Cambridge: Cambridge University Press, 1998, x, 548. ISBN 0521583888. info
  • COOPER, Keith D. a Linda TORCZON. Engineering a compiler. Second Edition.San Francisco: Morgan Kaufmann Publishers, 2012. ISBN 978-0-12-088478-0
  • COOPER, Keith D. and Linda TORCZON. Engineering a compiler. San Francisco: Morgan Kaufmann Publishers, 2004, xxx, 801. ISBN 155860698X. info
  • GRUNE, Dick. Modern compiler design. Chichester: John Wiley & Sons, 2000, xviii, 736. ISBN 0471976970. info
Teaching methods
Lectures, homeworks, home reading, class discussion
Assessment methods
written final exam without any reading materials (closed book).
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2021, Autumn 2022, Spring 2024, Spring 2025.
  • Enrolment Statistics (Autumn 2020, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2020/PA008