Automaty a formálne jazyky

Prednášajúci:Viliam Hromada
Cvičiaci:Viliam Hromada
Kategória predmetu:,
Organizácia
Študijné materiály
Doplnkové materiály

Organizácia predmetu

Prednáška a cvičenie:
  • Prednáška: Pondelok 15:00 – 16:40, AB-150.
  • Cvičenie: Štvrtok 13:00 – 14:40, DE-150.
Konzultácie:

Konzultačné hodiny po dohode mailom.

Podmienky absolvovania

Študentstvo absolvuje:

  • Dva písomné testy, každý test je za 20 bodov, t.j. súhrnne za 2 testy je možné získať 40 bodov,
    pričom podmienkou pre účasť na skúške je získať z oboch testov dokopy aspoň 20 bodov.
  • Písomnú skúšku, ktorá je ohodnotená 60 bodmi.

Výsledná známka z predmetu je tvorená na základe súčtu bodov získaných na skúške a zo spomínaných testov.  Jej výsledná hodnota je určená podľa platnej klasifikačnej stupnice STU.

Cieľ predmetu

Cieľom predmetu AFJ je, aby študentstvo získalo 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 študentstvo bolo schopné samostatne študovať práce využívajúce základné poznatky z teoretickej informatiky, aby rozumelo 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.
  3. Bezkontextové gramatiky.Úpravy bezkontextových gramatík. CHNF.  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.

Prednášky

Cvičenia

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.
  • Hromada, V.: ZBIERKA RIEŠENÝCH ÚLOH Z PREDMETU AUTOMATY A FORMÁLNE JAZYKY, Spektrum STU, Bratislava, 2023.
  • 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í…

Alternatívne je k dispozícii napríklad nasledovná softvérová pomôcka, ktorá tiež dokáže konštruovať LL(1), SLR(1), LALR(1), LR(1) parsery. http://www.supereasyfree.com/software/simulators/compilers/principles-techniques-and-tools/parsing-simulator/parsing-simulator.zip

Softvérová pomôcka

Pri samoštúdiu a príprave na predmet AFJ odporúčam pracovať s programom JFLAP vo verzii 7.1 ktorý je možné stiahnuť z tejto stránky: https://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/