Sylabus na skúšku z kompilátorov.
1. Štruktúra kompilátorov.
1.1. Základné pojmy. Vzťah k teórii jazykov. Syntaktická analýza.
Sémantika. Jedno a viac prechodové kompilátory.
1.2. Jednoduchý jednoprechodový kompilátor. Rekurzívny zostup.
Syntaktické diagramy.
2. Lexikálna analýza.
2.1. Dôvody oddelenia lexikálnej a syntaktickej analýzy. Lexikál-
na štruktúra jazykov. Regulárne jazyky. Konečné automaty.
2.2. Syntéza: Regulárny jazyk - nedeterministický konečný automat
- deterministický konečný automat.
2.3. Pattern matching : Boyer - Moore, Knuth - Morris - Pratt,
Dömölki, Aho - Corasick.
3. Syntaktická analýza.
3.1. Bezkontextové gramatiky. Návrh gramatiky jazyka. Syntaktické
stromy.
3.2. Metódy zhora - dolu: rekurzívny zostup, LL(1), LL(k).
3.3. Metódy zdola - hore: Operátorovo precedenčné gramatiky a
jazyky, LR(k) metódy ( SLR(1), LALR(1)).3.4. Spätne deterministické kontextové jazyky
3.5. Všeobecné metódy pre bezkontextové jazyky: Earley-ho
algoritmus, Cocke - Younger - Kasami.
3.6. Oprava chýb a zotavenie sa z chýb pri syntaktickej analýze.
4. Syntaxou riadené preklady.
4.1. Atribútové gramatiky. Syntetizované a zdedené atribúty.
4.2. Vyhodnocovanie atribútov. Porovnanie metód zhora - dole a
zdola - hore.
4.3. Graf závislosti atribútov. Test na cirkularitu.
5. Kontrola typov.
5.1. Systém typov v programovacích jazykoch a konverzie medzi typmi.
5.2. Gramatika typov a kontrola typov ako syntaxou riadený reklad.
5.3. Polymorfické typy. Unifikácia.
5.4. Algoritmy unifikácie: Robinson, Herbrand, Prívara - Ružička.
6. Podpora v čase behu ( Run-time environments ).
6.1. Organizácia a pridelovanie pamäti.
6.2. Odovzdávanie parametrov, lokálne a nelokálne premenné.
6.3. Pridelovanie a organizácia dynamickej pamäti.
6.4. Tabuľka symbolov - hašovanie.6.5. Zber smetí (garbage collection)
7. Generovanie medzijazyka.
7.1. Formy medzijazyka: Poľská bezzátvorková forma, trojadresový kód, trojice, štvorice.
7.2. Generovanie medzijazyka syntaxou riadeným prekladom.
7.3. 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 funkcii.
7.4. Spätné plátanie ( backpatching ).
8. Generovanie kódu.
8.1. Cieľový počítač: CISC, RISC, SIC. Ceny inštrukcii.
8.2. Administrácia pamäti. Statická pamäť, zásobník, dynamická
pamäť - heap.
8.3. Pridelovanie registrov. Pridelovanie registrov farbením grafu.
8.4. Generovanie kódu z dagu.8.5 Generovanie kódu pokrývaním ozdobeného stromu
9. Optimalizácia kódu.
9.1. Kukátková ( peephole ) optimalizácia.
9.2. Optimalizácia základných blokov, optimalizačné transformácie.
9.3. Globálna analýza toku dát, intervalová analýza.
9.4. Iteratívne riešenie rovníc toku dát. Efektívne algoritmy
analýzy toku dát.
10. Paralelizmus a lokalita10.1. Architektúra súčasných počítačov
10.2. Modely paralelizmu
10.3. Optimalizácia vnorených cyklov
10.4. Celočíselné lineárne programovanie.