Název:

Formální jazyky a překladače

Zkratka:IFJ
Ak.rok:2018/2019
Semestr:zimní
Studijní plán:
ProgramObor/
specializace
RočníkPovinnost
BIT-2.povinný
IT-BC-3BIT2.povinný
Vyučovací jazyk:čeština
Informace veřejné:http://www.fit.vutbr.cz/study/courses/IFJ/public/
Kredity:5 kreditů
Ukončení:zápočet+zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvič.lab. cvič.poč. cvič.jiná
Rozsah:3900013
 zkouškatestycvičenílaboratořeostatní
Body:55200025
Garant:Meduna Alexander, prof. RNDr., CSc. (UIFS)
Zástupce garanta:Křivka Zbyněk, Ing., Ph.D. (UIFS)
Přednášející:Burgetová Ivana, Ing., Ph.D. (UIFS)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexander, prof. RNDr., CSc. (UIFS)
Cvičící:Kocman Radim, Ing. (UIFS)
Křena Bohuslav, Ing., Ph.D. (UITS)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Martiško Jakub, Ing. (UIFS)
Regéciová Dominika, Ing. (UIFS)
Zobal Lukáš, Ing. (UIFS)
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav informačních systémů FIT VUT v Brně
Prerekvizity: 
Diskrétní matematika (IDA), UMAT
Navazující:
Principy programovacích jazyků a OOP (IPP), UIFS
 
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ů.
Anotace:
  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.
Požadované prerekvizitní znalosti a dovednosti:
  Znalost diskrétní matematiky.
Získané dovednosti, znalosti a kompetence:
  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;
  • 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.

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).
Literatura referenční:
 
  • Parsons, T. W.: Introduction to Compiler Construction. Freeman, New York, 1992.
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.
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ů.
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.
 

Vaše IPv4 adresa: 54.163.20.123