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

česky, anglicky

Zakončení

zápočet+zkouška (písemná)

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í

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

Požadované prerekvizitní znalosti a dovednosti

Znalost diskrétní matematiky.

Literatura studijní

Osnova přednášek

  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.

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

DenTypTýdnyMístn.OdDoKapacitaPSKSkupInfo
St zkouška 2024-10-30 E104 E105 E112 11:0012:20 IFJ: PZK St 30. 10. 2024 - Běh 1
St přednáška výuky E104 E105 E112 11:0013:50294 2BIA 3BIT 10 - 19 xx Meduna
St zkouška 2024-10-30 E104 E105 E112 12:3013:50 IFJ: PZK St 30. 10. 2024 - Běh 2
Čt zkouška 2024-10-31 E104 E105 E112 08:0009:20 IFJ: PZK Čt 31. 10. 2024 - Běh 3
Čt přednáška 1., 2., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky E104 E105 E112 08:0010:50294 2BIB 3BIT 20 - 29 xx Burgetová
Čt přednáška 2024-10-03 E104 E105 E112 08:0010:50294 2BIB 3BIT 20 - 29 xx Křivka
Čt zkouška 2024-10-31 E104 E105 E112 09:3010:50 IFJ: PZK Čt 31. 10. 2024 - Běh 4

Zařazení předmětu ve studijních plánech

Nahoru