Detail předmětu

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

FIT-IFJeAk. rok: 2022/2023

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.

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

Výsledky učení předmětu

Základní obeznámenost s formálními jazyky a jejich modely. Schopnost sestrojit překladač.

Prerekvizity

Diskrétní matematika. Základní programátorské schopnosti.

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ů.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

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

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 MIT-EN magisterský navazující 1 ročník, zimní semestr, povinný

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

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

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

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

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í.

Cvičení odborného základu

13 hod., povinná

Vyučující / Lektor

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

Projekt

13 hod., povinná

Vyučující / Lektor

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

Elearning

eLearning: aktuální otevřený kurz