Automaty a formálne jazyky

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

Organizácia predmetu

Riadny termín skúšky.

Zasadací poriadok na riadny termín skúšky 22.5.2024 od 14:00.

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

Konzultačné hodiny po dohode mailom

Podmienky absolvovania

Študentstvo absolvuje:

  • 4 zadania. Každé zadanie je za 10 bodov, t.j. súhrnne za 4 zadania je možné získať 40 bodov.

To znamená, že počas semestra môže študentstvo získať súhrnne 40 bodov za všetky zadania. Podmienkou pre vykonanie skúšky je zisk minimálne 20 bodov zo zadaní.

Študentstvo, ktoré splní podmienky pre vykonanie skúšky (t.j. získa zo zadaní súhrnne minimálne 20 bodov) následne absolvuje skúšku z predmetu, 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.

Dávam do pozornosti študijný poriadok STU, konkrétne, čl. 13, odsek (5):

(5) Preukázaná nečestnosť študenta pri hodnotení študijných výsledkov (zistenie opisovania, podvádzanie, použitie nedovolených pomôcok a iných praktík vrátane
nedovolenej spolupráce počas písomného alebo ústneho overovania vedomostí študenta, plagiátorstvo a pod.) má za následok neúspešné absolvovanie predmetu (čl. 16 študijného poriadku). Takéto konanie študenta je porušenie zásad študijnej morálky a môže byť predmetom disciplinárneho konania.

Podmienky absolvovania predmetu sú zverejnené aj v Akademickom informačnom systéme na príslušnom Dokumentovom serveri predmetu. Ten istý dokument nájdete aj tu.

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.

  1. Zadanie č. 1. Interpreter zjednodušeného jazyka štvoríc. 5 testovacích vstupov zo zadania nájdete aj tu. Odovzdajte zdrojový kód Vášho riešenia do príslušného miesta odovzdania v AISe do 3. 3. 2024, 23:59. Zadania po termíne posielajte sem..
  2. Zadanie č. 2. Thompsonova konštrukcia. Odovzdajte zdrojový kód Vášho riešenia do príslušného miesta odovzdania v AISe do 27. 3. 2024, 23:59. Zadania po termíne posielajte sem..
  3. Zadanie č. 3. Redukcia BNF. Odovzdajte zdrojový kód Vášho riešenia do príslušného miesta odovzdania v AISe do 21. 4. 2024, 23:59. Zadania po termíne posielajte sem.
  4. Zadanie č. 4. LL(1)-parser. Odovzdajte zdrojový kód Vášho riešenia do príslušného miesta odovzdania v AISe do 12. 5. 2024, 23:59. Zadania po termíne posielajte sem.

Prednášky

  1. Úvodné pojmy, formálna gramatika, Chomského hierarchia.
  2. Deterministické a nedeterministické konečné automaty, ich ekvivalencia.
  3. Regulárne výrazy, prevod regex -> NKA.
  4. Bezkontextové gramatiky, derivačné stromy, úpravy gramatík.
  5. Chomského normálny tvar, CYK algoritmus; Množiny FIRST,FOLLOW.
  6. Zásobníkové automaty.
  7. Lexikálna analýza.
  8. Syntaktická analýza top-down, LL(1)-parser.
  9. Syntaktická analýza bottom-up, LR(0)-parser.
  10. SLR(1)-parser.
  11. LR(1)-parser.
  12. Sémantická analýza.

Cvičenia + sady príkladov

  1. Úvodné pojmy, gramatiky.
    Ďalšie úlohy.
  2. Deterministické konečné automaty, nedeterministické konečné automaty, ich ekvivalencia.
    Ďalšie úlohy.
  3. Regulárne výrazy, regex -> NKA (Thompsonova konštrukcia).
    Ďalšie úlohy.
  4. Jednoznačnosť gramatiky, úpravy gramatík.
    Ďalšie úlohy.
  5. Chomského normálny tvar, CYK algoritmus; FIRST,FOLLOW.
    Ďalšie úlohy.
  6. Zásobníkové automaty.
    Ďalšie úlohy.
  7. Lexikálna analýza – k tejto problematike cvičenie ani príklady nebývajú, všetko dôležité (aj k počítaniu) odznelo na prednáške.
  8. LL(1)-parser.
    Ďalšie úlohy.
  9. LR(0)-parser.
    Ďalšie úlohy.
  10. SLR(1)-parser.
    Ďalšie úlohy.
  11. LR(1)-parser.
    Ďalšie úlohy.

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/