Detail předmětu

Formální jazyky a překladače

FIT-IFJAk. rok: 2014/2015

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 a LR 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.

Jazyk výuky

čeština

Počet kreditů

5

Garant předmětu

prof. RNDr. Alexandr Meduna, CSc.

Zajišťuje ústav

Ústav informačních systémů (UIFS)

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.

Způsob a kritéria hodnocení

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ě 5 bodů je za programovou část projektu.

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 a LR gramatiky.
    • Deterministická syntaktická analýza shora dolů: rekurzívní sestup.
    • Deterministická syntaktická analýza zdola nahoru: jednoduchá precedenční analýza, LR 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-5 studentů na tým) implementace překladače/interpretu jednoduchého programovacího jazyka (včetně odpovídající dokumentace).

Učební cíle

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

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

Prerekvizity a korekvizity

Základní literatura

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

Doporučená 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.

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

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

    obor BIT , 2 ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Alexandr Meduna, CSc.

Osnova

  • 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 a LR gramatiky.
  • Deterministická syntaktická analýza shora dolů: rekurzívní sestup.
  • Deterministická syntaktická analýza zdola nahoru: jednoduchá precedenční analýza, LR 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.

Projekt

13 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Alexandr Meduna, CSc.