Programovací jazyky a překladače

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Studenti budou umět základní metody implementace běžných programovacích jazyků. Získají zkušenost s návrhem a implementací překladu jednotlivých konstruktů programovacích jazyků (datové typy, podprogramy, apod). Naučí se formálně specifikovat překlad textu, který vyhovuje určité syntaxi, do cílové formy a na základě této specifikace napsat překladač. Překladačem se zde rozumí nejen překladač programovacího jazyka, ale jakýkoliv jiný program analyzující a zpracovávající text zapsaný v jazyku, který je dán LL(1) gramatikou.

Požadavky:

Osnova přednášek:

1. Struktura překladače, lexikální analyzátor.

2. Deterministická syntaktická analýza shora-dolů: LL syntaktická analýza.

3. [2] Implementace LL analýzy. Vlastnosti LL gramatik.

5. Transformace na LL(1) gramatiky, zotavení se z chyb při LL analýze.

6. Formalismy pro popis syntaxí řízeného překladu a sémantiky: překladové a atributové gramatiky.

7. Jednoprůchodový atributovaný překlad řízený LL analýzou, L-atributové gramatiky, příklady jednoduchých překladů.

8. Vnitřní datové struktury překladače, vnitřní reprezentace.

9. Abstraktní syntaktický strom, tříadresový kód - vnitřní reprezentace překladače GNU.

10. Vnitřní reprezentace překladače LLVM.

11. Příklady jednoduchého překladače.

12. Lokální optimalizace kódu.

13. Další varianty LL syntaktické analýzy.

Osnova cvičení:

1. Návrh a realizace lexikálního analyzátoru.

2. Realizace syntaktické analýzy rekurzívním sestupem.

3. Atributové překladové gramatiky.

4. Překlad do jazyka zásobníkového počítače.

5. Překlad do syntaktického stromu.

6. [2] Konzultace k domácí práci.

Cíle studia:

Předmět obsahuje přehled obecných rysů programovacích jazyků a výklad základních metod jejich implementace. Návrh a programová realizace jednotlivých částí překladače jsou podloženy základní teorií gramatik a automatů. Pro ilustraci metod je zaveden jednoduchý programovací jazyk a navržen a realizován překladač. Dále jsou probrány základní metody implementace datových typů, podprogramů a datových abstrakcí.

Studijní materiály:

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.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BI-PJP/

Další informace:

https://courses.fit.cvut.cz/BI-PJP/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Bc. program Informatika, pro fázi studia bez oboru, 2015-2020 (VO)
• Bc. obor Bezpečnost a informační technologie, 2015-2020 (volitelný předmět)
• Bc. obor Teoretická informatika, 2015-2020 (povinný předmět oboru)
• Bc. obor Počítačové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Informační systémy a management, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Počítačová grafika, 2015-2020 (volitelný předmět)
• Bc. obor Znalostní inženýrství, 2018-2020 (volitelný předmět)