Detail předmětu

Výstavba překladačů (v angličtině)

FIT-VYPaAk. rok: 2024/2025

Předmět diskutuje pokročilá a doplňující témata týkající se konstrukce překladačů, která svou náročností překračují bakalářskou úroveň. Tato diskuse se bude soustředit na následující tři okruhy: (I) Pokročilá témata konstrukce klasických kompilátorů: konstrukce LR rozkladových tabulek, precedenční analýza vyššího řádu, důležité metody syntaktické analýzy s návraty, pokročilé metody optimalizace. (II) Principy paralelních kompilátorů: struktura paralelního překladače, fundamentální metody paralelní syntaktické analýzy, základní modely pro paralelní překlad. (III) Formální překladové modely a jejich vlastnosti: převodníky, překladové gramatiky, vlastnosti syntaxí řízených překladů (charakterizující jazyky, nekonečná hierarchie překladů apod.), vlastnosti formálních jazyků relevantní pro překladače, moderní formální modely pro překlad.

Odkazy

Proč je předmět vyučován

V předmětu VYPa se na magisterské úrovni vyučuje tvorba překladačů, což vyžaduje správnou kombinaci teoretických znalostí i praktických dovedností. Z teorie představuje matematické modely jako automaty a gramatiky, které stojí v pozadí překladu a jeho fází. Na základě těchto modelů jsou potom co nejpřístupnějším způsobem vyučovány další koncepty, metody a techniky používané při návrhu překladačů.

Z praktického pohledu jsou vyučovány vybrané techniky implementace překladačů. U těchto technik je krok za krokem probírána jejich implementace. Dále je prezentována řada příkladů a programů, které ukazují aplikace různých algoritmů pro překlad.

Po absolvování kurzu by měl být student schopen chápat proces překladu, tvorby překladače a měl by být schopen se dále v dané oblasti zdokonalovat s využitím pokročilé literatury.

Jazyk výuky

angličtina

Počet kreditů

5

Garant předmětu

prof. RNDr. Alexandr Meduna, CSc.

Zajišťuje ústav

Ústav informačních systémů (UIFS)

Nabízen zahraničním studentům

Všech fakult

Vstupní znalosti

Základní znalost diskrétní matematiky.

Pravidla hodnocení a ukončení předmětu

  • Půlsemestrální písemná zkouška - 15 bodů
  • Hodnocené projekt(y) - 30 bodů
  • Závěrečná písemná zkouška - 55 bodů

Pokud v průběhu semestru student onemocní nebo se vyskytne jiná překážka ve studiu, je třeba tuto překážku řádně ohlásit a doložit. Pak k ní lze přihlédnout a přizpůsobit jí hodnocení:
  • U projektu může student požádat příslušného učitele o přiměřené prodloužení termínu pro odevzdání.
  • Pokud se student nemohl zúčastnit půlsemestrální zkoušky, může přednášejícího požádat, aby body za půlsemestrální zkoušku byly odvozeny od bodového zisku u prvního termínu zkoušky, kterého se zúčastní.
  • Pokud se student nemůže zúčastnit obhajoby projektu a ostatní členové týmu s tím vysloví souhlas, může získat za obhajobu stejný počet bodů jako na obhajobě přítomní členové týmu.

Učební cíle

Detailně objasnit konstrukci překladačů, včetně moderních paralelních kompilátorů. Podrobně se seznámit s formálními překladovými modely a jejich vlastnostmi.
Schopnost sestrojit náročný překladač, včetně moderního paralelního kompilátoru. Hluboká obeznámenost s formálními překladovými modely a jejich vlastnostmi.
Obecná znalost formálních modelů pro překlad a jejich aplikace.

Základní literatura

A. Meduna: Elements of Compiler Design. Taylor & Francis, 2008. (EN)
K.D. Cooper, L. Torczon: Engineering a Compiler, 3rd edition. Morgan Kaufmann, 2022. (EN)
A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman: Compilers: Principles, Techniques, and Tools, 2nd edition. Pearson Education, 2006. (EN)

