Detail předmětu
Formální jazyky a překladače
IFJ Ak. rok 2024/2025 zimní semestr 5 kreditů
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.
Odkazy
- Veřejné stránky předmětu (v privátní části jsou snímky (CZ i EN) k přednáškám a pomocné materiály k projektu)
- E-learning stránky pro ZS 2024/25 (Moodle, privátní, pouze v češtině) pro podporu projektu a poskytování dalších materiálů k předmětu
Proč je předmět vyučován
Předmět IFJ dává na bakalářské úrovni jasný a ucelený úvod do teorie formálních jazyků a jejich aplikace v informatice. Úvod pokrývá témata zaměřená na formální jazyky a jejich model (především gramatiky a automaty), dále nastiňuje základní myšlenky teorie výpočtu včetně vyčíslitelnosti a rozhodnutelnosti. Pro zdůraznění vazby teorie na praxi je demonstrována aplikace ve zpracování programovacích jazyků a implementaci překladačů.
- pokrývá důležité základní koncepty teorie formálních jazyků;
- vysvětluje, jak jsou jazykové modely využívány při překladu;
- zaměřuje se na analyzátory programovacích jazyků jako lexikální analyzátor a syntaktický analyzátor postavené na regulárních výrazech, konečných automatech, bezkontextových gramatikách a zásobníkových automatech
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.
Garant předmětu
Koordinátor předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 13 hod. projekty
Bodové hodnocení
- 55 bodů závěrečná zkouška (písemná část)
- 17 bodů půlsemestrální test (písemná část)
- 28 bodů projekty
Zajišťuje ústav
Přednášející
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Cvičící
Cíle předmětu
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č.
Doporučené prerekvizity
- Diskrétní matematika (IDM)
Požadované prerekvizitní znalosti a dovednosti
Znalost diskrétní matematiky.
Literatura studijní
Osnova přednášek
- 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.
Osnova ostatní - projekty, práce
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
Průběžná kontrola studia probíhá v rámci půlsemestrální zkoušky (17 bodů), u které neexistuje náhradní, ani 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.
- 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ů.
Rozvrh
| Den | Typ | Týdny | Místn. | Od | Do | Kapacita | PSK | Skup | Info |
|---|---|---|---|---|---|---|---|---|---|
| St | zkouška | 2024-10-30 | E104 E105 E112 | 11:00 | 12:20 | IFJ: PZK St 30. 10. 2024 - Běh 1 | |||
| St | přednáška | 1., 2., 3., 4., 5., 6., 7., 9., 10., 11., 12., 13. výuky | E104 E105 E112 | 11:00 | 13:50 | 294 | 2BIA 3BIT | 10 - 19 xx | Meduna |
| St | přednáška | 2024-11-06 | E104 E105 E112 | 11:00 | 13:50 | 294 | 2BIA 3BIT | 10 - 19 xx | Křivka |
| St | zkouška | 2024-10-30 | E104 E105 E112 | 12:30 | 13:50 | IFJ: PZK St 30. 10. 2024 - Běh 2 | |||
| Čt | zkouška | 2024-10-31 | E104 E105 E112 | 08:00 | 09:20 | IFJ: PZK Čt 31. 10. 2024 - Běh 3 | |||
| Čt | přednáška | 1., 2., 4., 5., 6., 7., 8., 9., 10., 11., 13. výuky | E104 E105 E112 | 08:00 | 10:50 | 294 | 2BIB 3BIT | 20 - 29 xx | Burgetová |
| Čt | přednáška | 3., 12. výuky | E104 E105 E112 | 08:00 | 10:50 | 294 | 2BIB 3BIT | 20 - 29 xx | Křivka |
| Čt | zkouška | 2025-01-16 | A112 A113 D0206 D0207 D105 E104 E105 E112 G202 L314 | 09:00 | 11:50 | 1. termín | |||
| Čt | zkouška | 2024-10-31 | E104 E105 E112 | 09:30 | 10:50 | IFJ: PZK Čt 31. 10. 2024 - Běh 4 | |||
| Čt | zkouška | 2025-01-30 | D0206 D0207 D105 | 10:00 | 11:50 | 2. termín | |||
| Čt | zkouška | 2025-01-30 | E104 | 10:00 | 12:50 | 2. termín - prodloužení | |||
| Čt | zkouška | 2025-01-30 | E112 | 10:00 | 11:50 | 2. termín | |||
| Čt | zkouška | 2025-02-06 | D0207 | 14:00 | 16:50 | 3. termín - prodloužení | |||
| Čt | zkouška | 2025-02-06 | D105 | 14:00 | 15:50 | 3. termín |
Zařazení předmětu ve studijních plánech
- Program BIT, 2. ročník, povinný
- Program BIT (anglicky), 2. ročník, povinný