Automaty a formálne jazyky

Prednášajúci:Viliam Hromada
Cvičiaci:Viliam Hromada
Kategória predmetu:,

Upozornenie

Od každého študenta sa požaduje, aby zadanie vypracoval sám a aby všetky odovzdané zdrojové kódy boli jeho vlastný výtvor. V prípade zistenia opisovania / kopírovania od iných študentov a taktiež v prípade kopírovania zdrojových kódov z internetu je študent hodnotený známkou FX v zmysle Študijného poriadku STU v Bratislave, kde sa v článku 13 „Kontrola a hodnotenie študijných výsledkov v rámci predmetu“ píše: Preukázaná nečestnosť študenta pri hodnotení študijných výsledkov (zistenie opisovania, použitie nedovolených pomôcok a iných praktík, plagiátorstvo apod.) má za následok hodnotenie klasifikačným stupňom FX – nedostatočne. Takéto konanie je porušenie zásad študijnej morálky a môže byť predmetom disciplinárneho konania.

Organizácia
Študijné materiály
Zadania
Doplnkové materiály

Organizácia predmetu

Predmet je členený do nasledujúcich aktivít:

  • Prednášky: 2 hodiny týždenne podľa rozvrhu
  • Cvičenie: 2 hodiny týždenne podľa rozvrhu
  • Samostatné domáce štúdium
Prednáška a cvičenie:
  • Prednášky: Pondelok, 09:00 – 11:40, AB150
  • Cvičenia: Pondelok, 13:00 – 14:40, AB150
Konzultácie:

Konzultačné hodiny po dohode mailom

Podmienky absolvovania

Zadania: 40 bodov (4 x 10 bodov)
Písomná skúška: 60 bodov

Na získanie zápočtu je potrebné získať minimálne 20 bodov v priebehu semestra.

Cieľ predmetu

Cieľom predmetu AFJ je, aby študenti získali rozšírené znalosti ohľadom formálnych jazykov, konečných automatov, zásobníkových automatov a ich využitia pri tvorbe kompilátorov a prekladu programu do strojového jazyka. Rozšíriť ich znalosti z oblasti teoretickej informatiky. Dosiahnuť, aby študenti boli schopní samostatne študovať práce využívajúce základné poznatky z teoretickej informatiky, aby rozumeli lexikálnej, syntaktickej  a sémantickej analýze programu v počítači.

Plán semestra

  1. Jazyky a ich reprezentácia, Gramatiky.
  2. Konečné automaty a regulárne gramatiky. NKA, DKA, ich ekvivalencia. Minimalizácia DKA. Pumpovacia lema pre regulárne jazyky.
  3. Bezkontextové gramatiky.Úpravy bezkontextových gramatík. CHNF. Pumpovacia lema pre bezkontextové jazyky. Zásobníkové automaty.
  4. Štruktúra kompilátora, Lexikálna analýza, FLEX.
  5. Syntaktická analýza. CYK algoritmus.
  6. Syntaktická analýza zhora-nadol, LL(1) analyzátor.
  7. Syntaktická analýza zdola-nahor, LR(0) analyzátor, SLR(1) analyzátor, LR(1) analyzátor, LALR(1) analyzátor.
  8. Riešenie konfliktov pri syntaktickej analýze, GLR syntaktický analyzátor.
  9. Sémantická analýza, sémantické podprogramy.

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

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!