Doporučená literatura

C.L. Jeffery: Build Your Own Programming Language: A programmer's guide to designing compilers, interpreters, and DSLs for solving modern computing problems. Packt Publishing, 2021. (EN)
D. Grune: Modern Compiler Design, 2nd edition. Springer, 2016. (EN)
D. Thain: Introduction to Compilers and Language Design, 2nd edition. Independently published, 2020. (EN)
D. Watson: A Practical Approach to Compiler Construction. Springer, 2017. (EN)
J. I. Moore: Introduction to Compiler Design: An Object-Oriented Approach Using Java, 2nd edition. SoftMoore Consulting, 2020. (EN)
R. Wilhelm, H. Seidl: Compiler Design: Virtual Machines. Springer, 2010. (EN)
T.Æ. Mogensen: Introduction to Compiler Design, 2nd edition. ‎ Springer, 2017. (EN)

Elearning

eLearning: aktuální otevřený kurz

Zařazení předmětu ve studijních plánech

  • Program IT-MGR-1H magisterský navazující

    specializace MGH , 0 ročník, zimní semestr, doporučený kurs

  • Program MIT-EN magisterský navazující 0 ročník, zimní semestr, povinný

  • Program MITAI magisterský navazující

    specializace NGRI , 0 ročník, zimní semestr, volitelný
    specializace NADE , 0 ročník, zimní semestr, volitelný
    specializace NISD , 0 ročník, zimní semestr, volitelný
    specializace NMAT , 0 ročník, zimní semestr, povinný
    specializace NSEC , 0 ročník, zimní semestr, volitelný
    specializace NISY do 2020/21 , 0 ročník, zimní semestr, volitelný
    specializace NNET , 0 ročník, zimní semestr, volitelný
    specializace NMAL , 0 ročník, zimní semestr, volitelný
    specializace NCPS , 0 ročník, zimní semestr, volitelný
    specializace NHPC , 0 ročník, zimní semestr, volitelný
    specializace NVER , 0 ročník, zimní semestr, volitelný
    specializace NIDE , 0 ročník, zimní semestr, volitelný
    specializace NISY , 0 ročník, zimní semestr, volitelný
    specializace NEMB do 2023/24 , 0 ročník, zimní semestr, volitelný
    specializace NSPE , 0 ročník, zimní semestr, volitelný
    specializace NEMB , 0 ročník, zimní semestr, volitelný
    specializace NBIO , 0 ročník, zimní semestr, volitelný
    specializace NSEN , 0 ročník, zimní semestr, volitelný
    specializace NVIZ , 0 ročník, zimní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Alexandr Meduna, CSc.
Ing. Zbyněk Křivka, Ph.D.
Ing. Martin Havel

Osnova

  1. Úvod: zopakování struktury překladače.
  2. Deterministická syntaktická analýza zdola nahoru: konstrukce LR rozkladových tabulek.
  3. Deterministická syntaktická analýza zdola nahoru: precedenční analýza vyššího řádu.
  4. Obecná syntaktická analýza: důležité metody syntaktické analýzy s návraty.
  5. Pokročilé metody optimalizace.
  6. Paralelní kompilátory: struktura paralelního překladače.
  7. Paralelní syntaktická analýza: principy.
  8. Deterministická paralelní syntaktická analýza shora dolů.
  9. Deterministická paralelní syntaktická analýza zdola nahoru.
  10. Generování paralelního kódu.
  11. Moderní formální prostředky pro specifikaci jazyka: řízené a paralelní modely.
  12. Formální prostředky pro specifikaci překladu: převodníky a překladové gramatiky.
  13. Očekávané budoucí trendy, shrnutí, závěr.

Projekt

13 hod., povinná

Vyučující / Lektor

Ing. Zbyněk Křivka, Ph.D.

Osnova

  1. Vytvoření pokročilého kompilátoru.
  2. Příprava a prezentace vybraného tématu o kompilátorech.

Elearning

eLearning: aktuální otevřený kurz