Kompilátory
(sylaby štátnic magisterského štúdia informatiky - plná verzia)
- Štruktúra kompilátorov.
- Základné pojmy. Vzťah k teórii jazykov. Syntaktická analýza. Sémantika. Jedno a viac prechodové kompilátory.
- Jednoduchý jednoprechodový kompilátor. Rekurzívny zostup. Syntaktické diagramy.
- Lexikálna analýza.
- Dôvody oddelenia lexikálnej a syntaktickej analýzy. Lexikálna štruktúra jazykov. Regulárne jazyky. Konečné automaty.
- Syntéza: Regulárny jazyk - nedeterministický konečný automat - deterministický konečný automat.
- Pattern matching : Boyer - Moore, Knuth - Morris - Pratt, Dömölki, Aho - Corasick.
- Syntaktická analýza.
- Bezkontextové gramatiky. Návrh gramatiky jazyka. Syntaktické stromy.
- Metódy zhora - dolu: rekurzívny zostup, LL(1), LL(k).
- Metódy zdola - hore: Operátorovo precedenčné gramatiky a jazyky, LR(k) metódy ( SLR(1), LALR(1)).
- Spätne deterministické kontextové jazyky.
- Všeobecné metódy pre bezkontextové jazyky: Earley-ho algoritmus, Cocke - Younger - Kasami.
- Oprava chýb a zotavenie sa z chýb pri syntaktickej analýze.
- Syntaxou riadené preklady.
- Atribútové gramatiky. Syntetizované a zdedené atribúty.
- Vyhodnocovanie atribútov. Porovnanie metód zhora - dole a zdola - hore.
- Graf závislosti atribútov. Test na cirkularitu.
- Kontrola typov.
- Systém typov v programovacích jazykoch a konverzie medzi typmi.
- Gramatika typov a kontrola typov ako syntaxou riadený preklad.
- Polymorfické typy. Unifikácia.
- Algoritmy unifikácie: Robinson, Herbrand, Prívara - Ružička.
- Podpora v čase behu (Run-time environments).
- Organizácia a prideľovanie pamäte.
- Odovzdávanie parametrov, lokálne a nelokálne premenné.
- Prideľovanie a organizácia dynamickej pamäte.
- Tabuľka symbolov - hašovanie.
- Zber smetí (garbage collection).
- Generovanie medzijazyka.
- Formy medzijazyka: Poľská bezzátvorková forma, trojadresový kód,
trojice, štvorice.
- Generovanie medzijazyka syntaxou riadeným prekladom.
- Popis základných konštrukcii: deklarácie, výrazy, príkaz priradenia,
booleovské výrazy, podmienené príkazy a cykly. Volanie procedúr a funkcií.
- Spätné plátanie (backpatching).
- Generovanie kódu.
- Cieľový počítač: CISC, RISC, SIC. Ceny inštrukcií.
- Administrácia pamäte. Statická pamäť, zásobník, dynamická pamäť - heap.
- Prideľovanie registrov. Prideľovanie registrov farbením grafu.
- Generovanie kódu z dagu.
- Generovanie kódu pokrývaním ozdobeného stromu.
- Optimalizácia kódu.
- Kukátková (peephole) optimalizácia.
- Optimalizácia základných blokov, optimalizačné transformácie.
- Globálna analýza toku dát, intervalová analýza.
- Iteratívne riešenie rovníc toku dát. Efektívne algoritmy analýzy toku dát.
- Paralelizmus a lokalita.
- Architektúra súčasných počítačov.
- Modely paralelizmu.
- Optimalizácia vnorených cyklov.
- Celočíselné lineárne programovanie.