## Otázky ## Následující seznam otázek shnuje mou představu o tom, co je z okruhu Programovací jazyky a překladače ke státnicím potřeba umět. Tato představa nebyla konzultována s vyučujícím(i). ### Struktura kompilátoru a navazujících nástrojů (linkery, loadery, debuggery, knihovny, preprocesory) ### * schéma překladače * popis linkeru * popis loaderu (Unix, Windows) * statické knihovny, dynamické knihovny, implmentace * popis C preprocesoru ### Konečné automaty a lexikální analýza ### * úkol lexikální analýzy * výstup lexikální analýzy, varianty, problémy * typické způsoby implementace * lex, flex ### Syntaktická analýza - LL, LR techniky ### * úkol syntaktické analýzy * výstup syntaktické analýzy (vč. možností při analýze shora dolů a zdola nahoru) * pojmy: gramatika, bezkontextová gramatika, derivace, levá/pravá derivace * definice: FIRST a FOLLOW * analýza shora dolů, vztah s LL, definice a popis LL, pojmy rozepsání a krácení * rozdíly mezi slabou a silnou LL * implementace analýzy shora dolů rekurzivním sestupem * analýza zdola nahoru, vztah s LR, definice a popis LR, pojmy shift a reduction * rozdíly mezi LR, SLR a LALR * konstrukce LR, SLR a LALR automatu * yacc, bison * gramatiky s regulární pravou stranou ### Syntaxí řízený překlad a atributové gramatiky ### * derivační strom vs. AST * definice: AG, Attr, Syn, Inh, normální forma, atributový výskyt, In, Out [Popis](http://arantxa.ii.uam.es/%7Emodonnel/Compilers/SemAnalSummary.pdf) * definice: acyklické AG, k-průchodové AG, jednoduše k-průchodové AG, zleva-doprava k-průchodové AG, jednoduše zleva-doprava k-průchodové AG * algoritmus konstrukce průchodů jednoduše zleva-doprava k-průchodovou AG ### Reprezentace programu mezikódem ### * důvody reprezentace mezikódem * pojem základní blok * formáty mezikódu: sekvenční (2-adresový, 3-adresový (trojice, čtveřice), prefixová/postfixová notace), graf základních bloků, strom, DAG * operandy mezikódu * SSA * funkce φ u trojic a SSA * generování mezikódu (použití AG, zisk z proházení operací, problém LHS a RHS u přiřazení a jeho řešení, synchronizace u DAGů) ### Překlad výrazů a programových struktur ### * preklad programove struktur - control-flow, tedy if/when/for/goto pripadne try/catch * vyrazy - zakladni princip vyhodnocovani, CSE, eventualne eliminace duplicitnich read/write operaci. ### Rozsahy platnosti proměnných, aktivační záznamy, implementace vnořených procedur, volací konvence ### * obsah aktivačního záznamu * způsoby implementace vnořených procedur (odkaz na všechny záznamy, odkaz na předchozí záznam, displej) a jejich vlastnosti (režie volání, přístupu k proměnným a prostorová náročnost) * implementace procedurálních parametrů v Pascalu * volací konvence: co vše zahrnují (registry vs. zásobník, zachovávání registrů, pořadí předávání parametrů, návratová hodnota, úklid zásobníku) * popis cdecl, stdcall, fastcall ### Vliv architektury počítače na generování kódu a optimalizaci ### #### Zdroje #### * Wikipedia: #### Obsah otázky #### * registry (počet, typy, způsob přístupu, (ne)ortogonalita) * instrukční sada (RISC, CISC, (ne)ortogonalita) * pipelining * superskalarita * out-of-order execution * spekulativní vykonávání instrukcí * SIMD * práce s pamětí (heap, stack), zarovnávání ### Metody generování kódu, přidělování registrů, optimalizace ### #### Zdroje #### * Wikipedia: #### Obsah otázky #### * klasifikace základních bloků podle rozsahu platnosti, výpočet liveBegin a liveEnd, určení kolizí * výběr a uspořádání instrukcí (1:1, 1:n, m:1, m:n), pojem generator-generator, řazení instrukcí * objekty umisťované do registrů * algoritmus obarvování grafu * optimalizace: důvody, čas vs. prostor, úroveň, požadované vlastnosti * druhy optimalizací: lokální, globální, v rámci programu * lokální optimalizace: CSE, copy propagation, dead-code elimination, constant folding, algebraické operace * globální optimalizace: CSE, copy propagation, dead-code elimination, optimalizace cyklů (přesun invariantního kódu, redukce síly operace, odstranění indukční proměnné) * paralelizace a vektorizace * profilem řízená optimalizace * scheduling (ma Bednarek ve slidech) ### Podpora kompilátorů pro synchronizační primitiva, vlákna ### #### Zdroje #### * [Using wait(), notify() and notifyAll()](http://www.javamex.com/tutorials/synchronization_wait_notify.shtml) * [Thread Local Storage](http://www.nynaeve.net/?p=180) #### Obsah otázky #### * Java: kritické sekce, monitory (synchronized), wait, notify * Java: vytvoření vlákna, paměťový model, TLS, podpora v knihovnách (thread (un)safe) * volatile proměnné * podpora knihovnami při absenci podpory kompilátoru ### Objektově orientované jazyky a principy jejich implementace ### #### Zdroje #### * [Memory Layout for Multiple and Virtual Inheritance](http://www.phpcompiler.org/doc/virtualinheritance.html) * [Compilation of object oriented languages](http://www.cs.hut.fi/Opinnot/T-106.850/Compilers/mb.pdf) * [C++ Vtable Examples](http://www.codesourcery.com/public/cxx-abi/cxx-vtable-ex.html) #### Obsah otázky #### * principy OO: zapouzdření, dědičnost a polymorfismus * class-based languages vs. prototype-based languages * OO podle Smalltalk: zasílání zpráv * implementace dědičnosti: tabulka virtuálních funkcí, volání virtuálních funkcí, princip pozdní vazby, layout objektů při jednonásobné a vícenásobné dědičnosti, diamond problem, virtuální dědičnost, RTTI a jeho implementace (typeid, dynamic_cast) * vtable obsahuje: pointer na nadrazenou tridu, adresy metod, (pri virtualni dedicnosti) offset k datum virtualne dedene tridy, (pri RTTI) pointer na type information strukturu ### Překladače vs. interpretry, skriptovací jazyky ### * rozdíly mezi překladačem a interpretrem * výhody/nevýhody překladačů a interpretrů * typické příklady použití překladačů a interpretrů * bytecode, virtuální stroj (zásobník vs. registry), JIT, příklady (Java, Lua) * optimalizační techniky u interpreterů: method caching, direct threading, value tagging * typické vlastnosti skriptovacích jazyků (dynamické typování, reflexivita, dynamičnost) * typické použití skriptovacích jazyků (skripty, web,...), důvody ## Materiály ## * [Web předmětu Principy překladačů](http://ulita.ms.mff.cuni.cz/pub/predn/pp/) * [Web předmětu Konstrukce překladačů](http://ulita.ms.mff.cuni.cz/mp/vyuka/SWI109/html/swi109-20072.html)