Detail předmětu

Formální jazyky a překladače (v angličtině)

FIT-IFJeAk. rok: 2024/2025

Kurs diskutuje formální jazyky a jejich modely. Na bázi těchto modelu objasňuje konstrukci překladačů. Výklad je organizován následovně: (I) Základní pojmy: formální jazyky a jejich modely, gramatiky, automaty; překlady. (II) Regulární jazyky a lexikální analýza: regulární jazyky a výrazy, konečné automaty, lexikální analyzátory; tabulka symbolu. (III) Bezkontextové jazyky a syntaktická analýza: bezkontextové jazyky a gramatiky, zásobníkové automaty, syntaktická analýza; deterministická syntaktická analýza, LL gramatiky, deterministická analýza shora dolů (rekurzivní sestup); princip deterministické analýzy zdola nahoru. (IV) Sémantická analýza a generováni kódu: sémantická analýza, generováni vnitřní formy programu, optimalizace, generováni cílového kódu.

Odkazy

Podmínky zápočtu

Udělení zápočtu je podmíněno získáním min. 20 bodů v průběhu semestru, z nichž nejméně 5 bodů je za projekt.

Jazyk výuky

angličtina

Počet kreditů

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

Diskrétní matematika.

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

Půlsemestrální zkouška v polovině semestru. Průběžná kontrola řešení projektu vedoucím.

Učební cíle

Seznámit se s formálními jazyky a jejich modely. Objasnit principy konstrukce překladačů na základě těchto modelů.
Základní obeznámenost s formálními jazyky a jejich modely. Schopnost sestrojit překladač.

Prerekvizity a korekvizity

Základní literatura

Meduna, A.: Formal Languages and Computation: Models and Their Applications. Taylor & Francis, New York, 2014. (EN)

Doporučená literatura

Meduna, A.: Elements of Compiler Design. Taylor & Francis, New York, 2008. (EN)
Nystrom, R.: Crafting Interpreters.‎ Genever Benning, 2021, Available online http://craftinginterpreters.com. (EN)
Parsons, T. W.: Introduction to Compiler Construction. Freeman, New York, 1992. (EN)

Elearning

eLearning: aktuální otevřený kurz

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

  • Program IT-BC-1H bakalářský

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

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

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

  • Základy formálních jazyků: abeceda, řetězce, jazyky.
  • Úvod do překladačů: struktura překladače.
  • Regulární jazyky a jejich modely: regulární výrazy, konečné automaty.
  • Varianty konečných automatů.
  • Lexikální analýza: lexikální analyzátor, tabulka symbolů.
  • Bezkontextové jazyky a jejich modely: bezkontextové gramatiky, zásobníkové automaty.
  • Zásobníkové automaty a obecný překlad.
  • Deterministická syntaktická analýza shora dolů: rekurzívní sestup.
  • Deterministická syntaktická analýza zdola nahoru: jednoduchá precedenční analýza.
  • Chomského hierarchie a korespondující modely. Závěrečné poznámky a shrnutí.

Projekt

13 hod., povinná

Vyučující / Lektor

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

Elearning

eLearning: aktuální otevřený kurz