D54X125 Gramatiky a jazyky (GJ)

Studijní obor: Aplikovaná informatika v dopravě

Semestr: 1

Typ studijního předmětu: povinně volitelný

Celkový hodinový rozsah výuky: přednáška + cvičení, 2-2, klasifikovaný zápočet

Počet kreditů: 4

Garant předmětu: doc.Ing.Josef Kotyk, CSc. – KŘPVT, FCHT, UPa

Nutné splněné povinnosti: Matematika I-II, Informatika I-II (bakalářské studium)

Podmínky pro absolvování předmětu: zápočtem se potvrzuje, že se student zúčastňoval v požadované míře povinné výuky a že splnil požadavky, jimiž bylo udělení zápočtu podmíněno. Podmínky udělení zápočtu určuje přednášející.

Anotace předmětu:

Cíl předmětu:

Seznámit posluchače se základními pojmy a poznatky teorie regulárních a bezkontextových jazykù, ústící v metody jejich syntaktické analýzy jako základu studia překladačů programovacích jazykù.

Obsah předmětu:

Pojem jazyka a gramatiky. Chomského klasifikace gramatik a hierarchie jazyků. Konečné automaty a regulární gramatiky. Jejich vzájemné vztahy. Vlastnosti regulárních jazyků. Derivační stromy. Bezkontextové gramatiky a zásobníkové automaty. Jejich vzájemné vztahy. Vlastnosti bezkontextových jazyků. Jednoduché precedenční gramatiky. LL a LR jazyky a jejich vlastnosti. Výpočet množin FIRST a FOLLOW. Deterministické zásobníkové automaty. Syntaktická analýza. Kontextové jazyky a jazyky bez omezení.

Seznam odborné literatury:

ČEŠKA MILAN: Gramatiky a jazyky. Brno, Brno 1988, skriptum FE VUT v Brně.

HOPCROFT, J.E. – ULLMAN, J. D.: Formálne jazyky a automaty. Alfa 1978.

ČEŠKA, M. -- MELICHAR, M. -- MOLNÁR, Ľ. Gramatiky a jazyky. SNTL, Praha, 1987.

KOUBEK, V. Automaty a gramatiky. elektronická publikace, Praha, listopad 1996.

MELICHAR, B.: Jazyky a překlady. Skripta ČVUT, Praha 1996