Formální jazyky a překladače

• 39 hod. přednášky
• 13 hod. projekty

• 55 bodů závěrečná zkouška (písemná část)
• 17 bodů půlsemestrální test (písemná část)
• 28 bodů projekty

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

• Diskrétní matematika (IDM)

Znalost diskrétní matematiky.

• kopie snímků přednášek (elektronické i papírové)
• Meduna, A.: Elements of Compiler Design. New York, US, Tailor & Francis, 2008.
• Meduna, A.: Automata and Languages. London, Springer, 2000.

• Parsons, T. W.: Introduction to Compiler Construction. Freeman, New York, 1992.

1. Formální jazyky.
2. Překlad jazyků a struktura překladače.
3. Regulární jazyky a jejich modely: regulární výrazy a konečné automaty.
4. Lexikální analýza: lexikální analyzátory; Lex; tabulka symbolů.
5. Bezkontextové jazyky a jejich modely: bezkontextové gramatiky a zásobníkové automaty.
6. Syntaktická analýza: deterministická syntaktická analýza; FIRST a FOLLOW, LL gramatiky.
7. Deterministická syntaktická analýza shora dolů: rekurzívní sestup.
8. Deterministická syntaktická analýza zdola nahoru: jednoduchá precedenční analýza; Yacc.
9. Sémantická analýza a generování vnitřní formy programu.
10. Optimalizace.
11. Generování cílového kódu.
12. Chomského klasifikace jazyků a korespondující modely.
13. Poznámky a shrnutí. Předběžná diskuze obsahu navazujícího předmětu VYPe.

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 a obhajoby).

Průběžná kontrola studia probíhá v rámci půlsemestrální zkoušky (17 bodů), u které neexistuje opravný termín. Dále studenti řeší v průběhu semestru jeden týmový projekt (28 bodů), který je odevzdáván ve stanoveném termínu. 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ě 4 body jsou za programovou část projektu.

Pokud se 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 (17 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 a z toho 4 z programové časti.
• Schopnost aplikace teoretických poznatků ověřuje týmový projekt (28 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í tří termínů. Pro získání bodů ze zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena nejméně 20 body. V opačném případě bude zkouška hodnocena 0 body.