Detail předmětu
Formální jazyky a překladače
IFJ Ak. rok 2023/2024 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.
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)
- 20 bodů půlsemestrální test (písemná část)
- 25 bodů projekty
Zajišťuje ústav
Přednášející
Kocman Radim, Ing., Ph.D. (CVT)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Cvičící
Stránky předmětu
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č.
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čů.
Předmět IFJ:
- 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
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 (20 bodů), u které neexistuje náhradní, ani opravný termín. Dále studenti řeší v průběhu semestru jeden týmový projekt (25 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 (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í tří termínů.
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.
Rozvrh
Den | Typ | Týdny | Místn. | Od | Do | Kapacita | PSK | Skup | Info |
---|---|---|---|---|---|---|---|---|---|
St | zkouška | 2023-10-25 | C228 E104 E105 E112 | 11:00 | 12:20 | PZK St 25. 10. 2023 - Běh 1 | |||
St | přednáška | 1., 2., 3., 4., 7., 8., 9., 11., 13. výuky | E104 E112 | 11:00 | 13:50 | 294 | 2BIA 3BIT | xx 10 - 19 | Meduna |
St | přednáška | 1., 2., 3., 4., 7., 8., 9., 13. výuky | E105 | 11:00 | 13:50 | 294 | 2BIA 3BIT | xx 10 - 19 | Meduna |
St | přednáška | 6., 10., 12. výuky | E104 E105 E112 | 11:00 | 13:50 | 294 | 2BIA 3BIT | xx 10 - 19 | Křivka |
St | přednáška | 2023-10-18 | E104 E105 E112 | 11:00 | 13:50 | 294 | 2BIA 3BIT | xx 10 - 19 | Kocman |
St | zkouška | 2023-10-25 | E104 E105 E112 | 12:30 | 13:50 | PZK St 25. 10. 2023 - Běh 2 | |||
Čt | zkouška | 2023-10-26 | D105 | 08:00 | 09:20 | PZK Čt 26. 10. 2023 - Běh 3 | |||
Čt | přednáška | 1., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12. výuky | D105 | 08:00 | 10:50 | 316 | 2BIB 3BIT | xx 20 - 29 | Burgetová |
Čt | přednáška | 2023-12-14 | D105 | 08:00 | 10:50 | 316 | 2BIB 3BIT | xx 20 - 29 | Křivka |
Čt | zkouška | 2023-10-26 | C228 D105 | 09:30 | 10:50 | PZK Čt 26. 10. 2023 - Běh 4 | |||
Čt | ostatní | 2023-11-16 | E105 | 11:00 | 11:50 | 72 | 2BIA 2BIB | xx 10 - 19 20 - 29 | Křivka IFJ Democviko projekt |
Pá | zkouška | 2024-01-12 | A112 D0206 D0207 D105 E104 E105 E112 | 08:00 | 10:50 | IFJ: řádná | |||
Pá | zkouška | 2024-01-26 | E104 | 09:00 | 10:50 | IFJ: 2. opravný termín | |||
Pá | zkouška | 2024-01-19 | D0206 D0207 D105 E104 E112 | 11:00 | 12:50 | IFJ: 1. opravný termín | |||
Pá | zkouška | 2024-01-26 | E104 | 11:00 | 11:50 | 2. termín - prodloužení | |||
Pá | zkouška | 2024-01-19 | E104 | 13:00 | 13:50 | 1. termín - prodloužení |
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ý
- Program IT-BC-3, obor BIT, 2. ročník, povinný