Module also offered within study programmes:
General information:
Code:
UBPJO-160
Name:
Compilation theory
Profile of education:
Academic (A)
Lecture language:
English
Semester:
Fall
Course homepage:
 
Responsible teacher:
Kuta Marcin (mkuta@agh.edu.pl)
Academic teachers:
Kuta Marcin (mkuta@agh.edu.pl)
Module summary

Students will learn how to program an abstract syntax and lexical analyzer, design a parser and implement an interpreter.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Skills
M_U001 The student knows how to implement an interpreter Project
M_U002 The student knows how to program an abstract syntax and lexical analyzer. Project
M_U003 The student knows how to design a parser. Project
M_U004 The student knows how to devise a type checker. Project
M_U005 The student knows how to proceed with code generation Project
M_U006 The student knows how to perform liveness analysis Project
Knowledge
M_W001 The student is familiar with regular expressions, finite automata, Lex and ML-Lex Test
M_W002 The student understands basic notions of context-free grammars, parsing and Yacc Test
M_W003 The student has a working knowledge of symbol tables and type-checking Test
M_W004 The student posseses a deep understanding of stack frames, intermediate trees, expressions to trees, declarations to trees, canonical trees, instruction selection, assemby code, liveness, register allocation and linking. Test
M_W005 The student is able to comprehend garbage collection, object-oriented languages, higher-order functions and closures Test
M_W006 The student knows about parser generation, just-in-time compilation, program analysis, optimization Test
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Skills
M_U001 The student knows how to implement an interpreter - - + - - - - - - - -
M_U002 The student knows how to program an abstract syntax and lexical analyzer. - - + - - - - - - - -
M_U003 The student knows how to design a parser. - - + - - - - - - - -
M_U004 The student knows how to devise a type checker. - - + - - - - - - - -
M_U005 The student knows how to proceed with code generation - - + - - - - - - - -
M_U006 The student knows how to perform liveness analysis - - + - - - - - - - -
Knowledge
M_W001 The student is familiar with regular expressions, finite automata, Lex and ML-Lex + - - - - - - - - - -
M_W002 The student understands basic notions of context-free grammars, parsing and Yacc + - - - - - - - - - -
M_W003 The student has a working knowledge of symbol tables and type-checking + - - - - - - - - - -
M_W004 The student posseses a deep understanding of stack frames, intermediate trees, expressions to trees, declarations to trees, canonical trees, instruction selection, assemby code, liveness, register allocation and linking. + - - - - - - - - - -
M_W005 The student is able to comprehend garbage collection, object-oriented languages, higher-order functions and closures + - - - - - - - - - -
M_W006 The student knows about parser generation, just-in-time compilation, program analysis, optimization + - - - - - - - - - -
Module content
Lectures:
Lectures on compilation theory

(1) Regular expressions, finite automata, PLY lex.
(2) Context-free grammars, parsing and PLY Yacc.
(3) Symbol tables, type-checking.
(4) Stack frames, intermediate trees, expressions to trees, declarations to trees, canonical trees.
(5) Instruction selection, assemby code, liveness, register allocation, linking.
(6) Garbage collection, object-oriented languages, higher-order functions, closured.
(7) Parser generation, just-in-time compilation, program analysis, optimization.

Laboratory classes:
Labs in compilation theory

(1) Programming assignment 1: interpreter.
(2) Programming assignment 2: lexical analyzer.
(3) Programming assignment 3: parser.
(4) Programming assignment 4: abstract syntax trees and type checker.
(5) Programming assignment 5: code interpreter/generator.
(6) Programming assignment 6: optimization.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 100 h
Module ECTS credits 4 ECTS
Participation in lectures 14 h
Realization of independently performed tasks 17 h
Participation in laboratory classes 14 h
Completion of a project 20 h
Preparation for classes 20 h
Contact hours 15 h
Additional information
Method of calculating the final grade:

6 programming assignment worth 60% total.
2 mid-term exams worth 40% total.

Prerequisites and additional requirements:

Theory of automata and formal languages

Recommended literature and teaching resources:

(1) Aho A. V., Lam M., Sethi R., Ullman J. D.: Compilers. Principles, Techniques and Tools, 2nd ed., Addison-Wesley, 2007
(2) Terence Parr : Language Implementation Patterns, Pragmatic Bookshelf, 2009
(3) Andrew Appel, Jens Palsberg: Modern Compiler Implementation in Java. Cambridge University Press, 2002.

Scientific publications of module course instructors related to the topic of the module:

Additional scientific publications not specified

Additional information:

None