Detail předmětu
Formální jazyky a překladače
IFJe Ak. rok 2012/2013 zimní semestr 5 kreditů
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
Zakončení
Rozsah
- 26 hod. přednášky
- 13 hod. cvičení
- 13 hod. projekty
Zajišťuje ústav
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ů.
Požadované prerekvizitní znalosti a dovednosti
Diskrétní matematika.
Literatura studijní
- Copy of lectures.
- 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.
- 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.
Průběžná kontrola studia
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 projekt.
Kontrolovaná výuka
Půlsemestrální zkouška v polovině semestru. Průběžná kontrola řešení projektu vedoucím.