Detail předmětu

Formální jazyky a překladače

FIT-IFJAk. rok: 2018/2019

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.

Výsledky učení předmětu

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

Prerekvizity

Znalost diskrétní matematiky.

Doporučená nebo povinná literatura

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

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

Způsob a kritéria hodnocení

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.

Jazyk výuky

čeština, angličtina

Osnovy výuky

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

Cíl

Seznámit se s formálními jazyky a jejich modely. Objasnit principy konstrukce překladačů na základě těchto modelů.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

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

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

  • Program IT-BC-3 bakalářský

    obor BIT , 2. ročník, zimní semestr, 5 kreditů, povinný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

Osnova


  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.

Projekt

13 hod., povinná

Vyučující / Lektor

Osnova

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