Prehlad cieľov predmetu — Formálne jazyky

Cvičenia

Oboznámiť sa s organizáciou cvičení predmetu Formálne jazyky a podmienkami udelenia zápočtu.
Definovať základné pojmy teórie formálnych jazykov.
Oboznámiť sa s regulárnymi výrazmi.
Prakticky precvičiť zostavenie vybraných regulárnych výrazov.

Zopakovať si tvorbu regulárnych výrazov na základe slovnej špecifikácie.
Definovať deterministický konečnostavovový automat (DKA) ako ekvivalentný spôsob určenia regulárneho jazyka.
Konštruovať DKA na základe zadaného regulárneho výrazu.
Implementovať DKA pre daný regulárny výraz vo vyššom programovacom jazyku (tvorba primitívneho jazykového procesora).

Zopakovať si definíciu DKA a porozumieť jeho minimalizácii.
Definovať nedeterministický konečnostavovový automat (NKA) ako rozšírenie DKA. Porovnať tieto dva druhy konečnostavových automatov.
NKA ako alternatívny spôsob definície regulárneho jazyka (konštruovať NKA na základe zadaného regulárneho výrazu).
Implementovať NKA pre daný regulárny výraz vo vyššom programovacom jazyku.

Definovať princíp determinizácie NKA (konštrukcia ekvivalentného DKA na základe zadaného NKA).
Definovať pumpovaciu lemu pre regulárne jazyky.
Prezentovať postup dôkazu neregularity jazyka na základe pumpovacej lémy.

Zápočtová písoma A.
Oboznámiť sa s definíciami základných pojmov z oblasti formálnych gramatík.
Definovať Backusova-Naurova forma (BNF) a rozšírenú Backusova-Naurova forma (EBNF) špecifikácie formálnych gramatík.
Zostrojiť formálnu gramatiku podľa špecifikácie jazyka.

Oboznámiť so špecifikáciou priority a asociativity operácií na úrovni syntaktického modelu jazyka.
Predstaviť základnú teóriu procesov kompilácie a interpretácie.
Konštruovať gramatiku aritmetických výrazov a implementovať ich syntaxou riadenú interpretáciu.

Oboznámiť sa s transformáciami bezkontextových gramatík.
Precvičiť si transformácie bezkontextových gramatík.
Implementácia syntaktického analyzátora a interpretátora na základe tranformovanej gramatiky jazyka aritmetických výrazov.

Definovať zásobníkový automat (ZA) ako ekvivalentný spôsob určenia bezkontextového jazyka.
Uviesť základné pojmy analýzy bezkontextových gramatík. Množiny $\mathit{FIRST},$ $\mathit{FOLLOW}$ , $\mathit{PREDICT}$ a definovať $LL(1)$ gramatiku.
Predstaviť ľavú faktorizáciu (determinizáciu gramatiky) a princíp nerekurzívnej syntaktickej analýzy zhora nadol postavenej na zásobníkovom automate.
Implementovať jednoduchý nerekurzívny syntaktický analyzátor zhora nadol.