Detail předmětu

Formální jazyky a překladače

FIT-IFJAk. rok: 2010/2011

Kurs diskutuje formální jazyky a jejich modely. Na bázi těchto modelu 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řeklady. (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 symbolu. (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áni kódu: sémantická analýze, generováni vnitřní formy programu, optimalizace, generováni 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

diskrétní matematika

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

  • 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áni 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 VYP.

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í zkouška v polovině semestru. Průběžná kontrola řešení projektu vedoucím.

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áni 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 VYP.

Projekt

13 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Alexandr Meduna, CSc.