Fakulta informačních technologií VUT v Brně

Detail předmětu

Formální jazyky a překladače

IFJ Ak. rok 2018/2019 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

Zástupce garanta předmětu

Jazyk výuky

česky

Zakončení

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

Rozsah

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

Bodové hodnocení

55 zkouška, 20 půlsemestrální test, 25 projekty

Zajišťuje ústav

Přednášející

Cvičící

Kocman Radim, Ing. (UIFS FIT VUT)
Křena Bohuslav, Ing., Ph.D. (UITS FIT VUT)
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Martiško Jakub, Ing. (UIFS FIT VUT)
Regéciová Dominika, Ing. (UIFS FIT VUT)
Zobal Lukáš, Ing. (UIFS FIT VUT)

Stránky předmětu

Získané dovednosti, znalosti a kompetence z předmětu

Základní obeznámenost s formálními jazyky a jejich modely. Schopnost sestrojit překladač.

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

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;
  • diskutuje pojem Turingova stroje jakožto univerzálního formalismu pro intuitivní popis pojmu procedura;
  • pokrývá základy teorie výpočtu, přesněji vyčíslitelnost a rozhodnutelnost.

Stručně řečeno, předmět prezentuje formální jazyky a jejich modely se zaměřením na jejich aplikaci v programátorské praxi. Všechny formalismy jsou představeny s dostatečnou přesností, aby neutrpěla srozumitelnost ani správnost. Každému formalismu předchází intuitivní vysvětlení, takže jsou studenti schopni pochopit i poměrně náročné pasáže. Po absolvování tohoto kurzu by měl být student schopen porozumět základům formálních jazyků, výpočtu, psaní překladačů a také by měl být schopen navazujícího studia z pokročilejší literatury.

Požadované prerekvizitní znalosti a dovednosti

Znalost diskrétní matematiky.

Literatura studijní

  • kopie přednášek (elektronické i papírové)
  • 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.

Literatura referenční

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

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č/interpret jednoduchého programovacího jazyka (včetně odpovídající dokumentace).

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.

Kontrolovaná výuka

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

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

DenTypTýdnyMístn.OdDoPSKSkupInfo
Stzkouška2019-01-30 D105 09:0011:50 2BIA 2BIB 3BIT 2. oprava
Stpřednáškavýuky E104 E105 E112 11:0013:50 2BIA 3BIT xx
Čtpřednáškavýuky E104 E105 E112 08:0010:50 2BIB 3BIT xx
Čtzkouška2019-01-24 D105 09:0011:50 2BIA 2BIB 3BIT 1. oprava
Čtzkouška2019-01-03 D0206 D105 E104 E112 10:0012:50 2BIA 2BIB 3BIT řádná

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

  • Program BIT, 2. ročník, povinný
  • Program IT-BC-3, obor BIT, 2. ročník, povinný
Nahoru