Detail předmětu
Formální jazyky a překladače
FIT-IFJAk. rok: 2022/2023
Kurs diskutuje formální jazyky a jejich modely. Na bázi těchto modelů 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řekladače. (II) Regulární jazyky a lexikální analýza: regulární jazyky a výrazy, konečné automaty a převodníky, lexikální analyzátory; Lex; tabulka symbolů. (III) Bezkontextové jazyky a syntaktická analýza: bezkontextové jazyky a gramatiky, zásobníkové automaty a převodníky, syntaktická analýza; deterministická syntaktická analýza, LL gramatiky, deterministická analýza shora dolů (rekurzivní sestup); princip deterministické analýzy zdola nahoru; Yacc. (IV) Sémantická analýza a generování kódu: sémantická analýza, generování vnitřní formy programu, optimalizace, generování cílového kódu.
Jazyk výuky
Počet kreditů
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Prerekvizity
Způsob a kritéria hodnocení
Učební cíle
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Pokud v průběhu semestru u studenta vyskytne překážka ve studiu (např. nemoc), je třeba tuto překážku řádně ohlásit a doložit.
- Půlsemestrální písemná zkouška se koná přibližně v polovině semestru bez možnosti náhradního, či opravného termínu (20 bodů). Pokud se student nemohl zúčastnit půlsemestrální zkoušky, může garanta 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í. Podmínkou pro přistoupení k tomuto termínu zkoušky je zisk alespoň 12 bodů dohromady ze všech částí projektu.
- Schopnost aplikace teoretických poznatků ověřuje týmový projekt (25 bodů), kde průběžnou kontrolu provádí studentský vedoucí každého týmu. Při onemocnění většiny členů týmu může tým požádat příslušného učitele o drobné prodloužení termínu pro odevzdání projektu.
- Na konci semestru se koná závěrečná zkouška (55 bodů) s možností dvou opravných termínů.
Prerekvizity a korekvizity
- doporučená prerekvizita
Diskrétní matematika
Doporučená literatura
Meduna, A.: Automata and Languages. London, Springer, 2000.
Meduna, A.: Elements of Compiler Design. New York, US, Tailor & Francis, 2008.
Meduna, A.: Formal Languages and Computation. New York, Taylor & Francis, 2014.
Parsons, T. W.: Introduction to Compiler Construction. Freeman, New York, 1992.
Elearning
Zařazení předmětu ve studijních plánech
Typ (způsob) výuky
Přednáška
Vyučující / Lektor
Osnova
- Formální jazyky.
- Překlad jazyků a struktura překladače.
- Regulární jazyky a jejich modely: regulární výrazy a konečné automaty.
- Lexikální analýza: lexikální analyzátory; Lex; tabulka symbolů.
- Bezkontextové jazyky a jejich modely: bezkontextové gramatiky a zásobníkové automaty.
- Syntaktická analýza: deterministická syntaktická analýza; FIRST a FOLLOW, LL gramatiky.
- Deterministická syntaktická analýza shora dolů: rekurzívní sestup.
- Deterministická syntaktická analýza zdola nahoru: jednoduchá precedenční analýza; Yacc.
- Sémantická analýza a generování vnitřní formy programu.
- Optimalizace.
- Generování cílového kódu.
- Chomského klasifikace jazyků a korespondující modely.
- Poznámky a shrnutí. Předběžná diskuze obsahu navazujícího předmětu VYPe.
Projekt
Vyučující / Lektor
Osnova
Studenti v rámci týmového projektu (3-4 studenti na tým) implementují překladač jednoduchého programovacího jazyka (včetně odpovídající dokumentace).
Elearning