Automaty a formálne jazyky

Videoprezentácie pre 12. a 13. týždeň

Videoprezentácie pre 11. týždeň

Videoprezentácie pre 10. týždeň

Videoprezentácie pre 8. týždeň (a 9.-ty, keďže v 9.-tom týždni je Veľká noc)

Videoprezentácie pre 7. týždeň

Videoprezentácie pre 6. týždeň

Videoprezentácie pre 4. a 5. týždeň

Prezentácie z prednášok:

Prednáška č. 1 – Úvod do formálnych jazykov, formálna gramatika, rôzne typy gramatík.

Prednáška č. 2 – Deterministické a nedeterministické konečné automaty a ich ekvivalencia. Minimalizácia konečných automatov.

Prednáška č. 3 – Regulárne výrazy. Ekvivalencia regulárnych výrazov, regulárnych gramatík a konečných automatov. Vlastnosti regulárnych jazykov. Pumpovacia lema pre regulárnej jazyky.

Prednáška č. 4 – Bezkontextové gramatiky a ich úpravy, odstránenie ľavej rekurzie. Vlastná gramatika. Chomského normálny tvar.

Prednáška č. 5 – Množina FIRST, FOLLOW, Zásobníkové automaty.

Prednáška č. 6 – Štruktúra kompilátora, Lexikálna analýza, FLEX.
Prednáška č. 6 – Zip dokumentov k jazyku Jukapo v2 použitých vo videoprednáške.

Prednáška č. 7 – Syntaktická analýza, CYK, Topdown, LL(1)

Prednáška č. 8 – Syntaktická analýza zdola-nahor (Bottom-up/LR), LR(0)-analyzátor

Prednáška č. 9 – SLR(1) analyzátor

Prednáška č. 10 – LR(1), LALR(1) analyzátory, riešenie konfliktov LR analýzy, GLR parser, vzťah LL/LR gramatík

Prednáška č. 11 – Sémantická analýza

Príklady na počítanie:

Cvičenie č. 1 – Formálne gramatiky

Cvičenie č. 2 – Konečné automaty, Determinizácia konečných automatov, Minimalizácia konečných automatov

Cvičenie č. 3 – Regulárne výrazy. Ekvivalencia regulárnych výrazov, konečných automatov a regulárnych gramatík. Pumpovacia lemma pre regulárne jazyky.

Cvičenie č. 4 – Úpravy bezkontextových gramatík na vlastné gramatiky a Chomského normálny tvar. Odstránenie ľavej rekurzie.

Cvičenie č. 5 – Množina FIRST, FOLLOW, Zásobníkové automaty

Cvičenie č. 6 – CYK algoritmus, LL(1) parsing

Cvičenie č. 7 – LL(1) test, LL(1) úpravy

Cvičenie č. 8 – LR(0),SLR(1) analyzátory

Cvičenie č. 9 – LR(1), LALR(1), GLR analyzátory

Zadanie číslo 1 – Jukapo Interpreter Deadline zadania je 8.3.2020, 23:59.

Zadanie číslo 2 – Konverzia regulárnej gramatiky na DKA Deadline zadania je 5.4.2020, 23:59.

Zadanie číslo 3 – Lexikálny analyzátor Deadline zadania je 3.5.2020, 23:59.

Zadanie číslo 4- Jukapo RELOADED Deadline zadania je 20.5.2020, 23:59.

Pre zadania posielané po deadline kliknite sem.

Literatúra

• Aho, A., Lam, M., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques and Tools, 2006.
• Dedera, Ľ.: Počítačové jazyky a ich spracovanie, AOS M.R.Štefánika Liptovský Mikuláš, 2014.
• Hopcroft, J.E., Ullman, J.D.: Formálne jazyky a automaty. ALFA, Bratislava, 1978.
• Linz, P.: An Introduction to Formal Languages and Automata, 2001.
• Molnár, Ľ., Češka, M., Melichar, B.: Gramatiky a jazyky. ALFA/SNTL, Bratislava, 1987.

Web stránka s analýzou gramatík

Na stránke Laboratória programovacích jazykov Katedry počitačových vied Univerzity v Calgary sa nachádza výborný softvérový nástroj pre syntaktickú analýzu gramatík. http://smlweb.cpsc.ucalgary.ca/start.html

Na stránke si viete dať zostrojiť príslušné LL/LR analyzátory pre ľubovoľné gramatiky.

Odporúčam taktiež podstránku http://smlweb.cpsc.ucalgary.ca/example-grammars/ kde sú ukážky rôznych gramatík, aj vzhľadom na ich príslušnosť/nepríslušnosť do LL(1)/LR(0)/SLR(1)/LALR(1)/LR(1)/LL(2)/LR(2) kombinácií…

Softvérová pomôcka

Pri samoštúdiu a príprave na predmet AFJ odporúčam pracovať s programom JFLAP ktorý je možné stiahnuť z tejto stránky: http://www.jflap.org/jflaptmp/

Autori programu zároveň zverejnili zdarma doplnkovú knihu k programu, ktorá sa dá zároveň použiť aj ako študijný materiál k predmetu AFJ: https://www2.cs.duke.edu/csed/jflap/jflapbook/

Zaujímavá hra

Vážení študenti! Pre skrátenie dlhých chvíľ medzi prednáškami – hra aj s prvkami konečných automatov: http://pleasingfungus.com/Manufactoria/

Ďakujem Bc. Jakubovi Kovářovi za link!