Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2022/2023

Programming Languages and Compilers

The course is not on the list Without time-table
Code Completion Credits Range Language
BI-PJP Z,ZK 5 2P+1C Czech
Enrollement in the course requires an assessment of the following courses:
Automata and Grammars (BI-AAG)
Lecturer:
Jan Janoušek (guarantor)
Tutor:
Tomáš Pecka, Štěpán Plachý, Radomír Polách
Supervisor:
Department of Theoretical Computer Science
Synopsis:

Students master basic methods of implementation of common high-level programming languages. They get experience with the design and implementation of individual compiler parts for a simple programming language: data types, subroutines, and data abstractions. Students are able to formally specify a translation of a text that has a certain syntax into a target form and write a compiler based on such a specification. The notion of compiler in this context is not limited to compilers of programming languages, but extends to all other programs for parsing and processing text in a language defined by a LL(1) grammar.

Requirements:
Syllabus of lectures:

1. Structure of a compiler, lexical analysis.

2. Deterministic top-down parsing: LL parsing.

3. [2] Implementing LL parsing, properties of LL grammars.

5. Transformations to LL(1) grammars, error recovery during LL parsing.

6. Formalisms for syntax-directed translation and semantics: translation and attributed grammar.

7. One-pass attributed translation directed by LL parsing, L-attributed grammars, examples of simple translations.

8. Data structures of a compiler, intermediate representations.

9. Abstract syntax tree, three address code - intermediate representations of GNU compiler.

10. Intermediate representations of the LLVM compiler.

11. An example of a simple compiler.

12. Local code optimization.

13. Other variants of LL parsing.

Syllabus of tutorials:

1. Lexer design and implementation.

2. Parser implementation using recursive descent.

3. Attribute translation grammars.

4. Compiling to a language of a stack machine.

5. Compiling to a syntax tree.

6. [2] Project consultations.

Study Objective:

After completing the course, students will be able to formally specify a translation of a text that has a certain syntax into the target form and write a compiler based on such specification. The notion of compiler in this context is not limited to compilers of programming languages but extends to all other programs for parsing and processing text in a language defined by a LL(1) grammar.

Study materials:

1. Trávníček, J. - Janoušek, J. (25%) - Melichar, B. - Cleophas, L.: On modifcation of Boyer-Moore-Horspool's algorithm for tree pattern matching in linearised trees. Theoretical Computer Science, 830: 60{90, 2020.

2. Plachý, Š. - Janoušek, J. (50%): On Synchronizing Tree Automata and Their Work-Optimal Parallel Run, Usable for Parallel Tree Pattern Matching. In SOFSEM 2020: Theory and Practice of Computer Science, Springer, pp. 576{586, 2020. ISBN 978-3-030-38918-5.

3. Šestáková, E. - Janoušek, J. (50%): Automata Approach to XML Data Indexing. Information, 9(1): 12{12, 2018.

4. Šestáková, E. - Melichar, B. - Janoušek, J. (33%): Constrained Approximate Subtree Matching by Finite Automata. In Proceedings of the Prague Stringology Conference 2018, CVUT v Praze, 2018, pp. 79{90. ISBN 978-80-01-06484-9.

5. Polách, R. - Trávníček, J. - Janoušek, J. (25%) - Melichar, B.: Ecient Determinisation of Visibly and Height-Deterministic Pushdown Automata. Computer Languages, Systems and Structures, 46: 91{105, 2016.

Note:
Further information:
https://courses.fit.cvut.cz/BI-PJP/
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2022-11-28
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet1123106.html