Fakulta informačních technologií VUT v Brně

Detail předmětu

Formální jazyky a překladače

IFJ Ak. rok 2006/2007 zimní semestr 5 kreditů

Aktuální akademický rok

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.

Garant předmětu

Jazyk výuky

český

Zakončení

zápočet+zkouška (písemná)

Rozsah

39 hod. přednášky, 13 hod. projekty

Bodové hodnocení

55 zkouška, 20 půlsemestrální test, 25 projekty

Zajišťuje ústav

Přednášející

Cvičící

Bidlo Radek, Ing. (UIFS FIT VUT)
Blatný Petr, Ing. (UIFS FIT VUT)
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Lukáš Roman, Ing., Ph.D. (UIFS FIT VUT)
Masopust Tomáš, RNDr., Ph.D. (UIFS FIT VUT)
Rychnovský Lukáš, Ing. (UIFS FIT VUT)
Schönecker Rudolf, Ing. (UIFS FIT VUT)
Škrkal Oto, Ing. (UIFS FIT VUT)
Techet Jiří, Ing., Ph.D. (UIFS FIT VUT)

Získané dovednosti, znalosti a kompetence z předmětu

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

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

Literatura studijní

  • kopie přednášek (elektronické i papírové)
  • Meduna, A.: Automata and Languages. London, Springer, 2000.

Literatura referenční

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

Osnova přednášek

  • Formální jazyky.
  • Chomského klasifikace jazyků a korespondující modely.
  • 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 symbolu.
  • 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.
  • Poznámky a shrnutí. Předběžná diskuze obsahu navazujícího předmětu VYP.

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

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

  • Program IT-BC-3, obor BIT, 2. ročník, povinný
Nahoru