Název:

Formální jazyky a překladače

Zkratka:IFJ
Ak.rok:2017/2018
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
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)
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í:Handlíř Jaroslav, Ing. (UIFS)
Kocman Radim, Ing. (UIFS)
Křena Bohuslav, Ing., Ph.D. (UITS)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Martiško Jakub, Ing. (UIFS)
Milkovič Marek, 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č.
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 řeší týmový projekt (3-4 studenti na tým) implementace překladače/interpretu 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.
Kontrolovaná výuka:
  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ů). Dále je vyžadována tvorba týmového projektu ověřující schopnost aplikace teoretických poznatků (25 bodů), kde průběžnou kontrolu provádí studentský vedoucí každého týmu. 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.227.31.145
Přepnout na IPv6 spojení

DNSSEC [dnssec]